背景
我正在构建一个注重性能的应用程序，遇到了一个必须使用std::set的地方。它就像一种魅力。但后来我开始阅读文档(你可以在这里找到)，我注意到的第一件事是
搜索、删除和插入操作具有对数复杂度。集合通常实现为红黑树。
搜索、删除和插入对我来说非常有意义，因为它们使用某种树结构(因为文档不能保证它使用红黑树)。但问题是，他们为什么要这样做？
我为自己的std::set制作了一个替代解决方案，它使用std::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需要很长时间来迭代条目。影响性能的一些事情是(如果我错了，请纠正我)，
- 缓存未命中
- 指针取消引用
- 更好的地方
对于去除速度较慢的矢量，
- 查找元素
- 元件的拆卸
- 可能调整大小
问题
正如我所看到的，使用std::vector而不是树结构存储条目在3/4个实例中表现更好。即使在std::set表现更好的地方，与迭代相比，它仍然是一个小数量。在我看来，开发人员更多地使用其他方面(查找、插入和迭代)，而不是删除。即使这些数字在纳秒的范围内，最轻微的改善也更好。
所以我的问题是，当std::set可以使用向量之类的东西来提高效率时，为什么要使用树结构？
注意：容器将填充平均1000个元素，并在应用程序的整个生命周期中重复迭代，这将直接影响应用程序的运行时间。
标准set有一些您无法在实现中提供的保证：
- 插入/擦除不会使其他迭代器/引用/指针无效
- 插入/擦除元素(最多)具有对数复杂性，而不是实现中的线性复杂性
如果这些对你来说无关紧要，欢迎你使用排序向量和二进制搜索。标准提供了std::sort、std::vector和std::binary_search，所以您可以使用。需要注意的是，每个容器都有一个特定的用例；"一刀切"；容器
该标准还提供了unordered_set，这是一个哈希表。它经常被批评为速度慢并导致缓存未命中。好吧，如果这以一种你认为是瓶颈的方式降低了你的性能，那么继续使用其他库中的一些其他哈希集实现。如果你相信你可以做得更好，那就去做吧。许多项目构建自己的容器，这些容器对该项目更加专业化。可以更快，使用更少的内存，可以对迭代器无效和/或操作的复杂性提供不同的保证。它们都能解决不同的问题。
另一点是分析和基准测试很难。确保你做对了。性能比较通常是按比例进行的(具有不同数量的输入参数)。选择一个恒定且相对较小的尺寸并不能说明全部情况。