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.

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:

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:

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.

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.

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.

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:

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:

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.

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.

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:

[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.

[](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

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.

auto f = [v1] () mutable { return ++v1; };

If we write the seemingly equivalent program using an if statement, our code won't compile:

[](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:

[](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:

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:

auto g = bind(f, a, b, _2, c, _1);

In effect, this call to bind maps:

g(_1, _2);
to f(a, b, _2, c, _1);

We can also use bind to invert the meaning:

bind(isShorter, _2, _1);

Binding reference parameters

[&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:

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.

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.

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:

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:

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.

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.

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.