C++ toolkit for coding rounds

C++ gives a coding round a large and fast standard library: a max-heap, sorted sets and maps with ordered queries, hash maps and an algorithm library for sorting, searching and counting. It also accepts code that is wrong without a word: a lookup that inserts, an unsigned size that wraps around, a sum that overflows into undefined behaviour, and input that is slow by default. This lesson goes through the containers and algorithms interview solutions use, reproduces each trap with the address and undefined-behaviour sanitizers switched on, measures the input methods with two standard libraries, and shows how to tell which C++23 features your compiler really has. Every program here was built with Apple clang 21.0.0 and GCC 16.2.0.

Containers and algorithms a round uses

One program uses the containers that most solutions need. It is built with both compilers, which print the same lines:

#include <algorithm>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <vector>

int main() {
    // priority_queue gives the largest element first; std::greater<> turns it into a min-heap.
    std::vector<int> scores = {40, 75, 62, 90};
    std::priority_queue<int> largest(scores.begin(), scores.end());
    std::priority_queue<int, std::vector<int>, std::greater<>> smallest(scores.begin(), scores.end());
    std::cout << "largest " << largest.top() << ", smallest " << smallest.top() << '\n';

    // A min-heap of (distance, node) pairs, as Dijkstra's algorithm uses it.
    std::priority_queue<std::pair<int, char>, std::vector<std::pair<int, char>>, std::greater<>> frontier;
    frontier.push({7, 'c'});
    frontier.push({2, 'a'});
    frontier.push({7, 'b'});
    while (!frontier.empty()) {
        auto [dist, node] = frontier.top();
        frontier.pop();
        std::cout << node << dist << ' ';
    }
    std::cout << '\n';

    // set and map keep keys sorted; their member lower_bound finds the first key not less than x in O(log n).
    std::set<int> slots = {9, 11, 14};
    auto next = slots.lower_bound(12);
    std::cout << "first slot at or after 12: " << *next << ", before it: " << *std::prev(next) << '\n';

    // unordered_map counts in average O(1); copy to a vector to sort the result.
    std::unordered_map<std::string, int> counts;
    for (std::string w : {"pear", "fig", "pear", "apple", "fig", "pear"}) ++counts[w];
    std::vector<std::pair<std::string, int>> byCount(counts.begin(), counts.end());
    std::ranges::sort(byCount, [](const auto& a, const auto& b) {
        return a.second != b.second ? a.second > b.second : a.first < b.first;
    });
    for (const auto& [word, n] : byCount) std::cout << word << '=' << n << ' ';
    std::cout << '\n';
}

"""Runs shell commands as you would type them in a terminal, and prints the session.

Each line of the script is one command. The session shows it after "$ ", then what it printed (standard output and
standard error together, as a terminal shows them), and, when the command fails, its exit status. A sanitizer report
is cut to its summary lines, and file paths in it to their last part, because the rest (addresses, process numbers,
the folders of the compiler) changes from run to run and from one computer to another.
"""

import os
import re
import subprocess

# Homebrew's folders (Apple silicon, then Intel Macs): the gcc formula installs g++-16 there.
HOMEBREW_BIN = ["/opt/homebrew/bin", "/usr/local/bin"]
REPORT_START = re.compile(r"^(?:=+|==\d+==.*)$")
ABSOLUTE_PATH = re.compile(r"(?:/[^/\s:]+)+/([^/\s:]+)")


def short_paths(line: str) -> str:
    return ABSOLUTE_PATH.sub(r"\1", line)


def tidy(output: str) -> list[str]:
    lines = []
    in_report = False
    for line in output.splitlines():
        if REPORT_START.match(line):
            in_report = True
        if "runtime error:" in line or line.startswith("SUMMARY:"):
            lines.append(short_paths(line))
        elif not in_report:
            lines.append(line)
    return lines


def run(script: str) -> None:
    env = dict(os.environ)
    env["PATH"] = os.pathsep.join([env.get("PATH", ""), *HOMEBREW_BIN])
    for command in script.strip().splitlines():
        command = command.strip()
        if not command:
            continue
        print(f"$ {command}")
        result = subprocess.run(command, shell=True, env=env, stdout=subprocess.PIPE, stderr=subprocess.STDOUT, text=True)
        for line in tidy(result.stdout):
            print(line)
        if result.returncode != 0:
            print(f"[exit status {result.returncode}]")

from session import run

# Built and run with both compilers.
run("""
clang++ -std=c++23 -Wall -Wextra containers.cpp -o containers && ./containers
g++-16 -std=c++23 -Wall -Wextra containers.cpp -o containers-gcc && ./containers-gcc
""")

$ clang++ -std=c++23 -Wall -Wextra containers.cpp -o containers && ./containers
largest 90, smallest 40
a2 b7 c7 
first slot at or after 12: 14, before it: 11
pear=3 fig=2 apple=1 
$ g++-16 -std=c++23 -Wall -Wextra containers.cpp -o containers-gcc && ./containers-gcc
largest 90, smallest 40
a2 b7 c7 
first slot at or after 12: 14, before it: 11
pear=3 fig=2 apple=1 

• std::priority_queue is a max-heap. Its default comparison is std::less, so top() is the largest element. Passing std::greater<> as the third template argument makes the smallest element the top, which Dijkstra’s algorithm and “k smallest” problems need. Pairs compare by their first member, then the second, so {7, 'b'} came out before {7, 'c'}.
• std::set and std::map keep keys sorted and answer ordered questions: lower_bound(12) is the first key not less than 12, and std::prev of it is the key just below.
• std::unordered_map counts with ++counts[w] in average O(1). It has no order, so copy it to a vector and sort when the output must be ordered; std::ranges::sort with a comparator sorts by count, then by word.

The costs the standard requires of each container are listed in the DSA toolkit lesson.

Search a set with its own lower_bound

std::lower_bound is a binary search, but on a std::set it walks: cppreference’s page on it notes that for iterators that are not random access, the number of iterator increments is linear, and that the member lower_bound of set and map should be preferred. The difference is easy to miss in a code review and impossible to miss in a time limit.

#include <algorithm>
#include <chrono>
#include <iostream>
#include <set>

// 500 queries for "the first element at or after x" in a set of 100,000 even numbers, two ways.
int main() {
    std::set<int> s;
    for (int i = 0; i < 100'000; ++i) s.insert(2 * i);

    auto timed = [](const char* label, auto&& query) {
        auto start = std::chrono::steady_clock::now();
        long long total = 0;
        for (int x = 1; x < 200'000; x += 400) total += query(x);
        auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::steady_clock::now() - start);
        std::cout << label << "total " << total << ", " << ms.count() << " ms\n";
    };
    timed("s.lower_bound(x):                 ", [&](int x) { return *s.lower_bound(x); });
    timed("std::lower_bound(s.begin(), ...): ", [&](int x) { return *std::lower_bound(s.begin(), s.end(), x); });
}

from session import run

run("""
clang++ -std=c++23 -O2 -Wall -Wextra set_search.cpp -o set_search && ./set_search
""")

$ clang++ -std=c++23 -O2 -Wall -Wextra set_search.cpp -o set_search && ./set_search
s.lower_bound(x):                 total 49901000, 0 ms
std::lower_bound(s.begin(), ...): total 49901000, 977 ms

Both find the same elements. The member function takes O(log n) per query; std::lower_bound makes O(log n) comparisons but moves the iterator up to n steps each time, so the 500 queries cost about 500 × 100,000 steps instead of 500 × 17.

Traps the compiler accepts

The next two programs compile cleanly with -Wall -Wextra. They are built here with -fsanitize=address,undefined, which adds checks that report the mistake while the program runs:

#include <cstddef>
#include <iostream>
#include <map>
#include <numeric>
#include <string>
#include <vector>

int main() {
    std::cout << std::unitbuf;  // print each line at once, so it appears before any sanitizer report

    // Reading a missing key with [] inserts it.
    std::map<std::string, int> score;
    if (score["asha"] == 0) std::cout << "asha has no score\n";
    std::cout << "size after one lookup: " << score.size() << ", contains(\"ravi\"): " << score.contains("ravi")
              << ", size still " << score.size() << '\n';

    // size() is unsigned: on an empty vector, size() - 1 wraps around to the largest size_t.
    std::vector<int> empty;
    std::cout << "empty.size() - 1 = " << empty.size() - 1 << '\n';

    // The type of accumulate's start value is the type of the sum.
    std::vector<int> big = {2'000'000'000, 2'000'000'000, 2'000'000'000};
    long long wide = std::accumulate(big.begin(), big.end(), 0LL);
    std::cout << "accumulate from 0LL: " << wide << '\n';
    int narrow = std::accumulate(big.begin(), big.end(), 0);
    std::cout << "accumulate from 0:   " << narrow << '\n';

    // (lo + hi) / 2 overflows for large ends; std::midpoint (C++20) and lo + (hi - lo) / 2 do not.
    int lo = 2'000'000'000, hi = 2'100'000'000;
    std::cout << "midpoint " << std::midpoint(lo, hi) << ", lo + (hi - lo) / 2 = " << lo + (hi - lo) / 2 << '\n';
    int naive = (lo + hi) / 2;
    std::cout << "(lo + hi) / 2 = " << naive << '\n';
}

#include <cstddef>
#include <iostream>
#include <vector>

// The sum of the steps between neighbours. The loop bound is wrong when v is empty: v.size() - 1 wraps around.
long long sum_of_steps(const std::vector<int>& v) {
    long long total = 0;
    for (std::size_t i = 0; i < v.size() - 1; ++i) total += v[i + 1] - v[i];
    return total;
}

int main() {
    std::cout << std::unitbuf;
    std::cout << sum_of_steps({3, 8, 6}) << '\n';
    std::cout << sum_of_steps({5}) << '\n';
    std::vector<int> none;
    none.reserve(4);  // room for 4 elements, none of them in use
    std::cout << sum_of_steps(none) << '\n';
}

from session import run

# Built with the address and undefined-behaviour sanitizers, which check the program while it runs.
run("""
clang++ -std=c++23 -g -Wall -Wextra -fsanitize=address,undefined traps.cpp -o traps && ./traps
clang++ -std=c++23 -g -Wall -Wextra -fsanitize=address,undefined oob.cpp -o oob && ./oob
""")

$ clang++ -std=c++23 -g -Wall -Wextra -fsanitize=address,undefined traps.cpp -o traps && ./traps
asha has no score
size after one lookup: 1, contains("ravi"): 0, size still 1
empty.size() - 1 = 18446744073709551615
accumulate from 0LL: 6000000000
accumulate.h:30:32: runtime error: signed integer overflow: 2000000000 + 2000000000 cannot be represented in type 'int'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior accumulate.h:30:32 
accumulate from 0:   1705032704
midpoint 2050000000, lo + (hi - lo) / 2 = 2050000000
traps.cpp:31:21: runtime error: signed integer overflow: 2000000000 + 2100000000 cannot be represented in type 'int'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior traps.cpp:31:21 
(lo + hi) / 2 = -97483648
$ clang++ -std=c++23 -g -Wall -Wextra -fsanitize=address,undefined oob.cpp -o oob && ./oob
3
0
SUMMARY: AddressSanitizer: container-overflow oob.cpp:8 in sum_of_steps(std::__1::vector<int, std::__1::allocator<int>> const&)
[exit status 134]

• m[key] inserts. Reading a missing key with operator[] creates it with a default value, so the check for Asha’s score grew the map to size 1. Test membership with contains (C++20) or find, which change nothing.
• Sizes are unsigned. empty.size() - 1 is not -1 but 18,446,744,073,709,551,615, the largest size_t. In oob.cpp the loop i < v.size() - 1 therefore runs past the end of an empty vector; with room reserved but no elements in use, AddressSanitizer reported a container overflow at line 8 and stopped the program. Write i + 1 < v.size().
• std::accumulate adds in the type of its start value. With 0, the sum of three values of 2 × 10⁹ is computed in int: the undefined-behaviour sanitizer reported a signed integer overflow inside accumulate, and the program printed 1,705,032,704. With 0LL it printed 6,000,000,000.
• Signed overflow is undefined behaviour. (lo + hi) / 2 with ends near 2 × 10⁹ overflowed and printed a negative number. std::midpoint (C++20) and lo + (hi - lo) / 2 give 2,050,000,000.

Without the sanitizers, the first and last results are just wrong numbers, and an optimiser may even transform code on the assumption that signed overflow never happens. Build practice code with the sanitizers on, and keep -O2 builds for timing.

Fast input and output

C++ streams start synchronised with C’s standard input and output, and cin is tied to cout, so every read first flushes the output. cppreference says that turning the synchronisation off “may be considerably faster in some cases”. How much depends on the standard library, so the same reader was built with both:

#include <chrono>
#include <cstring>
#include <iostream>

// Reads a count and then that many integers from standard input, and prints their sum and the time it took.
// With the argument "fast", the stream is first untied from C's stdio and from cout.
int main(int argc, char** argv) {
    bool fast = argc > 1 && std::strcmp(argv[1], "fast") == 0;
    auto start = std::chrono::steady_clock::now();
    if (fast) {
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
    }
    int n;
    std::cin >> n;
    long long sum = 0;
    for (int i = 0; i < n; ++i) {
        int x;
        std::cin >> x;
        sum += x;
    }
    auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::steady_clock::now() - start).count();
    std::cout << (fast ? "unsynced cin: " : "default cin:  ") << "sum " << sum << ", " << ms << " ms\n";
}

#include <chrono>
#include <cstdio>

int main() {
    auto start = std::chrono::steady_clock::now();
    int n;
    if (std::scanf("%d", &n) != 1) return 1;
    long long sum = 0;
    for (int i = 0; i < n; ++i) {
        int x;
        if (std::scanf("%d", &x) != 1) return 1;
        sum += x;
    }
    auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::steady_clock::now() - start).count();
    std::printf("scanf:        sum %lld, %lld ms\n", sum, static_cast<long long>(ms));
}

import random

# 200,000 integers between -10^9 and 10^9, ten to a line, after their count: a typical large test input.
random.seed(1)
n = 200_000
values = [random.randint(-10**9, 10**9) for _ in range(n)]
with open("numbers.txt", "w") as f:
    f.write(f"{n}\n")
    for i in range(0, n, 10):
        f.write(" ".join(map(str, values[i : i + 10])) + "\n")
print(f"wrote {n} numbers, sum {sum(values)}")

from session import run

# The same reader built with GCC 16 (libstdc++) and with Apple clang (libc++), then C's scanf for comparison.
run("""
python3 make_numbers.py
g++-16 -std=c++23 -O2 read_ints.cpp -o read_gcc && ./read_gcc < numbers.txt && ./read_gcc fast < numbers.txt
clang++ -std=c++23 -O2 read_ints.cpp -o read_clang && ./read_clang < numbers.txt && ./read_clang fast < numbers.txt
clang++ -std=c++23 -O2 read_scanf.cpp -o read_scanf && ./read_scanf < numbers.txt
""")

$ python3 make_numbers.py
wrote 200000 numbers, sum -213236582986
$ g++-16 -std=c++23 -O2 read_ints.cpp -o read_gcc && ./read_gcc < numbers.txt && ./read_gcc fast < numbers.txt
default cin:  sum -213236582986, 566 ms
unsynced cin: sum -213236582986, 15 ms
$ clang++ -std=c++23 -O2 read_ints.cpp -o read_clang && ./read_clang < numbers.txt && ./read_clang fast < numbers.txt
default cin:  sum -213236582986, 845 ms
unsynced cin: sum -213236582986, 929 ms
$ clang++ -std=c++23 -O2 read_scanf.cpp -o read_scanf && ./read_scanf < numbers.txt
scanf:        sum -213236582986, 29 ms

With GCC’s libstdc++, the standard library of most judges, std::ios::sync_with_stdio(false) and cin.tie(nullptr) made the same loop dozens of times faster. With Apple clang’s libc++ on macOS, both cin versions stayed slow, while scanf was fast. So write the two lines at the top of main for a judge, and if you practise on a Mac, do not judge a solution’s speed by its cin time there. After switching synchronisation off, do not mix cin with scanf, or cout with printf, in one program. For output, end lines with '\n' rather than std::endl, which also flushes the stream every time.

Which C++23 features your compiler has

Choosing -std=c++23 asks for the C++23 language, but the library features come from the compiler’s standard library, and each library adds them at its own pace. Feature-test macros such as __cpp_lib_ranges_enumerate tell a program what it got:

#include <print>
#include <ranges>
#include <vector>

int main() {
    std::vector<int> scores = {72, 100, 9};
    std::vector<char> names = {'a', 'b', 'c'};
    auto doubled = scores | std::views::transform([](int s) { return 2 * s; }) | std::ranges::to<std::vector>();
    for (auto [name, score] : std::views::zip(names, doubled)) std::print("{}={} ", name, score);
    std::println("");
#ifdef __cpp_lib_ranges_enumerate
    for (auto [i, s] : std::views::enumerate(scores)) std::print("{}:{} ", i, s);
    std::println("");
#else
    std::println("views::enumerate: not in this standard library");
#endif
}

#include <print>
#include <ranges>
#include <vector>

int main() {
    std::vector<int> scores = {72, 100, 9};
    for (auto [i, s] : std::views::enumerate(scores)) std::print("{}:{} ", i, s);
    std::println("");
}

from session import run

# C++23 library features with each compiler's own standard library: libc++ (Apple clang) and libstdc++ (GCC 16).
run("""
clang++ -std=c++23 -Wall -Wextra features.cpp -o features && ./features
g++-16 -std=c++23 -Wall -Wextra features.cpp -o features-gcc && ./features-gcc
clang++ -std=c++23 enumerate.cpp -o enumerate
g++-16 -std=c++23 enumerate.cpp -o enumerate-gcc && ./enumerate-gcc
""")

$ clang++ -std=c++23 -Wall -Wextra features.cpp -o features && ./features
a=144 b=200 c=18 
views::enumerate: not in this standard library
$ g++-16 -std=c++23 -Wall -Wextra features.cpp -o features-gcc && ./features-gcc
a=144 b=200 c=18 
0:72 1:100 2:9 
$ clang++ -std=c++23 enumerate.cpp -o enumerate
enumerate.cpp:7:36: error: no member named 'enumerate' in namespace 'std::ranges::views'
    7 |     for (auto [i, s] : std::views::enumerate(scores)) std::print("{}:{} ", i, s);
      |                                    ^~~~~~~~~
1 error generated.
[exit status 1]
$ g++-16 -std=c++23 enumerate.cpp -o enumerate-gcc && ./enumerate-gcc
0:72 1:100 2:9 

Both libraries had std::print, std::ranges::to and views::zip. Apple clang’s libc++ did not have views::enumerate, so the file that calls it failed to compile there, while GCC 16 compiled and ran it. Platforms add another layer: HackerRank’s execution environment page offers “C++20” built with G++ 8.3.0 and “C++23” built with G++ 14.2.0, and a compiler as old as G++ 8.3.0 predates most of the C++20 library, so on such a platform pick the option with the newer compiler, whatever its label. When in doubt, a plain loop with an index is never missing.

Interview questions

Fresher · Why is std::priority_queue<int> a max-heap, and how do you make a min-heap?

std::priority_queue takes a comparison object, std::less<T> by default, and keeps the element that compares greatest under it at the top, so with less the largest value is top(). That is the opposite of Python’s heapq, Java’s PriorityQueue and Go’s container/heap, which put the smallest first. For a min-heap, pass the container and std::greater<> as template arguments: std::priority_queue<int, std::vector<int>, std::greater<>>. For pairs such as (distance, node) the same works, because pairs compare by their first member and then the second. Negating values also works but is easy to forget when reading the top, and it fails for the smallest int, whose negation overflows.

Key takeaways

• priority_queue is a max-heap; use std::greater<> for a min-heap of numbers or pairs.
• On set and map, call the member lower_bound: std::lower_bound on their iterators walks linearly.
• m[key] inserts; use contains or find to look.
• Sizes are unsigned, accumulate sums in the type of its start value, and signed overflow is undefined: practise with -fsanitize=address,undefined.
• Untie and unsync the streams for judges; GCC’s cin became dozens of times faster here, Apple’s libc++ did not.
• Check library features with your actual compiler, or with feature-test macros, before relying on them.