问题描述
有时候，有一个按键排序的字典是有意义的。在C ++中，这通常用红黑树实现。但是任何自平衡二叉搜索树都会做（fwiw，Knuth在这个问题上特别清楚）。迄今为止我所能想到的最好的解决方案是采取，并创建一个基本实现STL映射接口的封装类（也可以在Python中方便地排列成对（两个元素元组））。这样一个元组基本上对应于std :: map :: value_type。是的，有Python的二等分模块，而在插入时它是对数的，就像自我平衡二叉树在插入时是对数的（对？），坦白说，我只是想要一个对象。被称为OrderedDict或某些东西（不，Python 3.1 OrderedDict不符合条件 - 这是插入时间的排序，坦率地说，插入时间排序与排序有关）并不是很明显。
注意，一个关键有序字典在许多行业中非常有用（例如，在财务方面，跟踪数据的价格簿是普通的，基本上是订单的价格字典 - >数量，汇总订单信息等）。如果有任何人有任何其他想法，那太好了。我知道的是，我在这里只有亚历克斯·马泰利的答案更智能地获得了500万次。所以我想我会问。
正如你所说，你可以用bisect来滚动自己的实现：
class OrderedDict：
def __init __（self，keyvalues_iter）：
self .__ srtlst__ = sorted（keyvalues_iter）
def __len __（self）：
return len（self .__ srtlst__）
def __contains __（self，key）：
index = bisect（self .__ srtlst__，key）
如果index< ; len（self .__ srtlst__）和self .__ srtlst __ [index] [0] == key：
return True
else：
return False
def __getitem __（self，key） ：
index = bisect（self .__ srtlst__，key）
如果index< len（self .__ srtlst__）和self .__ srtlst __ [index] [0] == key：
return self .__ srtlst__ [index] [1]
else：
raise KeyError（key）
def __setitem __（sekf，key，value）：
index = bisect（self .__ srtlst__，key）
如果index< len（self .__ srtlst__）和self .__ srtlst __ [index] [0] == key：
s elf .__ srtlst __ [index] [1] = value
else：
self .__ srtlst __ [index] =（key，value）
def __delitem __（sekf，key，value）：
index = bisect（self .__ srtlst__，key）
如果index< len（self .__ srtlst__）和self .__ srtlst __ [index] [0] == key：
del __srtlst __ [index]
else：
raise KeyError（key）
def __iter __（self）：
return（v for k，v in self .__ srtlst__）
def clear（self）：
self .__ srtlst__ = []
def get（self，key，default = None）：
index = bisect（self .__ srtlst__，key）
如果index< len（self .__ srtlst__ ）和self .__ srtlst __ [index] [0] == key：
return self .__ srtlst __ [index] [1]
else：
返回默认
def items（self） ：
return self .__ srtlst __ [：]
def iteritems（self）：
return iter（self .__ srtlst__）
def iterkeys（self）：
return对于k，v in self .__ srtlst__）
def itervalues（self）：
return（v for k，v in self .__ srtlst _ $）
def key（self）：
return [k for k，v in self .__ srtlst__]
def values（self）：
return [v for k，v in
def setdefault（self，key，default）：
index = bisect（self .__ srtlst__，key）
如果index< len（self .__ srtlst__）和self .__ srtlst __ [ index] [0] == key：
return self .__ srtlst __ [index] [1]
else：
self .__ srtlst __ [index] =（key，default）
return默认
def update（self，other）：
#a更有效的实现可以合并排序列表
for k，v在other.iteritems（）中：
self [ k] = v
嗯...似乎我已经为你做了， ！
Sometimes it makes sense to have a key-ordered dictionary. In C++, this is often implemented with a Red-black tree. But any self-balancing binary search tree will do (fwiw, Knuth is particularly clear on this subject). The best solution I've been able to come up with so far is to take R. McGraw's AVL-tree type and create a wrapper class that basically implements the STL map interface (also counting on the handy ordering of pairs (two element tuples) in Python). Such a tuple basically corresponds to std::map::value_type.
Yes, there's Python's bisect module, and while that is logarithmic at insertion time in the same way that self-balancing binary trees are logarithmic at insertion time (right?), frankly I just want an object. Called OrderedDict or something (and no, the Python 3.1 OrderedDict doesn't qualify -- that's for 'insertion-time' ordering -- and frankly what insertion-time ordering has to do with ordering is not quite obvious).
Note, a key-ordered dictionary is highly useful in many industries (in finance for instance, it's ordinary to keep track of price books of data, which are basically ordered dictionaries of price -> quantity, aggregated order information, etc.).
If anyone has any other ideas, that's great. All I know is I just got five million times smarter by Alex Martelli's 'answers' here. So I thought I'd ask.
As you said, you can roll your own implementation with bisect:
class OrderedDict:
def __init__(self, keyvalues_iter):
self.__srtlst__ = sorted(keyvalues_iter)
def __len__(self):
return len(self.__srtlst__)
def __contains__(self, key):
index = bisect(self.__srtlst__, key)
if index<len(self.__srtlst__) and self.__srtlst__[index][0] == key:
return True
else:
return False
def __getitem__(self, key):
index = bisect(self.__srtlst__, key)
if index<len(self.__srtlst__) and self.__srtlst__[index][0] == key:
return self.__srtlst__[index][1]
else:
raise KeyError(key)
def __setitem__(sekf, key, value):
index = bisect(self.__srtlst__, key)
if index<len(self.__srtlst__) and self.__srtlst__[index][0] == key:
self.__srtlst__[index][1] = value
else:
self.__srtlst__[index]=(key, value)
def __delitem__(sekf, key, value):
index = bisect(self.__srtlst__, key)
if index<len(self.__srtlst__) and self.__srtlst__[index][0] == key:
del __srtlst__[index]
else:
raise KeyError(key)
def __iter__(self):
return (v for k,v in self.__srtlst__)
def clear(self):
self.__srtlst__ = []
def get(self, key, default=None):
index = bisect(self.__srtlst__, key)
if index<len(self.__srtlst__) and self.__srtlst__[index][0] == key:
return self.__srtlst__[index][1]
else:
return default
def items(self):
return self.__srtlst__[:]
def iteritems(self):
return iter(self.__srtlst__)
def iterkeys(self):
return (k for k,v in self.__srtlst__)
def itervalues(self):
return (v for k,v in self.__srtlst__)
def keys(self):
return [k for k,v in self.__srtlst__]
def values(self):
return [v for k,v in self.__srtlst__]
def setdefault(self, key, default):
index = bisect(self.__srtlst__, key)
if index<len(self.__srtlst__) and self.__srtlst__[index][0] == key:
return self.__srtlst__[index][1]
else:
self.__srtlst__[index]=(key, default)
return default
def update(self, other):
#a more efficient implementation could be done merging the sorted lists
for k, v in other.iteritems():
self[k] = v
hmmm... it seems that I already did that for you, d'oh!
这篇关于将std :: map映射到Python的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！