4

Since Python 3.7, dictionaries are ordered. So why I can't get keys by index?

ddejohn
  • 8,775
  • 3
  • 17
  • 30
Module_art
  • 999
  • 2
  • 9
  • 26
  • Does this answer your question? https://stackoverflow.com/questions/4326658/how-to-index-into-a-dictionary – nathan liang Mar 26 '22 at 21:47
  • No it doesn't because they only say, that before the dict was unordered and in newer Python version it is ordered. What I already knew. – Module_art Mar 26 '22 at 21:50
  • I think the answer you're looking for is along the lies of "just because the keys are ordered doesn't mean they can be indexed in constant time". Consider an implementation that stores keys in a linked list (which is exactly what CPython's `OrderedDict` did, at least historically). – Brian61354270 Mar 26 '22 at 21:56

2 Answers2

5

Building in such an API would be an "attractive nuisance": the implementation can't support it efficiently, so better not to tempt people into using an inappropriate data structure.

It's for much the same reason that, e.g., a linked list rarely offers an indexing API. That's totally ordered too, but there's no efficient way to find the i'th element for an arbitrary i. You have to start at the beginning, and follow i links in turn to find the i'th.

Same end result for a CPython dict. It doesn't use a linked list, but same thing in the end: it uses a flat vector under the covers, but basically any number of the vector's entries can be "holes". There's no way to jump over holes short of looking at each entry, one at a time. People expect a[i] to take O(1) (constant) time, not O(i) time.

Tim Peters
  • 67,464
  • 13
  • 126
  • 132
  • Thank you. In fact it's the same dictionary as collections OrderedDict? I understand now why I can't get keys by index better. – Module_art Mar 27 '22 at 00:00
  • 2
    While `collections.OrderedDict` and the builtin `dict` are both ordered, their implementations are very different. What the built-in `dict` does is better suited to its C implementation. `OrderedDict` actually does use a linked list to remember the order; the built-in `dict` implementation is substantially subtler. But in either case, finding the `i`'th key (or value) takes `O(i)` time. – Tim Peters Mar 27 '22 at 00:05
  • BTW, I gave an overview of `OrderedDict`'s implementation here some time ago: https://stackoverflow.com/a/18951209/2705542 – Tim Peters Mar 27 '22 at 00:30
  • Interesting that was my second question, how does the dict remember the order, now I know. thx – Module_art Mar 27 '22 at 15:02
1

Here's a workaround if you're really desperate for this functionality:

In [2]: d
Out[2]: {'a': 'A', 'b': 'B', 'c': 'C'}

In [3]: indexed_keys = dict(enumerate(d.keys()))

In [4]: d[indexed_keys[1]]
Out[4]: 'B'

So keys is a dictionary itself, but whose key values directly correspond to the "index" at which the keys of d are located. So getting the key at index i is still O(1). Now you're using two O(1) look ups to get a value associated with a key's "index" in the original dictionary.

This obviously wouldn't work if your original dictionary's keys collide with their enumeration, but if that happens you have bigger issues to work out -- like picking a more appropriate data structure.

ddejohn
  • 8,775
  • 3
  • 17
  • 30