On Fri, Dec 20, 2019 at 4:15 PM Wes Turner firstname.lastname@example.org wrote:
How slow and space-inefficient would it be to just implement the set methods on top of dict?
Speed: Dict doesn't cache the position of the first item. Calling next(iter(D)) repeatedly is O(N) in worst case. Space: It waste 8bytes per member.
Do dicts lose insertion order when a key is deleted? AFAIU, OrderedDict do not lose insertion order on delete.
Dict keeps insertion order after deletion too.
Would this limit the utility of an ordered set as a queue? What set methods does a queue need to have?
I want O(1) D.popleft(). (The name is borrowed from deque. popfirst() would be better maybe).
-- Inada Naoki email@example.com