什么样的树实现是STL设置？ [英] What kind of tree implementation is STL set?

问题描述

我知道在STL 向量表示动态数组的实现。因此 list 表示链表的实现（双向链表）。我知道 set 有一个类似于树的实现。看看所提到的算法复杂度，集合中的大部分内置函数是复杂度 o（1）或 o（log n）。所以这个树被实现为平衡树或任何其他种类的树如红黑树和如果为什么选择这样的树结构？

I know that in STL vector represents the implementation of a dynamic array. So does the list represents the implementation of a linked list (doubly linked list). I know that set has an implementation similar to tree . Looking at the algorithm complexity as mentioned most of the inbuilt function in set is of complexity o(1) or o(log n). So is this tree implemented as Balanced Tree or any other kind of tree such as red-black tree and if So Why such a tree structure was chosen ?

推荐答案

标准对实现没有限制（复杂性保证除外）。

The standard imposes no restrictions on the implementation (other than the complexity guarantees).

换句话说，它是依赖于实现的。通常，它是一个红黑树（参见 / usr / include / c ++ / xyz / bits / stl_tree.h ，其中 xyz 是您特定的GCC版本）。

In other words, it's implementation-dependent. Typically, it's a red-black tree (see e.g. /usr/include/c++/x.y.z/bits/stl_tree.h, where x.y.z is your particular GCC version).

这篇关于什么样的树实现是STL设置？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！