C++ set and multiset

A set is a bag of unique items kept in sorted order, like a collection of different stickers lined up. A multiset also allows repeats.

In this page:

What is a set?
Inserting and Erasing
set vs multiset
Iterating over a set
Searching a set

Syntax

cpp

#include <set>

std::set<data_type> set_name = {value1, value2};
set_name.insert(value);
set_name.erase(value);

What is a set?

std::set stores unique elements in sorted order, implemented as a balanced binary search tree. It is useful when you need a collection with no duplicates and fast ordered lookups, in O(log n) time.

Example: What is a set?

cpp

// Include std::cout and std::cin
#include <iostream>
// Include std::set
#include <set>

// Program execution starts in main()
int main() {
	std::set<int> nums = {3, 1, 2};
	for (int n : nums) std::cout << n << " ";
	// Print to the console with cout
	std::cout << std::endl;
	// Return 0 to signal that the program finished successfully
	return 0;
}

Inserting and Erasing

insert() adds an element and returns a pair indicating whether it was newly inserted. erase() removes an element by value or by iterator.

Because a set enforces uniqueness automatically, inserting a duplicate value simply does nothing and leaves the set unchanged.

Example: Inserting and Erasing

cpp

// Include std::cout and std::cin
#include <iostream>
// Include std::set
#include <set>

// Program execution starts in main()
int main() {
	std::set<int> nums;
	nums.insert(5);
	nums.insert(5);
	nums.erase(5);
	// Print to the console with cout
	std::cout << nums.size() << std::endl;
	// Return 0 to signal that the program finished successfully
	return 0;
}

set vs multiset

std::set silently ignores duplicate inserts. std::multiset allows multiple equal elements, all stored in sorted order, useful for keeping a sorted collection with repeats (e.g. sorted scores).

Example: set vs multiset

cpp

// Include std::cout and std::cin
#include <iostream>
// Include std::set
#include <set>

// Program execution starts in main()
int main() {
	std::set<int> s;
	s.insert(5);
	s.insert(5);
	std::multiset<int> ms;
	ms.insert(5);
	ms.insert(5);
	// Print to the console with cout
	std::cout << s.size() << " " << ms.size() << std::endl;
	// Return 0 to signal that the program finished successfully
	return 0;
}

Iterating over a set

Iterating a set visits elements in ascending sorted order automatically, without needing an explicit sort step. This ordering guarantee is what distinguishes std::set from std::unordered_set, which offers no such guarantee.

Example: Iterating over a set

cpp

// Include std::cout and std::cin
#include <iostream>
// Include std::set
#include <set>

// Program execution starts in main()
int main() {
	std::set<int> nums = {5, 1, 3};
	for (int n : nums) std::cout << n << " ";
	// Print to the console with cout
	std::cout << std::endl;
	// Return 0 to signal that the program finished successfully
	return 0;
}

Searching a set

find() returns an iterator to the element or end() if missing. count() returns 0 or 1 for a set (or the number of matches for a multiset). Both run in O(log n).

Since count() can only ever return 0 or 1 for a plain set, many developers prefer find() for clearer, non-boolean-looking intent.

Example: Searching a set

cpp

// Include std::cout and std::cin
#include <iostream>
// Include std::set
#include <set>

// Program execution starts in main()
int main() {
	std::set<int> nums = {1, 2, 3};
	// Declare it and set it to nums.find(2)
	auto it = nums.find(2);
	// Print to the console with cout
	std::cout << (it != nums.end()) << " " << nums.count(2) << std::endl;
	// Return 0 to signal that the program finished successfully
	return 0;
}

Chapter Quiz — Complete all 15 topics to unlock

0/15 topics done

Complete these topics first:

← Previous Lesson C++ unordered_map Next Lesson → C++ unordered_set