set and multiset in C++ STL

A std::set keeps unique values in sorted order and finds, inserts and removes any of them in O(log n). That makes it perfect for "have I seen this before?", "what's the smallest value above x?" and keeping a sorted collection that changes – questions that come up constantly in DSA problems.

The basics

#include <iostream>
#include <set>

int main() {
    std::set<int> s{50, 20, 40, 20, 10};         // duplicates are ignored, values sorted
    s.insert(30);
    auto [it, inserted] = s.insert(40);           // insert returns {iterator, was it new?}
    std::cout << "40 inserted again? " << std::boolalpha << inserted << '\n';

    for (int x : s) std::cout << x << ' ';        // always in sorted order
    std::cout << "| size " << s.size() << '\n';

    std::cout << "has 30? " << s.contains(30) << ", has 35? " << s.contains(35) << '\n';   // C++20
    s.erase(20);
    std::cout << "smallest " << *s.begin() << ", largest " << *s.rbegin() << '\n';
    return 0;
}

40 inserted again? false
10 20 30 40 50 | size 5
has 30? true, has 35? false
smallest 10, largest 50

Because the tree stays balanced, its height is about log₂ n, so every operation is O(log n) – about 20 steps for a million elements. Iterating visits the values in sorted order.

lower_bound and upper_bound

#include <iostream>
#include <set>

int main() {
    std::set<int> prices{99, 149, 299, 499, 999};

    auto a = prices.lower_bound(300);        // first value >= 300
    auto b = prices.upper_bound(499);        // first value > 499
    std::cout << "first >= 300: " << *a << ", first > 499: " << *b << '\n';

    auto c = prices.lower_bound(250);
    if (c != prices.begin()) std::cout << "largest below 250: " << *std::prev(c) << '\n';

    if (prices.lower_bound(2000) == prices.end()) std::cout << "nothing costs 2000 or more\n";

    int count = 0;                           // values in the range [100, 500]
    for (auto it = prices.lower_bound(100); it != prices.upper_bound(500); ++it) count++;
    std::cout << count << " prices between 100 and 500\n";
    return 0;
}

first >= 300: 499, first > 499: 999
largest below 250: 149
nothing costs 2000 or more
3 prices between 100 and 500

Custom ordering

#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;   // length, then alphabetical
    }
};

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

    std::set<std::string, ByLength> words{"stack", "map", "set", "vector", "queue"};
    for (const auto& w : words) std::cout << w << ' ';
    std::cout << '\n';
    return 0;
}

9 7 3 1 
map set queue stack vector 

The set treats two values as the same when neither comes before the other. With a comparator that only compared length, "map" and "set" would be "equal" and one would be dropped – so always break ties.

multiset: sorted with duplicates

#include <iostream>
#include <set>

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

    scores.erase(scores.find(70));          // erase ONE 70
    std::cout << "after erasing one: " << scores.count(70) << '\n';
    scores.erase(85);                       // erase ALL 85s
    for (int s : scores) std::cout << s << ' ';
    std::cout << '\n';
    std::cout << "median-ish: " << *std::next(scores.begin(), scores.size() / 2) << '\n';
    return 0;
}

70 appears 3 times
after erasing one: 2
70 70 90 
median-ish: 70

Practice

Summary