Generic algorithm

Best example of generic algorithms is <algorithm>, which is part of STL. Another is <numeric>, contains adjacent_difference(), accumulate(), inner_product() and partial_sum().

One criticism of the generic algorithms is that their design, although elegant, places the burden of correctness on the programmer. For example, an invalid iterator or iterator pair marking an invalid range results in undefined run-time behavior.

Search algorithms - linear, binary.

adjacent_find(), binary_search(), count(), count_if(),
equal_range(), find(), find_end(), find_first_of(),
find_if(), lower_bound(), upper_bound(), search(), search_n()

Sorting and general ordering algorithms - stable, non-stable.

inplace_merge(), merge(), nth_element(), partial_sort(),
partial_sort_copy(), partition(), random_shuffle(), reverse(),
reverse_copy(), rotate(), rotate_copy(), sort(), stable_sort(),
stable_partition()

Delete and substitute algorithms

copy(), copy_backwards(), iter_swap(), remove(), remove_copy(),
remove_if(), remove_copy_if(), replace(), replace_copy(),
replace_if(), replace_copy_if(), swap(), swap_range(), unique(),
unique_copy()

Permutation algorithms
```
next_permutation(), prev_permutation()
```
Generation and mutation algorithms - fill sequence, replace existing sequence.
```
fill(), fill_n(),for_each(), generate(), generate_n(), transform()
```

Relational algorithms

equal(), includes(), lexicographical_compare(), max(),
max_element(), min(), min_element(), mismatch()

Set algorithms

set_union(), set_intersection(), set_difference(),
set_symmetric_difference()

Heap algorithms - a form of binary tree represented as an array.
```
make_heap(), pop_heap(), push_heap(), sort_heap()
```

Many algorithms support multiple versions:

use built-in operator
accept either function object or pointer to function providing an alternative implementation of that operator. This is particular useful when the underlying element type does not overload the required operator.

Some algorithms use overloading, some add _if suffix for predicate instance.

For those algorithms that modify the container over which they operate, there are generally two versions:

in-place version that changes the container against which it is applied.
version returns a copy of the container with the changes applied, with _copy suffix.

Function object is an object that in some way behaves like a pointer to function, typically, that would mean an object of a class that defines the application operator, operator(). Function object is a more general concept than a function because a function object can have state that persist across several calls (like a static local variable) and can be initialized and examined from outside the object (unlike a static local variable).

class Sum {
public:
  Sum(int i) : val(i) { }
  operator int() const { return val; }  // extract value
  int operator()(int i) { return val+=i; } // application
protected:
  int val;
};

void f(vector<int> v)
{
  Sum s = 0; // initial value 0
  s = for_each(v.begin(), v.end(), s); // gather the sum of all elements
  cout << "the sum is " << s << "\n";
  // or
  cout << "the sum is " << for_each(v.begin(), v.end(), Sum(0)) << "\n";
}

for_each() applies a pointer to function or function object to each element of a container marked by an iterator pair.

Note that a function object with an inline application operator inlines beautifully because there are no pointers involved that might confuse optimizers. To contrast, current optimizers are rarely (never?) able to inline a call through a pointer to function.

There are three sources of function object:

Predefined function object, by including <functional>. The primary use is as arguments to the generic algorithms, usually to override the default operation.
- arithmetic (plus, minus, multiplies, divides, modulus, negate)
```
plus<int> intAdd;
int i1 = 10, i2 = 20;
int sum = intAdd(i1, i2);
```
- relational(equal_to, not_equal_to, greater, greater_equal, less, less_equal)
```
vector<string> svec;
sort(svec.begin(), svec.end(), greater());
```
- logical(logical_and, logical_or, logical_not)
Predefined function adaptor, to specialize or extend the predefined function objects (or, for that matter, any function object), divided into two categories:
1. Binders: converts a binary function object into a unary object by binding one of the arguments to a particular value (bind1st, bind2nd).
```
// count all elements that are less than or equal to 10
count_if(vec.begin(), vec.end(), bind2nd(less_equal(), 10));
```
2. Negators: reverses the truth value of a function object. (not1, not2)
```
// count all elements that are not (less than or equal to 10)
count_if(vec.begin(), vec.end(),
         not1(bind2nd(less_equal(), 10)));
```
User-defined function object, to be passed to the generic algorithms and possibly against which to apply the function adaptors.

There are 5 iterator categories (from minimum supports to maximum):

InputIterator
OutputIterator
ForwardIterator
BidirectionalIterator
RandomAccessIterator

Different algorithms require different iterator categories. Passing iterator fewer support than expected is an error, but not guaranteed to be caught at compile-time because the iterator categories are not actual types. Rather, they are type parameters passed to the function template.

Constant iterator is similar to constant pointer, which prevent modifying the element through the iterator, although still can increse the iterator and dereference it. Constant container is bound only to a constant iterator.

Iterator adaptor:

Insert iterator, to insert element to container to prevent copy(), unique_copy() algorithm will fail as no space available within container.
1. back_inserter(), which causes the container's push_back() insert operation to be invoked in place of the assignment operator.
2. front_inserter(), which causes the container's push_front() insert operation to be invoked in place of the assignment operator.
3. inserter(), which causes the container's insert() insert operation to be invoked in place of the assignment operator.
The iterator marking the position to begin insertion does not remain fixed but instead is incremented with each element that is inserted so that each element is inserted in turn.
```
unique_copy(ivec.begin(), ivec.end(), inserter(vres, vres.begin());
// same as
vector<int>::iterator iter = vres.begin(), iter2 = ivec.begin();
for ( ; iter2!=ivec.end(); iter++, iter2++)
  vres.insert(iter, *iter2);
```

Reverse iterator, to traverse the container from the last element to the first (rbegin(), rend()). Its difference against forward iterator is ++ means accessing the previous element, so as --.

sort(vec.rbegin(), vec.rend()); // sorts vector in descending order
// internally
vector<int>::reverse_iterator r_iter;
for (r_iter=vec.rbegin(); // binds r_iter to last element
     r_iter!=vec.rend(); // not equal 1 past 1st element
     r_iter++) // decrements iterator one element!
  // ...

iostream iterator, by including <iterator>, to work in conjunction with input and output stream (including file IO). Its default constructor marks end-of-stream, which is used to define the ending position.

istream_iterator<int> input(cin), eos;
vector<int> vec;
copy(input, eos, inserter(vec, vec.begin()));
// ...
ostream outFile("Output.txt");
ostream_iterator<int> output(outFile, " ");
unique_copy(vec.begin(), vec.end(), output);

// reading standard input and echo
copy(istream_iterator<int>(cin), istream_iterator<int>(),
     ostream_iterator<int>(cout));

Index