c++ - C++ STL中的二叉搜索树实现？

Question

请问您知道 C++ STL 是否包含 二叉搜索树 (BST) 实现，或者我是否应该构建自己的 BST 对象？

如果 STL 不包含 BST 的实现，是否有可用的库？

我的目标是能够尽快找到所需的记录:我有一个记录列表(它不应该超过几千个。)，我做一个每帧(它是一个电脑游戏)在该列表中搜索。我使用 unsigned int 作为我感兴趣的记录的标识符。无论哪种方式最快对我来说都是最好的。

Answer 1

您需要一种在给定 key 的情况下查找某些数据的方法。由于键是 unsigned int，这为您提供了多种可能性。当然，你可以使用 std::map:

typedef std::map<unsigned int, record_t> my_records;

但是，还有其他可能性。例如， HashMap 很可能会比二叉树更快。 HashMap 在 C++ 中称为 unordered_map，是 C++11 的一部分。标准，可能已经被您的编译器/标准库支持(检查您的编译器版本和文档)。它们首次出现在 C++TR1 (std::tr1::unordered_map)

如果您的键分布相当紧密，您甚至可以使用一个简单的 数组 并将键用作索引。当谈到原始速度时，没有什么能比索引到数组中更好了。 OTOH，如果您的 key 分配过于随机，您将浪费大量空间。

如果您将记录存储为指针，移动它们的成本很低，另一种方法可能是将数据按键排序在 vector 中:

typedef std::vector< std::pair<unsigned int, record_t*> > my_records;

由于其更好的数据局部性，可能与处理器缓存配合得很好，一个简单的 std::vector 通常比理论上应该具有优势的其他数据结构执行得更好。它的弱点是插入/从中取出。但是，在这种情况下，在 32 位系统上，这将需要移动 2*32 位 POD 的条目，您的实现可能会通过调用 CPU 内部函数来执行内存移动。