Skip to content
Laviyx Learn

Try

C++ course menu

C++ std::set: Sorted Unique Values, Lookups and Set Operations

Learn std::set in C++: storing unique values in sorted order, insert and erase, find and contains, lower_bound and upper_bound, removing duplicates from a vector, set union and intersection, custom ordering, and multiset.

Intermediate11 min readUpdated
On this page

A std::set (from <set>) stores unique values in sorted order. Adding a value that is already present does nothing. Like std::map, it is a balanced tree, so insert, erase and find take O(log n) time. Think of a set as a map with keys but no values.

Creating and using a set#

C++
#include <iostream>
#include <set>

int main() {
    std::set<int> numbers = {5, 1, 4, 1, 5, 9};

    numbers.insert(3);
    numbers.insert(4);   // already present: ignored

    for (int n : numbers) std::cout << n << ' ';
    std::cout << "\nsize: " << numbers.size() << '\n';
}
Output
1 3 4 5 9
size: 5

Duplicates disappear and the values come out sorted, whatever the insertion order.

Checking membership and erasing#

C++
#include <iostream>
#include <set>
#include <string>

int main() {
    std::set<std::string> enrolled = {"Asha", "Ravi", "Meera"};

    std::cout << std::boolalpha;
    std::cout << enrolled.contains("Ravi") << ' ' << enrolled.contains("John") << '\n';  // C++20

    enrolled.erase("Ravi");
    auto [it, added] = enrolled.insert("John");
    std::cout << added << ' ' << *it << '\n';

    for (const auto& name : enrolled) std::cout << name << ' ';
    std::cout << '\n';
}
Output
true false
true John
Asha John Meera

Before C++20, write enrolled.count("Ravi") > 0 or enrolled.find("Ravi") != enrolled.end().

Removing duplicates from a vector#

Building a set from a vector removes duplicates and sorts in one step:

C++
#include <iostream>
#include <set>
#include <vector>

int main() {
    std::vector<int> visits = {7, 3, 7, 1, 3, 9, 1};

    std::set<int> unique(visits.begin(), visits.end());
    std::vector<int> result(unique.begin(), unique.end());

    for (int x : result) std::cout << x << ' ';
    std::cout << '\n';
}
Output
1 3 7 9

If you need to keep the original order instead, track seen values in a set while building a new vector.

Ordered queries: lower_bound and upper_bound#

Because the values are sorted, a set can answer "the smallest value at least X" quickly:

C++
#include <iostream>
#include <set>

int main() {
    std::set<int> slots = {9, 11, 14, 16};   // free appointment hours

    int wanted = 12;
    auto it = slots.lower_bound(wanted);     // first slot >= 12
    if (it != slots.end()) {
        std::cout << "Next free slot at " << *it << ":00\n";
    }

    std::cout << "Slots before noon: ";
    for (auto i = slots.begin(); i != slots.lower_bound(12); ++i) {
        std::cout << *i << ' ';
    }
    std::cout << '\n';

    std::cout << "Earliest " << *slots.begin() << ", latest " << *slots.rbegin() << '\n';
}
Output
Next free slot at 14:00
Slots before noon: 9 11
Earliest 9, latest 16

lower_bound(x) gives the first element >= x, and upper_bound(x) the first element > x. The smallest element is *s.begin() and the largest is *s.rbegin().

Set operations#

<algorithm> provides union, intersection and difference for sorted ranges, which sets always are:

C++
#include <algorithm>
#include <iostream>
#include <iterator>
#include <set>
#include <string>

void print(const std::set<std::string>& s) {
    for (const auto& x : s) std::cout << x << ' ';
    std::cout << '\n';
}

int main() {
    std::set<std::string> chess = {"Asha", "John", "Meera", "Ravi"};
    std::set<std::string> music = {"John", "Kiran", "Meera", "Priya"};

    std::set<std::string> both;
    std::set_intersection(chess.begin(), chess.end(), music.begin(), music.end(),
                          std::inserter(both, both.begin()));

    std::set<std::string> either;
    std::set_union(chess.begin(), chess.end(), music.begin(), music.end(),
                   std::inserter(either, either.begin()));

    std::set<std::string> only_chess;
    std::set_difference(chess.begin(), chess.end(), music.begin(), music.end(),
                        std::inserter(only_chess, only_chess.begin()));

    print(both);
    print(either);
    print(only_chess);
}
Output
John Meera
Asha John Kiran Meera Priya Ravi
Asha Ravi

std::inserter creates an iterator that calls insert on the destination set for each result.

Custom order#

Pass a comparator to change the order. Descending order uses std::greater; you can also sort by any rule with a custom comparator:

C++
#include <functional>
#include <iostream>
#include <set>
#include <string>

struct ByLength {
    bool operator()(const std::string& a, const std::string& b) const {
        if (a.size() != b.size()) return a.size() < b.size();
        return a < b;   // tie-break so different words of equal length are both kept
    }
};

int main() {
    std::set<int, std::greater<int>> desc = {3, 9, 1};
    for (int x : desc) std::cout << x << ' ';
    std::cout << '\n';

    std::set<std::string, ByLength> words = {"banana", "fig", "apple", "kiwi", "date"};
    for (const auto& w : words) std::cout << w << ' ';
    std::cout << '\n';
}
Output
9 3 1
fig date kiwi apple banana

A set treats two values as equal when neither is "less" than the other according to its comparator. Without the tie-break, "kiwi" and "date" (both length 4) would count as duplicates and one would be dropped.

multiset#

A std::multiset keeps duplicates, still sorted. count(x) tells how many copies there are, and erase(x) removes all of them (erase one copy with erase(s.find(x))):

C++
#include <iostream>
#include <set>

int main() {
    std::multiset<int> scores = {70, 85, 70, 90, 70};
    std::cout << scores.count(70) << '\n';

    scores.erase(scores.find(70));   // remove just one 70
    for (int s : scores) std::cout << s << ' ';
    std::cout << '\n';
}
Output
3
70 70 85 90

set or unordered_set?#

Use std::set when you need sorted values, the smallest/largest, or lower_bound queries. Use std::unordered_set when you only need fast "is it there?" checks; see unordered_set.

Common mistakes#

Practice#

Practice exercise

Given the text "the quick brown fox jumps over the lazy dog the end", print the distinct words in alphabetical order, and how many distinct words there are.

Show solution
C++
#include <iostream>
#include <set>
#include <sstream>
#include <string>

int main() {
    std::istringstream in("the quick brown fox jumps over the lazy dog the end");
    std::set<std::string> words;
    std::string w;
    while (in >> w) words.insert(w);

    for (const auto& word : words) std::cout << word << ' ';
    std::cout << '\n' << words.size() << " distinct words\n";
}
Output
brown dog end fox jumps lazy over quick the
9 distinct words

Key takeaway#

Finished this lesson?

Related lessons

C++C++ std::map: Key-Value Pairs, Lookup, Insert, Erase and IterationLearn std::map in C++: creating maps, inserting and updating with [], insert and insert_or_assign, safe lookups with find, contains and at, erasing, iterating in sorted key order with structured bindings, custom ordering, and multimap.Intermediate13 min readC++C++ unordered_map and unordered_set: Hash Tables for Fast LookupLearn std::unordered_map and std::unordered_set: O(1) average lookups with hashing, inserting, finding and erasing, counting frequencies, detecting duplicates, the two-sum problem, hashing your own types, and when to choose them over map and set.Intermediate11 min readC++C++ STL Algorithms: sort, find, count, accumulate, transform and MoreLearn the most useful C++ <algorithm> and <numeric> functions: sort with custom comparators, stable_sort, find and find_if, count_if, any_of/all_of, min_element and max_element, accumulate, transform, remove_if with erase, binary_search, reverse, unique, and C++20 ranges.Intermediate14 min read