C++
Library
since C++98
Beginner

std::vector

Dynamic contiguous array container. Default choice for sequential collections. O(1) random access and amortized O(1) append. Reallocates when capacity exhausted.

C++98C++11C++14C++17C++20C++23
std::vectorsince C++98

A dynamically-resizable, contiguous array stored on the heap that manages its own memory and provides O(1) random access and amortized O(1) append operations.

Overview

std::vector<T> is the most widely-used container in C++. It owns a heap-allocated buffer of contiguous elements, automatically resizing when capacity is exceeded. Every element is accessible in constant time by index, and appending to the end (when spare capacity exists) is also constant time.

Choose std::vector by default for any sequential collection unless you have a specific reason otherwise (e.g., front insertion performance, pointer stability). It dominates because:

  • Cache locality: Elements are contiguous; hardware prefetchers are optimized for this layout.
  • Simplicity: Familiar to all C++ programmers; lowest cognitive overhead.
  • Performance: Wins against std::list, std::deque, and other alternatives in nearly all real-world workloads (even front insertion on list is rarely worth the cache penalty for reasonable sizes).

The key trade-off is memory overhead: std::vector always allocates more than the current size (exponentially, typically doubling). Also, reallocations invalidate iterators, pointers, and references to elements—a subtle hazard in large codebases.

Syntax

cpp
#include <vector>

// Basic declarations (C++98)
std::vector<int> v;                          // empty
std::vector<int> v(10);                      // 10 default-initialized ints
std::vector<int> v(10, 42);                  // 10 ints, each set to 42

// Initializer list (C++11)
std::vector<int> v = {1, 2, 3, 4, 5};

// Class template argument deduction (C++17)
std::vector v{1, 2, 3};                      // deduces vector<int>

// Template signature
template<typename T, typename Alloc = std::allocator<T>>
class vector { /* ... */ };

Key member functions

FunctionComplexityIntroducedNotes
operator[i]O(1)C++98No bounds check; UB if out of range
at(i)O(1)C++98Throws std::out_of_range
front(), back()O(1)C++98UB if empty
data()O(1)C++11Raw pointer to underlying buffer
push_back(x)Amortized O(1)C++98May reallocate and invalidate all iterators
emplace_back(args…)Amortized O(1)C++11Constructs element in-place; no temporary
pop_back()O(1)C++98UB if empty; does not shrink capacity
insert(it, x)O(n)C++98Invalidates all iterators at or after insertion point
erase(it)O(n)C++98Shifts elements; invalidates from erase point onward
resize(n)O(n)C++98Grows or shrinks; value-initializes new elements
reserve(n)O(n) worst-caseC++98Pre-allocates without changing size
clear()O(n)C++98Destroys all elements; capacity unchanged
shrink_to_fit()O(n)C++11Non-binding request to reduce capacity to size()

Examples

Basic usage and capacity management

cpp
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v;
    
    std::cout << "Initial: size=" << v.size() 
              << ", capacity=" << v.capacity() << '\n';  // 0, 0
    
    v.push_back(10);
    v.push_back(20);
    std::cout << "After 2 pushes: size=" << v.size() 
              << ", capacity=" << v.capacity() << '\n';  // 2, likely 2 or 4
    
    v.reserve(100);  // Guarantee space for 100 elements without reallocation
    std::cout << "After reserve(100): capacity=" << v.capacity() << '\n';  // 100
    
    // Access
    std::cout << v[0] << '\n';        // 10 — unchecked, fast
    std::cout << v.at(0) << '\n';     // 10 — throws if out of range
}

Avoiding reallocations with reserve()

cpp
#include <vector>

// Inefficient: multiple reallocations
std::vector<int> inefficient() {
    std::vector<int> v;
    for (int i = 0; i < 100'000; ++i)
        v.push_back(i);  // Reallocates when size reaches capacity
    return v;
}

// Efficient: single allocation
std::vector<int> efficient() {
    std::vector<int> v;
    v.reserve(100'000);  // Single allocation up-front
    for (int i = 0; i < 100'000; ++i)
        v.push_back(i);  // No reallocations
    return v;
}

Range-based for and iterators

cpp
std::vector<std::string> names{"Alice", "Bob", "Carol"};

// C++11: range-for loop
for (const auto& name : names)
    std::cout << name << '\n';

// Manual iteration
for (auto it = names.begin(); it != names.end(); ++it)
    std::cout << *it << '\n';

// Reverse iteration
for (auto it = names.rbegin(); it != names.rend(); ++it)
    std::cout << *it << '\n';

Insertion and erasure

cpp
std::vector<int> v{1, 2, 3, 4, 5};

// Insert at position (O(n) shift)
auto it = v.begin() + 2;
v.insert(it, 99);  // {1, 2, 99, 3, 4, 5}

// Erase single element (O(n) shift)
v.erase(v.begin() + 2);  // {1, 2, 3, 4, 5}

// Erase by value (erase-remove idiom, pre-C++20)
v.erase(std::remove(v.begin(), v.end(), 3), v.end());

// C++20: std::erase and std::erase_if (cleaner, no need for <algorithm> in same way)
std::erase(v, 3);                            // remove all 3s
std::erase_if(v, [](int x) { return x % 2 == 0; });  // remove evens

Emplacement construction (C++11+)

cpp
struct Point { int x, y; };

std::vector<Point> pts;

// Traditional: construct temporary, then move into vector
pts.push_back(Point{1, 2});

// C++11+: construct directly in vector's storage
pts.emplace_back(3, 4);  // Arguments forwarded; no temporary object created

Best Practices

1. Reserve capacity upfront if size is known
Reallocations during growth are expensive and invalidate iterators. If the final size is known or bounded, reserve in advance:

cpp
std::vector<int> v;
v.reserve(1000);  // Allocate once
for (int i = 0; i < 1000; ++i)
    v.push_back(compute(i));  // No reallocations

2. Prefer emplace_back() over push_back()
emplace_back() (C++11) constructs elements in-place without temporary objects. For large or complex types, this is noticeably faster.

3. Use at() defensively, [] in proven code
at() checks bounds and throws std::out_of_range; [] is unchecked. Use at() when bounds are uncertain (e.g., user input); use [] in tight loops where bounds are mathematically proven.

4. Pass by const reference, not by value
Passing a vector by value copies the entire buffer. Always pass by const reference for read-only parameters:

cpp
void process(const std::vector<int>& v);  // Efficient
void process(std::vector<int> v);         // Expensive copy — avoid
void process(std::vector<int>&& v);       // Take ownership (move)

5. Avoid storing iterators across modifications
Do not hold iterators from begin() or end() if the vector will be resized. Use indices, or restructure to eliminate the iterator:

cpp
std::vector<int> v{1, 2, 3, 4, 5};
auto it = v.begin() + 2;
v.push_back(6);    // May reallocate; it is now dangling
// std::cout << *it;  // UB

// SAFE: Use indices or guarantee no reallocation
int idx = 2;
v.reserve(10);     // Prevent reallocation
v.push_back(6);    // Safe now
std::cout << v[idx];

Common Pitfalls

Iterator invalidation on reallocation
When a vector reallocates (because size() == capacity() and you append), every iterator, pointer, and reference to elements becomes invalid. This is the #1 source of subtle bugs:

cpp
std::vector<int> v{1, 2, 3};
int* ptr = &v[0];
v.push_back(4);    // May reallocate
std::cout << *ptr; // Dangling pointer — undefined behavior

std::vector<bool> is not a real container
std::vector<bool> is a specialized, bit-packed version that breaks container semantics. Iterators no longer return bool&, and operator& doesn't yield a valid pointer. Avoid it:

cpp
std::vector<bool> vb{true, false, true};   // Problematic specialization
std::vector<char> vc{1, 0, 1};             // Better: standard container semantics
std::bitset<N> b;                          // C++11: best for fixed-size bit sets

Bounds checking: [] vs at()
operator[] performs no bounds check. Out-of-bounds access is undefined behavior and may silently corrupt memory:

cpp
std::vector<int> v{1, 2, 3};
v[10];      // UB — silent memory corruption in release builds
v.at(10);   // Throws std::out_of_range — safe, but slower

Expensive moves and copies
Vector reallocations move or copy all elements. For large objects or tight loops, this is expensive. Pre-allocate with reserve():

cpp
struct Large { char data[1024]; };
std::vector<Large> v;
v.reserve(1000);  // Single allocation; no reallocations during append

Stale references after mutation
References obtained before any mutation become invalid if the vector reallocates:

cpp
std::vector<int> v{1, 2, 3};
int& ref = v[0];
v.push_back(4);    // May reallocate
std::cout << ref;  // Dangling reference — UB

See Also

  • std::array — Fixed-size array wrapper; no heap allocation; C++11
  • std::deque — Double-ended queue; O(1) front and back insertion; worse cache locality
  • std::list — Doubly-linked list; O(n) random access; stable pointers/iterators
  • std::string — Specialization for char; adds string-specific operations
  • Algorithms (<algorithm>) — std::find, std::sort, std::erase, std::erase_if (C++20)
  • Memory (<memory>) — std::allocator, custom allocation strategies
  • Iterators — Understanding invalidation rules is critical for correct vector usage