查找返回迭代器的Python字典

我想念C++ std :: map（它是一个有序的字典）的东西是查找一个键返回指向地图中正确位置的迭代器。这意味着你可以查找一个键，然后从那里开始迭代，例如如果密钥实际上是你感兴趣的范围的开始，或者如果你想“我的字典中的项目紧跟在密钥之后”。查找返回迭代器的Python字典

是否还有其他一些支持这种功能的python dict？

来源

2011-11-01 John Robertson

http://stackoverflow.com/questions/1491037/mapping-stdmap-to-python，这是你在找什么？ – John

你可以深入OrderedDict实现来实现一个解决方案，但是实现本身是依赖于版本的，并且将来可能并不总是有办法做到这一点。 FWIW，Python 2.7'foo._OrderedDict__map [somekey] [1] [2]'和3.2'foo._OrderedDict__map [somekey] .next.key'每个都会给你'somekey'后的密钥，但不要这样做。 – Duncan

在Python2.7 +，你可以使用一个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)

产生

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

对于python2.6的或更少，你可以使用OrderedDict recipe。

来源

2011-11-01 17:52:32 unutbu

这样，你最终会看到O（n）的查找时间。 –

无论如何迭代'foo'中的项目是O（n），所以我不认为在O（1）时间内查找迭代器的开始会提高总体时间复杂度。（O（1）查找可以用'foo._OrderedDict__map'完成，但这取决于实现的细节。） – unutbu

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

来源

2011-11-01 18:05:24 jcfollower

集合模块在Python的本机OrderedDict类没有按不支持推进的行动从随机选择的密钥前进。还有其他支持该操作的有序字典的实现。其中一个可能会满足你的需求：

来源

2011-11-01 18:16:57

Python的本地'OrderedDict'类也不保留它的内容按键排序。我认为OP需要看一下所谓的'SortedDict'的实现。 – martineau

为给定的键控函数排序数据并将其插入到OrderedDict进行查找和遍历是很简单的：http://docs.python.org/library/collections.html#ordereddict-examples-and-recipes除非添加新密钥，否则需要使用度假区（尽管SortedDict实现也必须在每次插入时执行insort（），或者在查找之前懒惰地执行完整排序）。 –

如果你不需要O（log n）的插入和在任意位置删除，您可以使用键 - 值对的列表，并使用bisect.bisect()查找项目：

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

打印

('c', 5)

来源

2011-11-01 20:29:06

的Python sortedcontainers module提供了支持这几个方面一个SortedDict类型。

SortedDict.irange返回切片映射的键的迭代器：

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

而且SortedDicts也可转位：

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

的iloc属性是有效切片或指数获得项目的代理。 index方法相反。

SortedContainers项目includes benchmarks和广泛的测试。测试覆盖100％的项目和压力在每个主要版本之前运行数小时。

来源

2015-10-13 18:25:52 GrantJ

查找返回迭代器的Python字典

回答

相关问题