🎓 A1Learner
🔍
0 of 34 lessons completed

C++ Sets

A set is a collection that stores unique values in sorted order. This lesson inserts and searches values in a set, and builds new sets from two sets.

Sorted and unique

Three values go into the set out of order, and a fourth insert repeats a value. The size stays at 3, and the values print in sorted order.

#include <iostream>
#include <set>

int main() {
  std::set<int> numbers;
  numbers.insert(30);
  numbers.insert(10);
  numbers.insert(20);
  std::cout << "Size: " << numbers.size() << "\n";
  numbers.insert(10);
  std::cout << "Size after duplicate: " << numbers.size() << "\n";
  for (int number : numbers) {
    std::cout << number << "\n";
  }
  return 0;
}

count and find answer membership

count answers 1 for a stored name and 0 for a missing name. find then locates Mina, and the program prints the value at that position.

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

int main() {
  std::set<std::string> names;
  names.insert("Ana");
  names.insert("Bo");
  names.insert("Mina");
  std::cout << "Bo: " << names.count("Bo") << "\n";
  std::cout << "Zoe: " << names.count("Zoe") << "\n";
  auto found = names.find("Mina");
  if (found != names.end()) {
    std::cout << "Found: " << *found << "\n";
  }
  return 0;
}

Union and intersection

The union starts as a copy of the first set and gains every value from the second set. The intersection keeps a value only when the second set holds it too.

#include <iostream>
#include <set>

int main() {
  std::set<int> first = {1, 3, 5, 7};
  std::set<int> second = {3, 4, 5, 6};
  std::set<int> all = first;
  for (int value : second) {
    all.insert(value);
  }
  std::set<int> both;
  for (int value : first) {
    if (second.count(value) == 1) {
      both.insert(value);
    }
  }
  std::cout << "Union:" << "\n";
  for (int value : all) {
    std::cout << value << "\n";
  }
  std::cout << "Intersection:" << "\n";
  for (int value : both) {
    std::cout << value << "\n";
  }
  return 0;
}

Example

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

int main() {
  std::set<std::string> guests;
  guests.insert("Mina");
  guests.insert("Ana");
  guests.insert("Theo");
  guests.insert("Ana");
  guests.insert("Bo");
  std::cout << "Guests: " << guests.size() << "\n";
  for (std::string guest : guests) {
    std::cout << guest << "\n";
  }
  return 0;
}

Key points

  • A set stores each value at most once.
  • A set keeps its values in sorted order.
  • Inserting a value that is already present leaves the set unchanged.
  • count gives 1 when a value is present and 0 when a value is absent.
  • find gives a position for a value, or the end position when the value is absent.
  • A union holds every value from two sets, with each value stored once.
  • An intersection holds only the values that sit in both sets.

In this example, five names are inserted into the guest set and one name appears twice. The set keeps four unique guests. The names print in sorted order, Ana first and Theo last.

Note

The <set> header gives a program the std::set type.

Try it Yourself

Edit the code, then press Run.

Running is simulated

Exercise

A set holds 10, 20, and 30. What happens when the program inserts 20 again?