std::map, std::set and custom comparators

std::map stores key-value pairs sorted by key, and std::set stores keys alone, sorted. Both find, insert and erase a key in O(log n), and both keep their elements in order all the time, so you can walk them from the smallest key to the largest and ask range questions: every key between two values, the first key after a given one, the nearest key below it. Use them when you need that order; when you only look keys up, a hash table is faster, as the first lesson of this module measured. The order comes from a comparator, std::less by default, and a custom comparator must be a strict weak ordering: one that never says a key comes before itself.

This lesson counts words with a map, answers range queries on a timetable with lower_bound and upper_bound, breaks a set and a sort with the most common comparator bug and shows what each library’s checks report, looks keys up without building strings, and moves elements between maps without copying them.

Counting with std::map

// Counting words with std::map: the keys come out in sorted order, and operator[] adds a key that is missing.
#include <map>
#include <print>
#include <sstream>
#include <stdexcept>
#include <string>

int main() {
    std::istringstream text("the cat saw the dog and the dog saw a cat");
    std::map<std::string, int> counts;
    for (std::string word; text >> word;) ++counts[word];  // a new word starts at int{}, which is 0
    std::println("{}", counts);
    std::println("{} distinct words", counts.size());

    // Looking with operator[] inserts what it does not find.
    if (counts["zebra"] == 0) std::println("no zebra, but now there are {} keys", counts.size());

    // find, contains and count only look.
    std::println("contains(\"lion\"): {}, count(\"cat\"): {}", counts.contains("lion"), counts.count("cat"));
    if (auto it = counts.find("dog"); it != counts.end()) std::println("dog appears {} times", it->second);
    std::println("still {} keys", counts.size());

    // at() reads without inserting and throws when the key is missing.
    try {
        std::println("{}", counts.at("lion"));
    } catch (const std::out_of_range&) {
        std::println("at(\"lion\") threw std::out_of_range");
    }
}

from session import run

# word_counts.cpp built and run with both compilers and their standard libraries.
run("""
clang++ -std=c++23 -Wall -Wextra word_counts.cpp -o word_counts
./word_counts
g++-16 -std=c++23 -Wall -Wextra word_counts.cpp -o word_counts-gcc
./word_counts-gcc
""")

$ clang++ -std=c++23 -Wall -Wextra word_counts.cpp -o word_counts
$ ./word_counts
{"a": 1, "and": 1, "cat": 2, "dog": 2, "saw": 2, "the": 3}
6 distinct words
no zebra, but now there are 7 keys
contains("lion"): false, count("cat"): 1
dog appears 2 times
still 7 keys
at("lion") threw std::out_of_range
$ g++-16 -std=c++23 -Wall -Wextra word_counts.cpp -o word_counts-gcc
$ ./word_counts-gcc
{"a": 1, "and": 1, "cat": 2, "dog": 2, "saw": 2, "the": 3}
6 distinct words
no zebra, but now there are 7 keys
contains("lion"): false, count("cat"): 1
dog appears 2 times
still 7 keys
at("lion") threw std::out_of_range

• ++counts[word] is the idiom for counting. operator[] returns a reference to the value stored for the key, and when the key is missing it first inserts the key with a value-initialised value, 0 for an int.
• The map printed its keys in alphabetical order without being asked: iteration always follows the comparator.
• The flip side of operator[]: just testing counts["zebra"] == 0 inserted "zebra", and the map grew from 6 to 7 keys. operator[] also cannot be used on a const map, and it needs a value type that can be default-constructed.
• find returns an iterator, end() when the key is missing; contains (C++20) returns a bool; count returns 0 or 1 for a map. None of them inserts anything.
• at returns a reference to an existing value and throws std::out_of_range for a missing key.

The elements of a std::map<K, V> are std::pair<const K, V>. The key is const so that nobody can change it in place and break the order; changing a key means removing the element and inserting it again, which the section on extract and merge below does without a copy. For inserting, insert and try_emplace leave an existing value alone and report whether they inserted, while insert_or_assign (C++17) overwrites it.

A std::set<K> is the same tree without values: insert, contains, erase and the range functions below, and its elements are const too. std::multimap and std::multiset allow several elements with equivalent keys, kept in the order they were inserted; count then counts all of them, and equal_range returns them as one range.

Range queries with lower_bound and upper_bound

Order makes questions possible that a hash table cannot answer without sorting. This timetable maps departure times, in minutes after midnight, to bus routes:

// Range questions on a std::map: a bus timetable keyed by departure time, in minutes after midnight.
#include <format>
#include <iterator>
#include <map>
#include <print>
#include <string>

std::string hhmm(int minutes) { return std::format("{:02}:{:02}", minutes / 60, minutes % 60); }

int main() {
    std::map<int, std::string> departures{
        {6 * 60 + 40, "route 4"},  {8 * 60 + 5, "route 9"},  {9 * 60, "route 4"},   {9 * 60 + 35, "route 12"},
        {10 * 60 + 20, "route 9"}, {11 * 60, "route 4"},     {12 * 60 + 15, "route 12"},
    };

    // Every departure from 09:00 to 11:00, both included: [lower_bound(09:00), upper_bound(11:00)).
    auto first = departures.lower_bound(9 * 60);   // the first key that is not less than 09:00
    auto last = departures.upper_bound(11 * 60);   // the first key that is greater than 11:00
    std::print("09:00 to 11:00:");
    for (auto it = first; it != last; ++it) std::print("  {} {}", hhmm(it->first), it->second);
    std::println("");

    // The next departure at or after 10:00, and the last one before 10:00.
    auto next = departures.lower_bound(10 * 60);
    std::println("next at or after 10:00: {} {}", hhmm(next->first), next->second);
    if (next != departures.begin()) {
        auto before = std::prev(next);
        std::println("last before 10:00: {} {}", hhmm(before->first), before->second);
    }

    // No departure after 12:15: upper_bound returns end(), which must not be dereferenced.
    auto late = departures.upper_bound(12 * 60 + 15);
    std::println("anything after 12:15? {}", late == departures.end() ? "no" : hhmm(late->first));

    // equal_range gives both bounds for one key: a key that is present, then one that is not.
    auto [from, to] = departures.equal_range(9 * 60 + 35);
    auto [gap_from, gap_to] = departures.equal_range(9 * 60 + 36);
    std::println("09:35 matches {} departure; 09:36 matches {}, and both its bounds point to {}", std::distance(from, to),
                 std::distance(gap_from, gap_to), hhmm(gap_from->first));
}

from session import run

# timetable.cpp built and run with both compilers and their standard libraries.
run("""
clang++ -std=c++23 -Wall -Wextra timetable.cpp -o timetable
./timetable
g++-16 -std=c++23 -Wall -Wextra timetable.cpp -o timetable-gcc
./timetable-gcc
""")

$ clang++ -std=c++23 -Wall -Wextra timetable.cpp -o timetable
$ ./timetable
09:00 to 11:00:  09:00 route 4  09:35 route 12  10:20 route 9  11:00 route 4
next at or after 10:00: 10:20 route 9
last before 10:00: 09:35 route 12
anything after 12:15? no
09:35 matches 1 departure; 09:36 matches 0, and both its bounds point to 10:20
$ g++-16 -std=c++23 -Wall -Wextra timetable.cpp -o timetable-gcc
$ ./timetable-gcc
09:00 to 11:00:  09:00 route 4  09:35 route 12  10:20 route 9  11:00 route 4
next at or after 10:00: 10:20 route 9
last before 10:00: 09:35 route 12
anything after 12:15? no
09:35 matches 1 departure; 09:36 matches 0, and both its bounds point to 10:20

Each function walks down the tree once, in O(log n):

• lower_bound(k) returns the first element whose key is not less than k: k itself when it is there, otherwise the next key above it.
• upper_bound(k) returns the first element whose key is greater than k.
• equal_range(k) returns both. For the missing 09:36, the range was empty, and both iterators pointed to 10:20, where 09:36 would be inserted.

The two bounds form a half-open range, like begin() and end(): [lower_bound(a), upper_bound(b)) holds every key from a to b, both included, and [lower_bound(a), lower_bound(b)) stops before b. For “the last key before k”, step back from lower_bound(k) with std::prev, but only after checking that it is not begin(). Every bound may also be end(), as upper_bound(12:15) was, and dereferencing end() is undefined behaviour.

Comparators must be strict weak orderings

A map or set never asks whether two keys are equal. It only asks its comparator comp(a, b): does a go before b? Two keys are equivalent when neither goes before the other, and the container keeps one element per equivalent key. The C++ standard requires comp to induce a strict weak ordering, which comes down to three rules:

1. Irreflexive: comp(a, a) is false. Nothing goes before itself.
2. Transitive: if a goes before b and b before c, then a goes before c.
3. Equivalence is transitive: if a is equivalent to b and b to c, then a is equivalent to c.

< on integers and strings, > for a descending order, and comparing a single field, such as a.age < b.age, all qualify; < on floating-point values qualifies only while no NaN is among them. The last one makes two people of the same age equivalent, so a std::set ordered that way keeps only one person per age; that is legal, and sometimes exactly what you want, but often a surprise. <= breaks rule 1, and this is what it does:

// A comparator that uses <= instead of < breaks the rule every ordered container relies on: it is not a strict
// weak ordering, because it says that a value comes before itself. This set is the result.
#include <print>
#include <set>

struct LessOrEqual {
    bool operator()(int a, int b) const { return a <= b; }  // wrong: must be a < b
};

int main() {
    std::set<int, LessOrEqual> s;
    for (int x : {3, 1, 3, 2, 3}) s.insert(x);
    std::println("size {}, elements {}", s.size(), s);
    std::println("count(3) = {}, contains(3) = {}, find(3) found it: {}", s.count(3), s.contains(3), s.find(3) != s.end());
}

// The same <= comparator given to std::ranges::sort, on 40 equal values and one smaller one.
#include <algorithm>
#include <print>
#include <vector>

int main() {
    std::vector<int> v(40, 7);
    v.push_back(1);
    std::ranges::sort(v, [](int a, int b) { return a <= b; });  // undefined behaviour: not a strict weak ordering
    std::println("sorted {} values, the first is {}", v.size(), v.front());
}

from session import run

# less_equal.cpp with both libraries, then with libc++'s debug hardening mode, which checks the comparator.
# less_equal_sort.cpp with AddressSanitizer and with each library's debug mode; grep and sed keep the key line of
# each report and hide the addresses, which change on every run.
run("""
clang++ -std=c++23 -Wall -Wextra less_equal.cpp -o less_equal && ./less_equal
g++-16 -std=c++23 -Wall -Wextra less_equal.cpp -o less_equal-gcc && ./less_equal-gcc
clang++ -std=c++23 -D_LIBCPP_HARDENING_MODE=_LIBCPP_HARDENING_MODE_DEBUG less_equal.cpp -o less_equal-debug
./less_equal-debug 2>&1 | grep -o "libc++ Hardening assertion.*"
clang++ -std=c++23 -g -fsanitize=address less_equal_sort.cpp -o sort_asan
ASAN_OPTIONS=symbolize=0 ./sort_asan 2>&1 | grep -E "ERROR|of size" | sed -E 's/==[0-9]+==//; s/0x[0-9a-f]+/0x…/g'
clang++ -std=c++23 -D_LIBCPP_HARDENING_MODE=_LIBCPP_HARDENING_MODE_DEBUG less_equal_sort.cpp -o sort_debug
./sort_debug 2>&1 | grep -o "libc++ Hardening assertion.*"
g++-16 -std=c++23 -D_GLIBCXX_DEBUG less_equal_sort.cpp -o sort_debug-gcc
./sort_debug-gcc 2>&1 | grep "Error"
""")

$ clang++ -std=c++23 -Wall -Wextra less_equal.cpp -o less_equal && ./less_equal
size 5, elements {1, 2, 3, 3, 3}
count(3) = 0, contains(3) = false, find(3) found it: false
$ g++-16 -std=c++23 -Wall -Wextra less_equal.cpp -o less_equal-gcc && ./less_equal-gcc
size 5, elements {1, 2, 3, 3, 3}
count(3) = 0, contains(3) = false, find(3) found it: false
$ clang++ -std=c++23 -D_LIBCPP_HARDENING_MODE=_LIBCPP_HARDENING_MODE_DEBUG less_equal.cpp -o less_equal-debug
$ ./less_equal-debug 2>&1 | grep -o "libc++ Hardening assertion.*"
libc++ Hardening assertion __result ? !static_cast<bool>(__comp_(__rhs_, __lhs_)) : true failed: Comparator does not induce a strict weak ordering
$ clang++ -std=c++23 -g -fsanitize=address less_equal_sort.cpp -o sort_asan
$ ASAN_OPTIONS=symbolize=0 ./sort_asan 2>&1 | grep -E "ERROR|of size" | sed -E 's/==[0-9]+==//; s/0x[0-9a-f]+/0x…/g'
ERROR: AddressSanitizer: container-overflow on address 0x… at pc 0x… bp 0x… sp 0x…
READ of size 4 at 0x… thread T0
$ clang++ -std=c++23 -D_LIBCPP_HARDENING_MODE=_LIBCPP_HARDENING_MODE_DEBUG less_equal_sort.cpp -o sort_debug
$ ./sort_debug 2>&1 | grep -o "libc++ Hardening assertion.*"
libc++ Hardening assertion __first != __end failed: Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?
$ g++-16 -std=c++23 -D_GLIBCXX_DEBUG less_equal_sort.cpp -o sort_debug-gcc
$ ./sort_debug-gcc 2>&1 | grep "Error"
Error: attempt to dereference a past-the-end iterator.

• The set kept three 3s and could not find any of them. Under <=, two 3s are never equivalent, because each one goes before the other, so every insertion added a node. Lookups ask “is there an element equivalent to 3?”, and with this comparator nothing is, so count(3) returned 0. Both libraries produced the same broken set, and neither complained.
• libc++’s debug mode stopped at the insertion, with “Comparator does not induce a strict weak ordering”. It checks, on the comparisons it happens to make, that comp(a, b) and comp(b, a) are never both true.
• The sort read memory outside the vector. std::ranges::sort relies on the ordering to stop its inner loops, and with <= a loop over equal values ran past the last element. AddressSanitizer reported a container-overflow: a read beyond the vector’s size, inside its spare capacity. libc++’s debug mode stopped the sort and named the likely cause, a comparator that breaks the ordering rules, while libstdc++’s debug mode reported an attempt to dereference a past-the-end iterator. Without a checker, nothing stops the loop: it goes on reading whatever memory follows the vector, and what happens next is undefined.

Both debug modes are slow and change how the library behaves, so they belong in test builds. The fix is always the same: compare with <, never <=, and for several fields compare them in order. The tuple lesson’s std::tie(a.marks, a.name) < std::tie(b.marks, b.name) is a strict weak ordering for any number of fields.

A comparator is part of the container’s type: std::set<int, std::greater<>> and std::set<int> are different types. Any type with a const call operator works, and since C++20 a lambda without captures does too: std::set<Student, decltype(by_marks)>.

Lookups without building a key

With the default comparator std::less<std::string>, a std::map<std::string, int> can only search for a std::string. A key that arrives as a std::string_view or a string literal has to become a temporary std::string first, and a string longer than its built-in buffer (22 characters in libc++, 15 in libstdc++) allocates memory for that. std::less<>, the comparator with no type, can compare a std::string with anything that compares with one, and it says so with a member type named is_transparent. The map’s lookup functions then accept other types:

// Looking up a std::string key with a std::string_view: with the default comparator, std::less<std::string>, the
// view must first become a std::string, which allocates when the text is too long for the string's own buffer.
// std::less<> compares a std::string with a std::string_view directly. The global operator new below counts every
// allocation the program makes.
#include <cstddef>
#include <cstdlib>
#include <functional>
#include <map>
#include <new>
#include <print>
#include <string>
#include <string_view>

static std::size_t allocations = 0;
void* operator new(std::size_t n) {
    ++allocations;
    if (void* p = std::malloc(n)) return p;
    throw std::bad_alloc{};
}
void operator delete(void* p) noexcept { std::free(p); }
void operator delete(void* p, std::size_t) noexcept { std::free(p); }

template <class Map>
std::size_t allocations_for_lookups(const Map& m, std::string_view key, int times) {
    std::size_t before = allocations;
    int found = 0;
    for (int i = 0; i < times; ++i) {
        if constexpr (requires { m.find(key); }) found += m.find(key) != m.end();  // a heterogeneous lookup
        else found += m.find(std::string(key)) != m.end();                     // build a std::string first
    }
    if (found != times) std::println("missing key!");
    return allocations - before;
}

int main() {
    const std::string_view key = "customer-000123-billing-address";  // 31 characters: too long to fit in place
    std::map<std::string, int> plain{{std::string(key), 1}};
    std::map<std::string, int, std::less<>> transparent{{std::string(key), 1}};

    std::println("1000 lookups, std::less<std::string>: {} allocations", allocations_for_lookups(plain, key, 1000));
    std::println("1000 lookups, std::less<>:            {} allocations", allocations_for_lookups(transparent, key, 1000));
}

from session import run

# transparent.cpp with -O2, with each compiler and its standard library.
run("""
clang++ -std=c++23 -O2 -Wall -Wextra transparent.cpp -o transparent
./transparent
g++-16 -std=c++23 -O2 -Wall -Wextra transparent.cpp -o transparent-gcc
./transparent-gcc
""")

$ clang++ -std=c++23 -O2 -Wall -Wextra transparent.cpp -o transparent
$ ./transparent
1000 lookups, std::less<std::string>: 1000 allocations
1000 lookups, std::less<>:            0 allocations
$ g++-16 -std=c++23 -O2 -Wall -Wextra transparent.cpp -o transparent-gcc
$ ./transparent-gcc
1000 lookups, std::less<std::string>: 1000 allocations
1000 lookups, std::less<>:            0 allocations

A thousand lookups cost a thousand allocations with std::less<std::string> and none with std::less<>, with both libraries. find, count, lower_bound, upper_bound and equal_range accept such keys since C++14 (paper N3657), contains since it was added in C++20, and erase and extract since C++23. Insertion with operator[] or try_emplace still needs a std::string until C++26, which adds those overloads too (paper P2363R5). A transparent comparator is opt-in because it changes which overloads exist: the default keeps existing code behaving as before.

Moving elements between maps: extract and merge

Every element of a map lives in a node of its own, and C++17 lets you take a node out and put it back, or into another map, without copying the element or allocating a new node:

// extract and merge (C++17) move nodes between maps without copying or allocating: a key can change, and elements
// can change maps, while pointers to them stay valid. The global operator new below counts allocations.
#include <cstddef>
#include <cstdlib>
#include <map>
#include <new>
#include <print>
#include <string>

static std::size_t allocations = 0;
void* operator new(std::size_t n) {
    ++allocations;
    if (void* p = std::malloc(n)) return p;
    throw std::bad_alloc{};
}
void operator delete(void* p) noexcept { std::free(p); }
void operator delete(void* p, std::size_t) noexcept { std::free(p); }

int main() {
    std::map<int, std::string> seats{{12, "Meera, travelling with a guide dog"}, {14, "Arjun"}, {15, "Kabir"}};
    const std::string* meera = &seats.at(12);

    // Move Meera from seat 12 to seat 3: the key of a map element is const, so take the node out, change it, put it back.
    std::size_t before = allocations;
    auto node = seats.extract(12);  // a node handle now owns the element; the map no longer has it
    node.key() = 3;
    seats.insert(std::move(node));
    std::size_t made = allocations - before;  // counted before printing, which may allocate
    std::println("{}", seats);
    std::println("allocations: {}, same string object: {}", made, &seats.at(3) == meera);

    // merge moves every node whose key is not in the target yet; the others stay where they were.
    std::map<int, std::string> waitlist{{14, "Dev"}, {20, "Asha"}, {21, "Ravi"}};
    const std::string* asha = &waitlist.at(20);
    before = allocations;
    seats.merge(waitlist);
    made = allocations - before;
    std::println("seats    {}", seats);
    std::println("waitlist {}  (seat 14 was taken)", waitlist);
    std::println("allocations: {}, Asha's string was not copied: {}", made, &seats.at(20) == asha);
}

from session import run

# nodes.cpp built and run with both compilers and their standard libraries.
run("""
clang++ -std=c++23 -Wall -Wextra nodes.cpp -o nodes
./nodes
g++-16 -std=c++23 -Wall -Wextra nodes.cpp -o nodes-gcc
./nodes-gcc
""")

$ clang++ -std=c++23 -Wall -Wextra nodes.cpp -o nodes
$ ./nodes
{3: "Meera, travelling with a guide dog", 14: "Arjun", 15: "Kabir"}
allocations: 0, same string object: true
seats    {3: "Meera, travelling with a guide dog", 14: "Arjun", 15: "Kabir", 20: "Asha", 21: "Ravi"}
waitlist {14: "Dev"}  (seat 14 was taken)
allocations: 0, Asha's string was not copied: true
$ g++-16 -std=c++23 -Wall -Wextra nodes.cpp -o nodes-gcc
$ ./nodes-gcc
{3: "Meera, travelling with a guide dog", 14: "Arjun", 15: "Kabir"}
allocations: 0, same string object: true
seats    {3: "Meera, travelling with a guide dog", 14: "Arjun", 15: "Kabir", 20: "Asha", 21: "Ravi"}
waitlist {14: "Dev"}  (seat 14 was taken)
allocations: 0, Asha's string was not copied: true

• extract(12) unlinked the node of seat 12 and returned a node handle that owns it. Through the handle the key is no longer const, so node.key() = 3 moved Meera to seat 3, and insert linked the same node back in.
• merge moved every node of the waitlist whose key was free in seats. Seat 14 was already taken, so Dev’s node stayed in the waitlist.
• Neither step allocated, and pointers to the moved strings still pointed to them: the elements never moved. That matters for large values, and for code that keeps pointers or references to elements.

A map can take nodes from any std::map or std::multimap with the same key, value and allocator types, even one with another comparator. Sets and multisets work the same way, and so do the unordered containers among themselves.

Your turn: book a meeting room

A room’s bookings are half-open intervals of minutes, [start, end), kept in a std::map from start to end. Write Room::book(start, end): it adds the booking and returns true, or returns false and changes nothing when the new booking overlaps an existing one. A booking that starts exactly when another ends does not overlap it.

// Starter code for "Your turn": the bookings of one meeting room, each a half-open interval [start, end) of minutes
// after midnight, kept in a std::map from start to end.
#pragma once
#include <map>
#include <utility>
#include <vector>

class Room {
public:
    // Books [start, end) and returns true; or returns false, and changes nothing, when it overlaps a booking.
    // A booking that starts exactly when another one ends does not overlap it. start is always less than end.
    bool book(int start, int end) {
        // TODO: look at bookings_.lower_bound(start) and at the booking just before it
        (void)start;
        (void)end;
        return false;
    }

    // Every booking in order of start time, for the tests.
    std::vector<std::pair<int, int>> list() const { return {bookings_.begin(), bookings_.end()}; }

private:
    std::map<int, int> bookings_;  // start -> end
};

// Sample tests for bookings.h. Build: clang++ -std=c++23 -g -fsanitize=address,undefined -Wall -Wextra bookings_tests.cpp -o bookings_tests
#include <print>
#include <random>
#include <utility>
#include <vector>
#include "bookings.h"

int checks = 0;
int failures = 0;

void check(bool ok, const char* what) {
    ++checks;
    if (!ok) {
        ++failures;
        std::println("FAIL {}", what);
    }
}

// The slow way, easy to get right: compare with every booking.
struct SlowRoom {
    std::vector<std::pair<int, int>> bookings;
    bool book(int start, int end) {
        for (auto [s, e] : bookings)
            if (start < e && s < end) return false;
        bookings.emplace_back(start, end);
        return true;
    }
};

int main() {
    Room room;
    check(room.book(600, 660), "10:00 to 11:00 in an empty room");
    check(room.book(660, 720), "a booking that starts when another ends");
    check(room.book(540, 600), "a booking that ends when another starts");
    check(!room.book(630, 690), "an overlap with two bookings");
    check(!room.book(610, 620), "a booking inside another one");
    check(!room.book(500, 800), "a booking around all the others");
    check(!room.book(600, 660), "the same booking twice");
    check(room.list() == std::vector<std::pair<int, int>>{{540, 600}, {600, 660}, {660, 720}}, "the three bookings, in order");

    // 5,000 random requests over a day, compared with the slow way.
    Room fast;
    SlowRoom slow;
    std::mt19937 random(3);
    bool same = true;
    for (int i = 0; i < 5'000 && same; ++i) {
        int start = int(random() % 1'400);
        int end = start + 1 + int(random() % 40);
        same = fast.book(start, end) == slow.book(start, end);
    }
    check(same, "5,000 random requests get the same answers as the slow way");

    std::println("{} of {} checks passed", checks - failures, checks);
    return failures == 0 ? 0 : 1;
}

from session import run

# The sample tests run against the starter code, before the TODO is done, with the sanitizers switched on.
run("""
clang++ -std=c++23 -g -fsanitize=address,undefined -Wall -Wextra bookings_tests.cpp -o bookings_tests && ./bookings_tests
g++-16 -std=c++23 -g -fsanitize=address,undefined -Wall -Wextra bookings_tests.cpp -o bookings_tests-gcc && ./bookings_tests-gcc
""")

$ clang++ -std=c++23 -g -fsanitize=address,undefined -Wall -Wextra bookings_tests.cpp -o bookings_tests && ./bookings_tests
FAIL 10:00 to 11:00 in an empty room
FAIL a booking that starts when another ends
FAIL a booking that ends when another starts
FAIL the three bookings, in order
FAIL 5,000 random requests get the same answers as the slow way
4 of 9 checks passed
[exit status 1]
$ g++-16 -std=c++23 -g -fsanitize=address,undefined -Wall -Wextra bookings_tests.cpp -o bookings_tests-gcc && ./bookings_tests-gcc
FAIL 10:00 to 11:00 in an empty room
FAIL a booking that starts when another ends
FAIL a booking that ends when another starts
FAIL the three bookings, in order
FAIL 5,000 random requests get the same answers as the slow way
4 of 9 checks passed
[exit status 1]

The starter refuses every booking, so it passes only the four checks that expect a refusal. You are done when both compilers print 9 of 9 checks passed. Because the bookings never overlap, only two existing bookings can collide with a new one: the first one that starts at or after start, which lower_bound(start) finds, and the one just before it. Check both in O(log n) instead of looking at every booking; the last test compares your answers with the slow way on 5,000 random requests. emplace_hint(next, start, end) inserts at the position you already found.

Interview questions

Fresher · What is the difference between m[key], m.at(key) and m.find(key) on a std::map?

All three look the key up in O(log n); they differ in what happens when it is missing. m[key] returns a reference to the value, and for a missing key it first inserts the key with a value-initialised value, such as 0 or an empty string, so it changes the map and cannot be used on a const map. m.at(key) returns a reference to an existing value and throws std::out_of_range for a missing key, so it never inserts. m.find(key) returns an iterator to the element, or m.end() for a missing key, and never inserts or throws; check it before dereferencing. Use [] to insert or update, at when a missing key is an error, and find or contains to ask whether the key is there. A common bug is testing if (m[key]), which quietly adds every key it tests.

Key takeaways

• std::map and std::set keep their keys sorted: lookups, insertions and erasures take O(log n), and iteration follows the key order.
• operator[] inserts a missing key; find, contains and count only look, and at throws for a missing key.
• lower_bound(k) is the first key not less than k and upper_bound(k) the first key greater than k; together they give a half-open range, and either can be end().
• A comparator must be a strict weak ordering. With <=, the set kept three 3s, found none of them, and the sort read past the end of its vector; libc++’s debug mode named the bug.
• std::less<> lets lookups take a std::string_view without building a std::string: 1,000 lookups made 1,000 allocations without it and none with it.
• extract and merge move nodes between maps without copying or allocating, and can change a key.