How slow and space-inefficient would it be to just implement the set methods on top of dict?

Do dicts lose insertion order when a key is deleted? AFAIU, OrderedDict do not lose insertion order on delete. Would this limit the utility of an ordered set as a queue? What set methods does a queue need to have?

On Thu, Dec 19, 2019, 11:41 PM Tim Peters <> wrote:
> I must admit that I was assuming without stating that a full OrderedSet
> implementation would support the MutableSequence interface.

Efficient access via index position too would be an enormous new
requirement,  My bet:  basic operations would need to change from O(1)
to O(log(N)).

BTW, in previous msgs there are links to various implementations
calling themselves "ordered sets".  One of them supplies O(1)
indexing, but at the expense of making deletion O(N) (!):

If efficient indexing is really wanted, then the original "use case"
Larry gave was definitely obscuring an XY problem ;-)
Python-Dev mailing list --
To unsubscribe send an email to
Message archived at
Code of Conduct: