c++ - STL设置了什么样的树实现？

Question

我知道在 STL 中vector代表了一个动态数组的实现。list代表链表（双向链表）的实现也是如此。我知道它set有一个类似于 tree 的实现。看一下算法复杂度，set 中的大多数内置函数的复杂度为o(1)或o(log n)。那么这棵树是实现为平衡树还是任何其他类型的树，如红黑树，如果是这样，为什么选择这样的树结构？

Answer 1

该标准对实现没有任何限制（除了复杂性保证）。

换句话说，它依赖于实现。通常，它是一棵红黑树（参见例如/usr/include/c++/x.y.z/bits/stl_tree.h，x.y.z您的特定 GCC 版本在哪里）。