为什么C++STL没有实现更高效的std::set实现？
背景
我正在构建一个注重性能的应用程序，但我遇到了一个必须使用std::set. 它就像一个魅力。但后来我开始阅读文档（你可以在这里找到），我注意到的第一件事是
搜索、移除和插入操作具有对数复杂度。集合通常被实现为红黑树。
搜索、删除和插入对我来说非常有意义，因为它们使用某种树结构（因为文档不保证它使用Red-Black Tree）。但问题是，他们为什么要这样做？
我std::set为我自己的解决方案做了一个替代解决方案，它使用 astd::vector来存储所有条目。然后我执行了一些基本的基准测试，这是结果，
Iterations: 100000
// Insertion
VectorSet : 211464us
std::set : 1272864us
// Find/ Lookup
VectorSet : 404264us
std::set : 551464us
// Removal
VectorSet : 254321964us
std::set : 834664us
// Traversal (iterating through all the elements (100000 elements; 100000 iterations)
VectorSet : 2464us
std::set : 4374174264us
根据这些结果，我的实现 ( VectorSet)std::set在插入和查找方面都表现出色，遍历次数超过 1800000 次。但是明显std::set优于我的实现VectorSet（这是可以理解的，因为我们正在处理向量）。
我可以证明为什么删除速度较慢VectorSet但速度较快，std::set以及为什么std::set遍历条目需要这么长时间。一些影响性能的事情是（如果我错了，请纠正我），
- 缓存未命中。
- 指针取消引用。
- 更好的地方。
对于移除速度较慢的向量，
- 寻找元素。
- 移除元素。
- 可能调整大小。
问题
正如我所见，使用 astd::vector来存储条目而不是树结构在 3/4 实例中表现更好。而且即使在std::set表现更好的地方，与迭代相比仍然是一个很小的数量。在我看来，开发人员更多地使用其他方面（查找、插入和迭代）而不是删除。尽管这些数字在纳秒范围内，但最细微的改进更好。
所以我的问题是，std::set当他们可以使用向量之类的东西来提高效率时，为什么还要使用树结构？
注意：容器将平均填充 1000 个元素，并将在整个应用程序生命周期内重复迭代，并将直接影响应用程序运行时。
回答
该标准set有一些您无法在实现中提供的保证：
- 插入/擦除不会使其他迭代器/引用/指针无效。
- 插入/擦除元素具有（最多）对数复杂度，而不是您的实现中的线性复杂度。
如果这些对您来说无关紧要，欢迎您使用排序向量和二分搜索。标准提供std::sort,std::vector和std::binary_search，所以你很高兴。需要注意的是，每个容器都有一个特定的用例，并且没有“一刀切”的容器。
该标准还提供了unordered_set，它是一个哈希表。它经常因速度缓慢和导致缓存未命中而受到批评。好吧，如果这以您认为是瓶颈的方式降低了您的性能，请继续使用其他库中的其他哈希集实现。如果你相信你可以做得更好，那就继续吧。许多项目构建自己的容器，这些容器更专门用于该项目。可以更快，使用更少的内存，可以对迭代器失效和/或操作的复杂性提供不同的保证。他们都解决了不同的问题。
另一点是分析和基准测试很困难。确保你做对了。性能比较通常是按比例进行的（输入参数数量不同）。选择恒定且相对较小的尺寸并不能说明全部情况。