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 Quick

    #include <vector>
    
    std::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 Make

    // 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
    Careful!

    Access Elements Access

    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 Assign

    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/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! 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
    • content 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

    Traversal Guidelines 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 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;
    // 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 Iterators

    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
    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;
    
    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
    std::vector<int> v {1, 2, 3, 4, 5, 6};
    for(auto i = begin(v); i != end(v); ++i) {   cout << *i; }
    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 Reverse Iterators

    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
    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;
    
    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
    std::vector<int> v {1, 2, 3, 4, 5, 6};
    for(auto i = rbegin(v); i != rend(v); ++i) {   cout << *i; }
    • 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: 

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

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

    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 Insert

    • .push_back(element)
    • .push_back({elem1,elem2,…})
    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();
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 1
    • 2
    • 3
    • 4
    • 5
    vector<int> v {1,2,3,4,5,6};
    v.clear();
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    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;

    use of iterator after insert/erase:

    v.insert(i,8);
    cout << *i; // 
    v.erase(i);
    cout << *i; // 
    • 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;
    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); // or: v.swap( vector<int>(v) );

    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 Growth

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

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

    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;

    use of iterator after insert/erase:

    v.insert(i,8);
    cout << *i; // 
    v.erase(i);
    cout << *i; // 
    • 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;
    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 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)

    Large, Uninitialized Buffers ⇒ No-Init Wrapper Uninitialized Buffers Uninitialized

    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!