python内建的dict（字典）类使用的是hash算法，因此它的key不是有序的。而C++中的std::map或std::set使用的是平衡二叉树（通常为红黑树），其key是有序的。在网上搜了搜，找到了一个用C和pyrex混合实现的红黑树模块，python-rbtree。
我编写了一个极简单的测试程序，在Solaris x86 + python 2.4.4平台上运行，分别使用dict和rbtree，插入两百万个记录（key是3个整型，value是1个整型，你大概猜到我在干什么了吧 
）。且在dict插入完之后，调用dict.keys().sort()对其key进行排序（也就是快排）。比较的结果是，两种方法使用的内存相当（大概在200M左右）。但是hash算法的速度要快一倍以上。当记录个数增加到五百万个时，结果还是差不多──即内存使用相当，hash算法快一倍。
至少在这个数量级上，内建的dict性能更佳。我还尝试了另一个纯Python的红黑树实现–RBTree.py，结果令人失望，在记录个数比较多的情况下，似乎根本无法得到正确的结果。
结论，python中的dict是可信赖的！