C++ set: Unique, Sorted Elements with std::set

A Bag of Unique, Sorted Values

You've seen unordered_map store key-value pairs with fast hash-based lookup. A std::set is the simpler cousin: it stores just values - no associated data - and it enforces two rules automatically. Every element is unique (duplicates are silently dropped), and the elements are always kept in sorted order.

That makes set the natural choice for questions like "have I seen this before?" or "give me the distinct items in sorted order." You insert without worrying about duplicates, and you iterate without sorting first.

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s;
    s.insert(40);
    s.insert(10);
    s.insert(30);
    s.insert(10);   // duplicate - ignored

    for (int x : s) cout << x << " ";   // 10 30 40 (sorted, no repeat)
}

Notice we inserted 10 twice and out of order, yet the output is sorted and 10 appears once. The set did the bookkeeping for you.

Inserting and Removing

insert adds a value if it isn't already there. It returns a pair whose .second is a bool telling you whether the insert actually happened - handy when you want to know if a value was new:

#include <iostream>
#include <set>
#include <string>
using namespace std;

int main() {
    set<string> seen;

    for (string word : {"go", "rust", "go", "cpp"}) {
        auto [it, inserted] = seen.insert(word);
        if (inserted)
            cout << "First time seeing: " << word << "\n";
        else
            cout << "Already saw: " << word << "\n";
    }
}

To remove a value, call erase with the value itself - it returns the number of elements removed (0 or 1 for a set). Erasing something that isn't there is harmless, not an error:

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s = {1, 2, 3, 4};

    s.erase(3);          // removes 3
    s.erase(99);         // does nothing, returns 0

    for (int x : s) cout << x << " ";   // 1 2 4
}

Checking Membership

The whole point of a set is fast "is this in here?" tests. The clearest way is count, which returns 1 or 0:

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> primes = {2, 3, 5, 7, 11};

    if (primes.count(7))
        cout << "7 is prime\n";

    if (!primes.count(9))
        cout << "9 is not in the set\n";
}

Since C++20 there's an even more readable option, contains, which returns a bool directly:

if (primes.contains(7)) { /* ... */ }   // C++20

A common mistake is reaching for operator[] the way you would with a map. A set has no operator[] - there's no value to fetch, only presence to test. Use count or contains, not s[7].

If you need the actual position (to erase it, or to look at neighbors), use find, which returns an iterator or end():

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s = {10, 20, 30};

    auto it = s.find(20);
    if (it != s.end()) {
        cout << "found " << *it << "\n";
        s.erase(it);   // erase by iterator - no second lookup
    }
    cout << "size now " << s.size() << "\n";
}

Ordered Iteration and Range Queries

Because a set is sorted, iterating always yields elements smallest-to-largest, and you get ordered-container tricks for free. lower_bound(x) gives the first element not less than x, and upper_bound(x) the first element strictly greater than x - together they let you scan a numeric range without checking every element:

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s = {5, 12, 18, 23, 31, 47};

    // print everything in [12, 31]
    auto begin = s.lower_bound(12);
    auto end = s.upper_bound(31);
    for (auto it = begin; it != end; ++it)
        cout << *it << " ";   // 12 18 23 31
}

A subtle but important rule: set elements are immutable. The iterator hands you a const reference, so you can't change an element in place - doing so could break the sort order the container relies on. To "change" a value, erase the old one and insert the new one.

By default the ordering is ascending (std::less). For descending order, supply a different comparator as the second template argument:

#include <iostream>
#include <functional>
#include <set>
using namespace std;

int main() {
    set<int, greater<int>> s = {5, 12, 18, 23};

    for (int x : s) cout << x << " ";   // 23 18 12 5
}

set vs multiset vs unordered_set

std::set is one of three close relatives, and picking the right one matters:

set<int>            // unique values, sorted, O(log n)
multiset<int>       // allows duplicates, sorted, O(log n)
unordered_set<int>  // unique values, NO order, average O(1)

Reach for unordered_set when you only need membership tests and don't care about order - its hash-based lookups are faster on average than the set's tree-based O(log n). Choose set when you need elements in sorted order, range queries with lower_bound/upper_bound, or stable iterator behavior. Use multiset only when duplicates are meaningful (for example, a histogram of repeated values) - in a multiset, count(x) can return more than 1, and erase(x) removes all copies unless you erase by a single iterator.

One classic use of set: deduplicate and sort a vector in one move.

#include <iostream>
#include <set>
#include <vector>
using namespace std;

int main() {
    vector<int> data = {4, 1, 4, 2, 1, 3};
    set<int> unique(data.begin(), data.end());

    for (int x : unique) cout << x << " ";   // 1 2 3 4
}

Constructing the set from the vector's iterators drops every duplicate and sorts the rest - no manual loop, no explicit sorting plus std::unique dance.

Next: pair and tuple

You've now seen .first and .second show up on the pair that insert returns, and structured bindings paired with the auto keyword (auto [it, inserted]) unpack it cleanly. Those lightweight "bundle a few values together" types are everywhere in the STL. Next we'll look at pair and tuple directly - how to build them, unpack them, and return multiple values from a function without defining a whole struct.