c++ - `std::set` 在每种情况下都会对元素进行排序吗？

Question

从cplusplus.com参考看来，它似乎对std::set元素进行了排序。

我需要对字符串进行排序，但我不确定它是否能在每个平台和编译器上正常工作。主要是GCC、MinGW、VC。

Answer 1

根据它的定义std::set是一个排序的容器。它是标准的一部分。对其进行排序有助于保持它是一个集合，而不仅仅是一个任意集合。

来源：http ://www.sgi.com/tech/stl/set.html

Answer 2

实际上 std::set 和 std::map 并没有真正排序。这两个容器都实现为红黑树。因此，当您迭代此类容器时，迭代器会以看起来该容器已排序的方式遍历树。首先它访问最左边的节点，然后是最左边的父节点，依此类推......

Answer 3

是的，std::set以这样一种方式存储它的元素，即迭代元素将按排序顺序完成（并且调用std::adjacent_find是为了显示std::set存储唯一项目）。

#include <algorithm>
#include <iterator>
#include <ios>
#include <iostream>
#include <set>
#include <string>

int main()
{
    auto const ss = std::set<std::string> { "foo", "bar", "test" };
    std::cout << std::boolalpha << std::is_sorted(begin(ss), end(ss)) << "\n";
    std::cout << std::boolalpha << (std::adjacent_find(begin(ss), end(ss)) == end(ss)) << "\n";
    std::copy(begin(ss), end(ss), std::ostream_iterator<std::string>(std::cout, "\n"));
}

现场示例

Answer 4

C++11 N3337 标准草案 23.2.4“关联容器”：

1 关联容器提供基于键的数据快速检索。该库提供四种基本类型的关联容器：set、multiset、map 和 multimap。

和：

10 关联容器迭代器的基本特性是它们以键的非降序遍历容器，其中非降序由用于构造它们的比较定义。

所以是的，顺序是有保证的，正如https://stackoverflow.com/a/11812871/895245提到的，基本上需要一个平衡的搜索树实现。

还与 C++11 形成对比unordered_set，后者可能会提供更好的性能，因为它的限制较少：为什么会有人使用 set 而不是 unordered_set？例如使用哈希集。