Lie Ryan wrote: > Isn't ordered dictionary essentially also an "always sorted" container? > It is always sorted depending on the order of insertion? I can't see any > technical reason why the data structure can't accommodate them both. Can > you point me to a discussion on this?
My phrasing was a little ambiguous - "always sorted for an arbitrary key function" is better handled with something other than a hash map + additional bookkeeping due to the effect on the speed of insertion and deletion. With a specifically insertion-ordered dict, only deletion is really slowed down by the additional bookkeeping: it drops to O(n) due to the need to find and remove the key being deleted from the sequence of keys as well as from the hash map). As Terry noted, supporting arbitrary sort orders would slow down insertion as well. Cheers, Nick. -- Nick Coghlan | ncogh...@gmail.com | Brisbane, Australia --------------------------------------------------------------- _______________________________________________ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
