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

Growth strategy and reserve

std::vector grows exponentially to achieve amortized O(1) append. Most implementations double capacity on each reallocation, so a vector that reaches 1 million elements will have triggered at most ~20 reallocations regardless of how it was built. The exact growth factor is implementation-defined (GCC uses 2×, MSVC uses 1.5×).

Use reserve() whenever the final size is predictable, and shrink_to_fit() when a vector has shed a large portion of its elements and memory pressure matters.

cpp
#include <vector>
#include <iostream>

// C++11: observe capacity growth
std::vector<int> v;
for (int i = 0; i < 20; ++i) {
    v.push_back(i);
    std::cout << "size=" << v.size()
              << "  capacity=" << v.capacity() << '\n';
    // Typical output: capacity doubles at 1, 2, 4, 8, 16, …
}

// Pre-allocate to eliminate every reallocation
v.clear();
v.reserve(1'000'000);  // C++11: single heap allocation
for (int i = 0; i < 1'000'000; ++i)
    v.push_back(i);    // Zero reallocations

// Release excess capacity after bulk-erase (C++11)
v.resize(10);
v.shrink_to_fit();  // Non-binding; capacity typically drops to 10

shrink_to_fit() is a non-binding request — the implementation may ignore it. For a guaranteed release, use the swap-with-temporary idiom:

cpp
// C++98/11: guaranteed shrink
std::vector<int>(v).swap(v);  // Swap with a freshly constructed copy

Iterator invalidation rules

Reallocation invalidates everything; in-place mutation invalidates only from the affected point forward. Understanding exactly when iterators, pointers, and references go stale is essential for correct vector usage.

OperationIterators invalidated
push_back / emplace_back — no reallocationNone
push_back / emplace_back — causes reallocationAll
insert / emplace at position pAll from p to end() (plus all if reallocation)
erase at position pAll from p to end()
pop_backend() iterator and iterator/reference to last element
resize, reserve, shrink_to_fitAll if reallocation; otherwise end() only
clearAll (but capacity unchanged)
swapAll (iterators now refer to the other vector)
cpp
#include <vector>

// C++11: safe pattern — use indices, not iterators, if the vector may grow
std::vector<int> v{1, 2, 3, 4, 5};
std::size_t idx = 2;          // Index stays valid across reallocations

v.push_back(6);               // May reallocate — idx is still valid
std::cout << v[idx] << '\n';  // OK: 3

// Unsafe: iterator captured before a push_back
auto it = v.begin() + 2;
v.push_back(7);               // Possible reallocation
// *it is now UB if reallocation occurred

Pre-calling reserve() before a sequence of mutations guarantees no reallocation and therefore no iterator invalidation during that sequence, provided the total size stays within the reserved capacity.

Emplace vs push_back

emplace_back constructs the element in-place; push_back constructs first and then moves (or copies). For cheap-to-move types (ints, pointers, std::unique_ptr) the difference is immeasurable. For larger value types the in-place construction avoids a move.

cpp
#include <vector>
#include <string>

// C++11
struct Config {
    std::string host;
    int port;
    bool tls;
};

std::vector<Config> configs;
configs.reserve(3);

// push_back: constructs a temporary Config, then move-constructs into the vector
configs.push_back(Config{"localhost", 8080, false});

// emplace_back: arguments are forwarded directly to Config's constructor
configs.emplace_back("example.com", 443, true);  // No temporary

// emplace_back with braced-init is allowed in C++20
// In C++11/14/17 brace-init requires explicit type
configs.emplace_back("api.example.com", 8443, true);  // C++11 OK

emplace_back is generally preferred for complex types, but push_back with a named variable communicates intent more clearly and should be used when readability matters:

cpp
// C++11: prefer push_back when you already have a named object
Config c{"db.internal", 5432, false};
configs.push_back(std::move(c));  // Move — as cheap as emplace_back

vector<bool>: the special case

std::vector<bool> is a library specialization that packs bits one-per-bit rather than one-per-byte, breaking standard container semantics. It is the only standard container whose reference type is a proxy object, not a real bool&.

cpp
#include <vector>

std::vector<bool> flags{true, false, true};

// operator[] returns a proxy, not bool&
auto ref = flags[0];          // Type is vector<bool>::reference, not bool&
// bool& real_ref = flags[0]; // Compile error

// Taking the address does NOT give a bool*
// bool* p = &flags[0];       // Compile error

// Generic code breaks:
// auto& x = flags[0];        // x is a proxy, not bool& — surprise

Prefer these alternatives depending on your use case:

cpp
// C++11: fixed number of bits — best performance
#include <bitset>
std::bitset<64> bits;

// Dynamic sequence of bools with real container semantics
std::vector<char> bools{1, 0, 1};    // 1 byte per element
std::vector<uint8_t> flags2{1, 0};   // Explicit unsigned

// C++23: std::bitset is still fixed; for dynamic bit sets use boost::dynamic_bitset
// or store uint64_t words manually

The specialization exists for memory efficiency in large bit arrays. Use it only when you explicitly need packed storage and understand the proxy semantics, or when interfacing with code that returns std::vector<bool>.

Erase-remove idiom and erase_if (C++20)

Removing elements by value or predicate from a vector requires shifting everything after each removed element; the erase-remove idiom does it in a single O(n) pass. std::remove moves surviving elements to the front and returns a new end iterator, then erase trims the tail.

cpp
#include <vector>
#include <algorithm>

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

// C++98/11: erase-remove idiom
v.erase(std::remove(v.begin(), v.end(), 2), v.end());
// v is now {1, 3, 4, 5}

// With a predicate
std::vector<int> w{1, 2, 3, 4, 5, 6};
w.erase(std::remove_if(w.begin(), w.end(),
                       [](int x) { return x % 2 == 0; }),
        w.end());
// w is now {1, 3, 5}

C++20 introduced free functions that express the same operation more directly:

cpp
#include <vector>

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

// C++20: free function in <vector>
std::erase(v, 2);                                           // Remove all 2s
std::erase_if(v, [](int x) { return x > 3; });             // Remove all > 3

// Works on any sequence container (list, deque, string…)
std::vector<std::string> words{"foo", "bar", "foo", "baz"};
std::erase(words, "foo");  // C++20 — {"bar", "baz"}

std::erase / std::erase_if return the number of elements removed (a size_type), which is useful for logging or assertions.

Initializing from ranges (C++23)

C++23's range constructors and std::from_range tag let you construct a vector directly from any range expression without a two-step insert dance. This composes cleanly with std::views pipelines.

cpp
#include <vector>
#include <ranges>

// C++23: construct vector from any range
auto squares = std::views::iota(1, 11)
             | std::views::transform([](int x) { return x * x; });

std::vector<int> v(std::from_range, squares);
// v == {1, 4, 9, 16, 25, 36, 49, 64, 81, 100}

// C++23: append from a range
std::vector<int> w{0};
w.append_range(squares);   // Appends all elements from the range view

// C++20: workaround without from_range — insert from a range
// std::ranges::copy(squares, std::back_inserter(v));  // C++20

append_range (C++23) is the range-aware counterpart to push_back and avoids the std::back_inserter boilerplate that was necessary in C++20.

cpp
// C++23: collect filtered results directly
auto evens = std::views::iota(1, 21)
           | std::views::filter([](int x) { return x % 2 == 0; });

std::vector<int> even_vec(std::from_range, evens);
// even_vec == {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}

Sorted vector as a map replacement

A sorted std::vector<std::pair<K,V>> outperforms std::map for read-heavy workloads because binary search on contiguous memory is cache-friendly. The trade-off is O(n) insertion and deletion, making this pattern best suited for "build once, query many times" tables.

cpp
#include <vector>
#include <algorithm>
#include <utility>

using Table = std::vector<std::pair<std::string, int>>;

// Build phase: insert all entries then sort once (C++11)
Table build_table() {
    Table t;
    t.reserve(5);
    t.emplace_back("banana", 2);
    t.emplace_back("apple",  1);
    t.emplace_back("cherry", 3);
    t.emplace_back("date",   4);
    t.emplace_back("elderberry", 5);
    std::sort(t.begin(), t.end());  // Sort by key (first element)
    return t;
}

// Lookup: O(log n) binary search (C++11)
int lookup(const Table& t, const std::string& key) {
    auto it = std::lower_bound(t.begin(), t.end(), key,
        [](const auto& entry, const auto& k) { return entry.first < k; });
    if (it != t.end() && it->first == key)
        return it->second;
    return -1;  // not found
}

For a clean interface, wrap the pattern in a helper or use a flat map from a library. C++23's std::flat_map (from <flat_map>) codifies this pattern in the standard:

cpp
// C++23: std::flat_map — sorted vector under the hood, map-like interface
#include <flat_map>

std::flat_map<std::string, int> fm{
    {"apple", 1}, {"banana", 2}, {"cherry", 3}
};
int v = fm["banana"];  // O(log n) binary search on contiguous storage

std::flat_map supports the same interface as std::map but stores keys and values in separate sorted vectors, giving better cache behavior for lookups.

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