在每种情况下，`std :: set`是否对元素进行排序？

从cplusplus.com参考似乎std::set各种因素。在每种情况下，`std :: set`是否对元素进行排序？

我需要排序的字符串，但我不知道它是否会在每个平台和编译器上正常运行。主要是GCC，MinGW，VC。

来源

2012-08-04 kravemir

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

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

来源

2012-08-04 13:51:50

为什么不'的std :: unordered_map'，已摊销O（1）插入/查找方面实现'的std :: set'？ – 2016-03-10 03:47:52

非常容易阅读关于源，感谢您的链接。 – 2017-05-02 21:39:09

是，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")); 
}

Live Example

来源

2012-08-04 14:00:08 TemplateRex

我真的不关心这个问题或答案，但我刚刚学习了一个新的令人敬畏的C++ 11语法，所以这是一个很好的答案！ – Mazyod 2013-08-08 23:46:31

@Mazyod很高兴你喜欢它！我更新了我现在编写它的方式（使用其他C++ 11功能）的答案：auto + initializer-list，非成员'begin（）'/'end（）'和'copy'到'ostream_iterator'而不是'for_each'和一个lambda。 – TemplateRex 2013-08-09 06:41:54

Actualy的std ::设置和std ::地图是不是真的来分类的。这两个容器均以red-black trees的形式实现。所以，当你迭代这种类型的容器时，迭代器以这样的方式遍历树，看起来像容器被排序。起初，它访问的最左节点，则最左边的父母等等...

来源

2012-08-04 23:49:20

+1好知道:) – kravemir 2012-08-05 09:43:12

措辞明智，http://en.cppreference.com/w/cpp/container/map说：“性病::地图是一个有序关联容器” – 2017-10-27 03:01:08

C++11 N3337 standard draft 23.2.4“关联容器”：

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

和：

10关联容器的迭代器的基本性质是它们通过在键的非递减的次序，其中非下降是由那是比较所限定的容器迭代用于构建它们。

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

也与C++ 11 unordered_set形成对比，其可以提供更好的性能，因为它具有较少的限制：Why on earth would anyone use set instead of unordered_set?例如，使用哈希集。

来源

2017-01-02 10:07:23

在每种情况下，`std :: set`是否对元素进行排序？

回答

相关问题