Does `std :: set` use sorting elements in each case?

Question

From cplusplus.com the link seems like std::set sorting the elements.

I need to sort the lines, but I'm not sure if this will work well on every platform and compiler. Mostly GCC, MinGW, VC.

Answer 1

By its definition, std::set is a sorted container. Its part of the standard. Sorting sorting helps maintain its set, not just an arbitrary collection.

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

Answer 2

Actualy std :: set and std :: map are not actually sorted. Both of these containers are implemented as red-black trees . Therefore, when you repeat such containers, the iterator goes through the tree in such a way that it looks like this container is sorted. First he visits the leftmost node, then the parent list of the leftmost, etc ...

Answer 3

Yes, std::set stores its elements in such a way that iteration on the elements will be performed in sorted order (and a call to std::adjacent_find should show that std::set also stores unique elements).

 #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

Answer 4

C ++ 11 Standard project N3337 23.2.4 "Associative containers":

1 Associative containers provide fast key-based data retrieval. The library provides four main types of associative containers: multitude, multiset, map, and multimail.

and

10 The main property of associative containers iterators is that they iterate through the containers in non-decreasing order of keys, where the non-descending is determined by the comparison that was used to build them.

so yes, order will be guaranteed, which, as stated in https://stackoverflow.com/a/12863/ ... , requires a balanced implementation of the search tree.

Also contrasts with C ++ 11 unordered_set , which can provide better performance as it has fewer restrictions: Why don't you use set instead of unordered_set? for example using a hash set.