Python dictionary with lookup that returns an iterator

Question

Something I miss about C++ std::map (which is a sorted dictionary) is that looking up a key returns an iterator pointing to the correct location in the map. This means you can lookup a key and then start iterating from there, e.g. if the key is actually the beginning of a range you are interested in, or if you wanted "the item in my dictionary just after key".

Is there some other python dict that supports this kind of functionality?

Answer 1

In Python2.7+, you could use an OrderedDict:

import collections
import itertools

foo=collections.OrderedDict((('a',1),('b',2),('c',3)))
for key,value in itertools.dropwhile(lambda x: x[0]!='b',foo.iteritems()):
    print(key,value)

yields

('b', 2)
('c', 3)

For Python2.6 or less, you could use the OrderedDict recipe.

Answer 2

my_dict = {'a': 1, 'b': 2, 'c': 3, 'd': 4}

print my_dict

keys = my_dict.keys()
keys.sort()
start_index = keys.index('b')

for key in keys[start_index:]:
    print key, my_dict[key]

=================================

{'a': 1, 'c': 3, 'b': 2, 'd': 4}

b 2

c 3

d 4

Answer 3

Python's native OrderedDict class in the collections module doesn't support an operation to advance forward from a key chosen at random. There are other implementations of ordered dictionaries that do support that operation. One of these may meet your needs:

• http://dev.pocoo.org/hg/sandbox/raw-file/tip/odict.py
• http://babel.edgewall.org/browser/trunk/babel/util.py?rev=374#L178
• http://code.djangoproject.com/browser/django/trunk/django/utils/datastructures.py?rev=7140#L53
• http://www.voidspace.org.uk/python/odict.html
• http://www.xs4all.nl/~anthon/Python/ordereddict/
• http://pypi.python.org/pypi/StableDict/0.2
• http://codespeak.net/svn/user/arigo/hack/pyfuse/OrderedDict.py

Answer 4

If you don't need O(log n) inserts and deletes at arbitrary positions, you can use a list of key-value pairs, and use bisect.bisect() to look up items:

d = [("a", 3), ("b", 4), ("c", 5)]
i = bisect.bisect(d, ("b",))
print d[i + 1]

prints

('c', 5)

Answer 5

The Python sortedcontainers module provides a SortedDict type that supports this in a couple ways.

SortedDict.irange returns an iterator that slices the mapping's keys:

from sortedcontainers import SortedDict
values = SortedDict(enumerate(range(10)))
assert list(values.irange(5, 8)) == [5, 6, 7, 8

And SortedDicts are also indexable:

assert values.iloc[4] == 4
assert values.iloc[2:5] == [2, 3, 4]
assert values.index(7) == 7

The iloc attribute is a proxy for efficiently slicing or getting items by index. The index method works oppositely.

The SortedContainers project includes benchmarks and extensive testing. Tests cover 100% of the project and stress runs for hours before every major release.