Version 0.3 update

HappyCerberus · HappyCerberus · commit b62ac1902389 · 2022-09-28T19:50:59.000+02:00
diff --git a/book.tex b/book.tex
@@ -33,14 +33,14 @@
 \frontmatter
 \input{chapters/00_title_page}
 
-%\input{chapters/01_preface} % Reviewed
+\input{chapters/01_preface} % Reviewed
 
 \mainmatter
 \tableofcontents
 
-%\input{chapters/02_introduction} % In review
-%\input{chapters/03_algorithms_00_main} % In review
-%\input{chapters/04_ranges_in_depth} % In review
+\input{chapters/02_introduction} % In review
+\input{chapters/03_algorithms_00_main} % In review
+\input{chapters/04_ranges_in_depth} % In review
 
 \input{chapters/90_theory} % TODO
 
diff --git a/chapters/02_introduction.tex b/chapters/02_introduction.tex
@@ -144,6 +144,8 @@ \section{A simpler mental model for iterators}
 
 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.
 
+\newpage
+
 In some cases, a single returned iterator denotes multiple ranges.
 
 \begin{box-note}
diff --git a/chapters/03_algorithms_02_swaps.tex b/chapters/03_algorithms_02_swaps.tex
@@ -1,32 +1,6 @@
 \section{Swaps}
 
-Before discussing swaps, we need to make a short detour and discuss argument-dependent lookup, an essential aspect of the pre-C++20 version of the std::swap algorithm.
-
-Argument-dependent lookup is relied upon heavily in C++, notably when overloading operators.
-
-\begin{box-note}
-\footnotesize Example of argument-dependent lookup for \cpp{operator<<} implemented as a function.
-\tcblower
-\cppfile{code_examples/theory/adl_code.h}
-\end{box-note}
-
-The situation changes slightly when the function is implemented as a friend function. Such a function is a member of the surrounding namespace. However, it is not visible outside of ADL.
-
-\begin{box-note}
-\footnotesize Example of argument-dependent lookup for \cpp{operator<<} implemented as a friend function.
-\tcblower
-\cppfile{code_examples/theory/adl_friend_code.h}
-\end{box-note}
-
-The benefit of relying on ADL is that there is no complexity on the caller's site. An unqualified call will invoke the correct overload. Except, this wouldn't be C++ if there weren't an exception to this rule.
-
-If on top of having the ability to specialize, we also want default behaviour as a fallback, the caller now needs to make sure to pull in the default overload to the local scope.
-
-\begin{box-note}
-\footnotesize Example of argument-dependent lookup with a default templated version of the function.
-\tcblower
-\cppfile{code_examples/theory/adl_default_code.h}
-\end{box-note}
+Before C++11 and the introduction of move operations, swaps were the only way objects with value semantics could exchange content without involving a deep copy.
 
 \subsection{\texorpdfstring{\cpp{std::swap}}{\texttt{std::swap}}}
 \index{\cpp{std::swap}}
@@ -35,7 +9,7 @@ \subsection{\texorpdfstring{\cpp{std::swap}}{\texttt{std::swap}}}
 
 \cppversions{\texttt{swap}}{\CC98}{\CC20}{N/A}{\CC20}
 
-Correctly calling swap (as mentioned at the beginning of this section) requires pulling the default std::swap version to the local scope.
+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}).
 
 \begin{box-note}
 \footnotesize Example of correctly calling \cpp{std::swap}.
diff --git a/chapters/03_algorithms_03_sorting.tex b/chapters/03_algorithms_03_sorting.tex
@@ -35,7 +35,7 @@ \section{Sorting}
 \subsection{\texorpdfstring{\cpp{std::lexicographical_compare}}{\texttt{std::lexicographical\_compare}}}
 \index{\cpp{std::lexicographical_compare}}
 
-Lexicographical \texttt{strict\_weak\_ordering} for ranges is exposed through the \texttt{std::lexicographical\_compare} algorithm.
+Lexicographical \texttt{strict\_weak\_ordering} for ranges is exposed through the \newline\texttt{std::lexicographical\_compare} algorithm.
 
 \cppversions{\texttt{lex\dots compare}}{\CC98}{\CC20}{\CC17}{\CC20}
 
@@ -58,7 +58,14 @@ \subsection{\texorpdfstring{\cpp{std::lexicographical_compare}}{\texttt{std::lex
 \subsection{\texorpdfstring{\cpp{std::lexicographical_compare_three_way}}{\texttt{std::lexicographical\_compare\_three\_way}}}
 \index{\cpp{std::lexicographical_compare_three_way}}
 
-The \texttt{std::lexicographical\_compare\_three\_way} is the spaceship operator equivalent to \texttt{std::lexicographical\_compare}. It returns one of \texttt{std::strong\_ordering}, \texttt{std::weak\_ordering} or \texttt{std::partial\_ordering} types, depending on the type returned by the elements' spaceship operator.
+The \texttt{std::lexicographical\_compare\_three\_way} is the spaceship operator equivalent to \texttt{std::lexicographical\_compare}. It returns one of:
+\begin{itemize}
+    \item\texttt{std::strong\_ordering}
+    \item \texttt{std::weak\_ordering}
+    \item \texttt{std::partial\_ordering}
+\end{itemize}
+
+The type depends on the type returned by the elements' spaceship operator.
 
 \cppversions{\texttt{lex\dots three\_way}}{\CC20}{\CC20}{N/A}{N/A}
 \constraints{\texttt{(input\_range, input\_range)}}{}{\texttt{operator<=>}}{\texttt{strong\_ordering}, \texttt{weak\_ordering}, \texttt{partial\_ordering}}
@@ -140,7 +147,7 @@ \subsection{\texorpdfstring{\cpp{std::is_sorted_until}}{\texttt{std::is\_sorted\
 \end{box-note}
 
 Note that because of the behaviour of \cpp{std::is_sorted_until}, the following is always true:\\
-\small\cpp{std::is_sorted(r.begin(), std::is_sorted_until(r.begin(), r.end()))}
+\begin{small}\cpp{std::is_sorted(r.begin(), std::is_sorted_until(r.begin(), r.end()))}\end{small}
 
 \subsection{\texorpdfstring{\cpp{std::partial_sort}}{\texttt{std::partial\_sort}}}
 \index{\cpp{std::partial_sort}}
@@ -188,8 +195,8 @@ \subsection{\texorpdfstring{\cpp{qsort}}{\texttt{qsort}} - C standard library}
 
 I would strongly recommend avoiding \cpp{qsort}, as \cpp{std::sort} and \cpp{std::ranges::sort} should be a better choice in every situation. Moreover, \cpp{qsort} is only valid for trivially copyable types, and those will correctly optimize to \cpp{memcpy}/\cpp{memmove} operations even when using \cpp{std::sort}.
 
-\begin{box-note}
+\begin{box-nobreak}
 \footnotesize Example of using \cpp{std::sort} to achieve the same result as in the previous example.
 \tcblower
 \cppfile{code_examples/algorithms/qsort_not_code.h}
-\end{box-note}
+\end{box-nobreak}
diff --git a/chapters/03_algorithms_04_partitioning.tex b/chapters/03_algorithms_04_partitioning.tex
@@ -45,11 +45,11 @@ \subsection{\texorpdfstring{\cpp{std::is_partitioned}}{\texttt{std::is\_partitio
 
 Note that a sorted range is always partitioned for any possible value (with a different partition point).
 
-\begin{box-note}
+\begin{box-nobreak}
 \footnotesize Example of using \cpp{std::is_partitioned}.
 \tcblower
 \cppfile{code_examples/algorithms/is_partitioned_code.h}
-\end{box-note}
+\end{box-nobreak}
 
 \subsection{\texorpdfstring{\cpp{std::partition_copy}}{\texttt{std::partition\_copy}}}
 \index{\cpp{std::partition_copy}}
diff --git a/chapters/03_algorithms_05_divide.tex b/chapters/03_algorithms_05_divide.tex
@@ -57,7 +57,7 @@ \subsection{\texorpdfstring{\cpp{std::equal_range}}{\texttt{std::equal\_range}}}
 \subsection{\texorpdfstring{\cpp{std::partition_point}}{\texttt{std::partition\_point}}}
 \index{\cpp{std::partition_point}}
 
-Despite the naming, \cpp{std:partition_point} works very similarly to \cpp{std::upper_bound}, however instead of searching for a particular value, it searches using a predicate.
+Despite the naming, \cpp{std:partition_point} works very similarly to \texttt{std::upper\-\_bound}, however instead of searching for a particular value, it searches using a predicate.
 
 \cppversions{\texttt{partition\_point}}{\CC11}{\CC20}{N/A}{\CC20}
 \constraints{\texttt{forward\_range}}{}{N/A}{\texttt{unary\_predicate}}
diff --git a/chapters/03_algorithms_07_sets.tex b/chapters/03_algorithms_07_sets.tex
@@ -34,11 +34,11 @@ \subsection{\texorpdfstring{\cpp{std::set_symmetric_difference}}{\texttt{std::se
 
 For equivalent elements, where the first range contains $M$ such elements and the second range contains $N$ such elements, the result will contain the last \cpp{std::abs(M-N)} such elements from the corresponding range. That is, if $M>N$, $M-N$ elements will be copied from the first range; otherwise, $N-M$ elements will be copied from the second range.
 
-\begin{box-note}
+\begin{box-nobreak}
 \footnotesize Example of using \cpp{std::set_symmetric_difference}.
 \tcblower
 \cppfile{code_examples/algorithms/set_symmetric_difference_code.h}
-\end{box-note}
+\end{box-nobreak}
 
 \begin{box-note}
 \footnotesize Example demonstrating \cpp{std::set_symmetric_difference} behaviour when equivalent elements are present.
diff --git a/chapters/03_algorithms_08_transformations.tex b/chapters/03_algorithms_08_transformations.tex
@@ -93,7 +93,7 @@ \subsection{\texorpdfstring{\cpp{std::reverse}}{\texttt{std::reverse}}}
 \cppfile{code_examples/algorithms/reverse_code.h}
 \end{box-note}
 
-C-style arrays and C-style strings can be adapted using \cpp{std::span} and \cpp{std::string_view} to allow reverse iteration.
+C-style arrays and C-style strings can be adapted using \cpp{std::span} and \texttt{std::string\-\_view} to allow reverse iteration.
 
 \begin{box-note}
 \footnotesize Example of using \cpp{std::span} and \cpp{std::string_view} to addapt C-style constructs for reverse iteration.
@@ -104,7 +104,7 @@ \subsection{\texorpdfstring{\cpp{std::reverse}}{\texttt{std::reverse}}}
 \subsection{\texorpdfstring{\cpp{std::rotate}}{\texttt{std::rotate}}}
 \index{\cpp{std::rotate}}
 
-The \cpp{std::rotate} algorithm rearranges elements in the range from \cpp{[first, middle),[middle, last)} to \cpp{[middle, last),[first, middle)}.
+The \cpp{std::rotate} algorithm rearranges elements in the range from \texttt{[first, middle),} \texttt{[middle, last)} to \texttt{[middle, last),} \texttt{[first, middle)}.
 
 \cppversions{\texttt{rotate}}{\CC11}{\CC20}{\CC17}{\CC20}
 \constraints{\texttt{(forward\_range, forward\_iterator)}}{\texttt{(forward\_range, forward\_iterator)}}{}{}
@@ -118,7 +118,7 @@ \subsection{\texorpdfstring{\cpp{std::rotate}}{\texttt{std::rotate}}}
 \subsection{\texorpdfstring{\cpp{std::shuffle}}{\texttt{std::shuffle}}}
 \index{\cpp{std::shuffle}}
 
-The \cpp{std::shuffle} algorithm is a successor of the now-defunct \cpp{std::random_shuffle} algorithm (deprecated in \CC14, removed in \CC17) and relies on new random facilities added in \CC11.
+The \cpp{std::shuffle} algorithm is a successor of the now-defunct (deprecated in \CC14, removed in \CC17) \cpp{std::random_shuffle} algorithm and relies on new random facilities added in \CC11.
 
 \cppversions{\texttt{shuffle}}{\CC11}{N/A}{N/A}{\CC20}
 \constraints{\texttt{random\_access\_range}}{}{}{}
diff --git a/chapters/03_algorithms_10_general_reductions.tex b/chapters/03_algorithms_10_general_reductions.tex
@@ -14,7 +14,7 @@ \subsection{\texorpdfstring{\cpp{std::reduce}}{\texttt{std::reduce}}}
 \cppversions{\texttt{reduce}}{\CC17}{\CC20}{\CC17}{N/A}
 \constraints{\texttt{input\_range}}{\texttt{forward\_range}}{\texttt{std::plus<>()}}{\texttt{binary\_functor}}
 
-Note that while we have access to a sequenced execution policy (\cpp{std::execution::seq}), this does not make \cpp{std::reduce} sequenced in a left-fold sense.
+Note that while we have access to a sequenced execution policy (i.e. \newline\cpp{std::execution::seq}), this does not make \cpp{std::reduce} sequenced in a left-fold sense.
 
 \begin{box-note}
 \footnotesize Example of using \cpp{std::reduce} with and without an execution policy.
@@ -35,7 +35,7 @@ \subsection{\texorpdfstring{\cpp{std::reduce}}{\texttt{std::reduce}}}
 \subsection{\texorpdfstring{\cpp{std::transform_reduce}}{\texttt{std::transform\_reduce}}}
 \index{\cpp{std::transform_reduce}}
 
-The \cpp{std::transform_reduce} algorithm is the generalised counterpart to \cpp{std::inner_product}. On top of the two-range variant, the algorithm also provides a unary overload.
+The \cpp{std::transform_reduce} algorithm is the generalised counterpart to \texttt{std::inner\-\_product}. On top of the two-range variant, the algorithm also provides a unary overload.
 
 \cppversions{\texttt{transform\_reduce}}{\CC17}{\CC20}{\CC17}{N/A}
 \constraints{\texttt{input\_range}}{\texttt{forward\_range}}{N/A}{\texttt{(binary\_functor, unary\_functor)}}
diff --git a/chapters/03_algorithms_12_generators.tex b/chapters/03_algorithms_12_generators.tex
@@ -50,12 +50,12 @@ \subsection{\texorpdfstring{\cpp{std::iota}}{\texttt{std::iota}}}
 \cppfile{code_examples/algorithms/iota_code.h}
 \end{box-note}
 
-Notably, the \cpp{std::iota} algorithm is also an outlier in the support added with the C++20 standard. The std::iota algorithm did not receive a range version. However, we do have access to an iota view.
+Notably, the \cpp{std::iota} algorithm is also an outlier in the support added with the C++20 standard. The \cpp{std::iota} algorithm did not receive a range version. However, we do have access to an iota view.
 
-\begin{box-note}
+\begin{box-nobreak}
 \footnotesize Example of using both finite and infinite \cpp{std::views::iota}.
 \tcblower
 \cppfile{code_examples/algorithms/iota_view_code.h}
-\end{box-note}
+\end{box-nobreak}
 
-Here we take advantage of the finite view constructor \cpp{std::views::iota(1,10)} to establish the output size (line 3), which allows us to use the infinite view \cpp{std::views::iota(5)} for the second parameter. Functionally, we could swap even the second view for a finite one. However, this would impose an additional (and unnecessary) boundary check.
+Here we take advantage of the finite view constructor \cpp{std::views::iota(1,10)} to establish the output size (line 3), which allows us to use the infinite view \texttt{std::views\-::iota(5)} for the second parameter. Functionally, we could swap even the second view for a finite one. However, this would impose an additional (and unnecessary) boundary check.
diff --git a/chapters/03_algorithms_13_copies_moves.tex b/chapters/03_algorithms_13_copies_moves.tex
@@ -50,11 +50,11 @@ \subsection{\texorpdfstring{\cpp{std::copy_backward}, \cpp{std::move_backward}}{
 
 The output iterator cannot be within \cpp{(first, last]} and will be treated as the end iterator for the destination range, meaning that the algorithm will write the first value to \cpp{std::prev(end)}.
 
-\begin{box-note}
+\begin{box-nobreak}
 \footnotesize Example of a non-overlapping and permitted overlapping case of \cpp{std::copy_backward}.
 \tcblower
 \cppfile{code_examples/algorithms/copy_backward_code.h}
-\end{box-note}
+\end{box-nobreak}
 
 \subsection{\texorpdfstring{\cpp{std::copy_n}}{\texttt{std::copy\_n}}}
 \index{\cpp{std::copy_n}}
diff --git a/chapters/03_algorithms_15_heap.tex b/chapters/03_algorithms_15_heap.tex
@@ -20,11 +20,11 @@ \subsection{\texorpdfstring{\cpp{std::make_heap}, \cpp{std::push_heap}, \cpp{std
 
 The \cpp{std::make_heap} algorithm reorders elements in the given range such that the elements maintain the max-heap property, that is, the element at index $i$ compares greater or equal to the elements at indexes $2i+1$ and $2i+2$.
 
-\begin{box-note}
+\begin{box-nobreak}
 \footnotesize Example of using \cpp{std::make_heap} to construct a max-heap and a min-heap (using a custom comparator).
 \tcblower
 \cppfile{code_examples/algorithms/make_heap_code.h}
-\end{box-note}
+\end{box-nobreak}
 
 The \cpp{std::push_heap} and \cpp{std::pop_heap} algorithms simulate push and pop operations for the max-heap data structure. However, because they operate on top of a range, they cannot manipulate the underlying data structure. Therefore, they use the last element of the range as the input/output.
 
@@ -61,7 +61,7 @@ \subsection{\texorpdfstring{\cpp{std::is_heap}, \cpp{std::is_heap_until}}{\textt
 
 \constraints{\texttt{random\_access\_range}}{}{\texttt{operator<}}{\texttt{strict\_weak\_ordering}}
 
-The two algorithms follow the same logic as \cpp{std::is_sorted} and \cpp{std::is_sorted_until}, returning a boolean and an iterator to the first out-of-order element respectively.
+The two algorithms follow the same logic as \cpp{std::is_sorted} and \texttt{std::is\-\_sorted\-\_until}, returning a boolean and an iterator to the first out-of-order element respectively.
 
 \begin{box-note}
 \footnotesize Example of using \cpp{std::is_heap} and \cpp{std::is_heap_until}.
diff --git a/chapters/03_algorithms_16_searching.tex b/chapters/03_algorithms_16_searching.tex
@@ -85,7 +85,7 @@ \subsection{\texorpdfstring{\cpp{std::search}, \cpp{std::find_end}}{\texttt{std:
 \index{\cpp{std::find_end}}
 
 Both \cpp{std::search} and \cpp{std::find_end} algorithms search for a sub-sequence in a sequence.
-The \cpp{std::search} algorithm will return the first instance, and \cpp{std::find_end} will return the last.
+The \cpp{std::search} algorithm will return the first instance, and \texttt{std::find\-\_end} will return the last.
 
 \cppversions{\texttt{search, find\_end}}{\CC98}{\CC20}{\CC17}{\CC20}
 \constraints{\texttt{(forward\_range, forward\_range)}}{\texttt{(forward\_range, forward\_range)}}{\texttt{operator==}}{\texttt{binary\_predicate}}
diff --git a/chapters/03_algorithms_17_minmax.tex b/chapters/03_algorithms_17_minmax.tex
@@ -105,4 +105,4 @@ \subsection{\texorpdfstring{\cpp{std::min_element}, \cpp{std::max_element}, \new
 \cppfile{code_examples/algorithms/min_element_dangling_code.h}
 \end{box-note}
 
-All ranged versions of algorithms that return iterators will return the \cpp{std::ranges::dangling} type when invoked on a temporary range. This would preclude the use case of using \cpp{std::span} to sub-reference a range, which is why the range algorithms have an additional concept of a \cpp{borrowed_range}. Such ranges can be passed in as temporaries since they do not own their elements.
+All ranged versions of algorithms that return iterators will return the \texttt{std::ranges\-::dangling} type when invoked on a temporary range. This would preclude the use case of using \cpp{std::span} to sub-reference a range, which is why the range algorithms have an additional concept of a \cpp{borrowed_range}. Such ranges can be passed in as temporaries since they do not own their elements.
diff --git a/chapters/04_ranges_in_depth.tex b/chapters/04_ranges_in_depth.tex
@@ -14,11 +14,11 @@ \section{Reliance on concepts}
 
 First, the definitions of all concepts are now part of the standard library, e.g. you can look up what exactly it means for a type to be a \cpp{random_access_range} and also use these concepts to constrain your code.
 
-\begin{box-note}
+\begin{box-nobreak}
 \footnotesize Example of using standard concepts in user code. The function accepts any random access range as the first argument and an output iterator with the same underlying type as the second argument.
 \tcblower
 \cppfile{code_examples/ranges/concepts_code.h}
-\end{box-note}
+\end{box-nobreak}
 
 Second, error messages now reference unsatisfied constraints instead of reporting an error deep in the library implementation.
 
@@ -86,7 +86,7 @@ \section{Dangling iterator protection}
 \cppfile{code_examples/ranges/dangling_code.h}
 \end{box-note}
 
-User types can declare themselves as borrowed ranges by specializing the \cpp{enable_borrowed_range} constant.
+User types can declare themselves as borrowed ranges by specializing the \texttt{enable\-\_borrowed\-\_range} constant.
 
 \begin{box-note}
 \footnotesize Example demonstrating declaring MyView as a borrowed range.
@@ -231,7 +231,7 @@ \subsection{\texorpdfstring{\cpp{std::views::split}, \cpp{std::views::lazy_split
 \index{\cpp{std::views::join_view}}
 
 The two split views split a single range into a view over sub-ranges. However, they differ in their implementation.
-The \cpp{std::view::split} maintains the bidirectional, random access or contiguous properties of the underlying range, and the \cpp{std::view::lazy_split} does not, but it does support input ranges.
+The \cpp{std::view::split} maintains the bidirectional, random access or contiguous properties of the underlying range, and the \texttt{std::view::\-lazy\_split} does not, but it does support input ranges.
 
 \begin{box-note}
 \footnotesize Example of using split view to parse a version number.
diff --git a/chapters/90_theory.tex b/chapters/90_theory.tex
