C++ STL设置实现

Question

为什么C++集实现为二叉树而不是哈希集,与二叉树提供的O(log n)相比,它可以提供O(1)的平均大小写复杂度？

Answer 1

因为C++集是由T比较运算符排序的,这使得以可预测的方式迭代成员成为可能.如果您知道您将对该集合执行的操作是插入,测试成员资格和/或删除元素,那么std::unordered_set实现哈希集的原因就是C++ 11.

Answer 2

据John Nagle所说,从2006年发布到comp.lang.c ++.主持:

实际的原因是编写规范的哈希表部分的人没有及时完成它.就这样.

标准化过程就是这样.