Skip to content

Chapter 12: Algorithms

12.1 Introduction

A standard algorithm is expressed in terms of (half-open) sequences of elements. A sequence is represented by a pair of iterators specifying the first element and the one-beyond-the-last element.

12.2

Iterators are used to separate algorithms and containers. An algorithm operates on its data through iterators and knows nothering about the container in which the elements are stored. Containers knows nothing about the algorithms operating on its elements; all it does is to supply iterators upon request.

check this idea

To compare with this python, this basic concepts is closer to Iterables in python's sense, rather than Sequence.

12.3

Any particular iterator is an object of some type.

12.4

Containers are not the only place where we find sequences of elements. The notion of iterators can be usefully applied to input and output: std::ostream_iterator<T> and std::istream_iterator<T>. See also ifstream/ofstream.

12.5

We often want to make a parameterized "action" to the algorithm. A more general variant looks for an element that fulfills a specific requirement, a predicate.

12.6

This section lists an overview of algorithms.

12.7

This section talks about the constrained algorithms, with the help of Concepts. More specifically, for C++ 20, the ranges concepts are defined in <ranges>.

Range (a Concept) is a generalization of the C++98 sequences defined by begin()/end() pairs. Range is a concept specifying what it takes to be a sequence of elements

  • A {begin, end} pair of iterators
  • A {begin, n} pair where begin is a iterators and n is the number of elements
  • A {begin, pred} pair, where pred{p} is a sentential that indicates the end of a sequence. if pred{p} is always true, we can have an infinite sequence.

More concepts can be found in <ranges>, <iterator>, <concepts>. For example Common<T,U> is a concept saying that a type C that we can use for compariing a T with a U by first conversting both to Cs.

Here I note down the discussion on the cnocept of sentinel: The basic idea of a sentinel is that we can iterate over a range starting at an iterator until the predicate becomes true for an element. That way, an iterator p and a sentinel s define a range [p:s(*p)].

Todo

Here, it is probably worth a dedicated study session of different concepts.

  • Core language concepts
  • Comaprison concepts
  • Object concepts
  • Callable concepts
  • Iterator concepts
  • Range concepts

!!! NOTE "This section has been moved out as Chapter 14 in the 3rd edition range v.s. view: The key difference is that a view doesn't own its elements; it is not responsible for deleting the elements of its underlying range - that's the range's responsbility. Views are supposed to be cheap to copy, so we pass them by value.

12.8 Container Algorithms

no notes

12.9 Parallel Algorithm

execution policy <execution>

  • parallel execution: tasks are done on multiple threads
  • vectorized execution: tasks are done on a single thread using vectorization, also known as SIMD (Single Instruction, Multiple Data)
  • policy types:
    • seq: sequential execution
    • par: parallel execution (if feasible)
    • par_unseq: parallel and/or unsequenced (vectorized) execution (if feasible)

Note

the execution policy indicators are just hints. A compiler and/or run-time scheduler will decide how much concurrency to use.