Beginner's Guide
    First Steps
    Input & Output
    Custom Types – Part 1
    Diagnostics
    Standard Library – Part 1
    Function Objects
    Standard Library – Part 2
    Code Organization
    Custom Types – Part 2
    Generic Programming
    Memory Management
    Software Design Basics

    Standard Sequence Containers Sequence Containers Sequ.Containers

    array<T,size>
    standard library sequence container 'array

    fixed-size contiguous array

    vector<T>
    standard library sequence container 'vector

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

    deque<T>
    standard library sequence container 'deque

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

    list<T>
    standard library sequence container 'list

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

    forward_list<T>
    standard library sequence container 'forward_list

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

    Common Features Common

    Regularity: Copy, Assign, Compare

    • deeply copyable: copying creates a new container object and copies all contained values
    • deeply assignable: all contained objects are copied from source to assignment target
    • deeply comparable: comparing two containers compares the contained objects
    • deep 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 C++17

    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

    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: C++11

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

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

    • container.cbegin() const@first_element
    • container.cend() const@one_behind_last_element

    or with free-standing functions: C++11

    • std::cbegin(container) const@first_element
    • std::cend(container) const@one_behind_last_element

    either with member function

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

    or with free-standing function: C++11

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

    • 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, erase, …)
    • 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>

    • 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, see here )

    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
    std::vector memory layout example

    Iterator Ranges

    iterator range

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

    iterator range examples
    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 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

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

    Shrink The Capacity / Free Memory 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); C++11-20 // or: v.swap( vector<int>(v) ); C++98-20

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

    deque<T>

    • 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, see here )
    #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>

    • 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 7 3 2
    2 3 8 4 7 4
    2 3 4 4 7 8
    2 3 4 7 8

    forward_list<T>

    • 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!
    flowchart for selecting an appropriate standard library container