根据C++规范，std::set的迭代顺序是否总是按升序排列？

Question

我在这里阅读到：http://www.cplusplus.com/reference/stl/set/ C++中的std::set通常被实现为一棵树（红黑树？）并且它是有序的。

我理解不了，这是否意味着根据规范，set的迭代顺序始终是升序？还是说这只是“常见实现细节”，有时候某些库/编译器可能会违反这种约定？

- Rodion Gorkovenko

---

你也可以将这些数字的负数存储在集合中，这样一来，当你访问元素时就可以撤销负数。所以基本上是按降序排列。 - Tilak Madichetti

Answer 1

根据C++标准，对于std::set中的元素进行迭代遍历时，其顺序是按照 std::less 或可选比较谓词模板参数所确定的排序方式进行的。

（同样根据C++标准，插入、查找和删除操作最多需要O(log n)的时间，因此平衡搜索树目前是实现std::set的唯一可行选择，尽管标准并不要求使用红黑树实现。）

- Fred Foo

---

即使对于足够小的集合，复杂度是无意义的，迭代器的稳定性也意味着使用索引到排序数组中是不可能起作用的。 - curiousguy

Answer 2

这意味着在内部，std::set将其元素存储为排序树。然而，规范对排序顺序没有任何说明。默认情况下，std::set使用std::less，所以会按照从低到高的顺序排序。但是，您可以使用模板参数使排序函数成为您想要的任何内容：

std::set<valueType, comparissonStruct> myCustomOrderedSet;

例如：

std::set<int, std::greater<int> > myInverseSortedSet;

或者

struct cmpStruct {
  bool operator() (int const & lhs, int const & rhs) const
  {
    return lhs > rhs;
  }
};

std::set<int, cmpStruct > myInverseSortedSet;

实际上，这些示例也在你提供的网站上提供。更具体地在这里：set构造函数。

- AVH

Answer 3

按照规范，集合的迭代顺序始终是升序

是的，如果按顺序打印出来，集合的值总是升序的。正如描述所说，它通常使用红黑树(RBT)实现，但编译器编写者有违反这一点的选项，但通常会遵循RBT的主题，因为任何其他实现都无法以资源高效的方式完成set任务。

- Shamim Hafiz - MSFT

Answer 4

C++11 N3337标准草案

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3337.pdf

23.2.4“关联容器”表示:

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

并且：

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

因此，C++标准确保有序。

这就是为什么例如gcc 6.4.0将其实现为BST而不是哈希图的原因：C ++中STL set的底层数据结构是什么？

与C++11的unordered_set相比，后者提供更好的性能，使用哈希图实现，但会付出更多的限制（没有自由排序遍历），如下所示：

• C ++中STL set的底层数据结构是什么？
• 为什么有人会使用set而不是unordered_set？例如使用哈希集。

- Ciro Santilli OurBigBook.com

---

问题涉及集合。 - Nikolay Dimitrov

@NikolayDimitrov，但我的回答不是在谈论集合吗？正如第一条引语所示，它们是可关联的容器。 - Ciro Santilli OurBigBook.com

集合按顺序迭代，这是主要的事情。例如，映射不是。 - Nikolay Dimitrov

据我理解和从 https://dev59.com/lmsz5IYBdhLWcg3wy7LU 得知，@NikolayDimitrov，两者似乎都是按顺序迭代的。 - Ciro Santilli OurBigBook.com

是的，抱歉，我指的是unordered_map，它是一个实际的哈希映射。 - Nikolay Dimitrov

Answer 5

默认比较器是less，因此集合将按升序排序。要更改此设置，可以指定另一个现有或自定义比较器作为模板参数。

- Marian Petre