将std :: map映射到Python

Question

有时候有一个按键排序的字典是有意义的.在C++中,这通常使用红黑树实现.但是任何自我平衡的二元搜索树都会这样做(fwiw,Knuth在这个问题上特别清楚).到目前为止我能够提出的最好的解决方案是采用R. McGraw的AVL树类型并创建一个基本上实现STL映射接口的包装类(也依赖于对的方便排序(两个元素元组))在Python).这样的元组基本上对应于std :: map :: value_type.

是的,有Python的bisect模块,虽然在插入时是对数的,但是在插入时自平衡二进制树是对数的(对吧？),坦白说我只想要一个对象.被称为OrderedDict或其他东西(不,Python 3.1 OrderedDict没有资格 - 这是'插入时'的排序 - 坦率地说,插入时间排序与排序有什么关系并不是很明显).

注意,按键排序的字典在许多行业中非常有用(例如,在金融中,跟踪数据的价格书是很平常的,这些数据基本上是订购的价格词典 - >数量,汇总订单信息等).

如果有人有任何其他想法,那就太好了.我所知道的是Alex Martelli在这里的"答案"让我只有五百万倍的智慧.所以我想我会问.

Answer 1

正如您所说，您可以使用 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  

嗯...看来我已经为你做到了，哦！