Skip to content
  • set & multiset · C++

set & multiset

LearnViaNotes @learnvianotes· 2 min read

std::set keeps unique keys in sorted order (a balanced binary search tree); std::multiset allows duplicates. Everything is O(log n).

std::set

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

int main() {
    std::set<int> s{5, 1, 4, 1, 3};              // duplicates dropped, sorted
    for (int x : s) std::cout << x << ' ';
    std::cout << '\n';

    auto [it, inserted] = s.insert(4);            // already there
    std::cout << inserted << ' ' << *it << '\n';
    std::cout << s.count(3) << s.contains(9) << '\n';   // contains: C++20
    s.erase(1);
    std::cout << *s.begin() << ' ' << *s.rbegin() << ' ' << s.size() << '\n';   // min, max

    std::cout << *s.lower_bound(4) << ' ' << *s.upper_bound(4) << '\n';   // first >= 4, first > 4
}
Output
1 3 4 5
0 4
10
3 5 3
4 5

Custom order

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

struct ByLength {
    bool operator()(const std::string& a, const std::string& b) const {
        return a.size() != b.size() ? a.size() < b.size() : a < b;   // tie-break so distinct words stay distinct
    }
};

int main() {
    std::set<int, std::greater<int>> desc{3, 1, 2};
    for (int x : desc) std::cout << x;
    std::cout << '\n';
    std::set<std::string, ByLength> words{"banana", "fig", "apple", "kiwi", "pear"};
    for (const auto& w : words) std::cout << w << ' ';
    std::cout << '\n';
}
Output
321
fig kiwi pear apple banana

std::multiset

C++
#include <iostream>
#include <set>
int main() {
    std::multiset<int> ms{3, 1, 3, 2, 3};
    std::cout << ms.count(3) << ' ' << ms.size() << '\n';
    ms.erase(ms.find(3));           // erase ONE copy
    std::cout << ms.count(3) << '\n';
    ms.erase(3);                    // erase ALL copies
    for (int x : ms) std::cout << x;
    std::cout << '\n';
}
Output
3 5
2
12

How is std::set implemented and what are its complexities?

Free for students and teachers

Write notes like this one

Cards for every idea, quizzes and flashcards, read aloud — on the web and your phone.

Something wrong with this note? Open it to report