18

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

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

4

4 回答 4

31

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

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

于 2012-08-04T13:51:50.227 回答
14

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

于 2012-08-04T23:49:20.547 回答
6

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

现场示例

于 2012-08-04T14:00:08.163 回答
2

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?例如使用哈希集。

于 2017-01-02T10:07:23.247 回答