我正在用 Python 开发一个“TreeDict”类。这基本上是一个字典，允许您按排序顺序检索其键值对，就像 Java 中的 Treemap 集合类一样。
我已经根据关系数据库中唯一索引的使用方式实现了一些功能，例如函数可让您检索与一系列键相对应的值、大于、小于或等于排序顺序中特定值的键、按排序顺序具有特定前缀的字符串或元组等。
不幸的是，我想不出任何现实生活中的问题需要这样的课程。我怀疑我们在 Python 中没有排序字典的原因是，在实践中它们并不经常被需要，不值得这样做，但我想被证明是错误的。
您能想到“TreeDict”的任何具体应用吗？这种数据结构可以最好地解决现实生活中的任何问题吗？我只是想确定这是否值得。
我已经看到几个答案指向“按有序序列行走”功能，这确实很重要，但没有一个答案强调另一个重要功能，即“查找带有键 >= this 的第一个条目”。即使没有真正需要从那里“步行”，这也有很多用途。
例如（这在最近的 SO 答案中出现），假设您想生成具有给定相对频率的伪随机值 - 即，您给出了一个字典
d{'wolf': 42, 'sheep': 15, 'dog': 23, 'goat': 15, 'cat': 5}
并且需要一种方法来生成“狼”，概率为 100 中的 42（因为 100 是给定的相对频率的总和），“羊”的概率为 100 中的 15，等等；并且不同值的数量可能非常大，相对频率也是如此。
然后，将给定值（以任何顺序）存储为树图中的值，相应的键是截至该点的“总累积频率”。即：
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
其中
firstGTKey.key.valuebsddb.bt_openset_location当您需要按键顺序浏览字典时，它很有用；有时会出现。事实上，我发现它在某些编程竞赛中比其他任何竞赛都更常见（想想 ACM 等）。
TreeMap 最有用的功能是当您想要快速找到最小或最大键时；使用排序字典，这通常是单个方法调用；并且在算法上可以在 O(log(n)) 时间内完成，而不是在集合未排序的情况下迭代每个键以查找最小值/最大值。基本上，界面更加友好。
我遇到的最常见的情况之一是当对象由特定名称标识时，并且您想要打印出根据名称排序的对象；说一下从目录名称到目录中文件数量的映射。
我使用它的另一个地方是在 Excel 电子表格包装中；从行号到行对象的映射。这可以让您快速找到最后一行索引，而无需循环遍历每一行。
此外，当您可以轻松地定义键上的比较关系（但不一定是 HashMap 所需的哈希函数）时，它也很有用。我能想到的最好的（虽然很弱）的例子是不区分大小写的字符串键。
保持元素排序的原因是为了更快的检索。假设我希望字典中的所有值都在排序范围内。使用 TreeDict 比使用常规哈希图要快得多。它基本上允许您按排序顺序保留字典中的所有内容。我知道在我当前正在开发的应用程序中使用这样的类来基本上查询数据结构。
在处理工业过程数据时，我经常使用
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它们可以使各种算法更容易实现。