Ordered Set

c++17 containers intermediate

Related: Ordered Map

std::set is a container that maintains its keys in sorted order at all times. Generally std::set is implemented as a tree of keys, and not a hash set. This means when iterating the keys of a std::set the order will always be known but that insertion or lookup (search) is slower than std::unordered_set.

#include <set>
#include <string>
#include <iostream>

int main() {
  std::set<std::string> tags{
    {"wild"},
    {"funny"},
    {"outgoing"},
    {"bashful"},
  };

  for (const auto& tag : tags) {
    std::cout << tag << "\n";
  }
}

bashful
funny
outgoing
wild

Changing the Sort Order of std::set

By default std::set uses the comparator function object std::less<Key> to determine the sort order of its keys. This means if “a” is less than “b” (a < b) then “a” sorts before “b”. The std library also provides std::greater<Key> for a convenient way to reverse the default sort order.

To change the sort order of std::set you provide a second template parameter which is a sort function object. The sort function object should implement a function call operator(()) that takes two const Key& elements and returns true if the first argument sorts before the second argument. That means the sort function’s signature is usually bool operator()(const Key& a, const Key& b) const where Key is the type of the keys in your set. Here’s an example of a custom sort function:

#include <set>
#include <string>
#include <iostream>

using std::string;

struct ShorterString {
  bool operator()(const string& a, const string& b) const {
    return a.size() <= b.size();
  }
};

int main() {
  std::set<string, ShorterString> tags{
    {"wild"},
    {"funny"},
    {"outgoing"},
    {"bashful"},
  };

  for (const auto& tag : tags) {
    std::cout << tag << "\n";
  }
}

wild
funny
bashful
outgoing