A free lesson from the course “C++ without Memory Allocations” on Stepik.
Associative containers are data structures where each element is stored in sorted order and is accessed through a key. Thanks to this, searching for an element does not take time that depends on the size of the array, but works very fast — roughly in O(log n) (logarithmic time). In the C++ standard library they are usually implemented using balanced search trees (most often red-black trees).
These containers come in two kinds:
-
where keys must be unique (you cannot insert two identical keys),
-
where keys may repeat (several elements with the same key).
set — a set of unique values
std::set stores keys only (without values) and guarantees that each key appears only once. All elements are automatically kept in sorted order. This is convenient when you need to work with a collection of unique data: numbers, names, ids, etc.
For example, if we insert numbers in any order, set will sort them automatically:
#include <set>
#include <iostream>
int main() {
std::set<int> s;
s.insert(5);
s.insert(1);
s.insert(3);
s.insert(5); // duplicate value is ignored
for (int x : s) {
std::cout << x << " ";
}
// Output: 1 3 5
}map — a dictionary (a mapping of the key → value relationship)
std::map stores data as key-value pairs. Keys are always unique and sorted, while values can be anything. You can use a map, for example, as a dictionary: look up the translation by a word, user data by id, a phone number by name, and so on.
#include <map>
#include <iostream>
int main() {
std::map<std::string, int> ages;
ages["Alice"] = 25;
ages["Bob"] = 30;
ages["Alice"] = 26; // overwrites the old value
for (auto& [name, age] : ages) {
std::cout << name << " -> " << age << "\n";
}
// Output:
// Alice -> 26
// Bob -> 30
}multiset — a set with repeating elements
Unlike set, std::multiset allows storing identical keys. All elements are also kept in sorted order, but now you can insert repeating values. This is useful if, for example, you need to keep statistics on how often numbers or words occur.
#include <set>
#include <iostream>
int main() {
std::multiset<int> ms;
ms.insert(5);
ms.insert(5);
ms.insert(1);
for (int x : ms) {
std::cout << x << " ";
}
// Output: 1 5 5
}multimap — a dictionary with repeating keys
std::multimap is similar to map, but it can store several values for one key. This is useful if, for example, one person has several phone numbers or one product has several reviews.
#include <map>
#include <iostream>
int main() {
std::multimap<std::string, std::string> phones;
phones.insert({"Alice", "123"});
phones.insert({"Alice", "456"});
phones.insert({"Bob", "789"});
for (auto& [name, phone] : phones) {
std::cout << name << " -> " << phone << "\n";
}
// Output:
// Alice -> 123
// Alice -> 456
// Bob -> 789
}