You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Copy file name to clipboardExpand all lines: chapters/01_preface.tex
+9-3Lines changed: 9 additions & 3 deletions
Original file line number
Diff line number
Diff line change
@@ -30,10 +30,16 @@ \section*{Why cc-by-sa-nc}
30
30
31
31
Explicitly, any personal use is permitted. For example, you can read, print, or share the book with your friends.
32
32
33
-
If you want to use this content where you are unsure whether you fit within the Creative Commons commercial definition\footnote{primarily intended for or directed toward commercial advantage or monetary compensation}, feel free to contact me on \href{https://twitter.com/SimonToth83}{Twitter}, \href{https://cz.linkedin.com/in/simontoth}{LinkedIn} or by \href{mailto:business@simontoth.eu}{email} (my DMs are always open).
33
+
If you want to use this content where you are unsure whether you fit within the Creative Commons commercial definition\footnote{primarily intended for or directed toward commercial advantage or monetary compensation}, feel free to contact me on \href{https://hachyderm.io/@simontoth}{Mastodon}, \href{https://cz.linkedin.com/in/simontoth}{LinkedIn} or by \href{mailto:business@simontoth.eu}{email} (my DMs are always open).
34
34
35
35
\section*{Book status}
36
36
37
-
The book is currently in pre-release.
37
+
This book is currently content-complete (upto and including \CC20).
38
38
39
-
To keep up with the changes, visit the hosting repository: \url{https://github.com/HappyCerberus/book-cpp-algorithms}. Internal changelog will be kept after version 1.0 is released.
39
+
To keep up with the changes, visit the hosting repository: \url{https://github.com/HappyCerberus/book-cpp-algorithms}.
Copy file name to clipboardExpand all lines: chapters/02_introduction.tex
+22-22Lines changed: 22 additions & 22 deletions
Original file line number
Diff line number
Diff line change
@@ -11,33 +11,33 @@ \section{History of standard \texorpdfstring{\CC}{C++} algorithms}
11
11
The \CC98 standard introduced most of the algorithms. However, it was the \CC11 standard with its introduction of lambdas that made algorithms worthwhile. Before lambdas, the time investment of writing a custom function object made the usefulness of algorithms dubious.
\footnotesize Example of \cpp{std::for_each}\index{\cpp{std::for_each}} algorithm with a custom function object, calculating the number of elements and their sum.
\footnotesize Example of \cpp{std::for_each}\index{\cpp{std::for_each}} algorithm with a capturing lambda, calculating the number of elements and their sum.
The \CC17 standard introduced parallel algorithms that provide an easy way to speed up processing with minimal effort. All you need to do is to specify the desired execution model, and the library will take care of parallelizing the execution.
\footnotesize Example of \cpp{std::for_each}\index{\cpp{std::for_each}} algorithm using unsequenced parallel execution model. Note that counters are now shared state and need to be \cpp{std::atomic}\index{\cpp{std::atomic}} or protected by a \cpp{std::mutex}\index{\cpp{std::mutex}}.
Finally, the \CC20 standard introduced a significant re-design in the form of ranges and views. Range versions of algorithms can now operate on ranges instead of \cpp{begin} and \cpp{end} iterators and views provide lazily evaluated versions of algorithms and utilities.
As of the time of writing, the \CC23 standard is not finalized. However, we already know that it will introduce more range algorithms, more views and the ability to implement custom views.
43
43
@@ -51,19 +51,19 @@ \section{Iterators and ranges}
51
51
52
52
To reference the entire content of a data structure, we can use the \cpp{begin()} and \cpp{end()} methods that return an iterator to the first element and an iterator one past the last element, respectively. Hence, the range \cpp{[begin, end)} contains all data structure elements.
Sentinels follow the same idea. However, they do not need to be of an iterator type. Instead, they only need to be comparable to an iterator. The exclusive end of the range is then the first iterator that compares equal to the sentinel.
\footnotesize Example of specifying a range using an iterator and custom sentinel. The sentinel will compare \cpp{true} with iterators at least the given distance from the start iterator, therefore defining a range with the specified number of elements.
\footnotesize Example demonstrating the difference between a random access iterator provided by \cpp{std::vector} and a bidirectional iterator provided by \cpp{std::list}.
\footnotesize Example with two ranges passed in as an argument. The input range is fully specified, and the end iterator for the output range is implied from the number of elements in the input range.
\footnotesize Example of \cpp{std::is_sorted_until} that returns an iterator to the first out-of-order element, which can also be thought as the end iterator for a maximal sorted sub-range.
The benefit of thinking about the returned value as the end iterator of a range is that it removes the potential for corner cases. For example, what if the algorithm doesn't find any element out of order? The returned value will be the end iterator of the source range, meaning that the range returned is simply the entire source range.
146
146
147
147
\newpage
148
148
149
149
In some cases, a single returned iterator denotes multiple ranges.
Copy file name to clipboardExpand all lines: chapters/03_algorithms_01_foreach.tex
+13-11Lines changed: 13 additions & 11 deletions
Original file line number
Diff line number
Diff line change
@@ -1,6 +1,6 @@
1
1
\section{Introducing the algorithms}
2
2
3
-
In this chapter, we introduce each of the 114 standard algorithms. The groups of algorithms are arbitrary and mainly introduced for presentation clarity. Therefore, you might correctly argue that a specific algorithm would be better suited to reside in a different group.
3
+
In this chapter, we introduce each of the standard algorithms. The groups of algorithms are arbitrary and mainly introduced for presentation clarity. Therefore, you might correctly argue that a specific algorithm would be better suited to reside in a different group.
4
4
5
5
Before we start, we will use the \cpp{std::for_each} and \cpp{std::for_each_n} algorithms to demonstrate this chapter's structure for each algorithm.
However, there are still a few corner cases when using \cpp{std::for_each} is preferable.
54
54
55
55
The first case is straightforward parallelization. Invoking an expensive operation for each element in parallel is trivial with \cpp{std::for_each}. As long as the operations are independent, there is no need for synchronization primitives.
\footnotesize Example of the range version of \cpp{std::ranges::for_each} utilizing a projection to invoke the method \cpp{getValue()} (line 13) on each element and summing the resulting values using a lambda (line 12).
\circled{4} While \cpp{std::for_each} operates on the entire range, the interval $[begin, end)$, \cpp{std::for_each_n} operates on the range $[first, first+n)$. Importantly, because the algorithm does not have access to the end iterator of the source range, it does no out-of-bounds checking, and it is the responsibility of the caller to ensure that the range $[first, first+n)$ is valid.
Sending invitations to the \texttt{MAIN\_SEATS} top players is done in parallel (lines 4-7). Then all users' scores are stored in chunks of \texttt{PAGE\_SIZE} records (lines 13-15). Note that calculating the remaining number of elements (line 12) and jumping ahead by the number of stored elements (line 17) requires a random access iterator (in this case, provided by \cpp{std::vector}).
Correctly calling swap requires pulling the default std::swap version to the local scope. To read more on why this is needed check out the theory chapter of this book, specifically the section on ADL (\ref{theory:adl}).
\footnotesize Example demonstrating the use \cpp{std::iter_swap} in a generic two-way partition algorithm. The algorithm uses concepts to constrain the acceptable types of its arguments.
\footnotesize Example demonstrating the use of range version of \cpp{std::ranges::iter_swap} to swap the values pointed to by two instances of \cpp{std::unique_ptr}.
\footnotesize Example of swapping the first three elements of an array with the last three elements using \cpp{std::swap_ranges}. Note the reversed order of elements due to the use of \cpp{rbegin}.
0 commit comments