# Chapter 10. Generic Algorithms
## 10.1 Overview
Most of the algorithms are defined in the `algorithm` header. The library also defines a set of generic numeric algorithms that are defined in the `numeric` header.
The iterator dereference operator gives access to an element's value.
Although iterators make the algorithms container independent, most of the algorithms use one operation on the element type.
## 10.2 A First Look at the Algorithms
### 10.2.1 Read-Only Algorithms
A number of the algorithms read, but never write to , the elements in their input range. The `accumulate` function takes three arguments. The first two specify a range of elements to sum. The third is an initial value fro the sum.
```cpp
int sum = accumulate(vec.cbegin(), vec.cend(), 0);
```
Another read-only algorithm is equal, which lets us determine whether two sequences hold the same values. The algorithm takes three iterators: The first two denote the range of elements in the first sequence; the third denotes the first element in the second sequence:
```cpp
equal(rester1.cbegin(), roster1.cend(), rester2.cbegin());
```
### 10.2.2 Algorithms That Write Container Elements
Some algorithms assign new values to the elements in a sequence. The `fill` algorithm takes a pair of iterators that denote a range and a third argument that is a value. `fill` assigns the given value to each element in the input sequence:
```cpp
fill(vec.begin(), vec.end(), 0);
```
The `fill_n` function takes a single iterator, a count, and a value. It assigns the given value to the specified number of elements starting at the element denoted by the iterator.
```cpp
vector<int> vec;
fill_n(vec.begin(), 10, 0);
```
Algorithms that write to a destination iterator assume the destination is large enough to hold the number of elements being written.
An **insert iterator** is an iterator that adds elements to a container. A **back inserter** is a function defined in the iterator header. `back_inserter` takes a reference to a container and returns an insert iterator bound to that container.
```cpp
auto it = back_inserter(vec);
*it = 42; // vec now has one element with value 42
fill_n(back_inserter(vec), 10, 0)); // appends ten elements to vec
```
Since passed an iterator returned by `back_inserter`, each assignment will call `push_back` on `vec`.
This algorithm takes three iterators. The first two denote an input range; the third denotes the beginning of the destination sequence.
```cpp
auto ret = copy(begin(a1), end(a1), a2);
```
The `replace` algorithm reads a sequence and replaces every instance of a given value with another value. This algorithm takes four parameters: two iterators denoting the input range, and two values. It replaces each element that is equal to the first value with the second:
```cpp
replace(ilst.begin(), ilst.end(), 0, 42);
```
If we want to leave the original sequence unchanged, we can call replace\_copy. That algorithm takes a third iterator argument denoting a destination in which to write the adjusted sequence:
```cpp
replace(ilst.cbegin(), ilst.cend(), back_inserter(ivec), 0, 42);
```
### 10.2.3 Algorithms That Reorder Container Elements
A call of `sort` arranges the elements in the input range into sorted order using the element type's `<` operator.
```cpp
void elimDups(vector<string> &words) {
sort(words.begin(), words.end());
auto end_unique = unique(words.begin(), words.end());
words.erase(end_unique, words.end());
}
```
The `unique` algorithm rearranges the input range to "eliminate" adjacent duplicated entries, and returns an iterator that denotes the end of the range of the unique values. The size of words is unchanged.
## 10.3 Customising Operation
### 10.3.1 Passing a Function to an Algorithm
A predicate is an expression that can be called and that returns a value that can be used as a condition. The predicates used by library algorithms are either **unary predicates** or **binary predicates**.
The version of `sort` that takes a binary predicate uses the given predicate in place of `<` to compare elements.
```cpp
bool isShorter(const string &s1, const string& s2) {
return s1.size() < s2.size();
}
sort(words.begin(), words.end(), isShorter);
```
A `stable_sort` algorithm maintains the original order among equal elements.
### 10.3.2 Lambda Expressions
A `lamba` expression has the form:
```cpp
[capture list](parameter list) -> return type { function body }
```
where `capture list` is a list of local variables defined in the enclosing function; `return type`, `parameter list`, and `function body` are the same as in any ordinary function.
Lambdas with function bodies that contain anything other than a single return statement that do not specify a return type return void.
```cpp
[](const string& a, const string& b) {
return a.size() < b.size();
}
```
The empty capture list indicates that this lambda will not use any local variables from the surrounding function.
A lambda may use a variable local to its surrounding function only if the lambda captures that variable in tis capture list. The capture list is used for local `nonstatic` variables only; lambdas can use local `statics` and variable declared outside the function directly.
### 10.3.3 Lambda Captures and Returns
```cpp
auto f = [v1] { return v1; };
auto f2 = [&v1] { return v1; };
// sz implicitly captured by value
[=](const string& s) { return s.zie() >= sz; };
```
| Lambda Capture List | Description |
| :--- | :--- |
| \[\] | Empty capture list. |
| \[names\] | names is comma-separated list of names local to the enclosing function. |
| \[&\] | Implicit by reference capture list. |
| \[=\] | Implicit by value capture list. |
| \[&, identifier\_list\] | identifier\_list is a comma-separated list of zero or more variables from the enclosing function. |
| \[=, reference\_list\] | Variables included in the reference\_list are captured by reference; any implicitly captured variable are captured by value. |
Be default, a lambda may not change the value of a variable that it copies by value. If we want to be able to change the value of a captured variable, we must follow the parameter list with the keyword `mutable`.
```cpp
auto f = [v1] () mutable { return ++v1; };
```
If we write the seemingly equivalent program using an if statement, our code won't compile:
```cpp
[](int i) { if (i < 0) retutn -i; else return i; };
```
When we need to define a return type for a lambda, we must use a trailing return type:
```cpp
[](int i) -> int
{ if (i < 0) return -i; else return i; };
```
### 10.3.4 Binding Arguments
The **bind**, which is defined in the `functional` heard. The bind function can be thought of as a general-purpose function adaptor. It takes a callable object and generates a new callable that "adapts" the parameter list of the original object.
The general form of a call to bind is:
```cpp
auto newCallable = bind(callable, arg_list);
```
We can use bind to fix the value of a parameter, assuming f is callable object that has five parameters, the following call to bind:
```cpp
auto g = bind(f, a, b, _2, c, _1);
```
In effect, this call to bind maps:
```text
g(_1, _2);
to f(a, b, _2, c, _1);
```
We can also use bind to invert the meaning:
```cpp
bind(isShorter, _2, _1);
```
#### Binding reference parameters
```cpp
[&os, c](const string&s) { os << s << c; };
// error: cannot copy os
for_each(words.begin(), words.end(), bind(print, os, _1, ' '));
// we must use the library ref function
bind(print, ref(os), _1, ' ');
```
There is also a `cref` function that generates class that holds a reference to const.
## 10.4 Revisiting Iterators
The library defines several additional kinds of iterators in the `iterator` header. These iterators include:
* Insert iterators: These iterators are bound to a container and can be used to insert elements into the container.
* Stream iterators: These iterators are bound to input or output streams and can be used to iterate through the associated IO stream.
* Reverse iterators: These iterators move backward, rather than forward.
* Move iterators: These special-purpose iterators move rather than copy their elements.
### 10.4.1 Insert Iterators
An inserter is an iterator adaptor that takes a container and yields an iterator that adds elements to the specified container. When we assign a value through an insert iterator, the iterator calls a container operation to add an element at a specified position in the given container.
There are three kinds of inserters:
* back\_inserter creates an iterator that users `push_back`.
* front\_inserter creates an iterator that uses `push_front`.
* inserter creates an iterator that use `insert`.
We can use `front_inserter` only if the container has `push_front`, we can use `back_inserter` only if it has `push_back`.
| Insert Iterator Operations | Description |
| :--- | :--- |
| it = t; | Inserts the value t at the current position denoted by it. |
| \*it, ++it, it++ | These operations exist but do nothing to it. |
If it is an iterator generated by inserter, then an assignment such as `*it = val` behaves as:
```cpp
it = c.insert(it, val);
++it;
```
### 10.4.2 iostream Iterators
An **istream\_iterator** reads an input stream, and an **ostream\_iterator** writes an output steam.
```cpp
istream_iterator<int> in_iter(cin);
istreqm_iterator<int> eof; // istream "end" iterator
while (in_iter != eof)
vec.push_back(*in_iter++);
istream_iterator<int> in_iter(cin), eof;
vector<int> vec(in_iter, eof); // construct vec from an iterator range
```
| istream\_iterator Operations | Description |
| :--- | :--- |
| istream\_iterator<T> in\(is\); | in reads values of type T from input stream is. |
| istream\_iterator<T> end; | Off-the-end iterator for an istream\_iterator that reads values of type T. |
| in1 == in2 | in1 and in2 must read the same type. |
| in1 != in2 | |
| \*in | Returns the value read from the stream. |
| in->mem | Synonym for \(\*in\).mem. |
| ++in, in++ | Read the next value from the input stream using the >> operator for the element type. |
The implementation is permitted to delay reading the stream until we use the iterator.
An ostream\_iterator can be defined for any type that has an output operator. When we create an ostream\_iterator, we may provide a second argument that specifies a character print to print following each element.
| ostream Iterator Operations | Description |
| :--- | :--- |
| ostream\_iterator<T> out\(os\); | out writes values of type T to output stream os. |
| ostream\_iterator<T> out\(os, d\); | out write values of type T followed by d to output stream os. |
| out = val; | Writes val to the ostream to which out is bound using the << operator. |
| \*out, ++out, out++ | These operations exist but do nothing to out. |
```cpp
ostream_iterator<int> out_iter(cout, " ");
for(auto e : vec)
*out_iter++ = e;
cout << endl;
```
This program writes each element from `vec` onto `cout` following each element with a space. It is worth noting that we can omit the dereference and the increment when we assign to `out_iter`. That is, we can write this loop equivalently as:
```cpp
for(auto e: vec)
out_iter = e;
cout << endl;
```
### 10.4.3 Reverse Iterators
A reverse iterator is an iterator that traverses a container backward, from the last element toward the first. A reverse iterator inverts the meaning of increment.
Reverse iterators require decrement operators.
## 10.5 Structure of Generic Algorithms
The iterator operations required by the algorithms are grouped into five **iterator categories**.
| Iterator Categories | Description |
| :--- | :--- |
| Input iterator | Read, but not write; single-pass, increment only. |
| Output iterator | Write, but not read; single-pass, increment only. |
| Forward iterator | Read and write; multi-pass, increment only. |
| Bidirectional iterator | Read and write; multi-pass, increment and decrement. |
| Random-access iterator | Read and write; multi-pass, full iterator arithmetic. |
Input iterators: can read elements in a sequence. An input iterator must provide:
* Equality and inequality operators \(==, !=\) to compare two iterators.
* Prefix and postfix increment \(++\) to advance the iterator.
* Dereference operator \(\*\) to read an element; dereference may appear only on the right-hand side of an assignment.
* The arrow operator \(->\) as a synonym for `(*it).member` , that is dereference the iterator and fetch a member from the underlying object.
Out iterators: can be thought of as having complementary functionality to input iterators; they write rather than read elements. Output iterators must provide:
* Prefix and postfix increment \(++\) to advance the iterator.
* Dereference \(\*\), which may appear only as the left-hand side of an assignment.
Forward iterators: can read and write a given sequence. They move in only one direction through the sequence. Forward iterators support all the operations of both input iterators and output iterators.
Bidirectional iterators: can read and write a sequence forward or backward. In addition to supporting all the operations of a forward iterator, a bidirectional iterator also supports the prefix and postfix decrement \(--\) operators.
Random-access iterators: provide constant-time access to any position in the sequence. These iterators support all the functionality of bidirectional iterators.
* The relation operators \(<, <=, >, and >=\) to compare the relative positions of two iterators.
* Addition and subtraction operators \(+, +=, -, and -=\) on an iterator and an integral value.
* The subtraction operator \(-\) when applied to two iterators, which yields the distance between two iterators.
* The subscript operator \(inter\[n\]\) as synonym for `*(iter+n)` .
### 10.5.2 Algorithm Parameter Patterns
Most of the algorithms have one of the following four forms:
```text
alg(beg, end, other args);
alg(beg, end, dest, other args);
alg(beg, end, beg2, other args);
alg(beg, end, beg2, end2, other args);
```
where `alg` is the name of the algorithm, and `beg` and `end` denote the input range on which the algorithm operates.
A `dest` parameter is an iterator that denotes a destination in which the algorithm can write its output. Algorithms that write to an output iterator assume the destination is large enough to hold the output.
Algorithms that take `beg2` alone assume that the sequence beginning at `beg2` is as large as the range denoted by `beg` and `end`.
### 10.5.3 Algorithm Naming Conventions
Separate from the parameter conventions, the algorithms also conform to a set of naming and overload conventions.
```cpp
unique(beg, end); // uses the == operator to compare the elements
unique(beg, end, comp); // uses comp to compare the elements
```
Algorithms that take an element value typically have a second named version that takes a predicate in place of the value.
```cpp
find(beg, end, val); // find the first instance of val in the input range
find_if(beg, end, pred); // find the first instance for which pred is true
```
## 10.6 Container-Specific Algorithms
| Algorithms that are Members of list and forward\_list | Description |
| :--- | :--- |
| lst.merge\(lst2\); | Merges elements from lst2 onto lst. |
| lst.merge\(lst2, comp\); | |
| lst.remove\(val\); | Calls erase to remove each element that is == to the given value or for which the given unary predicate succeeds. |
| lst.remove\_if\(pred\); | |
| lst.reverse\(\); | Reverses the order of the elements in lst. |
| lst.sort\(\); | Reverses the order of the elements in lst; |
| lst.sort\(comp\); | |
| lst.unique\(\); | Calls erase to remove consecutive copies of the same value. |
| lst.unique\(pred\); | |
#### The splice members
| Arguments to the list and forward\_list splice Members | Description |
| :--- | :--- |
| lst.splice\(p, lst2\); | p is an iterator to an element in lst or an iterator just before an element in flst. |
| lst.splice\(p, lst2, p2\); | p2 is a valid iterator into lst2. |
| lst.splice\(p, lst2, b, e\); | b and e must denote a valid range in lst2. |
- Introduction
- Chapter 1. Getting Start
- Chapter 2. Variables and Basic Types
- Chapter 3. String, Vectors, and Arrays
- Chapter 4. Expressions
- Chapter 5. Statements
- Chapter 6. Functions
- Chapter 7. Classes
- Chapter 8. The IO Library
- Chapter 9. Sequential Containers
- Chapter 10. Generic Algorithms
- Chapter 11. Associative Container
- Chapter 12. Dynamic Memory
- Chapter 13. Copy Control
- Chapter 14. Overloaded Operations and Conversions
- Chapter 15. Object-Oriented Programming
- Chapter 16. Template Argument Deduction
- Chapter 17. Specialized Library Facilities
- Chapter 18. Tools for Large Programs
- Chapter 19. Specialized Tools and Techniques