Why python does not include a ordered dict (by default)?

Question

Python have some great structures to model data. Here are some :

              +-------------------+-----------------------------------+
              | indexed by int    | no-indexed by int                 |
+-------------+-------------------+-----------------------------------+
| no-indexed  | [1, 2, 3]         | {1, 2, 3}                         |
| by key      | or                | or                                |
|             | [x+1 in range(3)] | {x+1 in range(3)}                 |
+-------------+-------------------+-----------------------------------+
| indexed     |                   | {'a': 97, 'c': 99, 'b': 98}       |
| by key      |                   | or                                |
|             |                   | {chr(x):x for x in range(97,100)} |
+-------------+-------------------+-----------------------------------+

Why python does not include by default a structure indexed by key+int (like a PHP Array) ? I know there is a library that emulate this object ( http://docs.python.org/3/library/collections.html#ordereddict-objects). But here is the representation of a "orderedDict" taken from the documentation :

OrderedDict([('pear', 1), ('apple', 4), ('orange', 2), ('banana', 3)])

Wouldn't it be better to have a native type that should logically be writen like this:

['a': 97, 'b': 98, 'c': 99]

And same logic for orderedDict comprehension :

[chr(x):x for x in range(97,100)]

Does it make sense to fill the table cell like this in the python design? It is there any particular reason for this to not be implemented yet?

Answer 1

Python's dictionaries are implemented as hash tables. Those are inherently unordered data structures. While it is possible to add extra logic to keep track of the order (as is done in collections.OrderedDict in Python 2.7 and 3.1+), there's a non-trivial overhead involved.

For instance, the recipe that the collections documentation suggest for use in Python 2.4-2.6 requires more than twice as much work to complete many basic dictionary operations (such as adding and removing values). This is because it must maintain a doubly-linked list to use for ordered iteration, and it needs an extra dictionary to help maintain the list. While its operations are still O(1), the constant terms are larger.

Since Python uses dict instances everywhere (for all variable lookups, for instance), they need to be very fast or every part of every program will suffer. Since ordered iteration is not needed very often, it makes sense to avoid the overhead it requires in the general case. If you need an ordered dictionary, use the one in the standard library (or the recipe it suggests, if you're using an earlier version of Python).