Invalidation in std::vector: reallocation, erase

1. Invalidation

When you first start working with std::vector, it feels very "friendly": you put elements, you get elements, everything is logical. Then you take a pointer Task* p = &tasks[0];, add a new task, and suddenly p becomes "an address that used to be true". That is exactly invalidation.

Invalidation (invalidate) in the context of containers is a situation when your binding to an element (reference, pointer, iterator) is no longer guaranteed to point to the same element it pointed to before. Sometimes it starts pointing to another element, sometimes to "nowhere". And "nowhere" in C++ often means not a nice error but potential UB: strange values, crashes, "works on my laptop" and a sudden failure in production.

Informally you can think like this: you saved a route to the box ("here is the address"), and the vector just moved to another apartment (or rearranged the furniture), and your route now leads to a wall.

2. Why std::vector "moves"

std::vector has a superpower: elements live in one contiguous chunk of memory (like an array). That's why vector is often fast: the CPU likes reading sequential data, caches are happy, life is good. The standard and related discussions emphasize that vector is a contiguous container, and there is even a separate category of contiguous iterators for vector, array and string.

But for this speed we pay the cost that the vector sometimes has to do an expensive operation: reallocation (reallocation). The idea is simple: the vector stores two numbers — size() (how many elements actually) and capacity() (how many elements fit in the current buffer without moving). As soon as you add an element and size() becomes greater than capacity(), the vector allocates a new, larger buffer, moves elements there and frees the old one.

From the point of view of your pointers/references this looks rough: "yesterday I lived at Lenin St 10, today — at Pushkin St 42; I hope you are not still sending mail to the old address".

3. reallocation: when it happens and what breaks

The sneakiest thing about reallocation is that you often do not see it. You write push_back, the code compiles, the test passes… and then with another data size capacity() turns out to be small and the vector moves. That's when the "magic" (as in "magic for night-time debuggers") starts.

Key idea: after reallocation all old addresses of elements become invalid. This applies to pointers, references and iterators to elements.

You can catch it visually like this: just print the address of the first element before and after adding.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v{10, 20, 30};

    std::cout << "addr before: " << &v[0] << "\n";
    v.push_back(40); // may trigger reallocation
    std::cout << "addr after:  " << &v[0] << "\n";
}

Sometimes the addresses match (reallocation didn't happen), sometimes they differ (it did happen). That "sometimes" is the reason why invalidation bugs are so unpleasant: they often depend on input sizes and even on how the linker/allocator distributed memory today.

To make it even clearer, you can compare data():

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v;
    v.push_back(1);

    std::cout << "data: " << v.data() << "\n";
    v.push_back(2); // possible move
    std::cout << "data: " << v.data() << "\n";
}

If data() changed — that's almost a sure signal that old "bindings" to elements should not be used.

Mini-diagram: what happens during reallocation

Before (capacity = 3):
[10][20][30]
 ^ addresses somewhere here

After (capacity grew, for example, to 6):
[10][20][30][40][  ][  ]
 ^ new buffer in another place
(old buffer freed)

Old pointers now point into freed memory. From the language perspective this is a "forbidden zone": it may "accidentally work", may crash, may corrupt data.

4. erase: element shift and invalidation

With erase things are sneaky in a different way. When removing an element from the middle of a std::vector, the vector must preserve contiguous storage. So it does what a normal array would do: shifts the tail left to close the hole.

This means addresses of elements after the removed one change. And indices "move" too.

#include <vector>

int main() {
    std::vector<int> v{10, 20, 30, 40};

    int* p30 = &v[2];          // address of element 30
    v.erase(v.begin() + 1);    // removed 20, 30 shifted

    // *p30 = 999; // potential UB: p30 may have become invalid
    (void)p30;
}

Here the psychological point is important: "but 30 remained in the vector!" — yes, it remained as a value, but it is not required to remain at the same address. You bound to the address, not to the idea of the number "30".

Even in standard materials there are discussions about the exact wording for erase and validity (up to issues about the specification of erase in [vector.modifiers]). That's a good marker that the topic is indeed subtle and important.

Mini-diagram: what erase does

Before:
index: 0   1   2   3
      [10][20][30][40]

erase(1) remove 20

After:
index: 0   1   2
      [10][30][40]
          ^
       address of "30" is now different (it moved to position 1)

5. Why const does not save you

Here a typical confusion happens: a student honestly takes const int& r = v[0];, and then thinks "it's const, so it's safe". Alas, const only says one thing: "you cannot change the value through r". But it does not guarantee anything about address stability, relocations, lifetime, or that the vector won't reallocate memory.

#include <vector>

int main() {
    std::vector<int> v{1, 2, 3};

    const int& r = v[0];
    v.push_back(4); // may invalidate r

    // int x = r; // potential UB
    (void)r;
}

This is like being given a "read-only pass" to a building. But if the building moved to another city, your pass doesn't make the old address real again.

6. Practical example: tasks and the "selected item"

To avoid the feeling "this is all about abstract numbers", let's look at a small fragment of our tutorial app. Assume we have a task model and a list of tasks in a std::vector.

#include <string>
#include <vector>

struct Task {
    int id{};
    std::string title;
    bool done{};
};

int main() {
    std::vector<Task> tasks;
    tasks.push_back(Task{1, "Read C++ book", false});
}

Now imagine we made a find function and return a pointer to the task if found.

#include <vector>

Task* FindTaskById(std::vector<Task>& tasks, int id) {
    for (Task& t : tasks) {
        if (t.id == id) return &t;
    }
    return nullptr;
}

While we use that pointer "here and now" — everything is fine. The problem begins if we decide to store it and keep modifying tasks.

Trap scenario:

#include <vector>

int main() {
    std::vector<Task> tasks;
    tasks.push_back(Task{1, "A", false});

    Task* selected = &tasks[0];
    tasks.push_back(Task{2, "B", false}); // may cause reallocation

    // selected->done = true; // potential UB
    (void)selected;
}

To a novice programmer this looks "logical": I selected a task, then added another, then mark the selected as done. But in terms of memory it may mean: "I remembered an address, then the vector moved, and I continue writing to the old address".

A separate pain: sometimes it "seems to work" because reallocation did not occur (capacity() had slack). So such a bug can live long and surface at the worst time.

What can go wrong and why it's hard to debug

When you use an invalidated reference/pointer/iterator, C++ usually does not warn you. The compiler does not know that at runtime you did push_back and "broke" the binding, and the program is not required to crash immediately. It may show the old value (because memory hasn't been reused yet), show garbage (because memory is reused), crash (if you accessed protected memory), or quietly corrupt other data and crash later (this is especially "fun").

This is one reason for the C++ meme: "Undefined Behavior — when the program does what you didn't expect, and does it confidently".

Good news is that std::vector behaves predictably if you keep a simple model: everything that forces the vector to move (reallocation) breaks all bindings to elements; everything that forces the vector to shift elements (erase in the middle) breaks bindings to elements that were shifted.

Risk map by std::vector operations

Below is a practical "brain table", not an attempt to make you a walking standard. Think of it as road signs: it does not explain the physics but it greatly reduces accidents.

push_back

emplace_back

reserve(n)

resize

erase(pos)

pos

erase(first, last)

clear()

operator[]

Note the subtlety: "sometimes breaks" is not "ignore it". It means "the code will behave differently for different data sizes".

How to write code to avoid stepping on invalidation

It's useful to develop a habit: a binding to a vector element should live very shortly. The ideal lifetime of a pointer/reference/iterator to a vector element is "within a small piece of code where the vector is not modified".

For example, this code is usually safer mentally and architecturally:

#include <vector>

void MarkFirstDone(std::vector<Task>& tasks) {
    if (tasks.empty()) return;

    Task& t = tasks[0];  // took a reference
    t.done = true;       // used it immediately
    // ... and no more push_back/erase here
}

And this approach should always include an internal "alarm": if you see a reference/pointer living long and there are nearby push_back or erase operations, your brain should say "stop, invalidation may happen here".

#include <vector>

void Suspicious(std::vector<Task>& tasks) {
    if (tasks.empty()) return;

    Task* p = &tasks[0];                   // binding
    tasks.push_back(Task{99, "X", false}); // potential move

    // p->done = true; // dangerous zone: p may have become invalid
    (void)p;
}

In this lecture we will not turn this into an "architectural religion" and decide what exactly to replace long-lived element addresses with. For now it's important to fix the reason: an address of a std::vector element is the address "right now", not an eternal identity.

7. Common mistakes with invalidation in std::vector

Mistake #1: storing T*/T&/iterator to a vector element "between actions", then doing push_back.
Classic: "I selected an element", "I saved a pointer to it", "I added another element", "why did my universe break?". The problem is possible reallocation: the vector moves and the pointer becomes garbage. The code looks reasonable, so the bug is especially persistent.

Mistake #2: thinking const makes the binding safe.
const T& and const T* forbid writing through that access, but do not guarantee address stability and do not prevent buffer relocation. If you hold a const reference to an element and there are growth operations nearby, it's still potentially dangerous.

Mistake #3: after erase continue using "old addresses" of elements that were to the right of the removed one.
With erase elements shift. Even if the logical object you need remained in the collection, physically it may be at another address. This breaks not only pointers but iterators and references too.

Mistake #4: "I did reserve, so addresses are stable forever".
reserve indeed helps reduce the number of moves, but it does not turn element addresses into a lifetime guarantee. Exceeding reserved capacity once — and the move will still happen. Also, erase is not cured by reserve: it's a different cause of address change.

Mistake #5: checking a bug "on small data" and concluding "so it's fine".
On small sizes capacity() often suffices, push_back doesn't trigger reallocation, and pointers "accidentally don't break". Then you give the program real input — and behavior changes. For invalidation topics this is especially typical: bugs don't appear immediately or consistently.

1

Task

C++ SELF, level 41, lesson 1

Locked

Backpack space

Backpack space

Open

1

Task

C++ SELF, level 41, lesson 1

Locked

Playlist selection

Playlist selection

Open

1

Task

C++ SELF, level 41, lesson 1

Locked

Spam cleanup

Spam cleanup

Open

1

Task

C++ SELF, level 41, lesson 1

Locked

Todo list commands

Todo list commands

Open