c++ - 为什么 C++ STL 不实现更高效的 std::set 实现？

Question

背景
我正在构建一个注重性能的应用程序，我遇到了一个必须使用 std::set 的地方。它就像一个魅力。但后来我开始阅读文档(你可以找到 here )，我注意到的第一件事是

Search, removal, and insertion operations have logarithmic complexity. Sets are usually implemented as red-black trees.

搜索、删除和插入对我来说非常有意义，因为它们使用的是 某种 树结构(因为文档不保证它使用 Red-Black Tree )。但问题是，他们为什么要这么做？

我对自己的 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(这是可以理解的，因为我们正在处理 vector )。

我可以证明为什么在 VectorSet 中移除速度较慢但在 std::set 中移除速度更快，以及为什么 std::set 需要这么长时间才能完成遍历条目。一些影响性能的事情是(如果我错了请纠正我)，

• 缓存未命中。
• 指针取消引用。
• 更好的地方。

对于 vector 的移除速度较慢，

• 寻找元素。
• 删除元素。
• 可能调整大小。

---

问题
如我所见，使用 std::vector 来存储条目而不是树结构在 3/4 实例中表现更好。并且即使在std::set表现较好的地方，与迭代遍历相比仍然是一个小量。在我看来，开发人员更多地使用其他方面(查找、插入和迭代)而不是删除。尽管这些数字在纳秒范围内，但最轻微的改进就更好了。

所以我的问题是，当 std::set 可以使用 vector 之类的东西来提高效率时，为什么要使用树结构？

注意:容器平均会被填充1000个元素，并会在应用的整个生命周期中反复迭代，直接影响应用的运行时间。

Answer 1

标准 set 有一些您无法在您的实现中提供的保证:

• 插入/删除不会使其他迭代器/引用/指针无效。
• 插入/删除元素(最多)具有对数复杂性，而不是您的实现中的线性复杂性。

如果这些对您来说无关紧要，欢迎您使用排序 vector 和二分查找。该标准提供了 std::sort、std::vector 和 std::binary_search，所以你可以开始了。需要注意的是，每个容器都有特定的用例，没有“一刀切”的容器。

标准还提供了unordered_set，这是一个哈希表。它经常因运行缓慢和导致缓存未命中而受到批评。好吧，如果这会以您认为是瓶颈的方式降低您的性能，请继续使用其他库中的一些其他哈希集实现。如果您相信自己可以做得更好，那就继续吧。许多项目构建自己的容器，这些容器更专门用于该项目。可以更快，使用更少的内存，可以对迭代器失效和/或操作的复杂性提供不同的保证。它们都解决了不同的问题。

---

另一点是分析和基准测试很难。确保你做对了。性能比较通常按比例进行(使用不同数量的输入参数)。选择一个恒定且相对较小的尺寸并不能说明全部情况。