将std :: map映射到Python
问题内容：
有时，有一个键序字典是有意义的。在C
++中，通常使用红黑树来实现。但是任何自平衡的二进制搜索树都可以做到（首先，Knuth在这个问题上特别清楚）。到目前为止，我能想到的最好的解决方案是采用R.
McGraw的AVL-
tree类型
并创建一个包装器类，该包装器类基本上实现STL映射接口（还依靠对的方便排序（两个元素元组）在Python中）。这样的元组基本上对应于std
:: map :: value_type。
是的，有Python的bisect模块，虽然它在插入时是对数的，就像自平衡二叉树在插入时是对数的（对吗？）一样，坦率地说，我只想要一个对象。称为OrderedDict之类的东西（不是，Python
3.1 OrderedDict不符合条件-这是针对“插入时间”排序的，坦率地说，插入时间排序与排序的关系还不是很明显）。
请注意，键序字典在许多行业中都非常有用（例如，在金融中，跟踪价格表的数据很常见，这些价格表基本上是价格的顺序字典->数量，汇总的订单信息等）。
如果有人有其他想法，那太好了。我所知道的是，我在这里仅凭Alex Martelli的“答案”就比自己聪明了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)
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
嗯…看来我已经为您做到了，天哪！
