diff options
| -rw-r--r-- | Doc/library/collections.rst | 96 |
1 files changed, 53 insertions, 43 deletions
diff --git a/Doc/library/collections.rst b/Doc/library/collections.rst index bde7b6e..d847d6b 100644 --- a/Doc/library/collections.rst +++ b/Doc/library/collections.rst @@ -887,7 +887,7 @@ field names, the method and attribute names start with an underscore. .. method:: somenamedtuple._asdict() - Return a new :class:`OrderedDict` which maps field names to their corresponding + Return a new :class:`dict` which maps field names to their corresponding values: .. doctest:: @@ -1024,17 +1024,41 @@ customize a prototype instance: :class:`OrderedDict` objects ---------------------------- -Ordered dictionaries are just like regular dictionaries but they remember the -order that items were inserted. When iterating over an ordered dictionary, -the items are returned in the order their keys were first added. +Ordered dictionaries are just like regular dictionaries but have some extra +capabilities relating to ordering operations. They have become less +important now that the built-in :class:`dict` class gained the ability +to remember insertion order (this new behavior became guaranteed in +Python 3.7). + +Some differences from :class:`dict` still remain: + +* The regular :class:`dict` was designed to be very good at mapping + operations. Tracking insertion order was secondary. + +* The :class:`OrderedDict` was designed to be good at reordering operations. + Space efficiency, iteration speed, and the performance of update + operations were secondary. + +* Algorithmically, :class:`OrderedDict` can handle frequent reordering + operations better than :class:`dict`. This makes it suitable for tracking + recent accesses (for example in an `LRU cache + <https://medium.com/@krishankantsinghal/my-first-blog-on-medium-583159139237>`_). + +* The equality operation for :class:`OrderedDict` checks for matching order. + +* The :meth:`popitem` method of :class:`OrderedDict` has a different + signature. It accepts an optional argument to specify which item is popped. + +* :class:`OrderedDict` has a :meth:`move_to_end` method to + efficiently reposition an element to an endpoint. + +* Until Python 3.8, :class:`dict` lacked a :meth:`__reversed__` method. + .. class:: OrderedDict([items]) - Return an instance of a dict subclass, supporting the usual :class:`dict` - methods. An *OrderedDict* is a dict that remembers the order that keys - were first inserted. If a new entry overwrites an existing entry, the - original insertion position is left unchanged. Deleting an entry and - reinserting it will move it to the end. + Return an instance of a :class:`dict` subclass that has methods + specialized for rearranging dictionary order. .. versionadded:: 3.1 @@ -1084,29 +1108,7 @@ anywhere a regular dictionary is used. :class:`OrderedDict` Examples and Recipes ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ -Since an ordered dictionary remembers its insertion order, it can be used -in conjunction with sorting to make a sorted dictionary:: - - >>> # regular unsorted dictionary - >>> d = {'banana': 3, 'apple': 4, 'pear': 1, 'orange': 2} - - >>> # dictionary sorted by key - >>> OrderedDict(sorted(d.items(), key=lambda t: t[0])) - OrderedDict([('apple', 4), ('banana', 3), ('orange', 2), ('pear', 1)]) - - >>> # dictionary sorted by value - >>> OrderedDict(sorted(d.items(), key=lambda t: t[1])) - OrderedDict([('pear', 1), ('orange', 2), ('banana', 3), ('apple', 4)]) - - >>> # dictionary sorted by length of the key string - >>> OrderedDict(sorted(d.items(), key=lambda t: len(t[0]))) - OrderedDict([('pear', 1), ('apple', 4), ('orange', 2), ('banana', 3)]) - -The new sorted dictionaries maintain their sort order when entries -are deleted. But when new keys are added, the keys are appended -to the end and the sort is not maintained. - -It is also straight-forward to create an ordered dictionary variant +It is straightforward to create an ordered dictionary variant that remembers the order the keys were *last* inserted. If a new entry overwrites an existing entry, the original insertion position is changed and moved to the end:: @@ -1115,21 +1117,29 @@ original insertion position is changed and moved to the end:: 'Store items in the order the keys were last added' def __setitem__(self, key, value): - if key in self: - del self[key] - OrderedDict.__setitem__(self, key, value) + super().__setitem__(key, value) + super().move_to_end(key) -An ordered dictionary can be combined with the :class:`Counter` class -so that the counter remembers the order elements are first encountered:: +An :class:`OrderedDict` would also be useful for implementing +variants of :func:`functools.lru_cache`:: - class OrderedCounter(Counter, OrderedDict): - 'Counter that remembers the order elements are first encountered' + class LRU(OrderedDict): + 'Limit size, evicting the least recently looked-up key when full' - def __repr__(self): - return '%s(%r)' % (self.__class__.__name__, OrderedDict(self)) + def __init__(self, maxsize=128, *args, **kwds): + self.maxsize = maxsize + super().__init__(*args, **kwds) - def __reduce__(self): - return self.__class__, (OrderedDict(self),) + def __getitem__(self, key): + value = super().__getitem__(key) + self.move_to_end(key) + return value + + def __setitem__(self, key, value): + super().__setitem__(key, value) + if len(self) > self.maxsize: + oldest = next(iter(self)) + del self[oldest] :class:`UserDict` objects |