std::vector
std::vector

  • array can hold different values/objects of same type
  • dynamic size can be changed at runtime

Quick Start

#include <vector>

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

  • 2
  • 4
  • 5
  • 2
  • 4
  • 5
  • 6
  • 2
  • 4
  • 5
  • 2
  • 3
  • 5
  • 2
  • 4
  • 5
  • 0
  • 0

prints 5 prints 2 3 5 0 0

Make New Vectors

// from list of values: 
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

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

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.reserve(4);
v.push_back(1);
v.push_back({2,3});

auto s = v.size(); auto c = v.capacity();
v.resize(6,0);
        capacity size
1 0
4 0
  • 1
4 1
  • 1
  • 2
  • 3
4 3
s: 3 c: 4
  • 1
  • 2
  • 3
  • 0
  • 0
  • 0
6 6

if number of elements (approximately) known 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.

vector is a so-called regular type (it behaves like int)
  • each copy of a vector is a new, independend object!
  • vectors can be deeply compared for equality

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!

  • Only write loops if there is no standard algorithm for your use case!
  • Prefer range-based for loops (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)

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;

With Iterators

An iterator refers to a position in a vector.
vector<int> v {1,2,3,4,5,6,7,8,9}
auto i = begin(v);  
auto e = end(v);
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • i
  • e
*i  accesses the element at i's position
cout << *i;
cout << *(i+2);
cout << *e;
prints 1
prints 3
 UNDEFINED BEHAVIOR
 
++i;
cout << *i;

i += 2; cout << *i;
--i; cout << *i;
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
prints 2
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
prints 4
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
prints 3
Example: Swapping adjacent pairs
Example
void swap_adjacent_pairs(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

An iterator refers to a position in a vector.
vector<int> v {1,2,3,4,5,6,7,8,9}
auto i = rbegin(v);  
auto e = rend(v);
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • e
  • i
*i  accesses the element at i's position
cout << *i;
cout << *(i+2);
cout << *e;
prints 9
prints 7
 UNDEFINED BEHAVIOR
 
++i;
cout << *i;

i += 2; cout << *i;
--i; cout << *i;
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
prints 8
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
prints 6
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
prints 7

ri.base() returns the corresponding normal (non-reverse) iterator

reverse position = normal position - 1

vector<int> v {1,2,3};
auto re = rbegin(v);
auto fw = re.base();
re 
  • 1
  • 2
  • 3
fw

With Indices

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;
}
  • Only write loops if there is no standard algorithm for your use case!
  • prefer range-based for loops or iterator-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: 

  • 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

vector<int> u {0,1,2,3};
vector<int> v {begin(u),               begin(u)+2};
u: 
  • 0
  • 1
  • 2
  • 3
v:
  • 0
  • 1
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

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

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(@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

  • .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

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

v.pop_back();
v.clear();
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

  • 1
  • 2
  • 3
  • 4
  • 5

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 vector's capacity, i.e., no memory is freed.

Attention After Insert/Erase!
After Insert/Erase

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
Overview: Invalidating Operations
Operations Invalidated Iterators
read only none
swap, std::swap only end()
clear, operator=, assign all
reserve, shrink_to_fit if capacity changed: all; else: none
erase iterators to erased elements and all after them (incl. end())
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()

Erasing elements from a vector does never change the capacity and thus never frees any memory.
Shrinking:
  • 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); v.swap( vector<int>(v) );

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
Vector elements are guaranteed to reside in one contiguous block of memory.
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!
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
Guidelines

  • 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
  • Only write loops if there is no standard algorithm for your use case!
  • Prefer range-based for loops (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)
Pay Attention To Iterator Invalidation
Iterator Validity

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
Overview: Invalidating Operations
Operations Invalidated Iterators
read only none
swap, std::swap only end()
clear, operator=, assign all
reserve, shrink_to_fit if capacity changed: all; else: none
erase iterators to erased elements and all after them (incl. end())
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()
Pay Attention To Reference/Pointer Invalidation
Reference/Pointer Validity

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; //  original memory might be gone!
*p = 3; //  - " -
v[2] = 5;  // 
Using indices is the only way to safely refer to the same vector items before and after potentially memory-block-changing operations.
Elements With Large Memory Footprint
Elements w/ Large Footprint

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)
Large, Uninitialized Buffers ⇒ No-Init Wrapper
Uninitialized Buffers

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

Problem: std::vector value-initializes underlying memory block
⇒ slow (up to minutes for multi-gigabyte buffers)

Idea: generic zero-overhead wrapper that prevents value-initialization
#include <type_traits>
template<class T>
class no_init {
  static_assert(
    std::is_fundamental<T;::value, 
    "T should be a fundamental type");
public:
  // constructor without initialization
  constexpr  no_init() noexcept {}
  // implicit conversion T → no_init<T> 
  constexpr  no_init(T value) noexcept: v_{value} {}
  // implicit conversion no_init<T> → T
  constexpr  operator T() const noexcept { return v_; }
private:
  T v_;
};

std::vector<no_init<int>> w; w.resize(1'000'000'000); // fast - no init!