Collapse All Levels Collapse Top Level Expand Top Level Expand All Levels
News Articles Recipes Beginner's Guide to C++ Lists
@hackingcpp RSS Feed About Privacy Home

    std::vector std::vector std::vector

    C++'s default dynamic array
    • array = can hold different values/objects of same type
    • dynamic = size can be changed at runtime

    Basic Usage Basics

    Quick Start

    #include <vector>

    std::vector<int> v {2, 4, 5};
v.push_back(6);
v.pop_back();
v[1] = 3;
v.resize(5, 0);

    cout << v[2];
for (int x : v) 
  cout << x << ' '
    

    • 2
    • 4
    • 5
    

    • 2
    • 4
    • 5
    • 6
    

    • 2
    • 4
    • 5
    •  
    

    • 2
    • 3
    • 5
    

    • 2
    • 3
    • 5
    • 0
    • 0
    

    prints 5

prints 2 3 5 0 0

    Make New Vectors

    // from list of values: C++11
vector<int> v {0, 1, 2, 3};
// manymultiple identical values:
vector<int> w (4, 2)
// deep copy:
vector<int> b {v};
    
v: 
    • 0
    • 1
    • 2
    • 3
    

w: 
    • 2
    • 2
    • 2
    • 2
    

b: 
    • 0
    • 1
    • 2
    • 3
    Careful!
    std::vector initialization pitfall

    Access Elements

    vector<int> v {2, 4, 6, 8};
// read value at index
cout << v[1];
// assign value at index
v[1] = 3;

    // first element
cout << v.front();
// last element
cout << v.back();
    v: 
    • 2
    • 4
    • 6
    • 8
    

prints 4

v: 
    • 2
    • 3
    • 6
    • 8
    

    
prints 2

prints 8

    Assign New Content

    vector<int> u {5,7};
vector<int> v {1,2,3};

    // copy-assign from other// copy-assign
u = v;

    // multiple times same value// many times same
v.assign(4, 9);
    • u
     
    • v
    

    • 5
    • 7
     
    • 1
    • 2
    • 3
    

    • u
       
    • v
    

    • 1
    • 2
    • 3
     
    • 1
    • 2
    • 3
    

    • u
       
    • v
    

    • 1
    • 2
    • 3
     
    • 9
    • 9
    • 9
    • 9

    Size vs. /Capacity

    • .size() → number of elements in vector
    • .resize(new_number_of_elements)
    • .capacity() → number of avail.available memory slots
    • .reserve(new_capacity) 
    
vector<int> v;
v.push_back(7);
v.reserve(4);
v.push_back(8);
v.push_back(9);

    auto s = v.size();
auto c = v.capacity();

    v.resize(6,0);
            capacity size
               0    0

    • 7
      •              1    1
    

    • 7
    •  
    •  
    •  
      •        4    1
    

    • 7
    • 8
    •  
    •  
      •        4    2
    

    • 7
    • 8
    • 9
    •  
      •        4    3
    

    s: 3
c: 4

    • 7
    • 8
    • 9
    • 0
    • 0
    • 0
      •    6    6

    If you know the (approximate) number of elements in advance ⇒ reserve before adding elements to the vector!

    This avoids unnecessary memory allocations and copying during the growth phase. See here for a short explanation.

    Copies Are Always Deep! Copy

    vector is a so-called regular type (it behaves like int )
    • deep copying: copying creates a new vector object and copies all contained objects
    • deep assignment: all contained objects are copied from source to assignment target
    • deep comparison: comparing two vectors compares the contained objects
    • deep ownership: destroying a vector destroys all contained objects

    Most types in the C++ standard library and ecosystem are regular.

    vector<int> a {1,2,3,4};
vector<int> b = a;  // copy a → b
if (a == b) cout << "equal";

    a[0] = 9;


    cout << b[0];
if (a != b) cout << "different";
    a: 
    • 1
    • 2
    • 3
    • 4
    
b: 
    • 1
    • 2
    • 3
    • 4
    
equal

    a: 
    • 9
    • 2
    • 3
    • 4
    
b: 
    • 1
    • 2
    • 3
    • 4
    

    1
different

    Be aware that copying vectors can be quite expensive (= take a long time) if they contain many elements!

    Traversal / Loops

    Traversal Guidelines

    • Try to only write loops if there is no well-tested library function/algorithm, e.g., from the standard library for what you want to do!
    • Prefer range-based for loops over other loop types (no bounds errors possible)
    • Prefer iterators over indices (no signed/unsigned integer problems, better long-term robustness)
    • Avoid random access patterns; prefer linear traversals (more cache & prefetching friendly)

    With Range-Based for C++11

    vector<int> v {2, 4, 6, 8};
// print all
for (int x : v)  cout << x << ' ';
// set all
for (int& x : v)  cin >> x;
    

prints 2 4 6 8
 
read values from console
    struct point { int x; int y; };
vector<point> w {{1,2}, {-3,5}};
// print all
for (point const& p : w)  cout <<'('<< p.x <<','<< p.y <<')';
// set all
for (point& p : w)  cin >> p.x >> p.y;
    // read-only, if type cheap to copy/or copy needed
for (auto x : v) { cout << x; }

    // read-only, if type expensive to copy
for (auto const& x : v) { cout << x; }

    // modify values
for (auto& x : v) { cin >> x; }

    With Iterators

    An iterator refers to a position in a vector.
    vector<int> v {1,2,3,4,5,6,7}
auto i = begin(v);  
auto e = end(v);
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    •  
    

    •  
    •  
    •  
    •  
    •  
    •  
    

    • i
    •  
    •  
    •  
    •  
    •  
    •  
    • e
    *i  accesses the element at i's position
    cout << *i;
cout << *(i+2);
cout << *e;
    prints 1
prints 3
 UNDEFINED BEHAVIOR

    The end iterator is only intended to be used as position indicator, it must not be used to access an element.

    • ++i  goes 1 toward end
    • --i  goes 1 towards begin
    • i += 2  goes forward by 2
    • i -= 3  goes backwards by 3
    ++i;

cout << *i;

    i += 2;

cout << *i;

    --i;

cout << *i;

    i += 5;
if (i == end(v)) 
  cout << "at end";
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    •  
    

    •  
    •  
    •  
    •  
    •  
    •  
    •  
    
prints 2

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    •  
    

    •  
    •  
    •  
    •  
    •  
    •  
    •  
    
prints 4

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    •  
    

    •  
    •  
    •  
    •  
    •  
    •  
    •  
    
prints 3

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    •  
    

    •  
    •  
    •  
    •  
    •  
    •  
    •  
    
at end
    Iterator-Based Loop
    std::vector<int> v {1, 2, 3, 4, 5, 6};
for (auto i = begin(v); i != end(v); ++i) {   cout << *i; }
    Example: Swapping Adjacent Pairs
    void swap_adjacent_pairs (std::vector<int>& v) {
  if (v.size() < 2) return;
  for (auto i=begin(v), j=i+1, e=end(v);      j < e; i+=2, j+=2)   {
    swap(*i,*j);
  }
}
    vector<int> w {1,2,3,4,5,6};
swap_adjacent_pairs(v);
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    

    • 2
    • 1
    • 4
    • 3
    • 6
    • 5

    With Reverse Iterators

    A reverse iterator refers to a position in a vector:
    vector<int> v {1,2,3,4,5,6,7}
auto i = rbegin(v);  
auto e = rend(v);
    •  
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    

    •  
    •  
    •  
    •  
    •  
    •  
    

    • e
    •  
    •  
    •  
    •  
    •  
    •  
    • i
    *i  accesses the element at i's position
    cout << *i;
cout << *(i+2);
cout << *e;
    prints 7
prints 5
 UNDEFINED BEHAVIOR

    The rend iterator is only intended to be used as position indicator, it must not be used to access an element.

    • ++i  goes 1 towards begin
    • --i  goes 1 towards end
    • i += 2  goes backwards by 2
    • i -= 3  goes forward by 3
    ++i;

cout << *i;

    i += 2;

cout << *i;

    --i;

cout << *i;

    i += 5;
if (i == rend(v)) 
  cout << "at rend";
    •  
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    

    •  
    •  
    •  
    •  
    •  
    •  
    •  
    
prints 6

    •  
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    

    •  
    •  
    •  
    •  
    •  
    •  
    •  
    
prints 4

    •  
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    

    •  
    •  
    •  
    •  
    •  
    •  
    •  
    
prints 5

    •  
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    

    •  
    •  
    •  
    •  
    •  
    •  
    •  
    
at rend
    Reverse Iterator-Based Loop
    std::vector<int> v {1, 2, 3, 4, 5, 6};
for (auto i = rbegin(v); i != rend(v); ++i) {   cout << *i; }
    ri.base() returns the corresponding normal (non-reverse) iterator
    • reverse position = normal position - 1
    • normal position = reverse position + 1
    vector<int> v {1,2,3};
auto re = rbegin(v);
auto fw = re.base();
    re 
    
   
    • 1
    • 2
    • 3
    •  
    
fw

    With Indices Indexed

    double interpolated (
  vector<double> const& x,  vector<double> const& y, double t) 
{
  if (x.size() != y.size()) return 0.0;
  double s = 0.0;
  for (std::size_t i = 0; i < v.size(); ++i) {
    s = t * x[i] + (1-t) * y[i];
  }
  return s;
}
    • Try to only write loops if there is no well-tested library function/algorithm, e.g., from the standard library for what you want to do!
    • prefer range-based or iterator-based loops over index-based traversal
    • use an index type identical to vector::size_type which is an unsigned integer (mixing signed and unsigned integers is a common source of subtle & hard-to-find bugs)
    • indices must not underflow, i.e., become < 0
    • do not access vectors at positions >= v.size()

    Insert/Erase

    Iterators

    Insert and erase positions are specified with iterators. They can be obtained with member functions:

    • vec.begin() → @first_element
    • vec.end() → @one_behind_last_element

    or with free-standing functions: C++11

    • begin(vec) → @first_element
    • end(vec) → @one_behind_last_element 
    vector<int> v {1,2,3,4,5}
auto i = begin(v);  
auto j = begin(v)+2;  
auto e = end(v);
    • 1
    • 2
    • 3
    • 4
    • 5
    •  
    

    

    • i
    • j
    • e

    Iterator Ranges

    = pair p,q of iterators
    iterator range

    end-of-range iterator q points one behind the last element in the range

    iterator range examples
    Making Vectors From Ranges
    vector<int> u {0,1,2,3};
vector<int> v {begin(u),               begin(u)+2};
    u: 
    • 0
    • 1
    • 2
    • 3
    
   
    
v: 
    • 0
    • 1
    Assigning Ranges To A Vector
    vector<int> u {0, 1, 2, 3};
vector<int> w; …
w.assign(begin(u)+1,         end(u));
    u: 
    • 0
    • 1
    • 2
    • 3
    •  
    
   
    
w: 
    • 1
    • 2
    • 3

    Insert Elements

    Insert At The End (Fastest)

    • .push_back(element) 
    vector<int> v {1,2,3};
v.push_back(4);
    • 1
    • 2
    • 3
    

    • 1
    • 2
    • 3
    • 4

    Insert Anywhere (Potentially Slow)

    insert positions are specified with iterators

    • .insert(@insert_pos, element)
    • .insert(@insert_pos, {elem1,elem2,…}) 
    vector<int> v {1,2,3};


    v.insert(begin(v)+1, 5);


    v.insert(begin(v), {7,8}); 


    v.insert(end(v), 9);

    
  
    • 1
    • 2
    • 3
    

      
    
⇒ 
    • 1
    • 5
    • 2
    • 3
    

      
    
⇒ 
    • 7
    • 8
    • 1
    • 5
    • 2
    • 3
    •  
    

      
    
⇒ 
    • 7
    • 8
    • 1
    • 5
    • 2
    • 3
    • 9

    Insert From Iterator Range

    • .insert(@insert_pos, @first, @last) 
    vector<int> y {4,5,6,7,8};
vector<int> x {1,2};
x.insert(begin(x), 
         begin(y),          begin(y)+3);


       
    
x: 
    • 1
    • 2
    
y: 
    • 4
    • 5
    • 6
    • 7
    • 8
    
   
    

    x: 
    • 4
    • 5
    • 6
    • 1
    • 2

    Insert & Construct Elements In-Place C++11

    • .emplace_back(arg1, arg2, …)
    • .emplace(@insert_pos, arg1, arg2, …)

    makes a new element with forwarded constructor arguments

    struct p2d {
  p2d(int x_, int y_):
    x{x_}, y{y_} {}
  int x, y;
};
vector<p2d> v { p2d{2,3} };

    // insert copy
v.push_back( p2d{6,4} );

    // construct in place with
// constructor ↓ ↓ arguments
v.emplace_back(9,7);

    // iterator ↓ to first pos
v.emplace(begin(v), 5,8);
    custom 
← constructor
necessary for
emplace(_back)


      • 2
      • 3
    

    

      • 2
      • 3
      • 6
      • 4
    

    


      • 2
      • 3
      • 6
      • 4
      • 9
      • 7
    

    

      • 5
      • 8
      • 2
      • 3
      • 6
      • 4
      • 9
      • 7

    Erase Elements

    Erase At The End (Fast)

    vector<int> v {1,2,3,4,5,6};
v.pop_back();
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    

    • 1
    • 2
    • 3
    • 4
    • 5
    •

    Erase Everything (Fast)

    vector<int> v {1,2,3,4,5,6};
v.clear();
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    

    •  
    •  
    •  
    •  
    •  
    •

    Erase Anywhere (Potentially Slow)

    which elements to erase is specified with iterators and iterator ranges

    • .erase(@position)
    • .erase(@range_begin, @range_end) 
    vector<int> v {1,2,3,4,5,6};
v.erase( begin(v)+2 );

      
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    
  
    
⇒ 
    • 1
    • 2
    • 4
    • 5
    • 6
    •  
    vector<int> v {1,2,3,4,5,6};
v.erase( begin(v)+1,          begin(v)+4 );
 
      
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    
  
    
⇒ 
    • 1
    • 5
    • 6
    •
    Erasing does not affect the capacity, i.e., none of the vector's memory is freed.

    Attention After Insert/Erase! After Insert/Erase Attention!

    All iterators into a vector are invalidated if its capacity is changed or elements are moved by insert, push_back, emplace, emplace_back, erase, =, assign, resize, reserve. (Swapping two vector's contents does not invalidate iterators, except for the end iterator.)

    vector<int> v {0,1,2,3,5,6};
auto i = begin(v) + 3;
    Dangerous

    use of iterator after insert/erase:

    v.insert(i,8);
cout << *i; // 
    v.erase(i);
cout << *i; //
    Correct
    • use new valid iterator returned by insert/erase
    • the returned iterator refers to the original position
    i = v.insert(i,8);
cout << *i;
    i = v.erase(i);  
cout << *i;
    Overview: Iterator Invalidating Operations Iterator Invalidating Operations Invalidation
    Operations Invalidated Iterators
    const (read only) operations none
    swap, std::swap only end()
    reserve, shrink_to_fit if capacity changed: all
    else: none
    push_back, emplace_back if capacity changed: all
    else: only end()
    insert, emplace if capacity changed: all
    else: only at or after insertion point (incl. end())
    resize if capacity changed: all
    else: only end() and iterators to erased elements
    pop_back iterators to erased element and end()
    erase iterators to erased elements and all after them (incl. end())
    clear, operator=, assign all

    Shrink The Capacity / Free Memory Shrink The Capacity Shrink

    Erasing elements from a vector does never change the capacity and thus never frees any memory.
    .shrink_to_fit() (May work)
    • ISO standard does not demand that it actually shrinks
    • standard library implementation might decide not to shrink
    vector<int> v;

    // add a lot of elements …
// erase elements …

    v.shrink_to_fit(); C++11
    Guaranteed to work:
    • make temporary copy ⇒ copy does exactly fit the elements
    • exchange memory buffers by swapping/moving
    • temporary gets automatically destroyed
    vector<int> v;

    // add a lot of elements …
// erase elements …

    // shrink: make a new copy and
// replace v's content with it:
v = vector<int>(v);       C++11-20
// or:
v.swap( vector<int>(v) ); C++98-20

    How Does It Work? How It Works

    Typical Memory Layout Layout

    Example: vector object w on the stack
    vector<int> w {0,1,2,3,4};
w.reserve(8); 
auto s = w.size();
auto c = w.capacity();
    w: 
    • 0
    • 1
    • 2
    • 3
    • 4
    
w: 
    • 0
    • 1
    • 2
    • 3
    • 4
    •  
    
s: 5
c: 8
    std::vector memory layout example
    Vector elements are guaranteed to reside in one contiguous block of memory.

    Growth Scheme

    Memory blocks, once allocated, can't be resized! (no guarantee that there is space left directly behind previously allocated memory block)

    Dynamic array implementations separate the array object from the actual memory block for storing values.

    Growth is then done the following way:

    • dynamically allocate new, (≈1.1-2×) larger memory block
    • copy/move old values to new block
    • destroy old, smaller block
    std::vector growth scheme example

    Dynamic Array…

    Erasing At Random Positions

    v: 
    • 0
    • 1
    • 2
    • 3
    • 4
    • 5
    •  
    
   
    
v.erase( begin(v)+2 );

    • destroy element

      • 0
      • 1
      •  
      • 3
      • 4
      • 5
      •

    • move remaining elements (potentially expensive)

      • 0
      • 1
      • 3
      • 4
      • 5
      •
    • size is one less, capacity has not changed!

    Inserting At Random Positions

    v: 
    • 0
    • 1
    • 2
    • 3
    • 4
    • 5
    •  
    
   
    
v.insert( begin(v)+2, 9 );

    • enough capacity for one additional element?

      yes ⇒ no memory allocation necessary

      no ⇒ reserve more capacity ( see here)

    • move old elements (potentially expensive)

      • 0
      • 1
      •  
      • 2
      • 3
      • 4
      • 5
      •

    • (copy-)construct new element at desired position

      • 0
      • 1
      • 9
      • 2
      • 3
      • 4
      • 5
      •

    Guidelines & Best Practices

    Use Cases for vector

    • random access: overhead-free, constant-time
    • linear traversal/searches: fast due to cache & prefetching friendly memory layout
    • one-sided growth: insertion at the end in amortized constant time
    • potentially long allocation times for very large amount of fundamental (int, double, …) values (e.g., as host-target for GPU results);
      this can be eliminated with zero-overhead-zero-init wrappers
    • slow if element type has high copy/assignment cost;
      can be mitigated by capacity reserving and in-place construction with emplace_back; see here
    • potentially slow if insert/erase operations at random positions dominate

    Iteration/Traversal

    • Try to only write loops if there is no well-tested library function/algorithm, e.g., from the standard library for what you want to do!
    • Prefer range-based for loops over other loop types (no bounds errors possible)
    • Prefer iterators over indices (no signed/unsigned integer problems, better long-term robustness)
    • Avoid random access patterns; prefer linear traversals (more cache & prefetching friendly)

    Interfacing With C Functions

    c_header.h
    int foo (int*, size_t);
    c++_file.cpp
    #include "c_header.h"
…
vector<int> v;
// … fill vector etc.
// raw pointer to memory, size
int x = foo(v.data(), v.size());

    Attention: Iterator Invalidation Iterator Validity Iterators

    All iterators into a vector are invalidated if its capacity is changed or elements are moved by insert, push_back, emplace, emplace_back, erase, =, assign, resize, reserve. (Swapping two vector's contents does not invalidate iterators, except for the end iterator.)

    vector<int> v {0,1,2,3,5,6};
auto i = begin(v) + 3;
    Dangerous

    use of iterator after insert/erase:

    v.insert(i,8);
cout << *i; // 
    v.erase(i);
cout << *i; //
    Correct
    • use new valid iterator returned by insert/erase
    • the returned iterator refers to the original position
    i = v.insert(i,8);
cout << *i;
    i = v.erase(i);  
cout << *i;
    Overview: Iterator Invalidating Operations Iterator Invalidating Operations Invalidation
    Operations Invalidated Iterators
    const (read only) operations none
    swap, std::swap only end()
    reserve, shrink_to_fit if capacity changed: all
    else: none
    push_back, emplace_back if capacity changed: all
    else: only end()
    insert, emplace if capacity changed: all
    else: only at or after insertion point (incl. end())
    resize if capacity changed: all
    else: only end() and iterators to erased elements
    pop_back iterators to erased element and end()
    erase iterators to erased elements and all after them (incl. end())
    clear, operator=, assign all

    Attention: Reference/Pointer Invalidation Reference/Pointer Validity Refs/Pointers

    All references or pointers into a vector are invalidated if its capacity is changed or elements are moved by insert, push_back, emplace, emplace_back, erase, =, assign, resize, reserve. (Swapping two vector's contents does not invalidate pointers or, references.)

    vector<int> v {0,1,2,3};
int& i = v[2];
int* p = &v[1];
v.resize(20);  
i = 5;  //  UNDEFINED BEHAVIOR: original memory might be gone!
*p = 3; //  UNDEFINED BEHAVIOR: original memory might be gone!
v[2] = 5;  // OK
    Using indices is the only way to safely refer to the same vector items before and after potentially memory-block-changing operations.

    Predictable Size ⇒ reserve reserve!

    Possibly several memory allocations & copying ⇒ slow:
    vector<int> v;
int n = 0;
cin >> n;
for (auto x : read_numbers(n))
  v.push_back(x);
    Memory is allocated only once:
    vector<int> v;
int n = 0;
cin >> n;
v.reserve(n);
for (auto x : read_numbers(n))
  v.push_back(x);

    Elements With Large Memory Footprint Elements w/ Large Footprint Large Elements

    Large only refers to the element itself, so only the bits that will actually reside in the vector, not to other memory the elements might point to.

    • expensive to copy
    • expensive to move
    • might also be expensive to initialize/construct
    • reserve instead of resize (prevents expensive premature constructions)
    • if possible, reserve only once in the beginning (prevents expensive copying due to reallocation)
    • insert at the end; avoid insertion at random positions (prevents that other elements have to change position)
    • insert new elements by constructing them in-place with emplace_back (prevents copying/moving)

    Uninitialized Numeric Arrays Uninitialized

    Situation:

    need very large uninitialized contiguous memory block of int/double, e.g., as target for GPU results

    Problem:

    std::vector value-initializes its underlying memory block, which means that, e.g., ints are initialized with 0 ⇒ slow (up to minutes for multi-gigabyte buffers)

    Solutions

    Cheat Sheet

    std::vector Interface Overview Sheet

    std::vector interface visual overview

    (click for fullscreen view)

    Related …

    Last updated: 2023-04-25

    Comments…