15.5. The set class

A set refers to any data structure in which every member of the set is unique. The integers define a set, because every number is unique. The values {3, 1, 4, 1, 5, 9} do not define a proper set, because the value 1 is repeated.

In C++, a std::set keeps its elements ordered according to its comparison object. By default, that comparison uses operator<. Like std::vector, a set is a generic class and declarations must include the object type stored in the class:

#include <iostream>
#include <set>

std::set<int> sample_set() {
  return {2, 7, 1, 8, 4, 5, 9};
}

The following example initializes a set with values and prints the set. Without running the code first, what do you think will be stored in x after initialization?

Answer

The two defining characteristics of a set are:

• A set is sorted.

• A set may contain only unique values.

Defining a set with repeated values is not an error. Equivalent values after the first are ignored.

When initialized, x will contain: 1 2 4 5 7 8 9

#include <iostream>
#include <set>

int main() {
  std::set<int> x {2, 7, 1, 8, 2, 8, 1, 8, 2, 8, 4, 5, 9};
  for (const auto value : x) {
    std::cout << value << ' ';
  }
  std::cout << '\n';
}

Like the sequence containers, each element in a set can be visited one at a time using a range-for loop. The preceding complete example uses that loop to display the sorted values.

Because set does not provide operator[], an index-based loop is not the appropriate way to visit its elements. Use a range-for loop or an iterator instead.

Sets can contain any key type for which the set's comparison object defines a strict weak ordering. The default comparison object uses operator<, but a caller can provide a different comparator instead. The key type does not have to overload operator< when a custom comparator is provided.

For example, this complete program stores the values in descending order:

struct descending {
  bool operator()(int lhs, int rhs) const {
    return lhs > rhs;
  }
};

int main() {
  std::set<int, descending> x {2, 7, 1, 8, 4, 5, 9};
  for (const auto value : x) {
    std::cout << value << ' ';
  }
  std::cout << '\n';
}

The keys in a std::set are treated as constant while they are in the container. Changing a key through an iterator could violate the ordering invariant, so dereferencing a set iterator produces a const reference.

For an ordered set, search, insertion, and erasure take \(O(\log N)\) time. The container uses \(O(N)\) storage. Unordered containers have average constant-time lookup, insertion, and erasure, but their worst-case time is \(O(N)\).

Use set::insert to add a new element to a set. The function returns a pair containing an iterator to the equivalent element and a Boolean that is true only when a new element was inserted.

#include <iostream>
#include <set>

int main() {
  auto x = std::set<int> {2, 7, 1, 8, 4, 5, 9};
  auto inserted = x.insert(6);
  auto duplicate = x.insert(8);

  std::cout << std::boolalpha
            << "inserted 6: " << inserted.second << '\n'
            << "value at returned position: " << *inserted.first << '\n'
            << "inserted duplicate 8: " << duplicate.second << '\n';
}

Because a set is not an indexed container, looking up a value is a search. The set::find function returns an iterator to the element with a specific key, or end() when the key is absent:

#include <iostream>
#include <set>

int main() {
  auto x = std::set<int> {2, 7, 1, 8, 4, 5, 9};
  const auto it = x.find(8);
  if (it != x.end()) {
    std::cout << "found: " << *it << '\n';
  }
}

C++20 Feature

C++20 added set::contains for membership checks. It returns a Boolean and avoids creating an iterator when the position is not needed.

#include <iostream>
#include <set>

int main() {
  const auto x = std::set<int> {2, 7, 1, 8, 4, 5, 9};
  std::cout << std::boolalpha
            << x.contains(8) << ' '
            << x.contains(3) << '\n';
}

The set::erase function removes an element from a set. When given an iterator, it removes the element at that position and does not invalidate iterators to other elements:

#include <iostream>
#include <set>

int main() {
  auto x = std::set<int> {2, 7, 1, 8, 4, 5, 9};
  const auto it = x.find(8);
  if (it != x.end()) {
    x.erase(it);
  }

  std::cout << std::boolalpha
            << (x.find(8) == x.end()) << '\n';
}

C++20 Feature

C++20 also provides std::erase_if for removing every element that satisfies a predicate. This is useful when the value to remove is described by a condition rather than a single key.

#include <iostream>
#include <set>

int main() {
  auto x = std::set<int> {2, 7, 1, 8, 4, 5, 9};
  std::erase_if(x, [](int value) { return value % 2 == 0; });

  for (const auto value : x) {
    std::cout << value << ' ';
  }
  std::cout << '\n';
}

15.5.1. Variations on std::set

The standard library provides related ordered and unordered containers:

multiset

A set in which duplicate keys are allowed.

unordered_set

A container of unique objects organized by a hash function, not by sorted order. Added in C++11.

A key type needs a hash function and an equality predicate. The standard library provides these for many built-in and library types. For a user type, provide a std::hash<Key> specialization or a custom hash object, and provide equality through operator== or a custom equality object.

unordered_multiset

An unordered_set in which duplicate keys are allowed.

---

More to Explore

• Standard library containers

• std::set

• std::unordered_set