Oleg Goncharov

Posted on Nov 5

std::vector: From Basics to Implementation Intricacies

#cpp #containers #memory #bestpractices

A comprehensive practical guide to one of the most popular containers in C++

Introduction

std::vector is arguably the most widely used STL container. At first glance, it seems simple: a dynamic array with automatic memory management. But under the hood lies a multitude of subtleties that separate a beginner from a professional programmer.

In this article, we'll journey from basic usage to a deep understanding of std::vector's internal implementation, examine all its methods, memory management peculiarities, exceptions, optimization tricks, and pitfalls. We'll also explore alternatives to std::vector and when to use them.

Part 1: Fundamentals

What is std::vector?

std::vector is a sequence container that encapsulates a dynamic array. Elements are stored contiguously in memory, providing:

Constant-time O(1) access by index
Efficient iteration over elements
Compatibility with C-style arrays

#include <vector>
#include <iostream>

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

    // Index-based access
    std::cout << v[0] << std::endl;  // 1

    // Size and capacity
    std::cout << "size: " << v.size() << std::endl;      // 5
    std::cout << "capacity: " << v.capacity() << std::endl; // >= 5

    return 0;
}

Size vs Capacity: The Critical Distinction

This is the most important distinction for understanding std::vector:

size() — the number of elements actually stored in the vector
capacity() — the number of elements for which memory is allocated (without reallocation)

std::vector<int> v;
std::cout << "size: " << v.size() << ", capacity: " << v.capacity() << std::endl;
// size: 0, capacity: 0

v.push_back(1);
std::cout << "size: " << v.size() << ", capacity: " << v.capacity() << std::endl;
// size: 1, capacity: 1 (or more, depending on implementation)

v.push_back(2);
std::cout << "size: " << v.size() << ", capacity: " << v.capacity() << std::endl;
// size: 2, capacity: 2 (or more)

Requirements for Container Elements

std::vector<T> imposes certain requirements on type T:

Mandatory Requirements:

Destructor — must be accessible
Move constructor or copy constructor — for insertion/reallocation operations

Recommended Requirements:

Move constructor marked noexcept — this is critically important for performance!

class MyClass {
public:
    MyClass() = default;

    // ❌ Bad: may throw an exception
    MyClass(MyClass&& other) { /* ... */ }

    // ✅ Good: guaranteed not to throw
    MyClass(MyClass&& other) noexcept { /* ... */ }
};

Why is noexcept important?

During memory reallocation, std::vector checks if the move constructor is marked noexcept:

If yes → uses move (fast)
If no → uses copy (slow, but safe during exceptions)

#include <vector>
#include <iostream>
#include <type_traits>

class WithNoexcept {
public:
    WithNoexcept(WithNoexcept&&) noexcept {}
};

class WithoutNoexcept {
public:
    WithoutNoexcept(WithoutNoexcept&&) {}
};

int main() {
    std::vector<WithNoexcept> v1;
    std::vector<WithoutNoexcept> v2;

    // v1 will use move during reallocation
    // v2 will use copy during reallocation

    std::cout << std::is_nothrow_move_constructible<WithNoexcept>::value << std::endl;     // 1
    std::cout << std::is_nothrow_move_constructible<WithoutNoexcept>::value << std::endl;  // 0

    return 0;
}

Part 2: Memory Management

reserve(): Pre-allocating Memory

Signature: void reserve(size_type new_cap)

What it does: Reserves memory for at least new_cap elements. It doesn't create elements, only allocates memory.

When to use:

✅ You know in advance how many elements there will be
✅ Want to avoid reallocations during multiple push_back calls
✅ Optimizing performance

When NOT to use:

❌ Don't know the exact number of elements
❌ There will be few elements (1-10)
❌ Working with huge objects and want to save memory

std::vector<int> v;

// ❌ Bad: multiple reallocations
for (int i = 0; i < 10000; ++i) {
    v.push_back(i);  // may cause reallocation many times
}

// ✅ Good: one reallocation
std::vector<int> v2;
v2.reserve(10000);  // pre-allocated memory
for (int i = 0; i < 10000; ++i) {
    v2.push_back(i);  // no reallocations
}

What it returns: void — nothing.

Can it throw an exception: Yes

std::length_error — if new_cap > max_size()
std::bad_alloc — if memory allocation fails
Exception from element's copy/move constructor during reallocation

What happens if memory is already allocated:

std::vector<int> v;
v.reserve(100);
std::cout << v.capacity() << std::endl;  // >= 100

v.reserve(50);  // ❌ Does NOT decrease capacity!
std::cout << v.capacity() << std::endl;  // >= 100 (unchanged)

v.reserve(200);  // ✅ Increases capacity
std::cout << v.capacity() << std::endl;  // >= 200

Rule: reserve() never decreases capacity().

What happens to elements:

If reserve(n) is larger than current capacity():

A new memory block of size >= n is allocated
All existing elements are moved (or copied) to the new memory
Old memory is freed
All iterators, pointers, and references to elements become invalid

std::vector<int> v = {1, 2, 3};
int* ptr = &v[0];  // pointer to first element

v.reserve(1000);   // reallocation!

// ❌ ptr now points to freed memory!
// Using ptr is undefined behavior

resize(): Changing Size

Signature:

void resize(size_type count)
void resize(size_type count, const T& value)

What it does: Changes the number of elements (size()) in the vector.

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

// Increasing size
v.resize(5);  // adds elements with default value (0)
// v = {1, 2, 3, 0, 0}

v.resize(7, 42);  // adds elements with value 42
// v = {1, 2, 3, 0, 0, 42, 42}

// Decreasing size
v.resize(2);  // removes elements from the end
// v = {1, 2}

Difference from reserve():

	`reserve(n)`	`resize(n)`
Changes `size()`	❌ No	✅ Yes
Changes `capacity()`	✅ May increase	✅ May increase
Creates elements	❌ No	✅ Yes
Decreases `capacity()`	❌ Never	❌ Never

Can it throw an exception: Yes

std::length_error — if count > max_size()
std::bad_alloc — during reallocation
Exception from T's constructor when creating new elements

shrink_to_fit(): Releasing Unused Memory

Signature: void shrink_to_fit()

What it does: "Request" to reduce capacity() to size() — release unused memory.

Important: This is not a mandatory operation! The standard doesn't guarantee that memory will be released.

std::vector<int> v(1000);  // size = 1000, capacity >= 1000
v.resize(10);              // size = 10, capacity >= 1000 (!)

std::cout << "Before: capacity = " << v.capacity() << std::endl;  // >= 1000

v.shrink_to_fit();  // request to release unused memory

std::cout << "After: capacity = " << v.capacity() << std::endl;   // >= 10 (usually)

Pros:

✅ Releases unused memory
✅ Useful after bulk deletion of elements

Cons:

❌ May cause reallocation (expensive)
❌ Invalidates all iterators, pointers, and references
❌ Doesn't guarantee memory release (implementation may ignore)

Can it throw an exception: Yes (during reallocation)

When to use:

After bulk deletion of elements
When memory is critical
When confident the vector won't grow further

Memory Allocation Strategies

How does std::vector allocate memory during push_back()?

When size() == capacity() and you call push_back(), the vector:

Allocates a new memory block (usually 1.5-2 times larger than current)
Moves/copies all elements to the new memory
Inserts the new element
Frees the old memory

Typical growth strategies:

MSVC: capacity × 1.5
GCC/Clang: capacity × 2

std::vector<int> v;
std::cout << "capacity: " << v.capacity() << std::endl;  // 0

for (int i = 0; i < 10; ++i) {
    v.push_back(i);
    std::cout << "size: " << v.size() 
              << ", capacity: " << v.capacity() << std::endl;
}

// Example output (GCC):
// size: 1, capacity: 1
// size: 2, capacity: 2
// size: 3, capacity: 4
// size: 4, capacity: 4
// size: 5, capacity: 8
// size: 6, capacity: 8
// ...

Amortized complexity: push_back() has amortized constant O(1) complexity, despite periodic reallocations.

Part 3: Element Access

operator[] vs at()

operator[]:

T& operator[](size_type pos)
const T& operator[](size_type pos) const

at():

T& at(size_type pos)
const T& at(size_type pos) const

Key difference: bounds checking

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

// operator[] — does NOT check bounds
int x = v[10];  // ❌ Undefined behavior! But compiles

// at() — checks bounds
try {
    int y = v.at(10);  // ✅ Throws std::out_of_range
} catch (const std::out_of_range& e) {
    std::cout << "Error: " << e.what() << std::endl;
}

When to use:

Use `[]`	Use `at()`
Index is guaranteed valid	Index may be invalid
Performance is critical	Safety is critical
Release build	Debug build
Inside loop by vector size	User input

// ✅ Use operator[] — index always valid
for (size_t i = 0; i < v.size(); ++i) {
    std::cout << v[i] << std::endl;
}

// ✅ Use at() — index from user
size_t user_index;
std::cin >> user_index;
try {
    std::cout << v.at(user_index) << std::endl;
} catch (const std::out_of_range&) {
    std::cout << "Invalid index!" << std::endl;
}

Performance: operator[] is faster since it contains no bounds check. The difference is usually negligible, but can be noticeable in tight loops.

front(), back(), data()

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

// front() — first element
int first = v.front();  // 1
// Equivalent to: v[0] or v.at(0)

// back() — last element
int last = v.back();    // 5
// Equivalent to: v[v.size() - 1]

// data() — pointer to first element (C-style array)
int* ptr = v.data();
// Can pass to C API
some_c_function(v.data(), v.size());

⚠️ Important: front() and back() on empty vector — undefined behavior!

std::vector<int> empty;
int x = empty.front();  // ❌ UB!
int y = empty.back();   // ❌ UB!

// ✅ Correct: check before using
if (!empty.empty()) {
    int x = empty.front();
}

Part 4: Element Modification

push_back() vs emplace_back()

push_back():

void push_back(const T& value);  // copy
void push_back(T&& value);       // move

emplace_back() (C++11):

template<class... Args>
void emplace_back(Args&&... args);  // construct in-place

Difference:

push_back creates an object, then moves/copies it into the vector
emplace_back creates an object directly in the vector (without copy/move)

struct Point {
    int x, y;

    Point(int x, int y) : x(x), y(y) {
        std::cout << "Constructor\n";
    }

    Point(const Point&) {
        std::cout << "Copy constructor\n";
    }

    Point(Point&&) noexcept {
        std::cout << "Move constructor\n";
    }
};

std::vector<Point> v;
v.reserve(10);  // to avoid reallocations

// push_back: constructor + move
v.push_back(Point(1, 2));
// Output:
// Constructor
// Move constructor

// emplace_back: only constructor
v.emplace_back(3, 4);
// Output:
// Constructor

When to use emplace_back:

✅ Complex objects with expensive move operations
✅ Want to avoid creating temporary objects
✅ Passing constructor arguments directly

Can it throw an exception: Yes (both methods)

Exception during reallocation
Exception from T's constructor

What they return:

push_back: void (before C++17), reference (C++17+)
emplace_back: void (before C++17), reference (C++17+)

insert() and emplace()

insert() — insert at arbitrary position:

// Insert single element
iterator insert(const_iterator pos, const T& value);
iterator insert(const_iterator pos, T&& value);

// Insert n copies
iterator insert(const_iterator pos, size_type count, const T& value);

// Insert range
template<class InputIt>
iterator insert(const_iterator pos, InputIt first, InputIt last);

emplace() — construct in-place at arbitrary position:

template<class... Args>
iterator emplace(const_iterator pos, Args&&... args);

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

// Insert single element
auto it = v.insert(v.begin() + 2, 42);  // {1, 2, 42, 3, 4, 5}

// Insert multiple elements
v.insert(v.begin(), 3, 100);  // {100, 100, 100, 1, 2, 42, 3, 4, 5}

// Insert range
std::vector<int> other = {7, 8, 9};
v.insert(v.end(), other.begin(), other.end());

⚠️ Important: Insertion in the middle of a vector — expensive operation O(n), as it requires shifting all elements after the insertion point.

Iterator invalidation:

If insertion caused reallocation → all iterators are invalidated
Otherwise → iterators after the insertion point are invalidated

erase() and Element Deletion

erase():

iterator erase(const_iterator pos);
iterator erase(const_iterator first, const_iterator last);

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

// Delete single element
v.erase(v.begin() + 2);  // {1, 2, 4, 5}

// Delete range
v.erase(v.begin() + 1, v.begin() + 3);  // {1, 5}

pop_back() — remove last element:

void pop_back();

std::vector<int> v = {1, 2, 3};
v.pop_back();  // {1, 2}

⚠️ Important: pop_back() on empty vector — undefined behavior!

Can it throw an exception: erase() and pop_back() — no (no-throw guarantee)

Iterator invalidation:

erase() — iterators after the deletion point are invalidated
pop_back() — iterator to the last element is invalidated

clear() — Clear the Vector

void clear() noexcept;

What it does: Removes all elements, size() becomes 0.

What it does NOT do: Does NOT release memory! capacity() remains unchanged.

std::vector<int> v(1000);
std::cout << "size: " << v.size() << ", capacity: " << v.capacity() << std::endl;
// size: 1000, capacity: 1000

v.clear();
std::cout << "size: " << v.size() << ", capacity: " << v.capacity() << std::endl;
// size: 0, capacity: 1000 (!)

Can it throw an exception: No (no-throw guarantee)

Part 5: swap() — Exchanging Content

Signature:

void swap(vector& other) noexcept;

What it does: Exchanges the content of two vectors in constant time O(1).

std::vector<int> v1 = {1, 2, 3};
std::vector<int> v2 = {4, 5, 6, 7, 8};

std::cout << "Before swap:\n";
std::cout << "v1.size() = " << v1.size() << ", v1.capacity() = " << v1.capacity() << std::endl;
std::cout << "v2.size() = " << v2.size() << ", v2.capacity() = " << v2.capacity() << std::endl;

v1.swap(v2);  // or std::swap(v1, v2);

std::cout << "After swap:\n";
std::cout << "v1.size() = " << v1.size() << ", v1.capacity() = " << v1.capacity() << std::endl;
std::cout << "v2.size() = " << v2.size() << ", v2.capacity() = " << v2.capacity() << std::endl;

// v1 = {4, 5, 6, 7, 8}
// v2 = {1, 2, 3}

What happens to elements: Elements are not moved and not copied! Only internal pointers are exchanged.

What happens to iterators: Iterators remain valid, but now reference the other vector!

std::vector<int> v1 = {1, 2, 3};
std::vector<int> v2 = {4, 5, 6};

auto it1 = v1.begin();  // points to element 1 in v1

v1.swap(v2);

// it1 is still valid, but now points to an element in v2!
std::cout << *it1 << std::endl;  // 1 (element is now in v2)

Can it throw an exception: No (no-throw guarantee)

Trick: Releasing Memory via swap

Before C++11, shrink_to_fit() didn't exist. This trick was used:

std::vector<int> v(1000);
v.resize(10);  // size = 10, capacity = 1000

// ❌ clear() doesn't release memory
v.clear();  // size = 0, capacity = 1000

// ✅ Trick: swap with temporary empty vector
std::vector<int>().swap(v);  // size = 0, capacity = 0

How it works:

std::vector<int>() — creates empty temporary vector
.swap(v) — exchange: v becomes empty, temporary gets old data
Temporary vector is destroyed along with v's old data

Alternative variant (even more idiomatic):

std::vector<int> v(1000);
v.resize(10);

// Release unused memory via swap with compact copy
std::vector<int>(v).swap(v);

How it works:

std::vector<int>(v) — creates copy of v with capacity() == size()
.swap(v) — exchange: v gets compact copy
Old v (with large capacity()) is destroyed

Today: Use shrink_to_fit() instead of these tricks. But knowing them is useful for legacy code.

Part 6: std::vector — Special Case

std::vector<bool> is a template specialization of std::vector that does not behave like a normal std::vector.

Why is std::vector Special?

Goal: Memory saving. A normal bool takes 1 byte, but std::vector<bool> stores each bool as 1 bit.

#include <vector>
#include <iostream>

int main() {
    std::vector<bool> vb(100);
    std::vector<int> vi(100);

    // vb takes ~13 bytes (100 bits + overhead)
    // vi takes ~400 bytes (100 × 4 bytes)

    return 0;
}

Problems with std::vector

Problem 1: operator[] returns not bool&, but a special proxy object.

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

// ❌ Doesn't compile!
// bool& ref = vb[0];  // Error: cannot bind non-const lvalue reference

// ✅ Works (but this is a proxy, not a real reference)
auto ref = vb[0];
ref = false;  // changes vb[0]

// ❌ Taking address doesn't work
// bool* ptr = &vb[0];  // Error

Problem 2: Violates expectations from std::vector<T>.

template<typename T>
void process(std::vector<T>& v) {
    T& first = v[0];  // ✅ Works for std::vector<int>
                      // ❌ Doesn't work for std::vector<bool>
}

Problem 3: Slower for element-wise operations (due to bit packing).

// std::vector<int> — faster
for (auto& elem : vi) {
    elem = 42;  // direct memory write
}

// std::vector<bool> — slower
for (auto elem : vb) {  // note: not auto&
    elem = true;  // bit operations
}

Alternatives to std::vector

If you need real bool elements:

// ✅ Use std::vector<char>
std::vector<char> vc = {1, 0, 1};
bool& ref = reinterpret_cast<bool&>(vc[0]);  // now works

// ✅ Use std::deque<bool> (not specialized)
std::deque<bool> db = {true, false, true};
bool& ref2 = db[0];  // real reference

// ✅ Use std::bitset (if size is known at compile time)
std::bitset<100> bs;
bs[0] = true;

When to use std::vector<bool>:

Need memory savings
Many elements (thousands, millions)
Rarely need references to individual elements

Part 7: Exceptions in std::vector

Which Methods Can Throw Exceptions?

Method	Can throw?	Which exceptions?
`reserve()`	✅ Yes	`std::length_error`, `std::bad_alloc`, from `T` constructor
`resize()`	✅ Yes	`std::length_error`, `std::bad_alloc`, from `T` constructor
`push_back()`	✅ Yes	`std::bad_alloc`, from `T` constructor
`emplace_back()`	✅ Yes	`std::bad_alloc`, from `T` constructor
`insert()`	✅ Yes	`std::bad_alloc`, from `T` constructor
`emplace()`	✅ Yes	`std::bad_alloc`, from `T` constructor
`at()`	✅ Yes	`std::out_of_range`
`operator[]`	❌ No	—
`front()`	❌ No	—
`back()`	❌ No	—
`erase()`	❌ No	—
`pop_back()`	❌ No	—
`clear()`	❌ No	—
`swap()`	❌ No	—
`shrink_to_fit()`	✅ Yes	`std::bad_alloc`, from `T` constructor

Exception Safety Guarantees

std::vector provides strong exception guarantee for most operations:

If an operation throws, the vector remains in its original state
BUT: only if T's move constructor is marked noexcept!

struct ThrowingType {
    ThrowingType() = default;
    ThrowingType(const ThrowingType&) = default;

    // ❌ May throw an exception
    ThrowingType(ThrowingType&&) {
        throw std::runtime_error("Move failed!");
    }
};

std::vector<ThrowingType> v(10);
try {
    v.reserve(20);  // may result in inconsistent state!
} catch (...) {
    // v may be corrupted
}

Rule: Always mark the move constructor as noexcept!

Part 8: Iterators and Their Invalidation

Types of Iterators

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

// Iterator
std::vector<int>::iterator it = v.begin();

// Const iterator
std::vector<int>::const_iterator cit = v.cbegin();

// Reverse iterator
std::vector<int>::reverse_iterator rit = v.rbegin();

// Const reverse iterator
std::vector<int>::const_reverse_iterator crit = v.crbegin();

When Are Iterators Invalidated?

Operation	Iterator Invalidation
`reserve()`, if capacity increased	All iterators
`push_back()`, if capacity increased	All iterators
`push_back()`, if capacity NOT increased	Only `end()`
`insert()`, if capacity increased	All iterators
`insert()`, if capacity NOT increased	Iterators after insertion point
`erase()`	Iterators after deletion point
`clear()`	All iterators
`resize()`, if capacity increased	All iterators
`resize()`, if capacity NOT increased	Iterators after `size()`
`shrink_to_fit()`, if reallocation occurred	All iterators
`swap()`	Remain valid but reference other vector
`operator[]`, `at()`, `front()`, `back()`	Never

Example of invalidation:

std::vector<int> v = {1, 2, 3};
auto it = v.begin();

v.push_back(4);  // may cause reallocation

// ❌ it may be invalidated!
std::cout << *it << std::endl;  // undefined behavior if reallocation occurred

Correct approach:

std::vector<int> v = {1, 2, 3};
v.reserve(10);  // guarantee no reallocations

auto it = v.begin();
v.push_back(4);  // no reallocation

std::cout << *it << std::endl;  // ✅ OK

Part 9: Alternatives to std::vector

Although std::vector is the universal choice for most cases, situations exist where alternative containers can be more efficient. Let's consider the main alternatives.

C-style Arrays (T array[N])

What it is: Classic C-style arrays.

int arr[100];  // stack
int* arr2 = new int[100];  // heap

Pros:

✅ Minimal overhead
✅ Very fast (especially on stack)
✅ Compatibility with C API

Cons:

❌ Fixed size (for stack arrays)
❌ No automatic memory management (for heap arrays)
❌ No bounds checking
❌ Don't support STL algorithms directly
❌ Easy to make mistakes with size

When to use:

Fixed size known at compile time
Performance is critical
Small size (< 100 elements)
Working with C API

Performance: According to benchmarks, C-style stack arrays (~1.0x) are faster than std::vector without reserve() (2-3x), but nearly identical to std::vector with pre-reserved memory (1.1x).

std::array (C++11)

What it is: Wrapper around C-style array with STL interface.

#include <array>

std::array<int, 100> arr = {1, 2, 3};  // rest initialized to 0

Pros:

✅ Safety: at() with bounds checking
✅ STL compatibility (iterators, algorithms)
✅ No heap allocations (stack)
✅ Knows its size (size())
✅ Same performance as C-style array

Cons:

❌ Fixed size at compile time
❌ Cannot grow dynamically
❌ Stack allocation limit (~1-2 MB)

When to use:

Size known at compile time
Small size (< 10,000 elements)
No need for dynamic size changes
Want STL compatibility

std::array<int, 5> arr = {1, 2, 3, 4, 5};

// ✅ STL algorithms work
std::sort(arr.begin(), arr.end());

// ✅ Safe access
try {
    int x = arr.at(10);  // throws std::out_of_range
} catch (...) {}

// ✅ Knows size
std::cout << arr.size() << std::endl;  // 5

Comparison with vector:

	`std::array<T, N>`	`std::vector<T>`
Size	Fixed at compile time	Dynamic
Storage	Stack	Heap
Overhead	None	Pointer + size + capacity
Performance	Slightly faster	Slightly slower
Size changes	❌ No	✅ Yes

std::valarray

What it is: Container for mathematical operations over arrays.

#include <valarray>

std::valarray<double> v1 = {1.0, 2.0, 3.0};
std::valarray<double> v2 = {4.0, 5.0, 6.0};

std::valarray<double> result = v1 + v2;  // element-wise addition
// result = {5.0, 7.0, 9.0}

Pros:

✅ Optimized for mathematical operations
✅ Element-wise operations (+, -, *, /)
✅ Mathematical functions (sin, cos, exp, log)
✅ Slices for working with subarrays

Cons:

❌ Not standardized for general use
❌ Less documented
❌ Less popular
❌ Not all compilers optimize well

When to use:

Numerical computations
Linear algebra
Element-wise mathematical operations

std::valarray<double> v = {1.0, 2.0, 3.0, 4.0};

// Element-wise operations
v *= 2.0;  // {2.0, 4.0, 6.0, 8.0}
v += 1.0;  // {3.0, 5.0, 7.0, 9.0}

// Mathematical functions
std::valarray<double> result = std::sin(v);

// Slices
std::valarray<double> slice = v[std::slice(0, 2, 2)];  // every 2nd element

Important: std::valarray is not recommended for new code. Use specialized libraries (Eigen, Armadillo).

Boost.Container Alternatives

Boost provides several alternatives to std::vector for specific cases.

boost::container::vector

What it is: Enhanced version of std::vector.

#include <boost/container/vector.hpp>

boost::container::vector<int> v = {1, 2, 3};

Differences from std::vector:

✅ No bool specialization (behaves like normal vector)
✅ More flexible allocator handling
✅ Support for recursive containers
✅ Same implementation on all platforms
✅ Customizable growth strategy

// Customize growth strategy to 50% instead of 100%
typedef boost::container::vector_options< 
    boost::container::growth_factor<boost::container::growth_factor_50>
>::type growth_50_option_t;

boost::container::vector<int, boost::container::new_allocator<int>, growth_50_option_t> v;

When to use:

Issues with std::vector<bool>
Need customization of growth strategy
Working with non-standard allocators

boost::container::small_vector

What it is: Vector with optimization for small number of elements (Small Buffer Optimization).

#include <boost/container/small_vector.hpp>

// Holds up to 10 elements without heap allocation
boost::container::small_vector<int, 10> v;

v.push_back(1);  // on stack
v.push_back(2);  // on stack
// ... up to 10 elements on stack

v.push_back(11);  // switches to heap

Pros:

✅ First N elements stored on stack (fast)
✅ Automatically switches to heap when exceeding N
✅ Compatible with std::vector API
✅ Avoids allocations for small sizes

Cons:

❌ Larger object size (on stack)
❌ Copying more expensive (if < N elements)

When to use:

Usually few elements (< 10-20)
Want to avoid heap allocations
Performance of allocation is critical

// Typical use case: path components
boost::container::small_vector<std::string, 4> path_components;
path_components.push_back("home");
path_components.push_back("user");
path_components.push_back("documents");
// All on stack, no allocations!

boost::container::static_vector

What it is: Vector with fixed maximum capacity stored on stack.

#include <boost/container/static_vector.hpp>

boost::container::static_vector<int, 100> v;

v.push_back(1);  // OK
v.push_back(2);  // OK
// ... maximum 100 elements

// v.push_back(101);  // ❌ Exception or UB if capacity exceeded

Pros:

✅ No heap allocations at all
✅ Predictable performance
✅ Can change size (unlike std::array)
✅ Compatible with std::vector API (mostly)

Cons:

❌ Maximum size fixed at compile time
❌ Takes stack space
❌ Cannot grow beyond capacity

When to use:

Embedded systems
Real-time systems (predictability)
Maximum size known
Heap allocations not allowed

// Embedded: buffer for UART
boost::container::static_vector<uint8_t, 256> uart_buffer;

void receive_byte(uint8_t byte) {
    if (uart_buffer.size() < uart_buffer.capacity()) {
        uart_buffer.push_back(byte);
    }
}

boost::container::stable_vector

What it is: Vector where iterators and references are not invalidated during insertion/deletion.

#include <boost/container/stable_vector.hpp>

boost::container::stable_vector<int> v = {1, 2, 3};

int& ref = v[1];  // reference to element
auto it = v.begin() + 1;

v.push_back(4);  // reallocation!
v.insert(v.begin(), 0);

// ✅ ref and it are still valid!
std::cout << ref << std::endl;  // 2
std::cout << *it << std::endl;  // 2

How it works: Each element is stored in a separate node (like in list), but there's an array of pointers for fast access.

Pros:

✅ Iterator and reference stability
✅ Random access O(1) (like vector)
✅ Iterators not invalidated on insertion

Cons:

❌ Larger memory overhead (~2 pointers per element)
❌ Slower traversal (not cache-friendly)
❌ Not contiguous storage

When to use:

Iterator stability is critical
Many insertions/deletions in middle
Long-lived references to elements

boost::container::devector

What it is: Hybrid of vector and deque — fast insertion from both ends.

#include <boost/container/devector.hpp>

boost::container::devector<int> v = {3, 4, 5};

v.push_front(2);  // O(1) amortized - fast!
v.push_front(1);  // O(1) amortized
v.push_back(6);   // O(1) amortized
v.push_back(7);   // O(1) amortized

// v = {1, 2, 3, 4, 5, 6, 7}

Pros:

✅ Fast insertion from both ends O(1)
✅ Contiguous storage (like vector)
✅ Random access O(1)

Cons:

❌ Larger overhead (4 pointers instead of 3)
❌ capacity() has different semantics
❌ size() can be > capacity()

When to use:

Need insertion from both ends
Contiguous storage important (unlike deque)
FIFO/LIFO patterns

// Use case: sliding window
boost::container::devector<int> window;

void add_value(int value) {
    window.push_back(value);
    if (window.size() > 100) {
        window.pop_front();  // O(1)!
    }
}

Performance Comparison

Container	Allocation	Random Access	Push Back	Push Front	Insert Middle	Iterator Stability
C array	Stack	O(1) ⚡	❌	❌	❌	✅
`std::array`	Stack	O(1) ⚡	❌	❌	❌	✅
`std::vector`	Heap	O(1) ⚡	O(1)*	O(n)	O(n)	❌
`std::valarray`	Heap	O(1)	O(n)	O(n)	O(n)	❌
`boost::small_vector<T,N>`	Stack → Heap	O(1) ⚡	O(1)*	O(n)	O(n)	❌
`boost::static_vector<T,N>`	Stack	O(1) ⚡	O(1)*	O(n)	O(n)	✅
`boost::stable_vector`	Heap	O(1) 🐌	O(1)*	O(n)	O(n)	✅
`boost::devector`	Heap	O(1) ⚡	O(1)*	O(1)*	O(n)	❌
`std::deque`	Heap	O(1) 🐌	O(1)*	O(1)*	O(n)	❌
`std::list`	Heap	O(n)	O(1)	O(1)	O(1)	✅

* amortized complexity

⚡ — cache-friendly (contiguous memory)

🐌 — not cache-friendly

Selection Recommendations

Use std::vector when:

✅ This is your default choice (90% of cases)
✅ Need dynamic size
✅ Many elements
✅ Insertion only at end

Use std::array when:

✅ Size known at compile time
✅ Small size (< 10,000)
✅ Want to avoid heap allocations

Use C array when:

✅ Working with C API
✅ Performance is critical
✅ Very small size

Use boost::small_vector when:

✅ Usually few elements (< 20)
✅ Want to avoid allocations
✅ May grow beyond N

Use boost::static_vector when:

✅ Embedded/real-time
✅ Heap not available
✅ Maximum size known

Use boost::stable_vector when:

✅ Iterator stability critical
✅ Long-lived references
✅ Many middle insertions

Use boost::devector when:

✅ Need insertion from both ends
✅ Contiguous storage important
✅ Sliding window, FIFO/LIFO

DO NOT use std::valarray:

❌ Use Eigen, Armadillo for numerical computations

Part 10: std::vector Evolution Across Standards

C++98/03: The Foundation

Basic functionality
push_back(), insert(), erase()
Performance issues with complex object insertion

C++11: Revolution

1. Move semantics

std::vector<std::string> v1 = {"hello", "world"};
std::vector<std::string> v2 = std::move(v1);  // move, not copy

2. emplace_back() and emplace()

v.emplace_back(arg1, arg2);  // construct in-place

3. Initializer lists

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

4. noexcept

void swap(vector& other) noexcept;

5. shrink_to_fit()

v.shrink_to_fit();  // previously used swap trick

C++17: Improvements

1. Return value from emplace_back()

auto& ref = v.emplace_back(42);  // now returns reference

2. Type deduction on construction (CTAD)

std::vector v = {1, 2, 3};  // std::vector<int>

C++20: Further Enhancements

1. erase() and erase_if()

std::erase(v, 42);  // remove all elements == 42
std::erase_if(v, [](int x) { return x % 2 == 0; });  // remove even

2. Ranges

auto result = v | std::views::filter([](int x) { return x > 0; })
                | std::views::transform([](int x) { return x * 2; });

C++23: Continued Improvements

1. append_range()

v.append_range(some_range);  // insert range at end

2. insert_range()

v.insert_range(v.begin(), some_range);

Part 11: Tricks and Optimizations

1. Avoid Unnecessary Copies

// ❌ Bad: copy on each insertion
std::vector<std::string> v;
for (const auto& s : data) {
    v.push_back(s);  // copy
}

// ✅ Good: move
std::vector<std::string> v;
for (auto&& s : data) {
    v.push_back(std::move(s));  // move
}

// ✅ Even better: emplace_back (if applicable)
std::vector<std::string> v;
for (const auto& s : data) {
    v.emplace_back(s);
}

2. reserve() for Known Size

// ❌ Bad: multiple reallocations
std::vector<int> v;
for (int i = 0; i < 10000; ++i) {
    v.push_back(i);
}

// ✅ Good: single allocation
std::vector<int> v;
v.reserve(10000);
for (int i = 0; i < 10000; ++i) {
    v.push_back(i);
}

3. Erasing by Condition: erase-remove Idiom

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

// ❌ Bad: O(n²)
for (auto it = v.begin(); it != v.end(); ) {
    if (*it % 2 == 0) {
        it = v.erase(it);
    } else {
        ++it;
    }
}

// ✅ Good: erase-remove idiom, O(n)
v.erase(
    std::remove_if(v.begin(), v.end(), [](int x) { return x % 2 == 0; }),
    v.end()
);

// ✅ Even better (C++20):
std::erase_if(v, [](int x) { return x % 2 == 0; });

4. Avoid bool as Element Type

// ❌ Bad: std::vector<bool> — not a real vector
std::vector<bool> vb;

// ✅ Good: use char or int
std::vector<char> vc;

// ✅ Or std::deque<bool>
std::deque<bool> db;

5. Use data() for C API Interaction

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

// ✅ Pass to C function
some_c_function(v.data(), v.size());

// ✅ Equivalent to:
some_c_function(&v[0], v.size());

// ⚠️ But data() is safer for empty vector

6. Prefer Range-Based For

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

// ❌ Old style
for (size_t i = 0; i < v.size(); ++i) {
    std::cout << v[i] << std::endl;
}

// ✅ Modern style
for (const auto& elem : v) {
    std::cout << elem << std::endl;
}

// ✅ With modification
for (auto& elem : v) {
    elem *= 2;
}

7. Memory Release

std::vector<int> v(1000000);
v.clear();  // size = 0, but capacity = 1000000!

// ✅ C++11+: shrink_to_fit
v.shrink_to_fit();

// ✅ Legacy: swap trick
std::vector<int>().swap(v);

// ✅ Or
std::vector<int>(v).swap(v);

8. Prefer emplace_back for Complex Types

struct BigObject {
    BigObject(int a, double b, std::string c) { /* ... */ }
};

std::vector<BigObject> v;
v.reserve(100);

// ❌ Bad: create temporary + move
v.push_back(BigObject(1, 2.0, "hello"));

// ✅ Good: construct in-place
v.emplace_back(1, 2.0, "hello");

9. Use resize() Instead of Multiple push_back()

// ❌ Bad
std::vector<int> v;
for (int i = 0; i < 1000; ++i) {
    v.push_back(0);
}

// ✅ Good
std::vector<int> v(1000);  // or v.resize(1000);

10. Be Careful with Nested Vectors

// ❌ Bad: memory fragmentation
std::vector<std::vector<int>> matrix;

// ✅ Better: flat array with indexing
std::vector<int> flat_matrix(rows * cols);
auto& elem = flat_matrix[row * cols + col];

Conclusion

std::vector is a powerful but subtle tool. Key takeaways:

Always remember:

size() ≠ capacity()
Reallocation invalidates iterators
reserve() for known size
noexcept on move constructor is critical
operator[] doesn't check bounds, at() does
std::vector<bool> is not a real std::vector
emplace_back() can be faster than push_back()
Use erase-remove idiom for conditional deletion

Avoid:

Multiple reallocations
std::vector<bool> if you need real references
Middle insertions (when avoidable)
Unnecessary copying

Use:

reserve() when you know size
emplace_back() for complex types
shrink_to_fit() for memory release
Range-based for loops
data() for C API

Alternatives:

std::array for fixed size
boost::small_vector for few elements
boost::static_vector for embedded
boost::stable_vector for iterator stability
boost::devector for both-end insertion

Mastering these details will help you write more efficient and safer code. std::vector is not just a dynamic array; it's a complex container with many subtleties that separate professionals from beginners.

Useful References:

Have questions? Ask in the comments!