map::lower_bound() equivalent for python's dict class?

Question

I am writing some code that requires me to fetch the lower bound of a key (for simplicity, ignore keys that lie below the smallest key in the collection).

In C++, using std::map (as the most comparable data type) I would simply use the lower_bound() to return the iterator.

My Pythonfoo is not that great, but I am guessing that (in case Python does not already have a way of doing this), this would be a good use of a lambda function ...

What is the Pythonic way of retrieving the lower bound key for a given index?

In case the question is too abstract, this is what I am actually trying to do:

I have a Python dict indexed by date. I want to be able to use a date to look up the dict, and return the value associated with the lowerbound of the specified key.

Snippet follows:

mymap = { datetime.date(2007, 1, 5): 'foo',
          datetime.date(2007, 1, 10): 'foofoo',
          datetime.date(2007, 2, 2): 'foobar',
          datetime.date(2007, 2, 7): 'foobarbar' }

mydate = datetime.date(2007, 1, 7)

# fetch lbound key for mydate from mymap
def mymap_lbound_key(orig):
    pass # return the lbound for the key 

I don't really want to loop through the keys, looking for the first key <= provided key, unless there is no better alternative ...

Answer 1

When I want something that resembles a c++ map, I use SortedDict. You can use irange to get an iterator to a key for which a given key is a lower bound--which I think is how std::lower_bound works.

code:

from sortedcontainers import SortedDict
sd = SortedDict()
sd[105] = 'a'
sd[102] = 'b'
sd[101] = 'c'

#SortedDict is sorted on insert, like std::map
print(sd)

# sd.irange(minimum=<key>) returns an iterator beginning with the first key not less than <key>
print("min = 100", list(sd.irange(minimum=100)))
print("min = 102", list(sd.irange(minimum=102)))
print("min = 103", list(sd.irange(minimum=103)))
print("min = 106", list(sd.irange(minimum=106)))

output:

SortedDict(None, 1000, {101: 'c', 102: 'b', 105: 'a'})
min = 100 [101, 102, 105]
min = 102 [102, 105]
min = 103 [105]
min = 106 []

Answer 2

if you have date somehow overloaded that it can compare things look into the bisect module.

a minimal integer coding example:

from bisect import bisect_left

data = {
    200 : -100,
    -50 : 0,
    51 : 100,
    250 : 200
}

keys = list(data.keys())

print data[  keys[ bisect_left(keys, -79) ]  ]

Answer 3

Python's dict class doesn't have this functionality; you'd need to write it yourself. It sure would be convenient if the keys were already sorted, wouldn't it, so you could do a binary search on them and avoid iterating over them all? In this vein, I'd have a look at the sorteddict class in the blist package. http://pypi.python.org/pypi/blist/