Does `std::set` sort elements in every case?

Question

From cplusplus.com reference it seems that std::set sorts elements.

I need to have sorted strings, but I'm not sure if it will work well on every platform and compiler. Mainly GCC, MinGW, VC.

score 33 · Accepted Answer · answered Aug 04 '12 at 13:51

33

By its definition std::set is a sorted container. Its part of the standard. Having it sorted helps maintain that its a set rather than just an arbitrary collection.

Source: http://www.sgi.com/tech/stl/set.html

answered Aug 04 '12 at 13:51

Daniel A. White

187,200
47
362
445

Why not implement `std::set` in terms of `std::unordered_map`, which has amortized O(1) insertion/look-up? – Andrey Mishchenko Mar 10 '16 at 03:47
5

@AndreyMishchenko, for that you can use `std::unordered_set` :) – santahopar Dec 24 '19 at 22:54

score 15 · Answer 2 · edited Dec 15 '16 at 22:18

15

Actualy std::set and std::map are not really sorted. Both of these containers are implemented as a red-black trees. So when you iterate such kind of containers, iterator walks through the tree in such way that it looks like that container is sorted. At first it visits the most left node then the parent of the most left one and so on...

edited Dec 15 '16 at 22:18

Adrian J. Moreno

14,350
1
37
44

answered Aug 04 '12 at 23:49

Sergey Vystoropskyi

453
4
11

1

Wording wise, http://en.cppreference.com/w/cpp/container/map says: "std::map is a sorted associative container" – Manohar Reddy Poreddy Oct 27 '17 at 03:01

score 6 · Answer 3 · edited Mar 06 '20 at 08:13

6

Yes, std::set stores its elements in such a way that iterating over the elements will be done in sorted order (and the call to std::adjacent_find is to show that std::set stores unique items as well).

#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

edited Mar 06 '20 at 08:13

boblicious

3,901
1
25
22

answered Aug 04 '12 at 14:00

TemplateRex

69,038
19
164
304

I really don't care about the question or answers, but I just learned a new awesome c++11 syntax, so this is a great answer! – Mazyod Aug 08 '13 at 23:46
@Mazyod Glad you liked it! I updated the answer to the way I would write it now (using some other C++11 features): auto + initializer-list, non-member `begin()`/`end()`, and `copy` to an `ostream_iterator` instead of `for_each` and a lambda. – TemplateRex Aug 09 '13 at 06:41

score 2 · Answer 4 · edited May 23 '17 at 12:18

C++11 N3337 standard draft 23.2.4 "Associative containers":

1 Associative containers provide fast retrieval of data based on keys. The library provides four basic kinds of associative containers: set, multiset, map and multimap.

and:

10 The fundamental property of iterators of associative containers is that they iterate through the containers in the non-descending order of keys where non-descending is defined by the comparison that was used to construct them.

so yes, order is guaranteed, which as https://stackoverflow.com/a/11812871/895245 mentioned basically requires a balanced search tree implementation.

Also contrast with C++11 unordered_set, which may provide better performance since it has less restrictions: Why on earth would anyone use set instead of unordered_set? e.g. using a hash set.

Does `std::set` sort elements in every case?

4 Answers4