查找返回迭代器的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字典

回答

相關問題