Generic Algorithms

Generic Algorithm: A type-independent algorithm that operates on sequences through iterators.

Most generic algorithms are defined in:

#include <algorithm>

Numeric algorithms such as accumulate() are defined in:

#include <numeric>

Algorithms normally operate on iterator ranges rather than directly on containers.

std::vector<int> values{
    10,
    20,
    30
};

auto iter =
    std::find(
        values.begin(),
        values.end(),
        20
    );

The algorithm knows only about:

begin iterator
end iterator
element operations

It does not need to know that the underlying container is a vector.

---

10.1 Overview

Most algorithms operate on an iterator range:

[begin, end)

The first iterator refers to the first element.

The second iterator refers one position past the last element.

find()

find(): Searches a range for the first element equal to a specified value.

#include <algorithm>
#include <vector>

std::vector<int> values{
    10,
    20,
    30,
    20
};

auto iter =
    std::find(
        values.begin(),
        values.end(),
        20
    );

If the value is found:

if (iter != values.end())
{
    std::cout << *iter;
}

Output:

20

Search Failure

If no matching value exists, find() returns the second iterator.

auto iter =
    std::find(
        values.begin(),
        values.end(),
        100
    );

if (iter == values.end())
{
    std::cout << "not found\n";
}

Therefore end() can represent both:

• the end of a range
• an unsuccessful search

Algorithms Are Container Independent

The same algorithm can operate on different sequences.

With a vector:

std::vector<int> values{
    1,
    2,
    3
};

auto iter =
    std::find(
        values.begin(),
        values.end(),
        2
    );

With a list:

std::list<int> values{
    1,
    2,
    3
};

auto iter =
    std::find(
        values.begin(),
        values.end(),
        2
    );

With a built-in array:

int values[] = {
    1,
    2,
    3
};

auto iter =
    std::find(
        std::begin(values),
        std::end(values),
        2
    );

The algorithm works because each range provides suitable iterators.

Element Requirements

Algorithms depend on operations provided by the element type.

For example, find() needs equality comparison.

Conceptually:

*iter == value

sort() normally needs ordering.

Conceptually:

a < b

The container itself does not determine these element operations.

Algorithms Do Not Change Container Size

Generic algorithms normally operate through iterators.

They may:

• read elements
• modify element values
• reorder elements

but they do not directly call container operations such as:

push_back()
insert()
erase()

Therefore an algorithm such as unique() does not actually remove container elements.

A container operation is needed when the container size must change.

---

10.2 A First Look at the Algorithms

Generic algorithms can be viewed broadly as:

1. read-only algorithms
2. algorithms that write elements
3. algorithms that reorder elements

1) Read-Only Algorithms

Read-only algorithms examine elements without changing them.

Important examples include:

find()
count()
accumulate()
equal()

find()

std::vector<int> values{
    1,
    2,
    3,
    4
};

auto iter =
    std::find(
        values.cbegin(),
        values.cend(),
        3
    );

Because the algorithm only reads the range, const iterators are appropriate.

count()

count(): Counts elements equal to a given value.

std::vector<int> values{
    1,
    2,
    1,
    3,
    1
};

auto count =
    std::count(
        values.cbegin(),
        values.cend(),
        1
    );

Result:

3

accumulate()

accumulate(): Combines all elements in a range beginning with an initial value.

Required header:

#include <numeric>

Example:

std::vector<int> values{
    1,
    2,
    3,
    4
};

int sum =
    std::accumulate(
        values.cbegin(),
        values.cend(),
        0
    );

Conceptually:

0 + 1 + 2 + 3 + 4

Result:

10

Initial Value Determines the Result Type

The third argument to accumulate() is important.

std::vector<double> values{
    1.5,
    2.5,
    3.5
};

double result =
    std::accumulate(
        values.begin(),
        values.end(),
        0.0
    );

Result:

7.5

Using an integer initial value can cause the accumulation to use an integer result type.

Choose the initial value type carefully.

Accumulating Strings

accumulate() works with any compatible type supporting the required operation.

std::vector<std::string> words{
    "C++",
    " ",
    "Primer"
};

std::string text =
    std::accumulate(
        words.cbegin(),
        words.cend(),
        std::string{}
    );

Result:

C++ Primer

equal()

equal(): Tests whether corresponding elements in two sequences are equal.

std::vector<int> a{
    1,
    2,
    3
};

std::list<int> b{
    1,
    2,
    3
};

bool same =
    std::equal(
        a.cbegin(),
        a.cend(),
        b.cbegin()
    );

Result:

true

The container types do not need to be the same.

When only the beginning of the second range is supplied, that second sequence must contain enough elements.

---

2) Algorithms That Write Container Elements

Algorithms such as fill() and fill_n() modify existing elements.

fill()

fill(): Assigns a value to every element in a range.

std::vector<int> values{
    1,
    2,
    3,
    4
};

std::fill(
    values.begin(),
    values.end(),
    0
);

Result:

0 0 0 0

The number of elements does not change.

Filling Part of a Container

std::vector<int> values{
    1,
    2,
    3,
    4,
    5
};

std::fill(
    values.begin(),
    values.begin() + 3,
    0
);

Result:

0 0 0 4 5

fill_n()

fill_n(): Writes a value a specified number of times beginning at a destination iterator.

std::vector<int> values(10);

std::fill_n(
    values.begin(),
    5,
    1
);

The first five elements become:

1 1 1 1 1

Destination Must Exist

This is invalid:

std::vector<int> values;

// Wrong:
// std::fill_n(
//     values.begin(),
//     10,
//     0
// );

An ordinary iterator cannot create new elements.

back_inserter()

Insert Iterator: An iterator adaptor that inserts elements into a container when values are assigned through it.

back_inserter() creates an iterator that uses push_back().

Required header:

#include <iterator>

Example:

std::vector<int> values;

auto destination =
    std::back_inserter(values);

*destination = 10;
*destination = 20;
*destination = 30;

Result:

10 20 30

fill_n() with back_inserter()

std::vector<int> values;

std::fill_n(
    std::back_inserter(values),
    5,
    10
);

Result:

10 10 10 10 10

The algorithm itself does not enlarge the container.

The insert iterator performs the insertion.

copy()

copy(): Copies an input range to a destination.

std::vector<int> source{
    1,
    2,
    3
};

std::vector<int> destination(
    source.size()
);

std::copy(
    source.cbegin(),
    source.cend(),
    destination.begin()
);

Result:

destination = {1, 2, 3}

copy() with an Insert Iterator

std::vector<int> source{
    1,
    2,
    3
};

std::vector<int> destination;

std::copy(
    source.cbegin(),
    source.cend(),
    std::back_inserter(destination)
);

Result:

1 2 3

replace()

replace(): Changes matching values inside a range.

std::vector<int> values{
    1,
    0,
    2,
    0,
    3
};

std::replace(
    values.begin(),
    values.end(),
    0,
    42
);

Result:

1 42 2 42 3

replace_copy()

replace_copy(): Copies elements to another destination while replacing selected values.

std::vector<int> source{
    1,
    0,
    2,
    0,
    3
};

std::vector<int> destination;

std::replace_copy(
    source.cbegin(),
    source.cend(),
    std::back_inserter(destination),
    0,
    42
);

source remains unchanged.

destination becomes:

1 42 2 42 3

---

3) Algorithms That Reorder Container Elements

Some algorithms rearrange elements in a sequence.

Important examples include:

sort()
unique()

sort()

sort(): Orders elements using < by default.

std::vector<int> values{
    4,
    2,
    5,
    1,
    3
};

std::sort(
    values.begin(),
    values.end()
);

Result:

1 2 3 4 5

unique()

unique(): Rearranges adjacent duplicate elements so that each unique value appears once at the beginning of the range.

std::vector<std::string> words{
    "the",
    "red",
    "fox",
    "the",
    "red"
};

std::sort(
    words.begin(),
    words.end()
);

auto unique_end =
    std::unique(
        words.begin(),
        words.end()
    );

Conceptually:

fox red the | ? ?
            ↑
       unique_end

unique() does not change the size of the container.

Sort-Unique-Erase Pattern

To actually remove duplicates:

std::sort(
    words.begin(),
    words.end()
);

auto unique_end =
    std::unique(
        words.begin(),
        words.end()
    );

words.erase(
    unique_end,
    words.end()
);

Conceptually:

sort
  ↓
equal elements become adjacent
  ↓
unique
  ↓
duplicates moved outside logical range
  ↓
erase
  ↓
container size reduced

---

10.3 Customizing Operations

Many algorithms allow the default operation to be replaced by a callable object.

Callable objects include:

• functions
• function pointers
• lambdas
• class objects with operator()

1) Passing a Function to an Algorithm

Predicate: A callable whose result can be used as a condition.

Unary Predicate: Takes one argument.

Binary Predicate: Takes two arguments.

Custom Comparator

Suppose strings should be sorted by length.

bool is_shorter(
    const std::string& a,
    const std::string& b)
{
    return
        a.size()
        < b.size();
}

Pass it to sort():

std::sort(
    words.begin(),
    words.end(),
    is_shorter
);

The algorithm now compares elements by length.

stable_sort()

stable_sort(): Sorts elements while preserving the original relative order of equivalent elements.

std::stable_sort(
    words.begin(),
    words.end(),
    is_shorter
);

This is useful when equal-length words should keep their previous ordering.

---

2) Lambda Expressions

Lambda Expression: An unnamed callable expression.

General form:

[capture_list]
(parameter_list)
-> return_type
{
    function_body
}

Simple example:

auto add =
    [](int a, int b)
    {
        return a + b;
    };

int result =
    add(10, 20);

Result:

30

Lambda as a Comparator

std::stable_sort(
    words.begin(),
    words.end(),
    [](const std::string& a,
       const std::string& b)
    {
        return
            a.size()
            < b.size();
    }
);

Capture List

A lambda can use local variables from its enclosing function only when they are captured.

std::size_t minimum_size = 5;

auto predicate =
    [minimum_size](
        const std::string& word)
    {
        return
            word.size()
            >= minimum_size;
    };

Empty Capture

[](const std::string& word)
{
    return word.empty();
}

An empty capture list prevents access to local non-static variables in the surrounding function.

find_if()

find_if(): Returns the first element for which a predicate is true.

std::size_t minimum_size = 5;

auto iter =
    std::find_if(
        words.begin(),
        words.end(),
        [minimum_size](
            const std::string& word)
        {
            return
                word.size()
                >= minimum_size;
        }
    );

for_each()

for_each(): Calls a callable for each element in a range.

std::for_each(
    words.begin(),
    words.end(),
    [](const std::string& word)
    {
        std::cout
            << word
            << ' ';
    }
);

---

3) Lambda Captures and Returns

Each lambda expression creates a unique unnamed closure type.

Captured variables become state stored in the lambda object.

Capture by Value

int value = 42;

auto lambda =
    [value]()
    {
        return value;
    };

value = 0;

int result =
    lambda();

Result:

42

The original value was copied when the lambda object was created.

Capture by Reference

int value = 42;

auto lambda =
    [&value]()
    {
        return value;
    };

value = 0;

int result =
    lambda();

Result:

0

The lambda refers to the original object.

Reference Lifetime

Captured references must remain valid while the lambda can use them.

Avoid returning a lambda that contains references to destroyed local variables.

Implicit Captures

Capture	Meaning
[]	Capture nothing
[x]	Capture x by value
[&x]	Capture x by reference
[=]	Capture used local variables by value
[&]	Capture used local variables by reference
[&, x]	Default reference, x by value
[=, &x]	Default value, x by reference

Mutable Lambdas

Variables captured by value cannot normally be modified inside the lambda.

Use mutable to modify the lambda's private copy.

int value = 10;

auto lambda =
    [value]() mutable
    {
        ++value;

        return value;
    };

Calls:

std::cout << lambda() << '\n';
std::cout << lambda() << '\n';

Output:

11
12

The original value remains 10.

Lambda Return Type

The compiler can often infer the return type.

auto square =
    [](int value)
    {
        return
            value * value;
    };

An explicit trailing return type can also be used.

auto absolute =
    [](int value)
    -> int
    {
        if (value < 0)
        {
            return -value;
        }

        return value;
    };

transform()

transform(): Applies a callable to each element and writes the result to a destination.

std::vector<int> source{
    -1,
    2,
    -3
};

std::vector<int> destination;

std::transform(
    source.begin(),
    source.end(),
    std::back_inserter(destination),
    [](int value)
    {
        return
            value < 0
            ? -value
            : value;
    }
);

Result:

1 2 3

---

4) Binding Arguments

bind(): Creates a new callable by binding or rearranging arguments of another callable.

Required header:

#include <functional>

Suppose:

bool check_size(
    const std::string& word,
    std::size_t size)
{
    return
        word.size()
        >= size;
}

find_if() needs a unary predicate.

Bind the second argument:

auto predicate =
    std::bind(
        check_size,
        std::placeholders::_1,
        5
    );

Conceptually:

predicate(word)

becomes:

check_size(
    word,
    5
);

Placeholders

Placeholders are defined in:

std::placeholders

Common names include:

_1
_2
_3
...

Reordering Arguments

bool compare(
    int a,
    int b)
{
    return a < b;
}

Normal order:

auto normal =
    std::bind(
        compare,
        std::placeholders::_1,
        std::placeholders::_2
    );

Reversed order:

auto reversed =
    std::bind(
        compare,
        std::placeholders::_2,
        std::placeholders::_1
    );

ref() and cref()

Arguments bound directly by bind() are normally stored by value.

Use:

std::ref(object)

to preserve reference semantics.

Use:

std::cref(object)

for reference-to-const semantics.

---

10.4 Revisiting Iterators

Important specialized iterator types include:

• insert iterators
• stream iterators
• reverse iterators
• move iterators

1) Insert Iterators

Insert iterators convert assignment into container insertion.

Inserter	Operation
back_inserter(c)	c.push_back()
front_inserter(c)	c.push_front()
inserter(c, p)	c.insert() before p

back_inserter()

std::vector<int> source{
    1,
    2,
    3
};

std::vector<int> destination;

std::copy(
    source.begin(),
    source.end(),
    std::back_inserter(destination)
);

Result:

1 2 3

front_inserter()

std::list<int> source{
    1,
    2,
    3,
    4
};

std::list<int> destination;

std::copy(
    source.begin(),
    source.end(),
    std::front_inserter(destination)
);

Result:

4 3 2 1

Repeated front insertion reverses insertion order.

inserter()

std::list<int> source{
    1,
    2,
    3,
    4
};

std::list<int> destination;

std::copy(
    source.begin(),
    source.end(),
    std::inserter(
        destination,
        destination.begin()
    )
);

Result:

1 2 3 4

---

2) iostream Iterators

istream_iterator: Reads values from an input stream using >>.

ostream_iterator: Writes values to an output stream using <<.

Required header:

#include <iterator>

istream_iterator

std::istream_iterator<int>
    input(std::cin);

std::istream_iterator<int>
    end;

The default-constructed iterator represents the end state.

Reading into a Container

std::istream_iterator<int>
    input(std::cin);

std::istream_iterator<int>
    end;

std::vector<int> values(
    input,
    end
);

Input:

10 20 30

followed by end-of-file creates:

10 20 30

in the vector.

accumulate() Directly from Input

std::istream_iterator<int>
    input(std::cin);

std::istream_iterator<int>
    end;

int sum =
    std::accumulate(
        input,
        end,
        0
    );

Input:

10 20 30

Result:

60

ostream_iterator

std::ostream_iterator<int>
    output(
        std::cout,
        " "
    );

output = 10;
output = 20;

Output:

10 20

Copying Directly to Output

std::vector<int> values{
    10,
    20,
    30
};

std::copy(
    values.begin(),
    values.end(),
    std::ostream_iterator<int>(
        std::cout,
        " "
    )
);

Output:

10 20 30

---

3) Reverse Iterators

Reverse Iterator: Traverses a sequence from the end toward the beginning.

std::vector<int> values{
    1,
    2,
    3,
    4
};

for (
    auto iter =
        values.rbegin();
    iter != values.rend();
    ++iter)
{
    std::cout
        << *iter
        << ' ';
}

Output:

4 3 2 1

For reverse iterators:

++ moves toward the beginning

Sorting in Reverse Order

std::vector<int> values{
    3,
    1,
    4,
    2
};

std::sort(
    values.rbegin(),
    values.rend()
);

Result:

4 3 2 1

base()

base() returns the corresponding ordinary iterator.

auto ordinary =
    reverse_iter.base();

The positions are offset by one because reverse and ordinary iterators refer to the sequence in opposite directions.

---

10.5 Structure of Generic Algorithms

Algorithms differ in the minimum operations required from their iterators.

1) The Five Iterator Categories

Category	Capability
Input Iterator	Read, single-pass, forward
Output Iterator	Write, single-pass, forward
Forward Iterator	Read/write, multi-pass, forward
Bidirectional Iterator	Forward operations plus backward movement
Random-Access Iterator	Full iterator arithmetic and random access

Input Iterator

Typical operations include:

*iter
iter->member
++iter
iter++
iter1 == iter2
iter1 != iter2

Example:

std::istream_iterator<int>

Output Iterator

Typical operations include:

*iter = value;
++iter;

Examples include:

std::ostream_iterator<int>
std::back_insert_iterator<std::vector<int>>

Forward Iterator

Supports repeated traversal while moving only forward.

forward_list provides forward iterators.

std::forward_list<int> values;

Supported:

++iter;

Not supported:

// --iter;

Bidirectional Iterator

Adds backward movement.

++iter;
--iter;

list provides bidirectional iterators.

Random-Access Iterator

Adds operations such as:

iter + n
iter - n
iter1 - iter2
iter[n]
iter1 < iter2

Containers providing random-access iterators include:

vector
deque
array
string

sort() Requirement

std::sort() requires random-access iterators.

This works:

std::vector<int> values;

std::sort(
    values.begin(),
    values.end()
);

This does not:

std::list<int> values;

// Error:
// std::sort(
//     values.begin(),
//     values.end()
// );

Use:

values.sort();

instead.

---

2) Algorithm Parameter Patterns

Generic algorithms commonly use a few standard parameter forms.

One Input Range

algorithm(
    begin,
    end,
    other_arguments
);

Example:

std::find(
    values.begin(),
    values.end(),
    10
);

Input Range and Destination

algorithm(
    begin,
    end,
    destination,
    other_arguments
);

Example:

std::copy(
    source.begin(),
    source.end(),
    destination.begin()
);

Input Range and Second Sequence

algorithm(
    begin,
    end,
    begin2,
    other_arguments
);

Example:

std::equal(
    a.begin(),
    a.end(),
    b.begin()
);

When only begin2 is supplied, the second sequence must contain enough elements.

Destination Capacity

A normal destination iterator requires existing storage.

std::copy(
    source.begin(),
    source.end(),
    destination.begin()
);

If the destination should grow:

std::copy(
    source.begin(),
    source.end(),
    std::back_inserter(
        destination
    )
);

Stream Destination

std::copy(
    values.begin(),
    values.end(),
    std::ostream_iterator<int>(
        std::cout,
        " "
    )
);

A destination iterator does not have to refer to a container.

---

3) Algorithm Naming Conventions

The standard library uses several naming patterns.

Predicate Versions

Some algorithms provide overloads accepting predicates.

std::sort(
    begin,
    end
);

and:

std::sort(
    begin,
    end,
    comparator
);

_if Versions

std::find(
    begin,
    end,
    value
);

finds a value.

std::find_if(
    begin,
    end,
    predicate
);

finds an element satisfying a predicate.

_copy Versions

std::reverse(
    begin,
    end
);

modifies the original range.

std::reverse_copy(
    begin,
    end,
    destination
);

writes the reversed result elsewhere.

Combined Suffixes

Some algorithm families provide forms conceptually like:

operation
operation_if
operation_copy
operation_copy_if

The suffix indicates how the algorithm behaves.

---

10.6 Container-Specific Algorithms

list and forward_list provide specialized member algorithms.

They are useful because linked lists do not provide random-access iterators, and link manipulation can often perform operations efficiently.

Important list operations include:

Operation	Meaning
sort()	Sort list
merge()	Merge sorted lists
remove()	Remove matching values
remove_if()	Remove elements matching predicate
reverse()	Reverse list
unique()	Remove consecutive duplicates
splice()	Transfer elements between lists

list::sort()

std::list<int> values{
    4,
    1,
    3,
    2
};

values.sort();

Result:

1 2 3 4

Use the list-specific member because generic std::sort() requires random-access iterators.

list::remove()

std::list<int> values{
    1,
    2,
    1,
    3,
    1
};

values.remove(1);

Result:

2 3

The list member actually removes matching nodes.

list::remove_if()

std::list<int> values{
    1,
    2,
    3,
    4,
    5
};

values.remove_if(
    [](int value)
    {
        return
            value % 2 == 0;
    }
);

Result:

1 3 5

list::unique()

std::list<int> values{
    1,
    1,
    2,
    2,
    3
};

values.unique();

Result:

1 2 3

Unlike generic std::unique(), the list member actually removes duplicate nodes.

Only consecutive duplicates are removed.

list::reverse()

std::list<int> values{
    1,
    2,
    3
};

values.reverse();

Result:

3 2 1

list::merge()

Both lists should be sorted according to the same ordering.

std::list<int> a{
    1,
    3,
    5
};

std::list<int> b{
    2,
    4,
    6
};

a.merge(b);

Afterward:

a = {1, 2, 3, 4, 5, 6}
b = {}

Elements are transferred from b into a.

splice()

splice(): Transfers elements from one list into another without copying the elements.

std::list<int> a{
    1,
    2
};

std::list<int> b{
    3,
    4
};

a.splice(
    a.end(),
    b
);

Afterward:

a = {1, 2, 3, 4}
b = {}

Moving One Element with splice()

std::list<int> a{
    1,
    2
};

std::list<int> b{
    3,
    4
};

auto iter =
    b.begin();

a.splice(
    a.end(),
    b,
    iter
);

Afterward:

a = {1, 2, 3}
b = {4}

forward_list::splice_after()

forward_list provides the corresponding operation:

splice_after()

because forward_list expresses modification relative to the position before an element.

Generic vs. List-Specific Operations

A crucial distinction is:

generic algorithms
    normally operate on values
    and do not directly change container size

list member algorithms
    may directly modify list structure

For example:

auto end =
    std::unique(
        values.begin(),
        values.end()
    );

does not erase elements from an ordinary sequence.

But:

list_values.unique();

actually removes duplicate nodes.

---

Essential Study Checklist

1. Generic algorithms operate on iterator ranges rather than directly on containers.
2. Most generic algorithms are declared in <algorithm>.
3. Numeric algorithms such as accumulate() are declared in <numeric>.
4. Standard ranges use the half-open form [begin, end).
5. find() returns an iterator to the first matching element.
6. If find() fails, it returns the second iterator argument.
7. Algorithms can work with different container types when their iterators satisfy the required operations.
8. Algorithms depend on operations supported by the element type.
9. Generic algorithms normally do not directly add or erase container elements.
10. count() counts elements equal to a value.
11. accumulate() combines elements beginning with an initial value.
12. The initial value passed to accumulate() influences the result type.
13. equal() compares corresponding elements from two sequences.
14. fill() assigns a value to every element in a range.
15. fill_n() writes a value a specified number of times.
16. Ordinary destination iterators require existing destination storage.
17. back_inserter() turns assignment into push_back().
18. Insert iterators let algorithms grow compatible containers.
19. copy() copies an input range to a destination.
20. replace() changes matching values in the original range.
21. replace_copy() writes a modified copy to another destination.
22. sort() orders elements using < by default.
23. unique() removes adjacent duplicates only from the logical range.
24. unique() does not change the container's actual size.
25. Use erase() after unique() when unwanted elements must actually be removed.
26. The sort-unique-erase pattern is a common way to eliminate duplicates.
27. A predicate is a callable whose result is used as a condition.
28. A unary predicate takes one argument.
29. A binary predicate takes two arguments.
30. Algorithms such as sort() can accept custom comparison predicates.
31. stable_sort() preserves the relative order of equivalent elements.
32. A lambda is an unnamed callable expression.
33. A lambda's capture list specifies which enclosing local variables it may use.
34. [x] captures x by value.
35. [&x] captures x by reference.
36. [=] implicitly captures used local variables by value.
37. [&] implicitly captures used local variables by reference.
38. Value captures store copies when the lambda object is created.
39. Reference captures require the referenced objects to remain alive.
40. mutable allows modification of values captured by value.
41. Lambda return types can often be inferred.
42. A trailing return type can explicitly specify a lambda's result type.
43. find_if() finds the first element satisfying a predicate.
44. for_each() invokes a callable for every element in a range.
45. transform() applies a callable and writes the returned results to a destination.
46. bind() creates a new callable from another callable.
47. std::placeholders::_1, _2, and so on represent arguments to the generated callable.
48. bind() can fix argument values or reorder argument positions.
49. std::ref() preserves reference semantics for a bound argument.
50. std::cref() preserves reference-to-const semantics.
51. back_inserter() inserts at the back.
52. front_inserter() inserts at the front and can reverse insertion order.
53. inserter() inserts before a specified iterator position.
54. istream_iterator reads typed values from an input stream.
55. A default-constructed istream_iterator represents the end state.
56. ostream_iterator writes values to an output stream.
57. Stream iterators let algorithms treat IO streams as sequences.
58. Reverse iterators traverse a sequence backward.
59. rbegin() and rend() provide reverse traversal.
60. Incrementing a reverse iterator moves toward the beginning of the underlying sequence.
61. Reverse iterators can be passed to compatible generic algorithms.
62. base() converts a reverse iterator position to its corresponding ordinary iterator.
63. Input iterators support single-pass reading.
64. Output iterators support writing.
65. Forward iterators support multi-pass forward traversal.
66. Bidirectional iterators add backward movement.
67. Random-access iterators add constant-time iterator arithmetic and indexing.
68. vector, deque, array, and string provide random-access iterators.
69. list provides bidirectional iterators.
70. forward_list provides forward iterators.
71. std::sort() requires random-access iterators.
72. list therefore uses its member sort() instead of generic std::sort().
73. Many algorithms follow the parameter form (beg, end, ...).
74. Algorithms that write output often accept a destination iterator.
75. A normal destination iterator assumes sufficient writable storage already exists.
76. Insert iterators can be used when the destination container must grow.
77. Some algorithms accept a second input sequence beginning at beg2.
78. If only beg2 is given, the second sequence must be long enough.
79. _if algorithm variants use predicates.
80. _copy algorithm variants write results to a separate destination.
81. list and forward_list provide specialized member algorithms.
82. list::sort() sorts by manipulating list structure.
83. list::remove() actually removes matching elements.
84. list::remove_if() actually removes elements satisfying a predicate.
85. list::unique() actually removes consecutive duplicate nodes.
86. list::reverse() reverses the list.
87. list::merge() transfers elements from another sorted list.
88. After list::merge(), transferred elements no longer remain in the source list.
89. list::splice() transfers nodes between lists without copying their values.
90. forward_list provides splice_after() for corresponding node-transfer operations.
91. Generic algorithms normally cannot directly change a container's structure.
92. List-specific member algorithms can directly modify the linked-list structure.