map:：lower_bound（）等价于python的dict类？

Question

我正在编写一些代码，要求我获取一个键的下界（为了简单起见，忽略位于集合中最小键之下的键）。在

<>在C++中，使用STD::MAP（作为最可比的数据类型），我只需使用LoeRixBoin（）返回迭代器。在

我的pythonfo不是很好，但是我猜（如果Python还没有办法做到这一点），这将是lambda函数的一个很好的使用。。。在

检索给定索引的下界键的Pythonic方法是什么？在

如果这个问题太抽象了，这就是我要做的：

我有一个按日期索引的Python dict。我希望能够使用日期来查找dict，并返回与指定键的lowerbound相关联的值。在

代码段如下：

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 

我真的不想遍历这些键，寻找第一个键<；=提供的键，除非没有更好的替代方法。。。在

Answer 1

当我想要类似于c++映射的东西时，我使用SortedDict。您可以使用irange获得一个迭代器，该迭代器指向一个给定键的下界——我认为std::lower_bound就是这样工作的。在

代码：

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)))

输出：

^{pr2}$

Answer 2

如果date以某种方式重载，它可以比较bisect module。在

最小整数编码示例：

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的dict类没有这个功能；您需要自己编写它。如果这些键已经被排序了，那肯定会很方便，不是吗，这样你就可以对它们进行二进制搜索，避免对它们进行遍历？在这种情况下，我将查看blist包中的sorteddict类。http://pypi.python.org/pypi/blist/