C++ STL 中的二叉搜索树实现？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/5085091/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Binary Search Tree Implementation in C++ STL?
提问by Bunkai.Satori
Do you know, please, if C++ STLcontains a Binary Search Tree (BST)implementation, or if I should construct my own BST object?
请问您知道C++ STL 是否包含二叉搜索树 (BST)实现，或者我是否应该构建自己的 BST 对象？
In case STL conains no implementation of BST, are there any libraries available?
如果 STL 没有实现 BST，是否有可用的库？
My goalis to be able to find the desired record as quickly as possible: I have a list of records (it should not be more few thousands.), and I do a per-frame (its a computer game) search in that list. I use unsigned int as an identifier of the record of my interest. Whatever way is the fastest will work best for me.
我的目标是能够尽快找到所需的记录：我有一个记录列表（不应超过几千个。），并且我在该列表中进行每帧（它是计算机游戏）搜索. 我使用 unsigned int 作为我感兴趣的记录的标识符。无论哪种方式最快，对我来说都是最好的。
回答by sbi
What you need is a way to look up some data given a key. With the key being an unsigned int, this gives you several possibilities. Of course, you could use a std::map:
您需要的是一种在给定键的情况下查找某些数据的方法。键是unsigned int，这为您提供了几种可能性。当然，你可以使用一个std::map：
typedef std::map<unsigned int, record_t> my_records;
However, there's other possibilities as well. For example, it's quite likely that a hash map would be even fasterthan a binary tree. Hash maps are called unordered_mapin C++, and are a part of the C++11standard, likely already supported by your compiler/std lib (check your compiler version and documentation). They were first available in C++TR1(std::tr1::unordered_map)
然而，还有其他的可能性。例如，哈希映射很可能比二叉树更快。哈希映射unordered_map在 C++ 中被调用，并且是C++11标准的一部分，可能已经被你的编译器/标准库支持（检查你的编译器版本和文档）。它们首先在C++TR1( std::tr1::unordered_map)
If your keys are rather closely distributed, you might even use a simple arrayand use the key as an index. When it comes to raw speed, nothing would beat indexing into an array. OTOH, if your key distribution is too random, you'd be wasting a lot of space.
如果您的键分布相当紧密，您甚至可以使用一个简单的数组并将键用作索引。当谈到原始速度时，没有什么比索引到数组更好了。OTOH，如果您的密钥分配太随机，您将浪费大量空间。
If you store your records as pointers, moving them around is cheap, and an alternative might be to keep your data sorted by key in a vector:
如果您将记录存储为pointers，则移动它们的成本很低，另一种方法可能是将数据按键排序在向量中：
typedef std::vector< std::pair<unsigned int, record_t*> > my_records;
Due to its better data locality, which presumably plays nice with processor cache, a simple std::vectoroften performs better than other data structures which theoretically should have an advantage. Its weak spot is inserting into/removing from the middle. However, in this case, on a 32bit system, this would require moving entries of 2*32bit POD around, which your implementation will likely perform by calling CPU intrinsics for memory move.
由于其更好的数据局部性，这可能与处理器缓存配合得很好，一个简单的std::vector通常比理论上应该具有优势的其他数据结构表现得更好。它的弱点是从中间插入/从中取出。但是，在这种情况下，在 32 位系统上，这将需要移动 2*32 位 POD 的条目，您的实现可能会通过调用 CPU 内部函数来执行内存移动。
回答by ltjax
std::setand std::mapare usually implemented as red-black trees, which are a variant of binary search trees. The specifics are implementation dependent tho.
std::set并且std::map通常实现为红黑树，它是二叉搜索树的变体。具体细节取决于实现。
回答by amarVashishth
A clean and simple BST implementation in CPP:
CPP 中一个干净简单的 BST 实现：
struct node {
int val;
node* left;
node* right;
};
node* createNewNode(int x)
{
node* nn = new node;
nn->val = x;
nn->left = nullptr;
nn->right = nullptr;
return nn;
}
void bstInsert(node* &root, int x)
{
if(root == nullptr) {
root = createNewNode(x);
return;
}
if(x < root->val)
{
if(root->left == nullptr) {
root->left = createNewNode(x);
return;
} else {
bstInsert(root->left, x);
}
}
if( x > root->val )
{
if(root->right == nullptr) {
root->right = createNewNode(x);
return;
} else {
bstInsert(root->right, x);
}
}
}
int main()
{
node* root = nullptr;
int x;
while(cin >> x) {
bstInsert(root, x);
}
return 0;
}
回答by corsiKa
STL's set class is typically implemented as a BST. It's not guaranteed (the only thing that is is it's signature, template < class Key, class Compare = less<Key>, class Allocator = allocator<Key> > class set;) but it's a pretty safe bet.
STL 的集合类通常作为 BST 实现。不能保证（唯一的是它的签名，template < class Key, class Compare = less<Key>, class Allocator = allocator<Key> > class set;）但这是一个非常安全的赌注。
Your post says you want speed (presumably for a tighter game loop).
你的帖子说你想要速度（大概是为了更紧凑的游戏循环）。
So why waste time on these slow-as-molasses O(lg n) structures and go for a hash map implementation?
那么为什么要浪费时间在这些像糖蜜一样慢的 O(lg n) 结构上并去实现哈希图呢？
