License : Creative Commons Attribution 4.0 International (CC BY-NC-SA 4.0)
Copyright : Frédéric Pennerath, CentraleSupelec
Last modified : April 19, 2024 10:22
Link to the source : containers.md

Containers

The container library : a global view

The concept of Container

* Iterators are used to enumerate elements of a container, using idiomatic iterator loops:

template<typename Container> 
void fill(Container& C, typename Container::const_reference V) {
    // Always use this idiomatic syntax for generic loops
    // Do not use operators <, > or post-increment if not necessary
    for(typename C::iterator it = C.begin(); it != C.end(); ++it) 
        *it = V;
}

template<typename Container> 
typename Container::value_type sum(const Container& C) {
    typename Container::value_type S{}; // 0 for numeric types
    for(typename C::const_iterator it = C.begin(); it != C.end(); ++it)
        S += *it;
    return S;
}

• C++11 brings syntaxic sugar to write standard loops:

template<typename Container> 
void fill(Container& C, typename Container::const_reference V) {
    for(auto& elt : C)  elt = V;
}

template<typename Container> 
auto sum(const Container& C) {
    decltype(*C.begin() + *C.begin()) S{}; // This is a trick to avoid using type alias value_type
    for(const auto& elt : C) S += elt;
    return S;
}

• They are different types of iterators, more or less powerful
  • Input iterators can enumerate values read-only.
  • Output iterators can enumerate values write-only.
  • Forward iterators are input/output iterators that point to a memory position.
  • Bidirectional iterators are forward iterators that can move backward.
  • Random iterators are bidirectional iterators that can skip a number of elements in constant time.

Sequential containers

The concept SequenceContainer

Contiguous sequential containers

Remarks:

• Iterators of contiguous container are native C pointers T*
• 👍 as efficient as C arrays
• 👍 Spans and subspans can be built on top of contiguous containers (see further)

Static arrays

• Static arrays (std::array<T,n>) have a fixed size n known at compile time.
• 👍 Fit on stack as no dynamic allocation is needed
• 👍 Like static C-array, but with container facilities (size(), begin(), end(),…)

Vectors (dynamic arrays)

• Dynamic arrays (std::vector) manage arrays dynamically allocated on the heap.
• 👍 push_back() is constant time => default container for LIFO adapter std::stack and priority queue std::priority_queue
• 👎 push_front() in linear time => use std::deque when constant time front insertion needed
• 👍 Iterators are native C pointer => as fast as C arrays
• 👎 Operator operator[](int) requires one more indirection than array.
• 👎 Dynamic resizing can make iterators invalid!
• Dynamic arrays can redimension when they are full => 👍 Constant amortized complexity / 👎 Linear worst case complexity

Strings

• Strings std::basic_string<C> are dynamic arrays of characters of type C.
• Compared to C-arrays of characters, they can be redimensionned (without risk of buffer overflow) and know their size.
• Compared to std::vector<char>, strings adds a hidden null termination character \0 and provide additional methods (substr(), contains(), etc).
• A string can be casted to a const char* in constant time (method c_str())
• std::basic_string<C> supports various type of characters (char, wchar, char8_t, char16_t, char32_t, …)
• std::string = std::basic_string<char> is a string of ASCII characters.

Spans (C++20) and string views (C++17)

• Not container but a view on a contiguous sequential container.
• std::span interface is similar to std::array
• Allows to use ranges on dynamically allocated arrays or subsets of vectors/arrays.

• Equivalent of a span for an array of characters (char, w_char, etc) to behave like a string.
• Not possible to cast a string_view into a const char* (no c_str() method) as it is impossible to add a null character without modifying the underlying array.
• Allows to process a native char* as a constant string, i.e. const std::string.

Non-contiguous sequential containers

Deque

• A map of fixed size chuncks (e.g. chunks of 8 elements in libstdc++)
• Example of a non contiguous but still random access container (i.e constant complexity to access an element)
• Only the first and last chunks are not full.
• The map is a dynamic array (sometimes resizing)
• Compared to vectors,
  • 👍 push_front() is constant time => natural candidate for FIFO (see std::queue)
  • 👍 redimensioning is usually in constant time (less variations of time processing for real-time applications)
  • 👎 operator[]() requires a double indirection (vector has only one)
  • 👎 iterators are not as fast as native C pointers (vectors, arrays).

Double linked list

• A list of dynamically allocated nodes
• Every node points to the previous and next nodes.
• Compared to arrays, vectors and deques,
  • 👎 linear complexity \(\Theta(i)\) to access element of index \(i\)
  • 👎 Iterators are not fast (no cache, one memory indirection every increment)
  • 👎 Iterators are not random (moving from position \(i\) to position \(j\) has linear complexity \(\Theta(|i-j|)\))
  • 👍 Iterators are not invalidated when inserting new elements
  • 👍 Inserting or deleting an element given its position (iterator) is constant time
  • 👍 Splicing (merging two lists) is constant time

Single linked list

• Same as double linked list byt every node points only to the next node.
• Compared to double linked lists,
  • 👎 no bidirectional iterators (no operator--())
  • 👍 less memory overhead

Complexities summary

Associative containers

Definition

Remarks:

• A multimap is a map such that accepts multiple entries mapped to the same key.
• A set (and multiset) is an associate container containing only keys (i.e V = void)

Ordered maps and sets

• std::map<K,V> / std::multimap<K,V> and std::set<K> / std::multiset<K> are ordered associative containers based on balanced search trees (in particular red-black trees).
• The callable implementing the ordering relation can be provided as a template parameter:

template<
    class Key,
    class T,
    class Compare = std::less<Key>, // Comparator
    class Allocator = std::allocator<std::pair<const Key, T> >
> class map;

• 👍 Access to elements (operator[], at(), find(), etc) is guaranteed to be in \(\log(n)\) in the worst case.
• 👍 Methods iterator lower_bound(const K& Kmin) and iterator upper_bound(const K& Kmax) allow to find the range of elements whose keys are comprised betwee Kmin and Kmax.

• Balanced search trees are binary trees such that:
  • Every node \(n\) of key \(k\) is such that its left child and its descendants have keys \(k' \leq k\) and right child and its descendants have keys \(k' > k\).
  • Every branch has a length in \(O(\log(n))\) (\(n\) being the number of pairs/nodes stored in the tree).
• Red black trees are a particular type of balanced search trees such that:
  • Every node is coloured, either red or black.
  • A red node cannot have a red child.
  • Every branch has the same number of black nodes.
  • As a consequence, length of a branch cannot be shorter than the half of the longest branch => the tree is balanced.

    

Unordered maps and sets

Notes:

• std::unordered_map<K,V> / std::unordered_multimap<K,V> and std::unordered_set<K> / std::unordered_multiset<K> are ubordered associative containers based on dynamic hash tables.
• The callable implementing the hashing function can be provided as a template parameter

template<
    class Key,
    class T,
    class Hash = std::hash<Key>,
    class KeyEqual = std::equal_to<Key>,
    class Allocator = std::allocator< std::pair<const Key, T> >
> class unordered_map;

Principles

• An hash function \(f: K \rightarrow int\) hashes every key \(k : K\) in its hash code, a “pseudo random” integer.
• The hash code \(C = f(k)\) addresses a bucket, i.e. a list or vector of pairs whose keys has the same hash code \(C\).
• The average length of bucket, called load factor is maintained under a given threshold thanks to redimensioning.

Redimensioning

Complexities summary