Chapter 35 of 48

vector

If you learn only one STL container, make it std::vector. It is a dynamic array: it stores elements next to each other in memory just like a normal array, so indexing is instant, but it can grow and shrink at run time and it manages its own memory. No new[], no delete[], no fixed size decided in advance.

In Arrays we saw that a built-in array's size is fixed at compile time, and in Dynamic Memory Allocation we saw how painful (and leak-prone) it is to resize a heap array by hand. vector does that work for you, correctly and efficiently. In Introduction to the STL we called it the default container; in this chapter we learn how to use it and, just as important, how it works inside, because that explains its performance and its traps.


What Is a vector?

std::vector<T> is a sequence container, declared in <vector>, that stores elements of type T in one contiguous block of dynamically allocated memory, resizing automatically as elements are added.

A vector object itself is small. In typical implementations (such as GCC's libstdc++) it holds just three pointers: the start of the buffer, the end of the used part, and the end of the allocated part. The elements live on the heap:

  std::vector<int> v  (on the stack, 24 bytes on a 64-bit system)
  ┌─────────┬─────────┬─────────┐
  │  begin  │   end   │ cap_end │
  └────┬────┴────┬────┴────┬────┘
       │         │         │
       ▼         ▼         ▼
     ┌────┬────┬────┬────┬────┬────┐   heap buffer
     │ 10 │ 20 │ 30 │ 40 │    │    │
     └────┴────┴────┴────┴────┴────┘
     ◀──── size() = 4 ────▶
     ◀──────── capacity() = 6 ────────▶

Two numbers describe every vector:

  • size: how many elements it currently holds.

  • capacity: how many elements fit in the memory already allocated, so capacity() ≥ size() always.

The gap between them is spare room that lets push_back be fast most of the time. When the destructor runs, the vector destroys its elements and frees the buffer automatically. This is the RAII idea from Constructors & Destructors, and it is why vectors do not leak.


Creating a vector

#include <iostream>
#include <vector>
#include <string>

void show(const std::string& label, const std::vector<int>& v) {
    std::cout << label << " (size " << v.size() << "): ";
    for (int x : v) std::cout << x << ' ';
    std::cout << '\n';
}

int main() {
    std::vector<int> a;                    // empty
    std::vector<int> b(4);                 // 4 elements, value-initialized to 0
    std::vector<int> c(4, 7);              // 4 elements, each 7
    std::vector<int> d = {1, 2, 3};        // initializer list (C++11)
    std::vector<int> e(d);                 // copy of d
    std::vector<int> f(d.begin() + 1, d.end());  // from an iterator range
    std::vector g{5, 6};                   // C++17 CTAD: deduced as vector<int>

    show("a", a);
    show("b", b);
    show("c", c);
    show("d", d);
    show("e", e);
    show("f", f);
    show("g", g);

    std::vector<int> p(3, 9);              // parentheses: 3 copies of 9
    std::vector<int> q{3, 9};              // braces: two elements, 3 and 9
    show("p", p);
    show("q", q);
}

Output:

a (size 0): 
b (size 4): 0 0 0 0 
c (size 4): 7 7 7 7 
d (size 3): 1 2 3 
e (size 3): 1 2 3 
f (size 2): 2 3 
g (size 2): 5 6 
p (size 3): 9 9 9 
q (size 2): 3 9 

Points to notice:

  • std::vector<int> b(4) creates four elements that are value-initialized, which means 0 for numbers. Unlike a local built-in array, a vector never holds garbage values.

  • std::vector g{5, 6} works without writing <int> because of class template argument deduction (C++17), introduced in Templates.

  • Parentheses vs braces is a famous trap: p(3, 9) means "3 copies of 9", while q{3, 9} means "the two elements 3 and 9". Braces prefer the initializer-list constructor whenever it can be used.


Adding, Accessing and Removing at the End

#include <iostream>
#include <vector>
#include <string>
#include <stdexcept>

int main() {
    std::vector<std::string> names;
    names.push_back("Asha");               // a string is created, then moved in
    names.emplace_back("Bilal");           // the string is constructed in place
    names.emplace_back(3, 'z');            // calls string(3, 'z') -> "zzz"

    std::cout << "front: " << names.front() << '\n';
    std::cout << "back : " << names.back() << '\n';
    std::cout << "names[1]: " << names[1] << '\n';

    names[2] = "Chitra";                   // modify through operator[]
    names.pop_back();                      // removes "Chitra"
    std::cout << "size after pop_back: " << names.size() << '\n';

    try {
        std::cout << names.at(5) << '\n';  // at() checks the index
    } catch (const std::out_of_range& e) {
        std::cout << "out_of_range caught\n";
    }
    std::cout << std::boolalpha << "empty? " << names.empty() << '\n';
}

Output:

front: Asha
back : zzz
names[1]: Bilal
size after pop_back: 2
out_of_range caught
empty? false
MemberDoesCost
push_back(x)Adds a copy of x (or moves it, if x is a temporary) at the endO(1) amortized
emplace_back(args...)Constructs a new element at the end directly from args (C++11; returns a reference to it since C++17)O(1) amortized
pop_back()Removes the last element (undefined behavior if empty)O(1)
v[i]Element i, no bounds check; out of range is undefined behaviorO(1)
v.at(i)Element i with bounds check; throws std::out_of_rangeO(1)
front() / back()First / last element (undefined behavior if empty)O(1)
size(), empty()Number of elements; whether it is zeroO(1)

push_back vs emplace_back: push_back needs an already-made object; emplace_back forwards its arguments to the element's constructor and builds it directly inside the vector, as in emplace_back(3, 'z'), which no push_back call could accept. For simple values like int there is no difference. The at() exception is caught exactly as shown in Exception Handling.


How a vector Grows: size vs capacity

What happens when you push_back into a full vector? The vector cannot just extend its block, because the memory after it may belong to someone else. So it reallocates:

  1. Allocate a new, bigger block.

  2. Move (or copy) all existing elements into the new block.

  3. Construct the new element.

  4. Destroy the old elements and free the old block.

Let us watch the capacity change:

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v;
    std::size_t lastCap = v.capacity();
    std::cout << "size 0, capacity " << lastCap << '\n';

    for (int i = 1; i <= 100; ++i) {
        v.push_back(i);
        if (v.capacity() != lastCap) {          // a reallocation just happened
            lastCap = v.capacity();
            std::cout << "size " << v.size() << ", capacity " << lastCap << '\n';
        }
    }
}

Output (GCC / libstdc++):

size 0, capacity 0
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

With GCC the capacity doubles each time. The exact growth factor is not fixed by the standard: Microsoft's library grows by about 1.5×, for example. What the standard does require is that push_back takes amortized constant time, and that is only possible with geometric growth (multiplying by a factor), never with "add 10 more slots each time".

Why is push_back amortized O(1)?

A single reallocation copies all n elements, which is O(n). But it happens rarely. With doubling, inserting n elements causes copies of 1 + 2 + 4 + … elements, each term a power of two smaller than n, and such a sum is always less than 2n. So n pushes cost at most n (constructing the new elements) + 2n (all the copying), that is under 3n element operations: O(1) per push on average. "Amortized" means averaged over a sequence of operations; one particular push can still be O(n).

pushes:      1   2   3   4   5   6   7   8   9  ...
copies:      0   1   2   0   4   0   0   0   8  ...   (copy happens only when full)
capacity:    1   2   4   4   8   8   8   8  16  ...
total copies for n = 9 pushes: 1 + 2 + 4 + 8 = 15  <  2 × 9

reserve, resize, shrink_to_fit, clear

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v;
    v.reserve(100);                       // allocate room for 100 up front
    std::cout << "after reserve: size " << v.size()
              << ", capacity " << v.capacity() << '\n';

    const int* where = v.data();
    for (int i = 0; i < 100; ++i) v.push_back(i);
    std::cout << "after 100 push_backs: capacity " << v.capacity()
              << ", moved? " << std::boolalpha << (where != v.data()) << '\n';

    v.resize(10);                         // keep the first 10 elements
    std::cout << "after resize(10): size " << v.size()
              << ", capacity " << v.capacity() << '\n';

    v.shrink_to_fit();                    // a request, not a promise
    std::cout << "after shrink_to_fit: capacity " << v.capacity() << '\n';

    v.clear();                            // removes elements, keeps memory
    std::cout << "after clear: size " << v.size()
              << ", capacity " << v.capacity() << '\n';

    v.resize(3, -1);                      // grow to 3, new elements = -1
    for (int x : v) std::cout << x << ' ';
    std::cout << '\n';
}

Output (GCC / libstdc++):

after reserve: size 0, capacity 100
after 100 push_backs: capacity 100, moved? false
after resize(10): size 10, capacity 100
after shrink_to_fit: capacity 10
after clear: size 0, capacity 10
-1 -1 -1 
FunctionChanges size?Changes capacity?
reserve(n)NoEnsures capacity ≥ n (never shrinks)
resize(n) / resize(n, val)Yes, to exactly n (new elements value-initialized or set to val)Only if n > capacity
clear()Yes, to 0No, memory is kept
shrink_to_fit()NoRequests capacity = size; the standard makes this non-binding (C++11)

Use reserve when you know roughly how many elements are coming. It avoids repeated reallocations, and as the output shows, the buffer did not move during all 100 pushes. A very common mistake is to call reserve(100) and then write v[5] = 1: reserve does not create elements, so size() is still 0 and that write is undefined behavior. Use resize if you want elements to exist.


Inserting and Erasing in the Middle

#include <iostream>
#include <vector>

void print(const std::vector<int>& v) {
    for (int x : v) std::cout << x << ' ';
    std::cout << '\n';
}

bool isOdd(int x) { return x % 2 != 0; }

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

    v.insert(v.begin() + 2, 25);              // before index 2
    print(v);
    v.insert(v.begin(), 3, 0);                // three 0s at the front
    print(v);
    v.erase(v.begin());                       // remove index 0
    print(v);
    v.erase(v.begin(), v.begin() + 2);        // remove the range [0, 2)
    print(v);

    std::vector<int> w = {1, 2, 3, 2, 6, 2, 8};
    auto removed = std::erase(w, 2);          // C++20: remove every 2
    std::cout << "removed " << removed << ": ";
    print(w);
    removed = std::erase_if(w, isOdd);        // C++20: remove by condition
    std::cout << "removed " << removed << ": ";
    print(w);
}

Output:

10 20 25 30 40 50 
0 0 0 10 20 25 30 40 50 
0 0 10 20 25 30 40 50 
10 20 25 30 40 50 
removed 3: 1 3 6 8 
removed 2: 6 8 

insert and erase take iterators, not indexes: position i is written v.begin() + i. Because elements must stay contiguous, inserting at position i shifts every element after it one place right, and erasing shifts them left:

insert 25 at index 2:

  before:  │ 10 │ 20 │ 30 │ 40 │ 50 │    │
                      └──→ └──→ └──→        each shifts right by one
  after:   │ 10 │ 20 │ 25 │ 30 │ 40 │ 50 │

So insertion or erasure in the middle is O(n) (linear in the number of elements after the position), and at the very end it is cheap. If your program inserts at the front all the time, consider deque or list from the list, deque & array chapter.

Removing all elements that match: before and after C++20

C++20 added the free functions std::erase(v, value) and std::erase_if(v, predicate), used above. Both return how many elements were removed. Before C++20 the standard way was the erase–remove idiom, which you will still see in a lot of code and in interviews:

#include <iostream>
#include <vector>
#include <algorithm>

void print(const std::vector<int>& v) {
    std::cout << "size " << v.size() << ": ";
    for (int x : v) std::cout << x << ' ';
    std::cout << '\n';
}

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

    // std::remove only shifts the kept elements forward.
    auto newEnd = std::remove(v.begin(), v.end(), 2);
    print(v);    // size unchanged; the tail holds leftover values
    std::cout << "kept elements: " << (newEnd - v.begin()) << '\n';

    v.erase(newEnd, v.end());   // now actually delete the tail
    print(v);
}

Output:

size 7: 1 3 6 8 6 2 8 
kept elements: 4
size 4: 1 3 6 8 

As explained in Introduction to the STL, the algorithm std::remove cannot change a container's size. It moves the elements to keep to the front and returns the new logical end; the elements after that are in a valid but unspecified state (here they happen to be 6 2 8). Only erase really deletes them. Both versions are O(n), much better than erasing matches one at a time, which can become O(n²).


Iterator Invalidation: the Most Important Trap

Because a vector may move its elements to a new buffer, any pointer, reference or iterator to an element can become invalid (dangling) after the vector is modified. Using an invalid one is undefined behavior: it may print garbage, crash, or seem to work today and fail tomorrow.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {1, 2, 3};
    v.shrink_to_fit();            // libstdc++: capacity becomes exactly 3
    int& first = v[0];            // reference into the vector's buffer
    v.push_back(4);               // size would exceed capacity: buffer reallocated
    std::cout << first << '\n';   // BUG: 'first' refers to freed memory
}

Compiled with g++ -std=c++23 -g -fsanitize=address,undefined, AddressSanitizer catches the bug (addresses vary from run to run; report shortened):

==978==ERROR: AddressSanitizer: heap-use-after-free on address 0x77962c9e0010 ...
READ of size 4 at 0x77962c9e0010 thread T0
    #0 ... in main v7.cpp:9
...
freed by thread T0 here:
    ...
    #8 ... in std::vector<int, std::allocator<int> >::push_back(int&&) ...
    #9 ... in main v7.cpp:8

The report says it exactly: line 9 read memory that push_back on line 8 had freed. Without the sanitizer this program may well print 1 and look fine, which is what makes this bug dangerous. The rules (from the standard) are:

OperationWhat becomes invalid
push_back, emplace_backIf the new size exceeds capacity: everything. Otherwise only end().
insert, emplaceIf reallocation happens: everything. Otherwise everything at or after the insertion point (and end()).
eraseEverything at or after the erased position, including end().
pop_backThe last element and end().
reserve, shrink_to_fitEverything, if the capacity actually changes.
clearEverything (all elements are gone).
resizeLike insert/erase at the end: everything if it reallocates.

Fixes: refer to elements by index instead of pointer/reference when the vector may grow, take references only after you finish adding, or reserve enough capacity first.

Erasing inside a loop, correctly

A loop like for (auto it = v.begin(); it != v.end(); ++it) if (...) v.erase(it); is broken: after erase(it), it is invalid, and ++it on it is undefined behavior. erase returns a valid iterator to the element after the removed one, so use that:

#include <iostream>
#include <vector>

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

    // Remove even numbers while walking the vector.
    for (auto it = v.begin(); it != v.end(); ) {
        if (*it % 2 == 0)
            it = v.erase(it);   // erase returns an iterator to the next element
        else
            ++it;               // advance only when nothing was erased
    }

    for (int x : v) std::cout << x << ' ';
    std::cout << '\n';
}

Output:

1 3 5 

(For this exact task, std::erase_if is simpler and O(n); the loop version is O(n²) in the worst case because each erase shifts the rest. The loop is still worth knowing because the same pattern is used for list, map and set.)


2D vectors

A vector of vectors gives a 2D table whose dimensions are decided at run time, which is very common in matrix and grid problems:

#include <iostream>
#include <vector>

int main() {
    int rows = 3, cols = 4;
    std::vector<std::vector<int>> grid(rows, std::vector<int>(cols, 0));

    for (int r = 0; r < rows; ++r)
        for (int c = 0; c < cols; ++c)
            grid[r][c] = r * cols + c;

    grid[1].push_back(99);          // rows may have different lengths ("jagged")

    for (const auto& row : grid) {
        for (int x : row) std::cout << x << ' ';
        std::cout << '\n';
    }
    std::cout << "rows: " << grid.size() << ", row 1 length: " << grid[1].size() << '\n';
}

Output:

0 1 2 3 
4 5 6 7 99 
8 9 10 11 
rows: 3, row 1 length: 5

grid(rows, std::vector<int>(cols, 0)) means "rows copies of a row that has cols zeros". Each row is a separate vector with its own heap buffer, so rows can even have different lengths. The cost is that the rows are not one contiguous block; for performance-critical code, a single vector<int> of size rows × cols indexed as r * cols + c is faster.


vectors and Functions

#include <iostream>
#include <vector>

// const reference: no copy, and the function cannot modify the caller's vector
long long sum(const std::vector<int>& v) {
    long long s = 0;
    for (int x : v) s += x;
    return s;
}

// non-const reference: modifies the caller's vector
void doubleAll(std::vector<int>& v) {
    for (int& x : v) x *= 2;      // int& so we change the element, not a copy
}

// return by value: cheap, the result is moved (or constructed in place)
std::vector<int> firstN(int n) {
    std::vector<int> r;
    r.reserve(n);
    for (int i = 1; i <= n; ++i) r.push_back(i);
    return r;
}

int main() {
    std::vector<int> v = firstN(5);
    std::cout << "sum = " << sum(v) << '\n';
    doubleAll(v);
    for (int x : v) std::cout << x << ' ';
    std::cout << '\n';
}

Output:

sum = 15
2 4 6 8 10 
  • Pass by const& when you only read. Passing by value copies every element: O(n) time and memory for nothing.

  • Pass by non-const & when the function must modify the caller's vector (as in References).

  • Return by value freely. Since C++11 a returned local vector is moved (just three pointers change hands) or, more often, built directly in the caller's variable (copy elision), so returning a big vector is cheap. The details are in Move Semantics & Rvalue References.

  • In for (int& x : v) the & is required to modify elements; for (int x : v) changes only a copy.


Copying, Comparing and Swapping

#include <iostream>
#include <vector>

int main() {
    std::vector<int> a = {1, 2, 3};
    std::vector<int> b = {1, 2, 4};
    std::vector<int> c = {1, 2};

    std::cout << std::boolalpha;
    std::cout << (a == b) << '\n';   // element-by-element
    std::cout << (a < b) << '\n';    // lexicographic: 3 < 4 decides
    std::cout << (c < a) << '\n';    // c is a prefix of a, so c is smaller

    std::vector<int> d = a;          // deep copy: independent elements
    d[0] = 100;
    std::cout << a[0] << ' ' << d[0] << '\n';

    a.swap(c);                       // O(1): just exchanges internal pointers
    std::cout << a.size() << ' ' << c.size() << '\n';

    std::vector<int> e = {7, 8};
    e.append_range(b);               // C++23: append a whole range
    for (int x : e) std::cout << x << ' ';
    std::cout << '\n';
}

Output:

false
true
true
1 100
2 3
7 8 1 2 4 
  • Copying a vector is a deep copy: new buffer, all elements copied. The class follows the rule of three/five correctly, so you never write a copy constructor for it.

  • == compares sizes and then elements. < compares lexicographically, like words in a dictionary. (Since C++20 these come from operator== and operator<=>.)

  • swap is O(1): it exchanges the internal pointers and does not touch elements.

  • append_range is new in C++23 (with insert_range and assign_range), supported by GCC 15. On older compilers write e.insert(e.end(), b.begin(), b.end()).


A Special Case: vector<bool>

std::vector<bool> is a specialization (see Templates) that packs bools into bits to save memory. As a result it does not behave like other vectors: v[i] returns a proxy object instead of a real bool&, you cannot take &v[0] as a bool*, and it has no data(). It works for simple use, but if you need normal vector behavior use std::vector<char>, or std::bitset for a fixed number of bits.


Complexity Summary

OperationComplexity
v[i], at, front, back, size, emptyO(1)
push_back, emplace_backO(1) amortized (O(n) on a reallocation)
pop_backO(1)
insert / erase at position pO(number of elements after p) plus number inserted/erased
Search by value (std::find)O(n)
Copy, clear, destructionO(n)
swap, move constructionO(1)

vector vs built-in array

FeatureBuilt-in array int a[10]std::vector<int>
SizeFixed at compile timeChanges at run time
Knows its sizeNo (decays to a pointer when passed)Yes, size()
MemoryStack (if local)Heap buffer, freed automatically
Bounds checkingNeverOptional with at()
Copy with =Not allowedYes, deep copy
Element access speedO(1)O(1), same contiguous layout

Common Mistakes

  • Indexing out of range with []. v[v.size()] is undefined behavior; use at() while debugging or check the index.

  • Calling front(), back() or pop_back() on an empty vector: undefined behavior. Check empty() first.

  • Confusing reserve with resize. After reserve(n) the size is still 0.

  • Keeping references/iterators across push_back. A reallocation leaves them dangling.

  • Signed/unsigned comparison. size() returns an unsigned std::size_t. for (int i = 0; i < v.size(); ++i) triggers a -Wsign-compare warning, and v.size() - 1 on an empty vector wraps around to a huge number. Prefer range-based for, or std::size_t indexes, or C++20 std::ssize(v).

  • vector<int> v(5) vs vector<int> v{5}: five zeros vs one element 5.

  • Passing vectors by value to functions that only read them.


Interview / GATE-Style Questions

Q1. What is the difference between size and capacity of a vector?

Size is the number of elements stored. Capacity is how many elements the allocated buffer can hold before a reallocation is needed. Always capacity ≥ size.

Q2. Why is push_back amortized O(1) and not O(1) in the worst case?

When the vector is full, push_back reallocates and moves all n elements, which is O(n). Because capacity grows geometrically (for example doubling), such reallocations are rare: n pushes cause fewer than 2n element copies in total, so the average cost per push is constant.

Q3. What is printed?
vector<int> a(3, 1), b{3, 1};
cout << a.size() << b.size();

32. a is three copies of 1; b uses the initializer-list constructor and holds two elements, 3 and 1.

Q4. Can a reference to v[0] become invalid when you call push_back? When?

Yes, if the push makes the size exceed the current capacity. The vector then moves its elements to a new buffer and frees the old one, so all existing references, pointers and iterators dangle. If capacity is sufficient, only end() is invalidated.

Q5. Difference between v[i] and v.at(i)?

Both return a reference to element i in O(1). v[i] does no checking, so an invalid index is undefined behavior; v.at(i) checks the index and throws std::out_of_range if it is invalid.

Q6. Does clear() free the vector's memory?

No. It destroys the elements and sets size to 0, but capacity is unchanged. To request releasing memory, call shrink_to_fit() afterwards (non-binding), or swap with an empty vector: std::vector<int>().swap(v);.

Q7. What is the erase–remove idiom?

v.erase(std::remove(v.begin(), v.end(), x), v.end());. std::remove moves the elements to keep to the front and returns the new logical end; erase then deletes the leftover tail. Since C++20 the same is written std::erase(v, x);.


Summary

  • std::vector<T> is a dynamic array: contiguous elements, O(1) indexing, automatic memory management.

  • size is the element count, capacity the allocated room; geometric growth makes push_back amortized O(1).

  • reserve changes capacity only, resize changes size, clear keeps the memory, shrink_to_fit is only a request.

  • [] is unchecked, at() throws std::out_of_range.

  • Insertion and erasure in the middle are O(n) because elements shift; use std::erase/std::erase_if (C++20) or the erase–remove idiom to remove by value.

  • Reallocation invalidates all iterators, pointers and references; erase invalidates everything from the erased point onward. Use the iterator returned by erase.

  • Pass by const&, return by value; copying is deep and swap is O(1).

  • vector<bool> is a bit-packed special case that does not behave like a normal container.