CODEWITHSUNDEEP
pythondictionarysorteddictionary
user334911
user334911

Reputation:

Python dictionary with lookup that returns an iterator

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?

Upvotes: 2

Views: 391

Answers (5)

GrantJ
GrantJ

Reputation: 8689

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.

Upvotes: 0

Sven Marnach
Sven Marnach

Reputation: 601559

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)

Upvotes: 0

Raymond Hettinger
Raymond Hettinger

Reputation: 226296

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:

Upvotes: 3

jcfollower
jcfollower

Reputation: 3158

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

Upvotes: 0

unutbu
unutbu

Reputation: 879421

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.

Upvotes: 2

Related Questions