C++ / STANDARD CONTAINERS
std::set and membership with ordering
Store unique keys in a std::set, test membership in logarithmic time, and use lower_bound and upper_bound for nearest-element and range queries.
What you will learn
- Look up elements with contains() or find() in O(log n) instead of a linear scan
- Read insert()'s returned pair to tell a fresh insert from a duplicate
- Use lower_bound/upper_bound to pull an ordered range or the nearest element
- Define duplicates through a strict weak ordering comparator, not operator==
Understanding std::set and membership with ordering
std::set stores each element as its own key in a balanced search tree ordered by a comparator, std::less<T> unless you supply another. Because the tree stays sorted, locating an element costs about log2(n) comparisons instead of the scan a vector needs, and walking from begin() to end() hands you the elements in ascending order with no sorting step. The price is one node per element, so lookups chase pointers around the heap rather than striding through contiguous memory.
Membership in a set is not decided by operator==; it is decided by the comparator alone. Two elements a and b are the same element when comp(a, b) and comp(b, a) are both false, which is what the standard calls equivalence. That is why a set of strings compared case-insensitively rejects APPLE once apple is present, and why the surviving element is the one inserted first: the container sees nothing new to store, so it has no reason to overwrite anything.
Dereferencing a set iterator yields a const reference, because an element's position in the tree was computed from its value; editing it in place would leave the tree sorted by a value that no longer exists. To change an element you remove and reinsert it, or use extract to detach the node, edit it, and relink it. The ordering also buys queries a hash set cannot answer: lower_bound(k) gives the first element not less than k, upper_bound(k) the first strictly greater, and together they delimit every element in a half-open range.
<iostream>
<set>
int main() {
std::set<int> s{42, 7, 19, 7, 91}; // the duplicate 7 is dropped on the way in
std::cout << "size: " << s.size() << "\n";
std::cout << "sorted:";
for (int v : s) std::cout << ' ' << v;
std::cout << "\n";
auto [it, inserted] = s.insert(19);
std::cout << "insert(19) -> " << std::boolalpha << inserted
<< ", points at " << *it << "\n";
std::cout << "contains(42): " << s.contains(42) << "\n";
std::cout << "contains(43): " << s.contains(43) << "\n";
auto lb = s.lower_bound(20); // first element not less than 20
std::cout << "first >= 20: " << *lb << "\n";
std::cout << "erase(7) removed " << s.erase(7) << "\n";
std::cout << "erase(7) removed " << s.erase(7) << "\n";
std::cout << "size: " << s.size() << "\n";
}
In a std::set the comparator alone decides both the traversal order and which elements count as the same element.
Worked examples
Equivalence is whatever the comparator says
A case-insensitive comparator makes two differently spelled strings the same element, so the second one is rejected.
<algorithm>
<cctype>
<iostream>
<set>
<string>
struct CaseInsensitive {
bool operator()(const std::string& a, const std::string& b) const {
std::size_t n = std::min(a.size(), b.size());
for (std::size_t i = 0; i < n; ++i) {
unsigned char ca = std::tolower(static_cast<unsigned char>(a[i]));
unsigned char cb = std::tolower(static_cast<unsigned char>(b[i]));
if (ca != cb) return ca < cb;
}
return a.size() < b.size();
}
};
int main() {
std::set<std::string, CaseInsensitive> tags{"apple", "Banana"};
std::cout << std::boolalpha;
std::cout << "APPLE is new? " << tags.insert("APPLE").second << "\n";
std::cout << "cherry is new? " << tags.insert("cherry").second << "\n";
for (const auto& t : tags) std::cout << t << "\n";
}
Example explained
Line 1The comparator lowercases each character pair, so it can never rank apple before APPLE or the other way round.
Line 2insert returns .second == false because both comparisons come out false, which the set reads as an equivalent element already being present.
Line 3The set keeps the spelling that arrived first, which is why the loop prints apple rather than APPLE.
Line 4Traversal uses the same comparator, so Banana sits between apple and cherry even though uppercase 'B' is numerically below lowercase 'a' in ASCII.
Range queries with lower_bound and upper_bound
The two bound functions turn a sorted set into a container you can slice by value rather than by index.
<iostream>
<set>
int main() {
std::set<int> ticks{5, 18, 30, 33, 47, 60, 72};
auto first = ticks.lower_bound(30); // first element not less than 30
auto last = ticks.lower_bound(60); // first element not less than 60
std::cout << "[30, 60):\n";
for (auto it = first; it != last; ++it)
std::cout << " " << *it << "\n";
std::cout << "next tick at or after 61: " << *ticks.lower_bound(61) << "\n";
std::cout << "nothing at or after 100: " << std::boolalpha
<< (ticks.lower_bound(100) == ticks.end()) << "\n";
}
Example explained
Line 1lower_bound(30) stops on 30 itself, since it means first element not less than the argument.
Line 2lower_bound(60) is the exclusive end of the loop, which is why 60 is not printed even though it is in the set.
Line 3The argument need not be an element: lower_bound(61) lands on 72, answering a nearest-above question in log n steps.
Line 4When every element is smaller than the argument the result is end(), so test against end() before dereferencing.
Changing an element without breaking the tree
extract detaches a node so its value can be edited and relinked at the correct new position.
<iostream>
<set>
<string>
<utility>
int main() {
std::set<std::string> names{"ada", "grace", "linus"};
auto node = names.extract("linus");
std::cout << "after extract, size = " << names.size() << "\n";
node.value() = "alan";
names.insert(std::move(node));
for (const auto& n : names) std::cout << n << "\n";
std::cout << "size = " << names.size() << "\n";
}
Example explained
Line 1Assigning through an iterator, as in *it = "alan", does not compile: set iterators expose const references.
Line 2extract unlinks the node and transfers ownership to you, which is why the size drops to 2 before the reinsertion.
Line 3node.value() is a non-const reference, the one legitimate place to modify a stored key.
Line 4insert(std::move(node)) relinks the same node at its new sorted position, so no string is copied and alan appears after ada.
Important notes
contains() arrived in C++20; before that use s.find(x) != s.end(). s.count(x) also works but can only ever return 0 or 1 in a set.
set iterators are bidirectional, not random access: there is no s[i] and no it + 2, and std::next(it, 2) has to step through the tree one node at a time.
Common mistakes
Calling std::find(s.begin(), s.end(), x): it compiles, but it visits every node and uses operator==, so you pay linear time and ignore the comparator the set is built on.
Writing a comparator with <= instead of <: comp(a, a) becomes true, which is not a strict weak ordering, so behaviour is undefined and typically shows up as duplicates being accepted or find missing elements that are present.
Expecting insert to overwrite the way map's operator[] does: on an equivalent key it changes nothing and returns false, so the newer object is silently discarded.
Try it yourself
Change, predict, then run
Build a std::set<int> from ten numbers that include a few duplicates, print its size and its contents in order, then use lower_bound and upper_bound to print only the values from 20 through 50 inclusive.
Open the C++ workspaceCheck your understanding
A std::set<std::string, CaseInsensitive> whose comparator ignores case already holds apple. What does inserting the string APPLE do?
- It inserts APPLE, because APPLE and apple are different under operator==.
- It inserts nothing and returns false plus an iterator to the stored apple.
- It replaces the stored element with APPLE and returns true.
- It inserts APPLE beside apple, since the comparator affects ordering but not uniqueness.
Show answer
The comparator ranks neither string before the other, so the set considers them one element and insert becomes a no-op reporting false. Option 0 is tempting because the strings genuinely differ, but a set never calls operator==; comparator equivalence is the only test it applies. Option 2 fails because insert never overwrites: replacing a stored element means erasing it and inserting the new one.