std::vector — Use std::vector for dynamic arrays and common operations - C Plus Plus

SECTION 1

Historical Context & Motivation

Before the Standard Template Library (STL) became part of C++, programmers who needed a dynamically sized collection had to manage heap memory manually—calling malloc or new[], tracking capacity themselves, and never forgetting to free or delete[] the allocation when it was no longer needed. This was tedious, error-prone, and the leading cause of memory leaks and buffer overflows in production C and C++ code. The need for a safe, efficient, and generic resizable array was one of the primary motivations behind what eventually became std::vector.

1979 • C with Classes

Bjarne Stroustrup begins work on C with Classes at Bell Labs. Dynamic arrays are managed through raw pointers and manual new[]/delete[] calls, with no standard container abstraction.

1994 • STL Proposal Accepted

Alexander Stepanov and Meng Lee present the STL to the ISO C++ committee. The library introduces generic containers—including vector—and iterator-based algorithms, fundamentally reshaping how C++ programmers think about data structures.

1998 • C++98 Standard

The first ISO C++ standard ships with std::vector as part of the standard library. It provides RAII-managed contiguous storage, iterators, and exception-safe element access.

2011 • C++11 Modernization

C++11 adds move semantics, emplace_back, initializer-list construction, and range-based for loops, making vector usage more expressive and efficient.

2020 • C++20 and Beyond

C++20 introduces ranges, the three-way comparison operator, and std::erase/std::erase_if for vectors, continuing to refine the container's ergonomics.

The central question that std::vector answers is deceptively simple: how do we provide a dynamically sized, contiguous-memory array that is as fast as a raw C array for random access, yet automatically manages its own memory, grows when needed, and cooperates with the generic algorithms of the STL? Understanding the design decisions behind vector—its growth strategy, iterator model, and memory layout—is foundational to writing idiomatic, performant C++.

SECTION 2

Core Principles & Definitions

std::vector<T> is a class template defined in <vector> that encapsulates a dynamically allocated contiguous array of objects of type T. It owns its storage, grows automatically on insertion, and destroys every element when the vector itself goes out of scope—embodying the RAII (Resource Acquisition Is Initialization) idiom. Five foundational ideas govern its behavior and performance characteristics.

Contiguous Storage

Elements reside in a single heap-allocated block, so &v[0] yields a pointer usable by any C API expecting a raw array. This also means excellent cache locality for sequential traversals.

Size vs. Capacity

size() reports the number of live elements. capacity() reports how many elements the current allocation can hold before a reallocation is triggered. The gap between the two is reserved but uninitialized storage.

Amortized Growth

When size() == capacity() and an element is inserted, vector allocates a new block (typically 1.5× or 2× the old capacity), moves every element, and frees the old block. This yields amortized O(1) push_back.

Iterator Model

Vector iterators are random-access iterators—they support pointer arithmetic. However, any operation that triggers reallocation (e.g., push_back past capacity) invalidates all existing iterators.

RAII Ownership

The vector's destructor calls each element's destructor and then deallocates the storage. Copy assignment deep-copies; move assignment transfers ownership. This eliminates the manual new/delete juggling of pre-STL C++.

✦

KEY TAKEAWAY

Think of std::vector like a notebook with blank pages at the back. Writing on the next blank page (push_back when size < capacity) is instant. But once every page is full, you must buy a bigger notebook (reallocation), copy all your notes, and recycle the old one. The trick is that each new notebook is double the size, so the expensive copying happens less and less frequently—giving you amortized constant cost per page written.

SECTION 3

Visual Explanation — Memory Layout

The diagram below illustrates the internal memory layout of a std::vector<int> that currently holds five elements but has a capacity of eight. The three internal pointers that every vector maintains—begin, end (one past the last live element), and end_of_storage (one past the last allocated slot)—are shown to clarify the distinction between size and capacity.

The vector object on the stack stores three pointers into a heap-allocated block. Slots [0]–[4] contain live elements; slots [5]–[7] are allocated but uninitialized—available for future push_back calls without reallocation.

Observe that the three internal pointers—begin_ptr (cyan), end_ptr (violet), and end_of_storage (pink)—encode both size and capacity without storing them as separate integers. The size is end_ptr − begin_ptr, and the capacity is end_of_storage − begin_ptr. This minimalist design ensures that sizeof(std::vector<T>) is exactly three pointers (typically 24 bytes on a 64-bit platform) regardless of how many elements the vector contains.

SECTION 4

How Growth Works — The Amortized Analysis

The most performance-critical aspect of std::vector is its geometric growth strategy. When a push_back call finds that size() == capacity(), the vector must allocate a new, larger block, move (or copy) every existing element into it, and deallocate the old block. The key design choice is the growth factor: a multiplicative constant k (commonly 2 in GCC's libstdc++ and 1.5 in MSVC's STL) by which the capacity is multiplied each time a reallocation occurs.

NEW CAPACITY AFTER REALLOCATION

capacity_new = k × capacity_old (k ≈ 1.5 or 2)

where k is the implementation-defined growth factor. A factor of 2 doubles the allocation; a factor of 1.5 grows by 50%. Both yield amortized O(1) insertion.

AMORTIZED COST OF N PUSH_BACKS

Total copies ≤ n × k / (k − 1) ⟹ amortized cost per push_back = O(1)

After n insertions starting from an empty vector, the total number of element copies caused by reallocations forms a geometric series. For k = 2, the sum converges to approximately 2n, so each insertion costs at most 2 copies on average—hence O(1) amortized.

NUMBER OF REALLOCATIONS

reallocations = ⌈log_k(n)⌉

Inserting n elements into an initially empty vector triggers at most ⌈log_k(n)⌉ reallocations. For n = 1 000 000 and k = 2, this is only about 20 reallocations.

⚠

Why Not Grow Linearly?

If the vector grew by a constant amount (e.g., add 100 slots each time), inserting n elements would cause O(n²) total copies because the number of reallocations is O(n), each copying O(n) elements. Geometric growth—multiplying by a factor > 1—keeps the total copies proportional to n, making amortized O(1) possible.

SECTION 5

Common Operations — A Detailed API Tour

The following diagram and table catalog the most frequently used std::vector member functions, grouped by category: construction, element access, modifiers, and capacity management. Understanding the time complexity and iterator invalidation rules for each operation is essential for writing correct and performant code.

A quick-reference map of the most commonly used std::vector operations, grouped into four categories: construction (cyan), element access (violet), modifiers (amber), and capacity management (emerald).

Operation	Time Complexity	Invalidates Iterators?
`push_back` / `emplace_back`	Amortized O(1)	Only if reallocation occurs (size == capacity); otherwise no
`pop_back`	O(1)	Only the past-the-end iterator and the erased element's iterator
`insert(pos, val)`	O(n) — shifts elements	All iterators at or after `pos`; all if reallocation
`erase(pos)`	O(n) — shifts elements	All iterators at or after `pos`
`operator[]` / `at()`	O(1)	No
`clear`	O(n) — destroys elements	All iterators
`reserve(n)`	O(n) if reallocation; O(1) otherwise	All iterators if reallocation occurs

Time complexities and iterator invalidation rules for key vector operations

SECTION 6

Worked Example — Building and Processing a Vector

Let us walk through a complete example: reading an unknown number of student scores into a vector, computing the mean, and removing all scores below 60 using the erase–remove idiom. This exercise combines construction, iteration, algorithm integration, and element removal—all core vector competencies.

Read, Compute Mean, and Filter Scores

1
Step 1 — Declare and populate the vector

We create an empty std::vector<int> and populate it with an initializer list to simulate pre-loaded scores. In practice, you might use push_back in a loop reading from std::cin. std::vector<int> scores{72, 85, 58, 91, 44, 67, 50, 88, 95, 61};

scores.size() = 10, scores.capacity() ≥ 10
2
Step 2 — Compute the mean using std::accumulate

We include <numeric> and call std::accumulate with the iterator pair scores.begin() and scores.end() and an initial value of 0. Because vector iterators are random-access, they satisfy the requirements of any STL algorithm. int total = std::accumulate(scores.begin(), scores.end(), 0); double mean = static_cast<double>(total) / scores.size();

total = 711, mean = 71.1
3
Step 3 — Remove failing scores with erase–remove

The erase–remove idiom is the canonical way to remove elements matching a predicate. std::remove_if (from <algorithm>) shifts the 'kept' elements to the front and returns an iterator to the new logical end. We then call erase to actually shrink the vector. scores.erase( std::remove_if(scores.begin(), scores.end(), [](int s){ return s < 60; }), scores.end()); In C++20, this simplifies to std::erase_if(scores, [](int s){ return s < 60; });

scores now contains {72, 85, 91, 67, 88, 95, 61} — 7 elements, all ≥ 60
4
Step 4 — Sort and display

Finally, we sort the remaining scores in ascending order with std::sort (O(n log n), using introsort) and print them with a range-based for loop. std::sort(scores.begin(), scores.end()); for (int s : scores) std::cout << s << ' ';

Output: 61 67 72 85 88 91 95

💡

emplace_back vs. push_back

push_back(x) copies or moves x into the vector. emplace_back(args...) constructs the element in place by forwarding args directly to T's constructor—avoiding an extra copy/move. For trivial types like int, the difference is negligible; for expensive-to-copy types like std::string or custom classes, prefer emplace_back.

SECTION 7

Strengths, Limitations & Container Comparisons

std::vector is the default container recommended by the C++ Core Guidelines (maintained by Bjarne Stroustrup and Herb Sutter), and for good reason: its contiguous memory layout yields excellent cache performance, and its random-access iterators enable every STL algorithm. However, it is not the right choice in every scenario. The following table compares vector against other common containers to help you make informed decisions.

Criterion	std::vector	std::deque	std::list
Memory layout	Single contiguous block	Array of fixed-size blocks	Doubly-linked nodes (scattered)
Random access	O(1) — excellent cache locality	O(1) — slightly worse locality	O(n) — no random access
push_back	Amortized O(1)	Amortized O(1)	O(1)
push_front	O(n) — must shift all elements	Amortized O(1)	O(1)
Insert/erase at middle	O(n)	O(n)	O(1) given iterator
Iterator invalidation on insert	All (if reallocation)	All iterators	None
C API interop (raw pointer)	Yes — data() yields T*	No	No

Comparison of std::vector, std::deque, and std::list

🔀

WHEN TO PICK SOMETHING ELSE

Use std::deque when you need efficient insertion at both ends (e.g., implementing a BFS queue). Use std::list or std::forward_list only when you require guaranteed O(1) splicing or when iterator stability across insertions is paramount. Use std::array when the size is known at compile time and will never change. In all other cases, start with std::vector and measure before switching.

SECTION 8

Connection to Advanced Theory

A solid grasp of std::vector opens the door to several advanced C++ topics. The allocator model, move semantics, exception safety guarantees, and the interplay between containers and algorithms all build on the foundational concepts explored in this lesson. The table below maps vector concepts to their advanced extensions.

Vector Concept	Advanced Extension
Default allocator (`std::allocator<T>`)	Custom allocators (pool allocators, arena allocators) for controlling allocation strategy and memory locality
Move semantics with `push_back(std::move(x))`	Perfect forwarding, universal references, and `noexcept` move constructors (vector uses move only if T's move ctor is noexcept)
Erase–remove idiom	C++20 `std::erase`/`std::erase_if`, Ranges library with views and actions for lazy/eager element filtering
Iterator-based algorithms	C++20 Ranges (constrained algorithms, pipe syntax), parallel execution policies (`std::execution::par`)
`vector<bool>` specialization	Space-efficient bitset; note: it is a proxy container and does NOT provide true bool references. Prefer `std::bitset` or `boost::dynamic_bitset` for clarity

From vector fundamentals to advanced C++ topics

⚠

The vector<bool> Trap

std::vector<bool> is a partial specialization that packs bits, meaning operator[] returns a proxy object, not a bool&. Code that takes a reference to an element—like bool& b = v[0];—will not compile. This has been widely criticized and is considered a design mistake. For a general-purpose boolean container, use std::vector<char> or std::deque<bool> instead.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

Explain why calling v.reserve(1000) before inserting 1000 elements into an empty vector improves performance compared to calling push_back 1000 times without reserving. What changes in terms of allocations, copies, and iterator validity?

Show answer

Without reserve, the vector starts with a small capacity and must reallocate approximately ⌈log₂(1000)⌉ ≈ 10 times, each time allocating a new block, copying all existing elements, and freeing the old block. With reserve(1000), a single allocation of at least 1000 slots is performed upfront, so all subsequent push_back calls are true O(1) with no reallocation. Additionally, iterators taken before the loop remain valid throughout because no reallocation occurs, which is critical if other code holds iterators.

Question 2: BASIC CALCULATION

A vector has size() == 6 and capacity() == 8 on a system where the growth factor is 2. After calling push_back four more times, what are the resulting size and capacity? How many reallocations occurred during those four insertions?

Show answer

Starting state: size = 6, capacity = 8. The first two push_backs fill slots 6 and 7, reaching size = 8 with no reallocation. The third push_back triggers a reallocation because size == capacity. The new capacity becomes 8 × 2 = 16. Elements are moved to the new block, and the third new element is placed. The fourth push_back uses an existing slot (size 10, capacity 16). Final result: size = 10, capacity = 16, with exactly 1 reallocation (which copied 8 elements).

Question 3: INTERMEDIATE

Write a function std::vector<int> removeDuplicates(std::vector<int> v) that takes a vector of integers (possibly unsorted), removes duplicate values, and returns the result sorted in ascending order. Use only standard library algorithms and vector operations. Aim for O(n log n) overall time complexity.

Show answer

The approach is to first sort the vector, then use std::unique to move duplicates to the end, and finally erase them:

std::vector<int> removeDuplicates(std::vector<int> v) {
    std::sort(v.begin(), v.end());          // O(n log n)
    auto it = std::unique(v.begin(), v.end()); // O(n)
    v.erase(it, v.end());                   // O(n) in worst case
    return v;
}

std::sort dominates at O(n log n). std::unique requires a sorted range and moves consecutive duplicates past the returned iterator. The erase call then physically removes them.

Question 4: APPLIED

You are processing a stream of sensor readings (doubles) arriving at 1 kHz. You need to buffer the last 10 seconds of readings for analysis. Design a solution using std::vector. Discuss: (a) how you would size the vector, (b) whether you would use reserve, (c) what happens when the buffer is full and a new reading arrives, and (d) whether std::vector is actually the best container for this use case.

Show answer

(a) You need to store 10 × 1000 = 10 000 readings. (b) You should call reserve(10000) to avoid reallocations during the initial fill. (c) When the buffer is full, the oldest reading must be removed before inserting the newest. Erasing from the front of a vector is O(n) because all remaining elements must shift—this is prohibitively expensive at 1 kHz. (d) A vector is actually a poor choice here. A std::deque (amortized O(1) pop_front) or, even better, a fixed-size circular buffer (e.g., boost::circular_buffer or a hand-rolled ring buffer over a vector with index arithmetic) would be the appropriate design.

Question 5: CRITICAL THINKING

The C++ standard mandates that std::vector storage be contiguous, and that push_back provide amortized O(1) time complexity. Prove that a multiplicative growth factor strictly greater than 1 is both necessary and sufficient for amortized O(1) insertion. Then argue whether the specific choice of k = 2 versus k = 1.5 has any practical consequence beyond constant factors. Consider memory fragmentation.

Show answer

Necessity: Suppose capacity grows by a constant c instead of a factor. After n insertions, the number of reallocations is Θ(n/c), and reallocations at step i copy Θ(i) elements. The total work is Σ(i from 1 to n/c) of c·i = Θ(n²/c), giving O(n) amortized cost per insertion—not O(1). A multiplicative factor k > 1 gives ⌈

\log_k

(n)⌉ reallocations. The total copies form a geometric series: n + n/k + n/k² + … ≤ n·k/(k−1), which is Θ(n), yielding amortized O(1). Sufficiency is thus established. Regarding k = 2 vs. k = 1.5: with k = 2, the new allocation is always larger than the sum of all previous allocations, so the old blocks can never be reused by the allocator for the new block. With k = 1.5 (or more precisely, k ≤ φ ≈ 1.618), after several reallocations the sum of previously freed blocks exceeds the next requested size, allowing the allocator to potentially reuse that memory—reducing heap fragmentation. This is a real engineering consideration cited by MSVC's choice of k = 1.5.

SUMMARY

Summary

std::vector is the workhorse container of the C++ Standard Library, providing a dynamically resizable, contiguous array with O(1) random access and amortized O(1) push_back. Its internal design revolves around three pointers—begin, end, and end-of-storage—encoding both size and capacity. A geometric growth strategy (factor k > 1) ensures that the total cost of n insertions is Θ(n), not Θ(n²).

Key operations include push_back / emplace_back for appending, reserve for pre-allocating capacity, the erase–remove idiom for efficient element removal, and the full suite of random-access iterators that interoperate with all STL algorithms. Be mindful of iterator invalidation on reallocation, the O(n) cost of insert/erase at non-back positions, and the pitfalls of vector<bool>. When in doubt, vector is the right starting point—profile before reaching for a more specialized container.