Using std::vector in C++

std::vector is the most commonly used sequential container in C++. It provides a dynamic array stored in contiguous memory: O(1) random access, amortized O(1) push_back, and usually O(n) cost for insertions or deletions in the middle due to element shifting. This article covers capacity management (size/capacity), growth behavior, reserve/resize, push_back vs emplace_back, iterator invalidation, memory layout (data()), shrink_to_fit, and performance tips.

1) Basic Usage

#include <vector>
#include <iostream>
using namespace std;

int main() {
    vector<int> v;                // empty
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);

    cout << "size=" << v.size() 
         << " capacity=" << v.capacity() << "\n";

    cout << v[1] << " " << v.at(2) << "\n"; // [] unchecked, at() checked

    for (int x : v) cout << x << " ";
}

size is the number of elements, while capacity is the number of elements the vector can hold before requiring reallocation.

2) Contiguous Memory & data()

A vector stores its elements in contiguous memory, so its buffer can safely be used with C APIs.

#include <cstring>  // memcpy
#include <vector>

int main() {
    vector<char> buf(8, 0);
    const char* msg = "C++";
    memcpy(buf.data(), msg, 3);   // contiguous memory
}

This layout is advantageous for I/O, SIMD, graphics, networking buffers, and interoperability with C libraries.

3) Growth Strategy, reserve and resize

• reserve(n): increases capacity to at least n without changing size.
• resize(n): changes the size to n (and grows capacity if needed).

#include <vector>
#include <iostream>
using namespace std;

int main() {
    vector<int> v;

    v.reserve(1000);          // reduces reallocations
    for (int i=0; i<1000; i++)
        v.push_back(i);

    v.resize(1200, -1);       // adds 200 new elements with default value -1

    cout << v.size() << " " << v.capacity() << "\n";
}

Growth factor depends on the platform (typically ~1.5–2×). Pre-reserving capacity can drastically improve performance.

4) Insertion & Deletion: push_back vs emplace_back, insert/erase

• push_back(x) inserts by copy/move.
• emplace_back(args...) constructs the object in-place (no temporary).
• insert and erase shift elements → generally O(n).

#include <string>
#include <vector>
using namespace std;

struct Book {
    string title; 
    double price; 
    int pages;
    Book(string t, double p, int s)
        : title(t), price(p), pages(s) {}
};

int main() {
    vector<Book> books;
    books.emplace_back("C++ Primer", 180.0, 950);       // in-place
    books.push_back(Book{"Effective C++", 150.0, 320}); // temporary + move
    books.insert(books.begin(), {"Clean Code", 175.0, 464});
    books.erase(books.begin() + 1);
}

emplace_back is preferred for expensive-to-copy objects. For frequent middle insertions, consider deque or list.

5) Iterator Invalidation

Reallocation and element shifting can invalidate iterators, pointers, and references.

• Reallocation (capacity growth) invalidates **all** iterators, references, and data().
• insert/erase invalidates iterators at or after the operation point.

#include <vector>
using namespace std;

int main() {
    vector<int> v{1,2,3};
    auto it = v.begin();
    v.push_back(4);   // may reallocate
    // 'it' may now be invalid → undefined behavior if used
}

Use reserve to prevent reallocation; reacquire iterators after operations that may invalidate them.

6) Performance Tips

• Use reserve when size is known in advance.
• Use emplace_back for in-place construction.
• Ensure your types support move semantics to avoid unnecessary copies.
• Prefer insertion at the end; middle operations cost O(n).
• clear() sets size to 0 but does not reduce capacity.
• shrink_to_fit() is a non-binding request; compilers may ignore it.

7) assign, swap, shrink_to_fit

#include <vector>
using namespace std;

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

    v.assign(3, 9);              // {9, 9, 9}

    vector<int>(v).swap(v);      // shrink idiom
    v.shrink_to_fit();           // request (not guaranteed)
}

The "shrink idiom" (vector<T>(v).swap(v)) is often more effective than shrink_to_fit().

8) Sorting, Searching & Algorithms

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int main() {
    vector<int> a{5,1,4,2,3};

    sort(a.begin(), a.end());                    // 1 2 3 4 5
    bool found4 = binary_search(a.begin(), a.end(), 4);
    auto pos = lower_bound(a.begin(), a.end(), 3);

    cout << found4 << " @" << (pos - a.begin()) << "\n";
}

With C++20, std::ranges allows cleaner pipelines via views.

9) Advanced Topics: Allocator, vector<bool>, Small Objects

• Custom allocators: for memory pools, tracking, alignment.
• vector<bool>: optimized bit-packed specialization; beware proxy references.
• Small string optimization: applies to std::string, not vector.

10) Example: Book List

#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

struct Book {
    string title;
    double price;
    int pages;
    Book(string t, double p, int s)
        : title(move(t)), price(p), pages(s) {}
};

int main() {
    vector<Book> books;
    books.reserve(4);

    books.emplace_back("C++ Primer", 180.0, 950);
    books.emplace_back("Effective C++", 150.0, 320);
    books.emplace_back("Clean Code", 175.0, 464);

    sort(books.begin(), books.end(),
         [](const Book& a, const Book& b){
             return a.price < b.price;
         });

    auto it = find_if(books.begin(), books.end(),
        [](const Book& b){ return b.price >= 160.0; });

    if (it != books.end())
        cout << it->title << " " << it->price << "\n";
}

11) Common Mistakes

• Using vector for frequent middle insertions → consider deque or list.
• Using invalidated iterators after reallocation.
• Unnecessary copying instead of using move/emplace.
• Not reserving capacity for known workloads.
• Assuming vector<bool> behaves like a normal vector.

12) TL;DR

Related Articles