set & map
std::set and std::map are the STL's ordered, tree-based associative containers. Both keep their elements sorted at all times and guarantee O(log n) time for insertion, lookup, and removal, because they're implemented internally as a balanced binary search tree (in practice, a red-black tree in essentially every standard library implementation).
std::set — sorted, unique elements
A std::set<T> stores a collection of unique values in sorted order. Inserting a duplicate value is simply ignored — a set never contains the same value twice.
set_basics.cpp
CPP
#include <set>
#include <iostream>
int main() {
std::set<int> nums;
nums.insert(30);
nums.insert(10);
nums.insert(20);
nums.insert(10); // duplicate — ignored, set is unchanged
// Iterating a set always visits elements in sorted order.
for (int n : nums) {
std::cout << n << " "; // 10 20 30
}
std::cout << std::endl;
if (nums.find(20) != nums.end()) {
std::cout << "20 is in the set" << std::endl;
}
nums.erase(10);
std::cout << nums.count(10) << std::endl; // 0 — no longer present
return 0;
}std::map — sorted key-value pairs
A std::map<K, V> stores key-value pairs, sorted by key, with each key appearing at most once. It offers the same O(log n) guarantees as set for insertion, lookup, and removal.
map_basics.cpp
CPP
#include <map>
#include <iostream>
#include <string>
int main() {
std::map<std::string, int> ages;
ages["Alice"] = 30;
ages["Bob"] = 25;
ages.insert({"Carol", 35});
// Overwrites the existing value for an existing key.
ages["Alice"] = 31;
// Iterating a map always visits entries sorted by key.
for (const auto& [name, age] : ages) {
std::cout << name << ": " << age << std::endl;
}
// Output is alphabetical: Alice, Bob, Carol — NOT insertion order.
auto it = ages.find("Bob");
if (it != ages.end()) {
std::cout << "Found Bob, age " << it->second << std::endl;
}
ages.erase("Bob");
std::cout << ages.count("Bob") << std::endl; // 0
return 0;
}Iterating a map or set always yields sorted order
This is one of the most useful properties of these containers: because they're maintained as a sorted tree internally, a simple range-based for loop over a map or set visits elements in ascending key/value order automatically — no separate sort step required. This is fundamentally different from unordered_map/unordered_set, which give no ordering guarantee at all.
Checking existence: find() vs. []
A subtle trap with std::map: using operator[] to read a key that doesn't exist yet will silently insert it with a default-constructed value, rather than signaling that it was missing. Use .find() (compare against .end()) or .count() when you only want to check whether a key is present without accidentally creating it.
map_gotcha.cpp
CPP
#include <map>
#include <iostream>
int main() {
std::map<std::string, int> scores;
std::cout << scores.size() << std::endl; // 0
// Just checking with [] silently inserts "missing" -> 0 !
if (scores["missing"] == 0) {
std::cout << "Looks missing, but it just got inserted!" << std::endl;
}
std::cout << scores.size() << std::endl; // 1, not 0 anymore
// Safer: find() never inserts.
if (scores.find("stillMissing") == scores.end()) {
std::cout << "Confirmed missing, no insertion happened" << std::endl;
}
return 0;
}multiset and multimap
For situations where duplicate keys are actually wanted, the STL provides std::multiset and std::multimap — they behave like set/map but allow the same key to appear more than once. Looking up a key in a multimap returns a range of matching entries (via .equal_range()) rather than a single result.
std::set<T>— sorted, unique values, O(log n) insert/find/erase.std::map<K, V>— sorted key-value pairs, unique keys, O(log n) insert/find/erase.Iterating either always visits elements in ascending sorted order.
std::multiset/std::multimapallow duplicate keys.Use
.find()or.count()to check existence —map::operator[]inserts a default value if the key is missing.