# Generic Algorithms

Generic algorthims are template functions that use iterators to do their thing on almost any (qualifying) container. For example:
```template < class InputIterator, class T >
InputIterator find(InputIterator first, InputIterator last,
const T& value) {
while (first != last && *first != value) ++first;
return first;
}
```
There is also often a predicate version which takes a function object argument as well as an iterator type:
```template < class InputIterator, class Predicate >
InputIterator find_if(InputIterator first, InputIterator last,
Predicate pred) {
while (first != last && !pred(*first)) ++first;
return first;
}
```
In addition, mutating operators often have a copy version that does not change the original range but does its job on a new range built from copying the range (using an output iterator). For example:
```template < class InputIterator, class OutputIterator, class T >
OutputIterator replace_copy(InputIterator first,
InputIterator last,
OutputIterator result,
const T& old_value,
const T& new_value) {
while (first != last) {
*result++ = *first == old_value ?
new_value :
*first;	++first; }
return result;
}
```
```

```

# Non-mutating sequence operations

## `for_each()`

• Apply a function to each element in a sequence.

## `find()`

• Find the first matching element in a sequence.
• Also `find_if()`.

## `find_end()`

• Return the last iterator in a matching sequence.

## `find_first_of()`

• Return the first iterator in a matching sequence.

## `adjacent_find()`

• Find two adjacent matching elements.

## `count()`

• Count the number of matching elements.

## `mismatch()`

• Find the first two mismatched elements.

## `equal()`

• Test two sequences for equality.

## `search()`

• Search for a sequence
• Search for equal values.
```

```

# Mutating sequence operations

## `copy()`

• Copies a range of elments to a second range.
• Also `copy_backward()`.

## `swap()`

• Swaps two elements.
• Also `iter_swap` (swaps two elements pointed by iterators).
• Also `swap_ranges` (swaps two ranges).

## `transform()`

• Performs an operation on one or two sequences storing the new result.

## `replace()`

• Replace selected elements in a range.
• Also `replace_copy(), replace_if(), replace_copy_if()`.

## `fill()`

• Fills a range with a specific value.
• Also `fill_n`.

## `generate()`

• Fills a range with a generated value.
• Also `generate_n`.

## `remove()`

• Removes specific values from a range.
• Also `remove_if(), remove_copy(), remove_copy_if`.

## `unique()`

• Eliminates runs of equal values from a range (container must have been sorted).
• Also `unique_if(), unique_copy(), unique_copy_if()`.

## `reverse()`

• Reverses a sequence.
• Also `reverse_copy()`.

## `rotate()`

• Rotates the elements of a sequence.
• Also `rotate_copy()`.

## `random_shuffle()`

• Shuffles a sequence.

## `partition()`

• Divides a range into two partitions (for quicksort).
• Also `stable_partition()`.
```

```

# Sorting and Searching

## `sort()`

• Sorts range using NlogN comparisons.

## `stable_sort()`

• Sorts while preserving relative order of elements.

## `partial_sort()`

• Puts the first N elements in their proper places.
• Also `partial_sort_copy()`.

## `nth_element()`

• Puts elements N in its proper place in the range.

## `lower_bound()`

• Finds the first position where an element can be inserted.

## `upper_bound()`

• Finds the last position where an element can be inserted.

## `equal_range()`

• Returns `lower_bound()` and `upper_bound()`.

## `binary_search()`

• Finds an element in the range.

## `merge()`

• Merges two sorted ranges.
• Also `inplace_merge()` (merges two consecutive ranges).
```

```

```

```

# Heaps

• Heaps are binary trees implemented over other sequence containers.
• heap.right(m) = heap[2m+1]
• heap.left(m) = heap[2m+2]
• heap.parent(k) = heap[k/2]

```

```

```

```

```

```