Containers

in

Richard Eigenmann, 1 Mar 2016

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

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

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 (<, <=, >=, >)

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

Sample5

Basic standard iterator operations

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

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.

Presentation Tool:

reveal.js

highlight.js