std::vector: the container to reach for first

std::vector<T> is C++’s resizable array. It keeps any number of values of one type T side by side in a single block of memory, adds new values at the end quickly, gives you any element by its position in one step, and frees its memory by itself when it goes out of scope. Because the elements sit next to each other, a vector is also the fastest standard container to loop over. That is why the C++ Core Guidelines tell you to use vector by default and to choose another container only when you have a reason to.

This lesson builds and reads vectors first. Then it looks inside: how a vector’s size differs from its capacity, what the two common standard libraries do when a vector grows, why growing leaves old pointers and references dangling, and what happens when an index is out of range, which depends on the compiler, the optimisation level and the library. The examples use two compilers: Apple clang with its standard library, libc++, and GCC 16 with libstdc++.

Create, fill and read a vector

// Creating, growing and reading a std::vector.
#include <cstddef>
#include <print>
#include <string>
#include <vector>

int main() {
    std::vector<int> marks{71, 64, 88};      // three elements, from a braced list
    marks.push_back(92);                     // add at the end
    marks.push_back(57);
    std::println("marks: {}", marks);        // C++23 prints a whole range
    std::println("size {}, first {}, last {}", marks.size(), marks.front(), marks.back());

    int total = 0;
    for (int m : marks) total += m;          // range-for visits every element in order
    std::println("total {}", total);

    for (std::size_t i = 0; i < marks.size(); ++i) {   // an index loop when the position matters
        if (marks[i] < 60) std::println("marks[{}] = {} needs a second attempt", i, marks[i]);
    }

    std::vector<int> five_zeros(5);          // (count): five value-initialised ints
    std::vector<int> five_sevens(5, 7);      // (count, value)
    std::vector<int> just_five{5};           // braces: one element, the number 5
    std::println("{} {} {}", five_zeros, five_sevens, just_five);

    std::vector<std::string> names;
    names.emplace_back(3, 'a');              // builds std::string(3, 'a') in place: "aaa"
    names.push_back("Ravi");                 // builds a temporary string, then moves it in
    std::println("{}", names);
}

from session import run

# basics.cpp built and run with Apple clang and its library, libc++, then with GCC 16 and libstdc++.
run("""
clang++ -std=c++23 -Wall -Wextra basics.cpp -o basics
./basics
g++-16 -std=c++23 -Wall -Wextra basics.cpp -o basics-gcc
./basics-gcc
""")

$ clang++ -std=c++23 -Wall -Wextra basics.cpp -o basics
$ ./basics
marks: [71, 64, 88, 92, 57]
size 5, first 71, last 57
total 372
marks[4] = 57 needs a second attempt
[0, 0, 0, 0, 0] [7, 7, 7, 7, 7] [5]
["aaa", "Ravi"]
$ g++-16 -std=c++23 -Wall -Wextra basics.cpp -o basics-gcc
$ ./basics-gcc
marks: [71, 64, 88, 92, 57]
size 5, first 71, last 57
total 372
marks[4] = 57 needs a second attempt
[0, 0, 0, 0, 0] [7, 7, 7, 7, 7] [5]
["aaa", "Ravi"]

The two programs print the same lines. What each part does:

• std::vector<int> marks{71, 64, 88}; creates a vector of three int elements from a braced list. The type in the angle brackets is the element type, and the header is <vector>.
• push_back(x) adds an element at the end. size() says how many elements there are, front() and back() give the first and the last, and marks[i] gives the element at index i, which runs from 0 to size() - 1.
• std::println("{}", marks) prints the whole vector in square brackets. Printing ranges this way is new in C++23; older code loops and prints each element.
• The range-for loop visits every element in order. For large elements such as strings, write for (const std::string& name : names) so that each element is read in place instead of copied.
• When the position matters, loop over the indexes with std::size_t, the unsigned type that size() returns. With an int index, i < marks.size() compares a signed number with an unsigned one, and both compilers warn about it under -Wall -Wextra.

Two details catch almost everyone once:

• Parentheses and braces mean different things. std::vector<int> v(5) holds five zeros and v(5, 7) holds five sevens, because parentheses pass a count and a value. std::vector<int> v{5} holds a single element, the number 5: braces list the elements.
• emplace_back builds the element in place. names.emplace_back(3, 'a') passes its arguments to the std::string constructor, which builds "aaa" directly in the vector’s memory. push_back("Ravi") first makes a temporary string and then moves it in. For values you already have, push_back is just as good.

Size, capacity and growth

A vector has two numbers. Its size is how many elements it holds. Its capacity is how many elements its buffer, the block of memory where the elements live, has room for. The vector object itself is small and fixed; the buffer is allocated on the heap:

While there is spare capacity, push_back just builds the new element in the next free slot. When the buffer is full, it has to allocate a bigger buffer, move every element into it, free the old buffer and only then add the new element. The standard does not say how much bigger. It only requires adding at the end to take amortised constant time, which rules out growing by a fixed number of slots. This program records what the libraries really do:

// Watches a vector grow: its capacity after each push_back that changes it, and how many elements had to move.
#include <cstddef>
#include <print>
#include <vector>

int main() {
    std::vector<int> v;
    std::println("empty: size {}, capacity {}, the vector object itself is {} bytes", v.size(), v.capacity(), sizeof v);
    int allocations = 0;
    std::size_t moved = 0;
    for (int i = 1; i <= 1000; ++i) {
        std::size_t old_capacity = v.capacity();
        std::size_t old_size = v.size();
        v.push_back(i);
        if (v.capacity() != old_capacity) {      // push_back needed a bigger buffer
            ++allocations;
            moved += old_size;                   // every element so far went to the new buffer
            std::println("size {:4}  capacity {:4}", v.size(), v.capacity());
        }
    }
    std::println("1000 push_backs: {} allocations, {} elements moved", allocations, moved);

    std::vector<int> w;
    w.reserve(1000);                             // one allocation, big enough for everything
    const int* buffer = w.data();
    for (int i = 1; i <= 1000; ++i) w.push_back(i);
    std::println("with reserve(1000) first: capacity {}, same buffer all along: {}", w.capacity(), w.data() == buffer);
    std::println("still {} bytes for the vector object, {} bytes in its buffer", sizeof w, w.capacity() * sizeof(int));
}

from session import run

# The growth of one vector, recorded with libc++ (Apple clang) and compared with libstdc++ (GCC 16).
run("""
clang++ -std=c++23 -Wall -Wextra growth.cpp -o growth
./growth
g++-16 -std=c++23 -Wall -Wextra growth.cpp -o growth-gcc
./growth > libcxx.txt
./growth-gcc > libstdcxx.txt
diff libcxx.txt libstdcxx.txt && echo "libstdc++ printed exactly the same"
""")

$ clang++ -std=c++23 -Wall -Wextra growth.cpp -o growth
$ ./growth
empty: size 0, capacity 0, the vector object itself is 24 bytes
size    1  capacity    1
size    2  capacity    2
size    3  capacity    4
size    5  capacity    8
size    9  capacity   16
size   17  capacity   32
size   33  capacity   64
size   65  capacity  128
size  129  capacity  256
size  257  capacity  512
size  513  capacity 1024
1000 push_backs: 11 allocations, 1023 elements moved
with reserve(1000) first: capacity 1000, same buffer all along: true
still 24 bytes for the vector object, 4000 bytes in its buffer
$ g++-16 -std=c++23 -Wall -Wextra growth.cpp -o growth-gcc
$ ./growth > libcxx.txt
$ ./growth-gcc > libstdcxx.txt
$ diff libcxx.txt libstdcxx.txt && echo "libstdc++ printed exactly the same"
libstdc++ printed exactly the same

Both libraries double the capacity whenever the buffer is full: 1, 2, 4 and so on up to 1,024. For 1,000 push_back calls that is 11 allocations, and the 10 that replaced an existing buffer moved 1 + 2 + 4 + … + 512 = 1,023 elements, about one move per element. Doubling is what keeps the cost down: each reallocation moves one element more than all the earlier ones together, so the total stays below the final capacity, and so below twice the size, however long the vector grows.

When you know the final size, reserve(n) allocates once. The second vector reserved 1,000 slots and kept the same buffer through all 1,000 calls. The vector object stayed 24 bytes throughout: both libraries store three pointers in it, and the elements live in the buffer, 4,000 bytes here.

Three more functions change these numbers:

• resize(n) changes the size: it adds value-initialised elements, zeros for int, or removes elements from the end. reserve(n) changes only the capacity and never adds elements.
• clear() removes every element but keeps the buffer, so the capacity stays the same.
• shrink_to_fit() asks the vector to give its spare capacity back. The standard calls it a non-binding request, so a library may keep the memory.

Growing moves the elements, and old references dangle

Reallocation has a consequence that causes many C++ bugs. A pointer, a reference or an iterator to an element points into the buffer, and after a reallocation that buffer is gone:

// A reference into a vector, kept across a push_back that reallocates.
#include <print>
#include <vector>

int main() {
    std::vector<int> scores{10, 20, 30};
    int& first = scores[0];          // refers to the element inside the vector's buffer
    std::println("capacity before: {}", scores.capacity());
    scores.push_back(40);            // the buffer is full: a new one is allocated, the old one freed
    std::println("capacity after: {}", scores.capacity());
    std::println("first = {}", first);   // reads the freed buffer: undefined behaviour
}

The compiler accepts this program, and without help the mistake is invisible: the last line reads whatever happens to be in the freed memory. AddressSanitizer, a checker built into Clang and GCC that you switch on with -fsanitize=address, stops the program at the bad read:

from session import run

# AddressSanitizer catches the read through the old reference. grep keeps the key lines of its report, and sed hides
# the addresses, which change on every run.
run("""
clang++ -std=c++23 -g -fsanitize=address dangling.cpp -o dangling
ASAN_OPTIONS=symbolize=0 ./dangling 2>&1 | grep -E "ERROR|of size|located|freed by|allocated by" | sed -E 's/==[0-9]+==//; s/0x[0-9a-f]+/0x…/g'
""")

$ clang++ -std=c++23 -g -fsanitize=address dangling.cpp -o dangling
$ ASAN_OPTIONS=symbolize=0 ./dangling 2>&1 | grep -E "ERROR|of size|located|freed by|allocated by" | sed -E 's/==[0-9]+==//; s/0x[0-9a-f]+/0x…/g'
ERROR: AddressSanitizer: heap-use-after-free on address 0x… at pc 0x… bp 0x… sp 0x…
READ of size 4 at 0x… thread T0
0x… is located 0 bytes inside of 12-byte region [0x…,0x…)
freed by thread T0 here:
previously allocated by thread T0 here:

The report names the bug, a heap-use-after-free, and says the read landed inside a 12-byte region that the program had already freed: the old buffer of three int values. The rule, from the standard’s section on vector modifiers: a call that makes the size larger than the capacity reallocates, and reallocation invalidates every reference, pointer and iterator to the elements. push_back, emplace_back, insert, resize and reserve can all do it. Without a reallocation, an insertion still invalidates those at or after the insertion point. Safe habits:

• Keep an index instead of a pointer or reference. scores[0] is still the first element after any growth.
• Take references just before you use them, after the last call that can add elements.
• Never add elements to a vector while a range-for loop is walking over it: the loop’s hidden iterators dangle in the same way.

Reading past the end: one bug, four results

marks[i] does not check i. The standard states a precondition, i < size(), and a call that breaks it has undefined behaviour: the standard makes no promise about what happens. Here is the most common way to break it, a loop that runs one step too far:

// An off-by-one loop: i <= size() reads one element past the end of the vector.
#include <cstddef>
#include <print>
#include <vector>

int total(const std::vector<int>& marks) {
    int sum = 0;
    for (std::size_t i = 0; i <= marks.size(); ++i) sum += marks[i];   // bug: should be i < marks.size()
    return sum;
}

int main() {
    std::vector<int> marks{71, 64, 88, 92, 57};
    std::println("total = {}", total(marks));   // the right answer is 372
}

from session import run

# One program with an off-by-one loop, built four ways: two compilers, without and with optimisation.
run("""
clang++ -std=c++23 -O0 oob.cpp -o oob-clang-O0
./oob-clang-O0
clang++ -std=c++23 -O2 oob.cpp -o oob-clang-O2
./oob-clang-O2
g++-16 -std=c++23 -O0 oob.cpp -o oob-gcc-O0
./oob-gcc-O0
g++-16 -std=c++23 -O2 oob.cpp -o oob-gcc-O2
./oob-gcc-O2
""")

$ clang++ -std=c++23 -O0 oob.cpp -o oob-clang-O0
$ ./oob-clang-O0
total = 372
$ clang++ -std=c++23 -O2 oob.cpp -o oob-clang-O2
$ ./oob-clang-O2
total = 0
$ g++-16 -std=c++23 -O0 oob.cpp -o oob-gcc-O0
$ ./oob-gcc-O0
/opt/homebrew/Cellar/gcc/16.2.0/include/c++/16/bits/stl_vector.h:1272: constexpr std::vector< <template-parameter-1-1>, <template-parameter-1-2> >::const_reference std::vector< <template-parameter-1-1>, <template-parameter-1-2> >::operator[](size_type) const [with _Tp = int; _Alloc = std::allocator<int>; const_reference = const int&; size_type = long unsigned int]: Assertion '__n < this->size()' failed.
[stopped by SIGABRT: a shell reports exit status 134]
$ g++-16 -std=c++23 -O2 oob.cpp -o oob-gcc-O2
$ ./oob-gcc-O2
total = 372

The same source gave four results:

• Clang without optimisation printed 372, the right total. The sixth read found a 0 in the memory just after the buffer, so the bug left no trace.
• Clang with -O2 printed 0. The optimiser worked out the whole total while compiling, and one of the six values it adds does not exist, so the result had no defined value. Clang could print anything, and it printed 0.
• GCC without optimisation stopped with a failed assertion. Since GCC 15, libstdc++ switches on its debug assertions in builds without optimisation; -D_GLIBCXX_NO_ASSERTIONS turns them off again.
• GCC with -O2 printed 372, and an optimised build checks nothing.

A test that prints the right answer proves nothing about a bug like this one.

Three ways to catch a bad index

Each of these turns the same bug into an error you can see, at the faulty read:

// The same off-by-one loop, with at() instead of [].
#include <cstddef>
#include <print>
#include <stdexcept>
#include <vector>

int total(const std::vector<int>& marks) {
    int sum = 0;
    for (std::size_t i = 0; i <= marks.size(); ++i) sum += marks.at(i);   // at() checks i < size()
    return sum;
}

int main() {
    std::vector<int> marks{71, 64, 88, 92, 57};
    try {
        std::println("total = {}", total(marks));
    } catch (const std::out_of_range& e) {
        std::println("caught std::out_of_range: {}", e.what());
    }
}

from session import run

# Three ways to catch the off-by-one read: at(), a hardened standard library and AddressSanitizer.
run("""
# 1. at() checks the index and throws std::out_of_range
clang++ -std=c++23 oob_at.cpp -o oob-at
./oob-at
g++-16 -std=c++23 oob_at.cpp -o oob-at-gcc
./oob-at-gcc
# 2. A hardened library checks operator[] itself, even with -O2
clang++ -std=c++23 -O2 -D_LIBCPP_HARDENING_MODE=_LIBCPP_HARDENING_MODE_FAST oob.cpp -o oob-fast
./oob-fast
clang++ -std=c++23 -O2 -D_LIBCPP_HARDENING_MODE=_LIBCPP_HARDENING_MODE_DEBUG oob.cpp -o oob-debug
./oob-debug
g++-16 -std=c++23 -O2 -D_GLIBCXX_ASSERTIONS oob.cpp -o oob-assertions
./oob-assertions
# 3. AddressSanitizer checks every memory access (key lines of its report, addresses hidden)
clang++ -std=c++23 -g -fsanitize=address oob.cpp -o oob-asan
ASAN_OPTIONS=symbolize=0 ./oob-asan 2>&1 | grep -E "ERROR|of size|located" | sed -E 's/==[0-9]+==//; s/0x[0-9a-f]+/0x…/g'
""")

# 1. at() checks the index and throws std::out_of_range
$ clang++ -std=c++23 oob_at.cpp -o oob-at
$ ./oob-at
caught std::out_of_range: vector
$ g++-16 -std=c++23 oob_at.cpp -o oob-at-gcc
$ ./oob-at-gcc
caught std::out_of_range: vector::_M_range_check: __n (which is 5) >= this->size() (which is 5)
# 2. A hardened library checks operator[] itself, even with -O2
$ clang++ -std=c++23 -O2 -D_LIBCPP_HARDENING_MODE=_LIBCPP_HARDENING_MODE_FAST oob.cpp -o oob-fast
$ ./oob-fast
[stopped by SIGTRAP: a shell reports exit status 133]
$ clang++ -std=c++23 -O2 -D_LIBCPP_HARDENING_MODE=_LIBCPP_HARDENING_MODE_DEBUG oob.cpp -o oob-debug
$ ./oob-debug
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__vector/vector.h:419: libc++ Hardening assertion __n < size() failed: vector[] index out of bounds
[stopped by SIGABRT: a shell reports exit status 134]
$ g++-16 -std=c++23 -O2 -D_GLIBCXX_ASSERTIONS oob.cpp -o oob-assertions
$ ./oob-assertions
/opt/homebrew/Cellar/gcc/16.2.0/include/c++/16/bits/stl_vector.h:1272: constexpr std::vector< <template-parameter-1-1>, <template-parameter-1-2> >::const_reference std::vector< <template-parameter-1-1>, <template-parameter-1-2> >::operator[](size_type) const [with _Tp = int; _Alloc = std::allocator<int>; const_reference = const int&; size_type = long unsigned int]: Assertion '__n < this->size()' failed.
[stopped by SIGABRT: a shell reports exit status 134]
# 3. AddressSanitizer checks every memory access (key lines of its report, addresses hidden)
$ clang++ -std=c++23 -g -fsanitize=address oob.cpp -o oob-asan
$ ASAN_OPTIONS=symbolize=0 ./oob-asan 2>&1 | grep -E "ERROR|of size|located" | sed -E 's/==[0-9]+==//; s/0x[0-9a-f]+/0x…/g'
ERROR: AddressSanitizer: heap-buffer-overflow on address 0x… at pc 0x… bp 0x… sp 0x…
READ of size 4 at 0x… thread T0
0x… is located 0 bytes after 20-byte region [0x…,0x…)
allocated by thread T0 here:

1. at(i) checks every call and throws std::out_of_range, which the program can catch. The message is the library’s own: libc++ says only vector, while libstdc++ names the index and the size.
2. A hardened standard library checks operator[] itself, even in an optimised build. In libc++ you choose a hardening mode with -D_LIBCPP_HARDENING_MODE=…. The fast mode, which the libc++ documentation recommends for production, keeps only cheap checks and stops the program with a trap, without a message (SIGTRAP above). The debug mode prints the failed check first and is meant for testing. In libstdc++, -D_GLIBCXX_ASSERTIONS does the same job in any build.
3. AddressSanitizer (ASan) checks every memory access, not just the library’s. Its report says the read was 0 bytes after a 20-byte region, the buffer of five int values. The Clang documentation puts its typical cost at twice the run time, so it is for testing, not for production.

Removing elements: std::erase and std::erase_if

Since C++20, two functions remove elements by value or by a test, and return how many they removed:

// Removing elements: std::erase and std::erase_if (C++20), and the erase-remove idiom they replace.
#include <algorithm>
#include <print>
#include <vector>

int main() {
    std::vector<int> runs{4, 0, 6, 0, 1, 0, 4};
    auto removed = std::erase(runs, 0);                          // every element equal to 0
    std::println("std::erase removed {}: {}", removed, runs);

    std::vector<int> marks{71, 34, 88, 29, 57};
    removed = std::erase_if(marks, [](int m) { return m < 35; }); // every element the test accepts
    std::println("std::erase_if removed {}: {}", removed, marks);

    std::vector<int> old_style{4, 0, 6, 0, 1, 0, 4};
    auto new_end = std::remove(old_style.begin(), old_style.end(), 0);  // moves the kept elements forward
    std::println("after std::remove: size {} (the tail is unspecified)", old_style.size());
    old_style.erase(new_end, old_style.end());                   // ...and erase() drops the tail
    std::println("erase-remove idiom: {}", old_style);

    std::vector<int> v{1, 2, 3, 4, 5, 6};
    for (auto it = v.begin(); it != v.end();) {                  // removing while looping:
        if (*it % 2 == 0) it = v.erase(it);                      // erase returns the next valid iterator
        else ++it;
    }
    std::println("odd numbers kept: {}", v);
}

from session import run

run("""
clang++ -std=c++23 -Wall -Wextra erase.cpp -o erase
./erase
g++-16 -std=c++23 -Wall -Wextra erase.cpp -o erase-gcc
./erase-gcc
""")

$ clang++ -std=c++23 -Wall -Wextra erase.cpp -o erase
$ ./erase
std::erase removed 3: [4, 6, 1, 4]
std::erase_if removed 2: [71, 88, 57]
after std::remove: size 7 (the tail is unspecified)
erase-remove idiom: [4, 6, 1, 4]
odd numbers kept: [1, 3, 5]
$ g++-16 -std=c++23 -Wall -Wextra erase.cpp -o erase-gcc
$ ./erase-gcc
std::erase removed 3: [4, 6, 1, 4]
std::erase_if removed 2: [71, 88, 57]
after std::remove: size 7 (the tail is unspecified)
erase-remove idiom: [4, 6, 1, 4]
odd numbers kept: [1, 3, 5]

• std::erase(runs, 0) removes every element equal to 0.
• std::erase_if(marks, test) removes every element for which the test returns true. The test here is a lambda, a small function written in place; lambdas have a lesson of their own.
• Older code writes the erase-remove idiom. std::remove moves the elements to keep to the front and returns where they end, without changing the size (still 7 in the output), and erase then cuts off the tail. The standard defines std::erase as exactly these two steps, so the new form is never slower, and it is harder to get wrong.
• To remove elements during a loop, use the iterator that v.erase(it) returns. It points to the element after the removed one, while it itself is invalid after the call.

Each removal moves every later element one place forward, so removing from the front of a large vector is slow. One std::erase_if pass moves each element at most once, however many it removes.

Your turn: two vector functions

Write two functions in the file below, then build and run it:

1. remove_duplicates_keep_order(v) keeps the first copy of each value, in the original order: {3, 1, 3, 2, 1} becomes {3, 1, 2}.
2. rotate_left(v, k) moves the first k elements to the end: {1, 2, 3, 4, 5} with k = 2 becomes {3, 4, 5, 1, 2}. A k larger than the size wraps around, and an empty vector must not crash.

// Exercise: write the two functions, then build and run this file. Every check must say "ok".
//   clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined vector_exercise.cpp -o vector_exercise
//   ./vector_exercise
#include <cstddef>
#include <print>
#include <vector>

// Removes every repeated value, keeping the first copy of each value in its original place:
// {3, 1, 3, 2, 1} becomes {3, 1, 2}.
void remove_duplicates_keep_order(std::vector<int>& v) {
    // your code here
}

// Moves the first k elements to the end, keeping the order of both parts:
// {1, 2, 3, 4, 5} with k = 2 becomes {3, 4, 5, 1, 2}. A k larger than the size wraps around.
void rotate_left(std::vector<int>& v, std::size_t k) {
    // your code here
}

int failures = 0;

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

int main() {
    std::vector<int> a{3, 1, 3, 2, 1};
    remove_duplicates_keep_order(a);
    check(a == std::vector<int>{3, 1, 2}, "{3, 1, 3, 2, 1} keeps {3, 1, 2}");

    std::vector<int> b{7, 7, 7};
    remove_duplicates_keep_order(b);
    check(b == std::vector<int>{7}, "{7, 7, 7} keeps {7}");

    std::vector<int> c;
    remove_duplicates_keep_order(c);
    check(c.empty(), "an empty vector stays empty");

    std::vector<int> d{1, 2, 3, 4, 5};
    rotate_left(d, 2);
    check(d == std::vector<int>{3, 4, 5, 1, 2}, "rotate_left({1, 2, 3, 4, 5}, 2) gives {3, 4, 5, 1, 2}");

    std::vector<int> e{1, 2, 3};
    rotate_left(e, 4);
    check(e == std::vector<int>{2, 3, 1}, "k = 4 on three elements works like k = 1");

    std::vector<int> f;
    rotate_left(f, 3);
    check(f.empty(), "rotating an empty vector does nothing (and does not crash)");

    std::vector<int> big(1'000'000);
    for (std::size_t i = 0; i < big.size(); ++i) big[i] = static_cast<int>(i);
    rotate_left(big, 999'999);
    check(big.front() == 999'999 && big[1] == 0 && big.back() == 999'998, "one million elements rotate by 999,999 quickly");

    std::vector<int> many;
    for (int i = 0; i < 100'000; ++i) many.push_back(i % 100);
    remove_duplicates_keep_order(many);
    check(many.size() == 100 && many.front() == 0 && many.back() == 99, "100,000 values with 100 distinct keep 0 to 99");

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

As it starts, the functions do nothing, so six of the eight checks fail:

from session import run

# The exercise as it starts: the two functions do nothing yet, so most checks fail.
run("""
clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined vector_exercise.cpp -o vector_exercise
./vector_exercise
""")

$ clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined vector_exercise.cpp -o vector_exercise
vector_exercise.cpp:10:53: warning: unused parameter 'v' [-Wunused-parameter]
   10 | void remove_duplicates_keep_order(std::vector<int>& v) {
      |                                                     ^
vector_exercise.cpp:16:36: warning: unused parameter 'v' [-Wunused-parameter]
   16 | void rotate_left(std::vector<int>& v, std::size_t k) {
      |                                    ^
vector_exercise.cpp:16:51: warning: unused parameter 'k' [-Wunused-parameter]
   16 | void rotate_left(std::vector<int>& v, std::size_t k) {
      |                                                   ^
3 warnings generated.
$ ./vector_exercise
FAILED  {3, 1, 3, 2, 1} keeps {3, 1, 2}
FAILED  {7, 7, 7} keeps {7}
ok      an empty vector stays empty
FAILED  rotate_left({1, 2, 3, 4, 5}, 2) gives {3, 4, 5, 1, 2}
FAILED  k = 4 on three elements works like k = 1
ok      rotating an empty vector does nothing (and does not crash)
FAILED  one million elements rotate by 999,999 quickly
FAILED  100,000 values with 100 distinct keep 0 to 99
6 of 8 checks failed
[exit status 1]

You are done when the program prints 0 of 8 checks failed and the sanitizers report nothing. The warnings about unused parameters disappear once your code uses them. Hints: std::find from <algorithm> tells you whether a value is already among the ones kept; k % v.size() reduces k, but only when the vector is not empty; and <algorithm> also has std::rotate. The checks with a million and with 100,000 elements catch solutions that are far too slow, such as one that rotates by a single place, k times over.

Interview questions

Fresher · What is the difference between a vector’s size and its capacity, and when does it matter?

The size is the number of elements the vector holds, and the capacity is the number of elements its current buffer has room for, so the capacity is never smaller than the size. Adding an element while there is spare capacity only builds it in the next slot. Adding one when size equals capacity reallocates: the vector allocates a bigger buffer (both libc++ and libstdc++ double it), moves every element there and frees the old buffer. That matters twice. It costs time, which reserve(n) avoids when you know the final size. And it invalidates every pointer, reference and iterator to the elements, so code that keeps one across a push_back can read freed memory. clear() sets the size to 0 but keeps the capacity.

Key takeaways

• A vector keeps its elements side by side in one buffer on the heap; the vector object itself is three pointers, 24 bytes on a 64-bit computer.
• std::vector<int> v(5) holds five zeros; std::vector<int> v{5} holds one element, 5.
• Size counts elements and capacity counts slots. Both libraries double the capacity when the buffer is full: 1,000 push_back calls made 11 allocations and moved 1,023 elements, and reserve(1000) made it one allocation and no moves.
• Reallocation invalidates every pointer, reference and iterator to the elements. Keep indexes, or take references after the last call that can add elements.
• v[i] with a bad index is undefined behaviour: the same bug printed 372, 0 or stopped the program, depending on the compiler and the optimisation level.
• at() throws std::out_of_range; hardened libraries (libc++’s fast mode, libstdc++’s _GLIBCXX_ASSERTIONS) stop the program; AddressSanitizer reports every bad access while you test.
• std::erase and std::erase_if (C++20) remove elements in one pass and return how many they removed.