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

问题描述

我知道在 STL 中 vector 表示动态数组的实现.list 表示链表(双向链表)的实现也是如此.我知道 set 有一个类似于 tree 的实现.从算法复杂度来看，集合中的大多数内置函数都是复杂度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屋！