Beginner's Guide
    First Steps
    Input & Output
    Basic Custom Types
    Diagnostics
    Standard Library
    Code Organization
    Powerful Custom Types
    Generic Programming
    Memory Management
    Software Design Basics

    Standard Sequence ContainersSequence ContainersSequ.Containers

    array<T,size>

    fixed-size contiguous array

    vector<T>

    dynamic contiguous array; armortized O(1) growth strategy;
    C++'s default container

    deque<T>

    double-ended queue; fast insert/erase at both ends

    list<T>

    doubly-linked list; O(1) insert, erase & splicing;
    in practice often slower than vector

    forward_list<T>

    singly-linked list; O(1) insert, erase & splicing; needs less memory than list; in practice often slower than vector

    Common Features Common

    Regularity

    All sequence containers in the standard library are so called regular types, i.e., they behave the same as fundamental types (int, double, …) in the following ways:

    • deep copying: copying creates a new container object and copies all contained values
    • deep assignment: all contained objects are copied from source to assignment target
    • deep comparison: comparing two containers compares the contained objects
    • content ownership: destroying the container destroys all contained objects
    std::vector<int> a {4,7,1,9};
    
    std::vector<int> b {1,2,3}; bool equal1 = (a == b); // false a = b; // copy assignment ⇒ b:
    • 4
    • 7
    • 1
    • 9
    bool equal2 = (a == b); // true a[0] = 3; // a:
    • 3
    • 7
    • 1
    • 9
    b:
    • 4
    • 7
    • 1
    • 9
    bool equal3 = (a == b); // false
    // different ways of making exact copies, // i.e., copy-constructing new containers: std::vector<int> a2 {a}; std::vector<int> a3 (a); std::vector<int> a4 = a; auto a5 {a}; auto a6 (a); auto a7 = a;

    Type Argument Deduction Type Deduction

    As of C++17 the element type can be deduced from constructor calls.

    std::vector v {1, 2, 3, 4}; 
    std::vector v {1.f, 2.3f, 4.5f};
    std::vector v {1., 2.3, 4.6};
    
    struct p2 { int x; int y; }; std::vector v {p2{1,2}};
    std::vector<int>
    std::vector<float>
    std::vector<double>
    
    std::vector<p2>

    Common Interface Parts Interface

    can be obtained from all standard sequence containers either with member functions:

    • container.begin() @first_element
    • container.end() @one_behind_last_element

    or with free-standing functions: 

    • std::begin(container) @first_element
    • std::end(container) @one_behind_last_element

    If you are not familiar with what iterators are, please refer to this article.

    either with member function

    • container.empty() true, if container has no elements

    or with free-standing function: 

    • std::empty(container) true, if container has no elements
    • container::value_type
    • container::size_type
    • container::iterator
    • container::const_iterator
    using con_t = std::vector<double>;
    con_t::size_type i = 0;         // std::size_t
    auto x = con_t::value_type{0};  // double

    array<T,size> array

    • overhead-free random access
    • fast traversal; good for linear searches
    • size has to be a constant expression (= known at compile time)
    • does not support size-changing operations (resize, insert, ersase, …)
    • potentially slow if element type has high copy/assignment cost (reordering elements requires copying/moving them)
    #include <array>
    std::array<int,6> a {4,8,15,16,23,42};
    cout << a.size();   // 6
    cout << a.[0];      // 4
    cout << a.[3];      // 16
    cout << a.front();  // 4
    cout << a.back();   // 42
    
    array<int,3> b {7,8,9}; a = b; // COMPILER ERROR: types don't match!

    STACK

    42
    23
    16
    15
    8
    4

    vector<T> vector

    • overhead-free random access
    • fast traversal; good for linear searches
    • insertion at the end in amortized constant time
    • potentially slow if insert/erase operations at front and/or random positions dominate
    • potentially slow if element type has high copy/assignment cost (reordering elements requires copying/moving them)
    • potentially long allocation times for very large amount of fundamental (int, double, …) values (can be eliminated with zero-overhead-zero-init wrappers)

    Quick Recap

    #include <vector>
    
    std::vector<int> v {2,4,5}; v.push_back(6); v.pop_back(); v[1] = 3;
    cout << v[2]; for(int x : v) cout << x << ' '
    v.reserve(8); v.resize(5, 0); cout << v.capacity(); cout << v.size();
    
    
    • 2
    • 4
    • 5
    • 2
    • 4
    • 5
    • 6
    • 2
    • 4
    • 5
    • 2
    • 3
    • 5

    prints 5 prints 2 3 5
    • 2
    • 3
    • 5
    • 2
    • 3
    • 5
    • 0
    • 0
    • 0
    prints 8 prints 5

    Iterator 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

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

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

    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

    deque<T> deque

    Double Ended Queue 
    • constant-time random access (extremely small overhead)
    • fast traversal; good for linear searches
    • good insertion and deletion performance at both ends
    • potentially slow if insert/erase operations at random positions dominate
    • potentially slow if element type has high copy/assignment cost (reordering elements requires copying/moving them)
    • potentially long allocation times for very large amount of fundamental (int, double, …) values (can be eliminated with zero-overhead-zero-init wrappers)
    #include <deque>
    
    std::deque<int> d {0, 0, 0};
    d.push_back(1);
    d.push_front(2);
    vector<int> v {3, 4, 5, 6}; d.insert(begin(d), begin(v), end(v));
    d.pop_front();
    d.erase(begin(d)+2, begin(d)+5);
    
    
    • 0
    • 0
    • 0

    • 0
    • 0
    • 0
    • 1

    • 2
    • 0
    • 0
    • 0
    • 1

    v:
    • 3
    • 4
    • 5
    • 6
    ⇒ d:
    • 3
    • 4
    • 5
    • 6
    • 2
    • 0
    • 0
    • 0
    • 1

    • 4
    • 5
    • 6
    • 2
    • 0
    • 0
    • 0
    • 1

    • 4
    • 5
    • 6
    • 2
    • 0
    • 0
    • 0
    • 1
    • 4
    • 5
    • 0
    • 0
    • 1

    list<T> list

    Doubly-linked List 
    • restructuring operations don't require elements to be moved/copied (good for storing large objects with high copy/assignment cost)
    • constant-time splicing (of complete lists)
    • random access only in linear time
    • slow traversal due to bad memory locality
    #include <list>
    std::list<int> l {3};
    
    l.push_back(2);
    l.push_front(4);
    l.splice(begin(l)+1, list<int>{8, 4, 7});
    l.reverse();
    l.sort();
    l.unique();
    
    3 
    
    3 2
    4 3 2
    4 8 4 8 3 2
    2 3 8 4 8 4
    2 3 4 4 8 8
    2 3 4 8

    forward_list <T> forward_list

    Singly-linked List 
    • uses less memory than list
    • restructuring operations don't require elements to be moved/copied (good for storing large objects with high copy/assignment cost)
    • constant-time splicing (of complete lists)
    • random access only in linear time
    • slow traversal due to bad memory locality
    • only forward traversal possible
    • somewhat cumbersome interface due to forward-only links
      • no: size(), back(), push_back(), pop_back(), insert()
      • instead: insert_after(), splice_after(), before_begin()
    #include <forward_list>
    std::forward_list<int> l {23,42,4}; 
    
    l.insert_after(begin(l), 5);
    l.insert_after( before_begin(l), 88);
    l.erase_after(begin(l));
    
    23  42  4
    
    23 5 42 4
    88 23 5 42 4
    88 5 42 4

    Guidelines

    Which Sequence Container Should I Use? Which Sequence Container? Which?

    Default choice: std::vector!