How to Read cppreference, and What O(log n) Promises

David is reading about std::vector. Next to push_back the reference says "constant, amortised". Next to insert it says the cost is linear in the distance to the end. He asks the obvious question: "Then why would anyone ever write insert?"

It is a good question, and the answer is on the same page, if you know where to look. This lesson teaches you to read that page. After it, every cost in this track is something you can check for yourself instead of taking on trust.

The reference every C++ programmer keeps open

Two documents describe the STL. The first is the C++ standard itself, the official ISO document that every compiler follows. It is precise and long, and the published version costs money. The committee's working drafts are free, and they are what people read: N4659 is the final draft of C++17, N4861 of C++20, and eel.is/c++draft shows the current one as web pages.

The second is cppreference.com, a free reference written by volunteers from the standard. It has one page per function, with examples, and it marks what changed in each standard. It is the page working C++ programmers keep open. Read cppreference day to day, and go to the draft when you need the exact wording.

The anatomy of a reference page

Open the page for std::vector<T>::insert. It looks dense, but it always has the same parts in the same order, and four of them carry almost everything you need.

1. The signatures. These are the declarations: every way you can call the function. insert has several, numbered (1), (2) and so on, and the rest of the page refers to them by number. Here are its C++17 forms:

iterator insert( const_iterator pos, const T& value );                    (1)
iterator insert( const_iterator pos, T&& value );                         (2)
iterator insert( const_iterator pos, size_type count, const T& value );   (3)
template< class InputIt >
iterator insert( const_iterator pos, InputIt first, InputIt last );       (4)
iterator insert( const_iterator pos, std::initializer_list<T> ilist );    (5)

Read them for what they take and what they return. Every form takes pos, an iterator saying where to insert, and every form returns an iterator. Form (3) inserts count copies of a value.

2. The parameters. One line per name in the signatures. Here you learn that the new elements go before pos, which is easy to guess wrong.

3. The complexity. The cost, written as a promise. For form (1) it is constant plus linear in the distance between pos and the end. In plain words, every element after the insertion point must move one place to make room.

4. Iterator invalidation. A short paragraph near the top says which old iterators still work afterwards. For insert: if the vector had to grow, every iterator into it is now invalid. Otherwise, only those at or after the insertion point are. You met this idea in Lesson 4's doubts, and Module 11 shows it moving.

So David's answer is on the page. insert exists because sometimes you need an element in the middle, and the complexity line tells you exactly what that costs.

auto it = v.insert(v.begin() + 1, 15);

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v = {10, 20, 30};
    auto it = v.insert(v.begin() + 1, 15);
    std::cout << "inserted " << *it << ", now:";
    for (int x : v) std::cout << ' ' << x;
    std::cout << '\n';
    v.insert(v.end(), 3, 99);
    std::cout << "three 99s at the end:";
    for (int x : v) std::cout << ' ' << x;
    std::cout << '\n';
}

inserted 15, now: 10 15 20 30
three 99s at the end: 10 15 20 30 99 99 99

The complexity words

Reference pages describe costs in a few fixed words. Lesson 3 gave you three of them. Here is the full set you will meet in this track, each with one real operation that has it.

The last row needs a closer look, because it is the one David asked about. Amortised means "on average over many calls". Most calls to push_back are one step. Now and then the vector is full, so it moves to a bigger block of memory and copies every element. That one call is slow. Because the capacity grows by a factor each time, the slow calls are rare enough that the average stays constant.

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v;
    std::size_t last = v.capacity();
    std::cout << "capacity changes:";
    for (int i = 1; i <= 100; i++) {
        v.push_back(i);
        if (v.capacity() != last) {
            last = v.capacity();
            std::cout << ' ' << last;
        }
    }
    std::cout << '\n';
}

capacity changes: 1 2 4 8 16 32 64 128

Checking a promise by measuring it

A complexity line is a promise about growth, not a time in seconds. So the honest test is to grow n and watch. This program builds a vector of n numbers twice. First it uses push_back, amortised constant each. Then it inserts every number at the front, linear each, so the whole job grows like n squared.

#include <chrono>
#include <iostream>
#include <vector>
using namespace std::chrono;

int main()
{
    for (int n : {1000, 10000, 100000}) {
        auto t0 = steady_clock::now();
        std::vector<int> back;
        for (int i = 0; i < n; i++) back.push_back(i);
        auto t1 = steady_clock::now();
        std::vector<int> front;
        for (int i = 0; i < n; i++) front.insert(front.begin(), i);
        auto t2 = steady_clock::now();
        std::cout << "n = " << n << ": push_back " << duration_cast<microseconds>(t1 - t0).count()
                  << " us, insert at front " << duration_cast<microseconds>(t2 - t1).count() << " us\n";
    }
}

n = 1000: push_back 7 us, insert at front 25 us
n = 10000: push_back 56 us, insert at front 1943 us
n = 100000: push_back 472 us, insert at front 308680 us

Read the chart against the promises. Ten times the elements made push_back about eight to ten times slower: linear in total, constant per call. Inserting at the front got 78 times slower, then 159 times slower: each insert is linear, so the whole job grows like n squared. At 100,000 elements it took about 650 times longer than push_back. Nothing in the program changed except n, and the page told you this would happen.

"Since C++20" and the compiler you actually run

The C++ standard is revised every three years: C++11, 14, 17, 20, 23. Reference pages mark when something arrived, with a note such as (since C++20) beside a signature or a small (C++20) beside a name. This track teaches C++17, which every university lab and contest judge you are likely to meet supports.

Where C++20 makes something better, the lesson shows it in a separate box titled "In C++20", right after the C++17 version. Its code runs on the Playground at -std=c++20. You will see the first one just below, and one in most modules from Module 2 on.

#include <iostream>
#include <set>

int main()
{
    std::set<int> seen = {30, 10, 20};
    if (seen.count(20) > 0) std::cout << "20 is in the set\n";
}

20 is in the set

#include <iostream>
#include <set>

int main()
{
    std::set<int> seen = {30, 10, 20};
    if (seen.contains(20)) std::cout << "20 is in the set\n";
}

20 is in the set

One more honest line. A "since C++20" marker says what the standard contains, not what your compiler has finished building. The Playground runs GCC 12, and GCC 12 does not have everything C++20 promises. The best-known gap is std::format, a C++20 way to build formatted text, which arrived in GCC 13. When a lesson wants something like that, it shows the C++17 way and names the newer one with the compiler it needs. cppreference's "compiler support" page lists, for each feature, the first GCC version that has it.

std::vector<int> v = {1, 2, 3};
v.insert(2, 99);

#include <format>
#include <iostream>

int main() {
    std::cout << std::format("{} items\n", 3);
}

That completes the map. Module 1 now teaches the few C++ pieces the rest of the track uses, starting with the same program written in C and in C++.