15.6. 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 must also be sorted. Like std::vector, a set is a generic class and declarations must include the object type stored in the class:

#include <set>

std::set<int> x {2,7,1,8,2,8,1,8,2,8,4,5,9};

What will be stored in x after initialization?

Show

The two defining characteristics of a set are:

  • A set is sorted.

  • A set may contain only unique values.

Defining a set with non-unique values is not an error. The new object simply replaces the old.

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

Like the sequence containers, each element in a set can be visited one at a time using a range-for loop.

 1#include <iostream>
 2#include <set>
 3
 4int main()
 5{
 6  std::set<int> x {2,7,1,8,4,5,9};
 7
 8  for (const auto& i: x) {
 9    std::cout << i << ' ';
10  }
11
12  return 0;
13}

Because set does not provide operator[], traditional for loops using an index are not possible:

std::set<int> x {2,7,1,8,4,5,9};

for (int i=0; i < x.size(); ++i) {  // OK
    std::cout << x[i] << ' ';         // compile error
}

Sets of any type can be created as long as the type is comparable. The comparison operator (comparator) used in sets by default is operator <. Any type used in a set should overload operator <. All of the types are comparable.

Use set::insert to add a new element to a set or replace an existing element:

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

Because a set is not an indexed container, every 'get' is a search:

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

The set::find function returns an iterator to the element with a specific key:

std::set<int> x {2,7,1,8,4,5,9};
auto it = x.find(8);
std::cout << *it;         // print the value returned from find()

The set::erase function is used to remove an element from a set. set::erase takes an iterator as the position in the set to remove:

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

it = x.find(8);
assert ( it == x.end() );  // this should be true

15.6.1. Variations on std::set

The STL provides 3 alternate forms of std::set class:

multiset

A set in which duplicate keys are allowed.

unordered_set

A set of unique objects stored based on the object hash function. Added in C++11.

In order to use a type in an unordered container, the type must override 3 functions:

  • override std::hash

  • override operator==

  • override operator<

before the type will compile when added to an unordered container.

unordered_multiset

An unordered_set in which duplicate keys are allowed.

More to Explore