[Python-checkins] r70100 - peps/trunk/pep-0372.txt

Mon Mar 2 21:40:37 CET 2009

Author: raymond.hettinger
Date: Mon Mar 2 21:40:36 2009
New Revision: 70100
Log:
Mark the PEP as Accepted.
Replace the odict references with OrderedDict.
Specify the __repr__() format.
Update the __eq__() specification as discussed on python-dev.
Modified:
 peps/trunk/pep-0372.txt
Modified: peps/trunk/pep-0372.txt
==============================================================================

--- peps/trunk/pep-0372.txt	(original)
+++ peps/trunk/pep-0372.txt	Mon Mar 2 21:40:36 2009
@@ -4,7 +4,7 @@
 Last-Modified: $Date$
 Author: Armin Ronacher <armin.ronacher at active-4.com>
 Raymond Hettinger <python at rcn.com>
-Status: Draft
+Status: Accepted
 Type: Standards Track
 Content-Type: text/x-rst
 Created: 15-Jun-2008
@@ -16,7 +16,7 @@
 ========
 
 This PEP proposes an ordered dictionary as a new data structure for
-the ``collections`` module, called "odict" in this PEP for short. The
+the ``collections`` module, called "OrderedDict" in this PEP. The
 proposed API incorporates the experiences gained from working with
 similar implementations that exist in various real-world applications
 and other programming languages.
@@ -44,13 +44,13 @@
 
 The following example shows the behavior for simple assignments:
 
- >>> d = odict()
+ >>> d = OrderedDict()
 >>> d['parrot'] = 'dead'
 >>> d['penguin'] = 'exploded'
 >>> d.items()
 [('parrot', 'dead'), ('penguin', 'exploded')]
 
-That the ordering is preserved makes an odict useful for a couple of
+That the ordering is preserved makes an OrderedDict useful for a couple of
 situations:
 
 - XML/HTML processing libraries currently drop the ordering of
@@ -97,10 +97,10 @@
 well as mappings like a dict does. Unlike a regular dictionary,
 the insertion order is preserved.
 
- >>> d = odict([('a', 'b'), ('c', 'd')])
+ >>> d = OrderedDict([('a', 'b'), ('c', 'd')])
 >>> d.update({'foo': 'bar'})
 >>> d
- collections.odict([('a', 'b'), ('c', 'd'), ('foo', 'bar')])
+ collections.OrderedDict([('a', 'b'), ('c', 'd'), ('foo', 'bar')])
 
 If ordered dicts are updated from regular dicts, the ordering of new
 keys is of course undefined.
@@ -119,7 +119,7 @@
 
 New methods not available on dict:
 
-``odict.__reversed__()``
+``OrderedDict.__reversed__()``
 Supports reverse iteration by key.
 
 
@@ -138,8 +138,8 @@
 former. This has the side-effect that the position of the first
 key is used because only the value is actually overwritten::
 
- >>> odict([('a', 1), ('b', 2), ('a', 3)])
- collections.odict([('a', 3), ('b', 2)])
+ >>> OrderedDict([('a', 1), ('b', 2), ('a', 3)])
+ collections.OrderedDict([('a', 3), ('b', 2)])
 
 This behavior is consistent with existing implementations in
 Python, the PHP array and the hashmap in Ruby 1.9.
@@ -155,10 +155,10 @@
 Do any limitations arise from subclassing dict?
 
 Yes. Since the API for dicts is different in Py2.x and Py3.x, the
- odict API must also be different. So, the Py2.7 version will need
+ OrderedDict API must also be different. So, the Py2.7 version will need
 to override iterkeys, itervalues, and iteritems.
 
-Does ``odict.popitem()`` return a particular key/value pair?
+Does ``OrderedDict.popitem()`` return a particular key/value pair?
 
 Yes. It pops-off the most recently inserted new key and its
 corresponding value. This corresponds to the usual LIFO behavior
@@ -167,23 +167,26 @@
 The actual implementation is more efficient and pops directly
 from a sorted list of keys.
 
-Does odict support indexing, slicing, and whatnot?
+Does OrderedDict support indexing, slicing, and whatnot?
 
- As a matter of fact, ``odict`` does not implement the ``Sequence``
+ As a matter of fact, ``OrderedDict`` does not implement the ``Sequence``
 interface. Rather, it is a ``MutableMapping`` that remembers
 the order of key insertion. The only sequence-like addition is
 support for ``reversed``.
 
-Does odict support alternate sort orders such as alphabetical?
+ An further advantage of not allowing indexing is that it leaves open
+ the possibility of a fast C implementation using linked lists.
+
+Does OrderedDict support alternate sort orders such as alphabetical?
 
 No. Those wanting different sort orders really need to be using another
- technique. The odict is all about recording insertion order. If any
+ technique. The OrderedDict is all about recording insertion order. If any
 other order is of interest, then another structure (like an in-memory
 dbm) is likely a better fit.
 
-How well does odict work with the json module, PyYAML, and ConfigParser?
+How well does OrderedDict work with the json module, PyYAML, and ConfigParser?
 
- For json, the good news is that json's encoder respects odict's iteration order::
+ For json, the good news is that json's encoder respects OrderedDict's iteration order::
 
 >>> items = [('one', 1), ('two', 2), ('three',3), ('four',4), ('five',5)]
 >>> json.dumps(OrderedDict(items))
@@ -221,20 +224,18 @@
 >>> config.remove_option('Log', 'error')
 >>> config.write(open('myconfig.ini', 'w'))
 
-How does odict handle equality testing?
+How does OrderedDict handle equality testing?
+
+ Comparing two ordered dictionaries implies that the test will be
+ order-sensitive so that list ``(od1.items())==list(od2.items())``.
 
- Being a dict, one might expect equality tests to not care about order. For
- an odict-to-dict comparison, this would be a necessity and it's probably
- not wise to silently switch comparison modes based on the input types.
- Also, some third-party tools that expect dict inputs may also expect the
- comparison to not care about order. Accordingly, we decided to punt and
- let the usual dict equality testing run without reference to internal
- ordering. This should be documented clearly since different people will
- have different expectations. If a use case does arise, it's not hard for
- a user explicitly craft an order based comparison::
+ When ordered dicts are compared with other Mappings, their order
+ insensitive comparison is used. This allows ordered dictionaries
+ to be substituted anywhere regular dictionaries are used.
 
- # Explict order-sensitive comparison
- >>> list(od1.items())==list(od2.items())
+How __repr__ format will maintain order during an repr/eval round-trip?
+
+ OrderedDict([('a', 1), ('b', 2)])
 
 What are the trade-offs of the possible underlying data structures?
 
@@ -255,6 +256,7 @@
 would keep the same big-oh performance as regular dictionaries. It is
 the fastest and most space efficient.
 
+
 Reference Implementation
 ========================
 
