Maps, sets, and iterators

2.1 Keys kept in order

std::map stores key-value pairs and keeps them ordered by key. std::set stores keys only and keeps them ordered too. Both lookups run in logarithmic time, which is much faster than scanning a vector once the collection grows.

A std::vector stores its elements in one contiguous block and remains the default choice for a sequence. A map or set costs more per element and pays for itself when lookups by key dominate. A map is the natural choice for looking up a value by a name, an id, or another key. A set answers whether a value is present and removes duplicates. Both containers require a comparison for the key type, and std::less<Key> is the default.

#include <iostream>
#include <map>
#include <string>

int main() {
    std::map<std::string, int> marks;
    marks["Ravi"] = 72;
    marks["Ada"] = 90;
    marks["Mei"] = 85;
    for (const auto& entry : marks) {
        std::cout << entry.first << ": " << entry.second << "\n";
    }
    return 0;
}

Ada: 90
Mei: 85
Ravi: 72

2.1.1 Lookup without inserting

marks["Ada"] returns a reference to the value for "Ada". When the key is missing, the operator inserts a new entry with a value-initialized value and returns it. That behavior is useful for building a map, and surprising when a lookup should not change it.

Use find when absence matters. It returns an iterator to the pair, or end() when the key is not there. count returns 0 or 1 for a map and is the shortest existence check. at returns a reference and throws std::out_of_range when the key is missing.

#include <iostream>
#include <map>
#include <string>

int main() {
    std::map<std::string, int> marks = {{"Ada", 90}, {"Ravi", 72}};
    auto found = marks.find("Ravi");
    if (found != marks.end()) {
        std::cout << "Found: " << found->second << "\n";
    } else {
        std::cout << "Missing\n";
    }
    auto missing = marks.find("Mei");
    std::cout << std::boolalpha << "Mei present: " << (missing != marks.end()) << "\n";
    return 0;
}

Found: 72
Mei present: false

2.1.2 Iterators

An iterator points at an element and supports movement with ++ and access with * or ->. begin() gives the first element and end() gives one past the last. A map iterator points at a std::pair<const Key, T>, so it->first is the key and it->second is the value.

Range-based loops and structured bindings hide most iterator syntax. C++17 lets you write for (const auto& [key, value] : map), which reads better than the pair members. Iterators are the common language between containers and algorithms, and the next lesson uses them with <algorithm>.

#include <iostream>
#include <map>
#include <string>

int main() {
    std::map<std::string, int> stock = {{"pen", 12}, {"book", 4}};
    for (const auto& [item, count] : stock) {
        std::cout << item << " x" << count << "\n";
    }
    return 0;
}

book x4
pen x12

2.1.3 Sets and uniqueness

std::set keeps one copy of each value and rejects duplicates. insert returns a pair: an iterator to the stored element and a bool that says whether the insert happened. Checking the bool is the direct way to learn whether a value was already present.

The default order uses <. A second template argument can change the order, as in std::set<int, std::greater<int>> for descending values. The comparator must define a strict weak ordering, the same requirement that sorting uses.

#include <iostream>
#include <set>

int main() {
    std::set<int> ids = {7, 3, 7, 5};
    auto duplicate = ids.insert(3);
    auto added = ids.insert(9);
    std::cout << "Size: " << ids.size() << "\n";
    std::cout << std::boolalpha << "Second 3 added: " << duplicate.second << "\n";
    std::cout << "9 added: " << added.second << "\n";
    for (int id : ids) {
        std::cout << id << "\n";
    }
    return 0;
}

Size: 4
Second 3 added: false
9 added: true
3
5
7
9

2.1.4 Ordered and unordered containers

std::map and std::set order their elements through comparisons. std::unordered_map and std::unordered_set use a hash instead and do not keep an order. Unordered containers often have faster average lookup, while ordered containers support range queries and predictable iteration order.

The hash version requires a hash function and an equality comparison for the key type. The standard library supplies both for strings and numbers. Choose the ordered version when order matters or when the key type has no ready hash.

#include <iostream>
#include <map>
#include <sstream>
#include <string>

int main() {
    std::string text = "red blue red green blue red";
    std::map<std::string, int> counts;
    std::istringstream stream(text);
    std::string word;
    while (stream >> word) {
        ++counts[word];
    }
    for (const auto& [item, count] : counts) {
        std::cout << item << ": " << count << "\n";
    }
    return 0;
}

blue: 2
green: 1
red: 3

2.1.5 Iterator invalidation

Inserting into a map or set does not invalidate iterators to other elements. Erasing an element invalidates only the iterator to that element. A vector behaves differently: growing it can move every element, so all iterators, pointers, and references into the old storage become invalid.

When erasing in a loop, use the iterator returned by erase: it = container.erase(it);. Do not increment an iterator after erasing it. The rule differs by container, and the container's documentation is the source of truth.

2.1.6 Common mistakes and practice

Mistakes to watch for:

• Using [] to check whether a key exists, which inserts it.
• Comparing an iterator with npos instead of end().
• Changing a map key through an iterator. The key is const.
• Erasing an element and then using its iterator.
• Assuming a set keeps insertion order rather than sorted order.

Practice:

1. Store four names and scores in a map and print them by name.
2. Use find to look up a missing key and print a message.
3. Add a duplicate value to a set and print the returned bool.
4. Use std::set<int, std::greater<int>> and print the values.
5. Count the words in a sentence with a map and print the frequencies.