将std::map映射到Python

Question

有时候，使用一个按键排序的字典是很有意义的。在C++中，这通常是通过一种叫做红黑树的数据结构来实现的。不过，任何一种自平衡的二叉搜索树也可以做到（顺便提一下，Knuth在这方面讲得特别清楚）。到目前为止，我找到的最佳解决方案是使用R. McGraw的AVL树类型，然后创建一个包装类，基本上实现STL的map接口（还依赖于Python中成对的元素（两个元素的元组）的方便排序）。这样的元组基本上对应于std::map::value_type。

是的，Python有一个bisect模块，虽然在插入时它的效率是对数级别的，就像自平衡的二叉树在插入时一样（对吧？），但说实话，我只是想要一个对象。叫做OrderedDict之类的（而且，Python 3.1的OrderedDict不算在内——那是为了“插入时”的排序——说实话，插入时的排序和真正的排序之间的关系并不明显）。

请注意，按键排序的字典在很多行业中非常有用（比如在金融行业，跟踪价格数据的价格书是很常见的，这基本上就是价格到数量的有序字典，聚合的订单信息等等）。

如果有人有其他的想法，那就太好了。我只知道，通过Alex Martelli在这里的“回答”，我变得聪明了五百万倍。所以我想问问。

Answer 1

列表根本不能替代树这种数据结构。

当你要往列表里插入东西时，可能需要把整个列表都移动一遍来腾出空间；而删除东西时，又得把列表重新调整回来。虽然批量添加或删除东西在某些情况下可以，但很多时候并不容易，甚至需要一些奇怪的操作。树的一个基本特点是，插入和删除的时间复杂度是O(log n)，而不管你怎么说，O(n)是无法变成O(log n)的。

如果你已经知道要把一个项目放到树的哪个位置，插入它的时间复杂度是O(1)。同样地，从树中删除一个项目也是O(1)。而在列表中，这两个操作的时间复杂度都是O(n)。std::map就支持这两种操作。

树的另一个基本特性是，遍历一系列值的时间复杂度是每次O(1)。如果把列表和字典结合在一起，就失去了这个特性，因为每次遍历都需要查找字典。（使用元组列表的方法就没有这个问题。）

树是最基本的数据类型之一。Python缺少树这种容器类型真是个遗憾。也许有第三方库实现了树（比如“未知”先生链接的那个库，我没试过，所以不能保证好坏），但在标准的Python中并没有这种类型。

Answer 2

我有同样的需求，Alex Martelli的回答让我完全信服：最好的办法是保持一个字典和一个部分排序的键的列表，然后在需要的时候再排序。这种方法很高效，因为Python的排序算法（也叫Timsort）有它特别的表现。

我测试了他的实现和我的实现，结果他的更好（因为他不在列表中间插入元素）。

我强烈建议你去看看AM评论中提到的关于Timsort的论文，真的是一颗珍珠。

Answer 3

正如你所说，你可以自己实现一个二分查找的功能：

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  

嗯……看起来我已经为你做过这个了，真是的！