Standard Library

The C++ standard library provides a set of useful classes and functions.

Limits

TODO:

Chrono

Used to calculate and measure time from different sources.

  using Clock = chrono::system_clock;
Clock::time_point start = Clock::now();

auto t1 = 5s; // 5 seconds
auto t2 = 150ms; // 150 milliseconds
auto t3 = t1 + t2; // 5150 milliseconds

Containers

Different types of containers are available in the standard library.

  • Bitvector
    • Bitset: bitset
  • Halbdynamisch
    • Halbdynamisch: vector (vector<bool> is a special case using one bit per boolean)
  • Lists
    • Double Ended Queue: deque
    • Doubly Linked List: list
    • Singly Linked List: forward_list
  • Ordered Sets
    • Set: set (keys are unique)
    • Multiset: multiset (duplicate keys allowed)
  • Maps
    • Map: map
    • Multimap: multimap (duplicate keys allowed)
  • Unordered Sets
    • Unordered Set: unordered_set (keys are unique)
    • Unordered Multiset: unordered_multiset (duplicate keys allowed)
  • Unordered Maps
    • Unordered Map: unordered_map
    • Unordered Multimap: unordered_multimap (duplicate keys allowed)
  • Interfaces (use other containers as storage and provide a different interface)
    • Stack: stack
    • Queue: queue
    • Priority Queue: priority_queue

Member Types

Required member types for a container X<T>:

  • X::value_type: type of the elements
  • X::reference: reference to container element
  • X::const_reference: const reference to container element
  • X::iterator: iterator to container element
  • X::const_iterator: const iterator to container element
  • X::difference_type: difference type for iterators
  • X::size_type: size type for container

Methods

  • Default, copy, and move constructor; destructor
  • Iterators: begin(), end(), cbegin() (read only), cend() (read only)
  • Size: max_size(), size(), empty()
  • Assignment and move operators
  • Relational operators
  • Swap: swap(X&)

Iterators

Iterators are used to iterate over a container. They are similar to pointers and can be used in the same way. Iterators are used to abstract from the underlying container.

  template<class Iter> void print(Iter it, Iter end) {
    while (it != end) {
        cout << *it++ << endl; // This works because the post-increment operator returns the old value
    }
}

Iterator Categories

Iterators are classified into five categories:

  • Input Iterator: Read only, forward only, single pass
  • Output Iterator: Write only, forward only, single pass
  • Forward Iterator: Read and write, forward only, multi pass
  • Bidirectional Iterator: Read and write, forward and backward, multi pass
  • Random Access Iterator: Read and write, forward and backward, multi pass, random access

Algorithms

Algorithms are functions that operate on iterators. They are used to abstract from the underlying container.

If algorithms require a begin and end iterator, the end iterator is always one past the last element.

  const int searchValue = 5;
vector<int> v = {9, 3, 5, 8, 1, 7, 2, 4};
sort(v.begin(), v.end()); // Sorts the vector
auto pos = lower_bound(v.cbegin(), v.cend(), searchValue);
cout << *pos << endl;

Different algorithms include:

  • Search element
    • find(), find_if(), find_if_not(), find_end(), find_first_of(), adjacent_find()
    • nth_element()
  • Search sequence
    • search(), search_n()
  • Count
    • count(), count_if()
  • Comparison
    • min(), max(), min_element(), max_element()
    • lexicographical_compare()
    • equal(), mismatch()

Parallel Algorithms

Parallel algorithms are available in the execution namespace. They are used in the same way as the normal algorithms, but require an execution policy as first argument.

  vector<int> v = {9, 3, 5, 8, 1, 7, 2, 4};
sort(execution::par, v.begin(), v.end()); // Sorts the vector in parallel