std::vectorstd::vectorstd::vector

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

Basic Usage Basics

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};
// many{multiple 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!

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 Assignment

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 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! Copying

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!

Loop Traversal Loops

Traversal Guidelines Guidelines

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

With Range-Based for With Range-for

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

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 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: 

  • 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

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

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

Insert & Construct Elements In-Place Insert Elements In-Place Insert In-Place

  • .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 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 Overview: Invalidating Operations
Operations Invalidated Iterators
read only 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 Shrinking

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) );

Interfacing With C Functions C Functions

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

Growth Scheme

Memory blocks, once allocated, can't be resized! (operating system does not guarantee there is space left after memory block)

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

Growth is then done the following way:

  • allocate new, (≈1.1-2×) larger memory block
  • copy/move old values to new block
  • destroy old, smaller block

Erasing At Random Positions Erasing

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 Inserting

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

Use Cases for vector Use Cases

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

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

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 Overview: Invalidating Operations
Operations Invalidated Iterators
read only 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!

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, 
    "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!