[Python-ideas] OrderedDict.peekitem()

[Masklinn]

On 2015-07-07, at 06:23 , Neil Girdhar <mistersheik at gmail.com> wrote:

> This thread is not about hash tables.  This thread is about indexing into an ordered dictionary when you need an ordered dictionary.  Someone pointed out that people expect indexing to be constant time.  I agree that no one expects indexing to be linear time.  My point was that logarithmic-time indexing is reasonable and possible.

Linear time indexing would be possible by changing the OrderedDict implementation to Raymond Hettinger's compact dictionaries[0] with a delete operation recompacting the entries array rather than just nulling the item (it would make removals on "early" keys of large dictionaries more expensive though, delete would become O(n) with n the number of "living" entries added after the one being removed).

[0] https://mail.python.org/pipermail/python-dev/2012-December/123028.html