std :: set迭代顺序是否总是根据C++规范提升？

Question

在这里http://www.cplusplus.com/reference/stl/set/我读到用C++中的std :: set"通常"实现为树(红黑色？)并对其进行排序.

我无法理解,这是否意味着通过规范迭代的顺序总是提升？或者它只是"通常的实现细节",有时,某些库/编译器可能违反此约定？

Answer 1

根据C++标准,std::set按照std::less由可选比较谓词模板参数确定的排序顺序迭代元素.

(同样根据C++标准,插入,查找和删除最多需要O(lg n)时间,因此平衡搜索树目前是唯一可行的实现选择std::set,即使标准没有强制要求使用红黑树.)

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 constructor.

Answer 3

根据规范，集合的迭代顺序始终是升序

是的，如果按顺序打印出来，set 的值总是升序的。正如描述所述，它通常使用红黑树（RBT）来实现，但编译器编写者可以选择违反这一点，但通常会坚持 RBT 主题，因为任何其他实现都不会资源有效地实现的任务set。

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 而不是 hashmap：What is theunderlying data Structure of a STL set in C++?

将此与 C++11 进行对比unordered_set，后者往往通过哈希图实现提供更好的性能，但代价是受到更多限制（没有自由排序遍历），如下所示：

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