2

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?

  • http://stackoverflow.com/questions/1491037/mapping-stdmap-to-python, is this what you were looking for? – John Nov 01 '11 at 17:51
  • You could dig into the OrderedDict implementation to implement a solution, but the implementation itself is version dependent and there might not always be a way to do this in the future. FWIW, Python 2.7 `foo._OrderedDict__map[somekey][1][2]` and 3.2 `foo._OrderedDict__map[somekey].next.key` will each give you the key following `somekey`, but don't do this. – Duncan Nov 01 '11 at 18:33

5 Answers5

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:

Raymond Hettinger
  • 216,523
  • 63
  • 388
  • 485
  • Python's native `OrderedDict` class also doesn't keep it contents in key sort order. I think the OP needs to look at implementations of what would be called a `SortedDict`. – martineau Nov 01 '11 at 20:20
  • It is trivial to sort data for a given key-function and the insert it into an OrderedDict for lookup and traversal: http://docs.python.org/library/collections.html#ordereddict-examples-and-recipes That works fine unless new keys are added, then a resort is required (though SortedDict implementations also have to do an insort() on every insertion or do a lazily do a full sort before a lookup). – Raymond Hettinger Nov 01 '11 at 21:11
2

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.

unutbu
  • 842,883
  • 184
  • 1,785
  • 1,677
  • 2
    This way, you end up with O(n) look-up time. – Sven Marnach Nov 01 '11 at 17:54
  • Iterating over the items in `foo` is O(n) anyway, so I don't think looking up the beginning of the iterator in O(1) time would improve the overall time complexity. (O(1) lookup can be done with `foo._OrderedDict__map`, but that would depend on implementation details.) – unutbu Nov 01 '11 at 18:41
0

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.

GrantJ
  • 8,162
  • 3
  • 52
  • 46
0
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

jcfollower
  • 3,103
  • 19
  • 25
0

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)
Sven Marnach
  • 574,206
  • 118
  • 941
  • 841