Containers

in

Richard Eigenmann, 1 Mar 2016

Revised 28 Mar 2016 (Thanks Andreas Gieriet)

Standard Template Library Containers

Sequence Containers

vector, list, forward_list, deque, array

Associative Containers

set, multiset, map, multimap

Container Adaptors

queue, priority_queue, stack

Single Container

pair, tuple

See http://en.cppreference.com/w/cpp/container

All containers

  • have a collection of elements
  • provide copy operations that copy elements. Copying can be done with assignment or a copy constructor.
  • name their element type "value_type" (amongst others)
  • have iterator types called "iterator" and "const_iterator". Iterators provide *, ++ (both prefix and postfix), ==, and != with the appropriate semantics. The iterators for list also provide –– for moving backward in the sequence; that’s called a bidirectional iterator. The iterators for vector also provide --, [], +, and - and are called random-access iterators.
  • provides insert() and erase(), front() and back(), push_back() and pop_back(), size(), etc.; vector and map also provide subscripting (e.g., operator []).
  • provide comparison operators (==, !=, <, <=, >, and >=) that compare the elements. Containers use lexicographical ordering for <, <=, >, and >=; that is, they compare the elements in order starting with the first. (Actually the elements must provide the operations.)

See Stroustroup, Programming Principle and Practice Using C++ 20.10

Containers have Iterators:

An STL sequence is what is usually called “half-open”; that is, the element identified by begin is part of the sequence, but the end iterator points one beyond the end of the sequence.

What is an Iterator?

  • An iterator points to (refers to) an element of a sequence (or one beyond the last element).
  • You can compare two iterators using == and !=
  • You can refer to the value of the element pointed to by an iterator using the unary * operator (“dereference” or “contents of”)
  • You can get an iterator to the next element by using ++.

See Stroustroup, Programming Principle and Practice Using C++ 20.3

Think of an Iterator as a Cursor on Containers, mimicking pointer-access on elements

  • pointer to first element (begin())
  • pointer behind last element (end())
  • go to next element(++it, it++ is not advised due to performance penalty)
  • get current element (*it)
  • pointer equality (== and !=)
  • go to previous element if supported (--it, it-- is not advised due to performance penalty)
  • random access if supported (it[pos], +, -)
  • pointer relation if supported (<, <=, >=, >)

Thanks Andreas Gieriet

Traditional approach with position-based for loop

#include <vector>
#include <iostream>

int main() {
    std::vector <int> myIntVector { 1, 4, 8 };

    for( int i=0; i < myIntVector.size(); ++i ) {
        std::cout << myIntVector[i] << " ";
    }

    return 0;
}
Output: 1 4 8

Sample1

From http://www.cprogramming.com/tutorial/stl/iterators.html

Iterator-based for loop approach

#include <vector>
#include <iostream>

int main() {
    std::vector<int> myIntVector { 1, 4, 8 };

    std::vector<int>::iterator it;
    for ( it = myIntVector.begin(); it != myIntVector.end(); ++it ) {
        std::cout << *it << " ";
    }

    return 0;
}
Output: 1 4 8

Sample2

From http://www.cprogramming.com/tutorial/stl/iterators.html

Introducing auto in C++11

#include <vector>
#include <iostream>

int main() {
    std::vector <int> myIntVector { 1, 4, 8 };

    //std::vector<int>::iterator it
    for (auto it = myIntVector.begin(); it != myIntVector.end(); ++it)
    {
        std::cout << *it << " ";
    }

    return 0;
}
Output: 1 4 8

Sample4

Reverse Iterator

#include <vector>
#include <iostream>

int main() {
    std::vector <int> myIntVector { 1, 4, 8 };

    //std::vector <int>::reverse_iterator it;
    for (auto it=myIntVector.rbegin(); it!=myIntVector.rend(); ++it)
    {
        std::cout << *it << " ";
    }

    return 0;
}
Output: 8 4 1

Note the rbegin and rend!

Sample3

From http://www.cprogramming.com/tutorial/stl/iterators.html

Iteration with auto and a range-for-loop in C++11

#include <vector>
#include <iostream>

int main() {
    std::vector <int> myIntVector { 1, 4, 8 };

    for ( const auto& element : myIntVector ) {
        std::cout << element << " ";
    }

    return 0;
}
Output: 1 4 8

The range-for-loop is defined in terms of begin() and end() functions returning iterators to the first and one beyond the end of our vector elements. The range-for-loop is simply “syntactic sugar” for a loop over a sequence using iterators.

Depeding on the use case: auto element or auto& element or const auto& element.

Sample5

Basic standard iterator operations

it1 == it2 true if and only if it1 and it2 point to the same element or both point to one beyond the last element
it1 != it2 the revers of the above
*it1 refers to the element(object) pointed to by iterator it1
var = *it1 reads the element pointed to by it1 into the variable var
*it1 = var writes the variable var into the element pointed to by it1
++it1 advance the iterator to the next element in the sequence or one beyond the last element

Finding the Highest value

#include <vector> <cr> #include <list> <cr> #include <iostream>
using namespace std;
template<typename Iterator>
Iterator high(Iterator first, Iterator last) {
    Iterator high = first;
    for (Iterator it = first; it != last; ++it)
        if (*high < *it) high = it;
    return high;
}

int main() {
    vector <int> myVec { 1, 4, 8 };
    list <int> myList { 10, 4, 8 };
    cout << "myVec high: "<<*high(myVec.begin(),myVec.end()) << endl;
    cout << "myList high: "<<*high(myList.begin(),myList.end())<<endl;
    return 0;
}

For a better way check out Algorithms in the next chapter!

FindHigh

vector vs. linked list:

Bjarne explains why vectors usually perform better: Video (7:45)

(Lists perform better for insertion and removal of elements but the linear search to get to the element dwarfs the vectors' move operation which performs well with modern caches.)

vector insert

Iterator q is has become invalid

list insert

No problems with Iterator q

Operations on C++ Sequence Containers

See: Wikipedia

Word Processor

The lines are kept in a list and the characters of the line in a vector. This allows easy insertion of new lines without having to copy huge blocks of text. Also, iterators pointing at specific lines will be unaffected by the insert or delete operations on other lines.

Suggested Exercise

Run a timing experiment to compare the performance of using a vector versus a list.

(Timing code from 26.6.1 on slide below).

Generate N random int values in the range [0:N). As each int is generated, insert it into a vector at the place where it belongs numerically (thereby forcing the vector to copy all later elements out). Repeat the experiment using a list.

Plot the results and find the point where one container is more performant than the other. Explain the result and then watch Bjarne's video (7:45)

Timing code

#include <chrono>
#include <iostream>
#include <vector>
using namespace chrono;
void do_something() {
    vector<int> pointless {0,1,2,3,4,5};
}
int main() {
    int n = 10000000;
    auto startTime = system_clock::now();
    for (int i = 0; i < n; i++) // timing loop
        do_something();
    auto endTime = system_clock::now();
    auto ms = duration_cast<( endTime - startTime).count();
    std::cout << "do_something() " << n << " times took "
        << ms << "ms" << std_endl;
}

Presentation Tool:

reveal.js

highlight.js