我正在用 Python 开发一个“TreeDict”类。这基本上是一个 dict，它允许您按排序顺序检索其键值对，就像 Java 中的 Treemap 集合类一样。
我已经根据关系数据库中唯一索引的使用方式实现了一些功能，例如，让您检索与一系列键对应的值的函数，按排序顺序大于、小于或等于特定值的键、字符串或按排序顺序具有特定前缀的元组等。
不幸的是，我想不出任何需要这样的课程的现实生活问题。我怀疑我们没有在 Python 中对 dicts 进行排序的原因是，在实践中，它们并不经常被要求值得，但我想被证明是错误的。
你能想到“TreeDict”的任何具体应用吗？这种数据结构能最好地解决任何现实生活中的问题吗？我只想确定这是否值得。
我已经看到几个答案指向“按顺序排列”功能，这确实很重要，但没有一个突出另一个大功能，即“使用键 >= 这个查找第一个条目”。即使没有真正需要从那里“走”，这也有很多用途。
例如（这出现在最近的 SO 答案中），假设您想生成具有给定相对频率的伪随机值 - 即，给您一个 dict d：
{'wolf': 42, 'sheep': 15, 'dog': 23, 'goat': 15, 'cat': 5}
并且需要一种方法来生成 'wolf' 的概率为 42 out of 100（因为 100 是给定的相对频率的总和），'sheep' 15 out of 100，等等；并且不同值的数量可能非常大，相对频率也是如此。
然后，将给定值（以任何顺序）存储为树形图中的值，对应的键是该点的“总累积频率”。IE：
def preprocess(d):
tot = 0
for v in d:
tot += d[v]
treemap.insert(key=tot, value=v)
return tot, treemap
现在，生成一个值可以非常快（O(log(len(d)))），如下所示：
def generate(tot, treemap, r=random):
n = r.randrange(tot)
return treemap.firstGTkey(n).value
wherefirstGTKey是一个方法，它返回第一个条目（在这个假设的例子中，带有.key和属性），键 > 给定参数。.value例如，我已经将这种方法用于存储为 B 树的大文件（使用 egbsddb.bt_open和set_location方法）。
保持元素排序的原因是为了更快地检索。假设我希望字典中的所有值都在排序范围内。使用 TreeDict 比使用常规哈希图要快得多。它基本上允许您按排序顺序保存字典中的所有内容。我知道在我目前正在使用的应用程序中使用这样的类来基本上查询数据结构。
当您需要按键的顺序浏览字典时，它很有用；有时会出现。实际上，我发现它在某些编程竞赛中比其他任何东西（想想 ACM 等）都更为普遍。
TreeMap 最有用的功能是当您想快速找到最小或最大键时；使用排序字典，这通常是一个方法调用；并且在算法上可以在 O(log(n)) 时间内完成，而不是在集合未排序的情况下遍历每个键以寻找最小值/最大值。基本上，一个更友好的界面。
我遇到的最常见的情况之一是当对象由特定名称标识时，您想打印出根据名称排序的对象；说从目录名称到目录中文件数的映射。
我使用它的另一个地方是在一个 excel 电子表格包装器中。从行号到行对象的映射。这使您可以快速找到最后一行索引，而无需遍历每一行。
此外，当您可以轻松定义键上的比较关系时，它也很有用，但不一定是散列函数，如 HashMaps 所需要的。我能想到的最好（虽然很弱）的例子是不区分大小写的字符串键。
我经常Dict<DateTime, someClassOrValue>在处理工业过程数据时使用——阀门打开/关闭、机械启动/停止等。
当我需要在相当长的时间内比较启动/停止或打开/关闭事件之间的时间间隔时，对键进行排序特别有用。
但是，由于我已经能够在 C# 中使用 linq，我发现使用 IEnumerables 并使用 IQueryable 扩展方法来获取我需要的信息通常更容易。
几乎所有“GROUP BY”报告都需要排序字典。
summary = sortedDefaultDict()
for row in somePileOfData:
summary[row.group_by] += row.balance
for k in sorted(summary.keys()):
print k, summary[k]
这在数据仓库应用程序中经常发生，很难表达这是多么重要。
如果sorted函数调用不起作用，从长远来看，它会节省大量时间。
你看到了吗：http ://code.activestate.com/recipes/576998/ ？
作
它们可以使各种算法更容易实现。