## Chapter 24 - Standard Template Library - Iterators and Algorithms

## Chapter Goals

- To understand how iterators generalize the idea of pointers
- To learn the various categories of iterators and the operations they provide
- To understand functions, generators, and predicates and how these can be generalized using function objects
- To explore the library of generic algorithms
- To learn how generic algorithms can be extended through the use of binders, negators, and adapters
- To explore how stream iterators can be used to permit generic algorithms to work with external files

## 24.1 Loose Coupling Produces a Strong Library

- Coupling - the degree to which one function or class depends upon another (sect. 13.4)
- Loose coupling - eliminating interconnections
- Programs are more flexible, portable, and robust
- STL is an excellent example

## 24.1 Loose Coupling Produces a Strong Library (cont.)

- Containers and algorithms know nothing about each other
- Reduces size of interfaces
- Containers provide iterators
- Algorithms only know iterators, not containers
- Generalized through template parameters
- Specialization done at compile time, not run time

## 24.2 Iterators

- Cycle through elements of a container (chptr. 16)
- Support same operations as pointers
- Sometimes are pointers
- `*` operator dereferences iterator:

  > `vector<int>::iterator p = a_vector.begin();
  > cout << *p << "\n";`

## 24.2 Iterators (cont.)

- 2 iterators describe a region in memory
- Region can be entire collection, or a (contiguous) subset
- Ending iterator not considered part of the region

- Just a marker for the end
- Do not attempt to access! Not checked

- Containers need not occupy contiguous memory
- `begin` returns starting iterator (all containers)
- `end` returns a past-the-end iterator

## 24.2 Iterators (cont.)

- A loop is often used to iterate over a range
- `operator++` moves iterator to next element
- Use `==` and `!=` to check iterator:

  >     container C;
  >     . . .
  >     container::iterator p=C.begin(), q=C.end();

  >     while (p != q)
  >     {
  >        cout << *p << "\n";
  >        ++p;
  >     }

- Idiom works for any container

## 24.2.1 Varieties of Iterators

- Some can move backwards (`operator--`)
- Some provide random access
- Some can inspect, but not change, elements
- Not all containers support all iterators
- Table (next slide) lists categories and their supported operations

## 24.2.1 Varieties of Iterators - Table

Iterators | Operations
--- | ---
Input Iterator | ==, !=, ++, and * (only for returning a value)
Output Iterator | ==, !=, ++, and * (only for assignment)
Forward Iterator | ==, !=, ++, and *
Bidirectional Iterator | ==, !=, ++, --, and *
Random Access Iterator | ==, !=, ++, --, [], *, as well as iter + n and iter - iter

## 24.3 Functions, Generators, and Predicates

- Many algorithms require functions as arguments
- E.g., `for_each` takes 2 template arguments:
  1. The type of iterator
  2. The function type

  >     template<typename Iterator, typename Action>
  >     void for_each(Iterator current, Iterator stop,
  >           Action action)
  >     {
  >        while (current != stop)
  >        {
  >           action(*current);
  >           ++current;
  >        }
  >     }

## 24.3 Functions, Generators, and Predicates (cont.)

- Using `for_each` to print each element in a list
- Each value is passed, in turn, to `print_element`

  >     void print_element(int value)
  >     {
  >        cout << value << "\n";
  >     }

  >     list<int> a_list;
  >     . . .
  >     for_each(a_list.begin(), a_list.end(), print_element);

## 24.3.1 Predicates

- A function that has no side-effects and returns true/false
- Often created using function objects

  >     bool is_even(int val)
  >     {
  >        return 0 == val % 2;
  >     }

## 24.3.1 Predicates (cont.)

>     bool is_leap_year(int year)
>     {
>           // Every 400 years is a leap year
>        if (0 == year % 400) return true;
>           // Otherwise centuries are not
>        if (0 == year % 100) return false;
>           // Every fourth year is
>        if (0 == year % 4) return true;
>        return false; // Otherwise not
>     }

## 24.3.1 Predicates (cont.)

- `std::find_if` like `find`, but takes a predicate
- Returns iterator to first found element
- Returns 2nd argument if not found

>     list<int>::iterator first_leap =find_if(a_list.begin(),
>        a_list.end(), is_leap_year);
>     if (first_leap != a_list.end()) . . . // Found it

## 24.3.2 Generators

- Takes no arguments, returns a value
- `rand` the most common (sect. 7.9)
- `generate` uses a generator, replaces each element in a sequence with a new value:

  > `vector<int> a(10);
  > generate(a.begin(), a.end(), rand);`

## 24.3.2 Generators (cont.)

- Fill sequence with random ints from 1 to 100:

  >     int rand_one_hundred()
  >     {
  >        return 1 + rand() % 100;
  >     }

  >     vector<int> b(50);
  >     generate(b.begin(), b.end(), rand_one_hundred);

## 24.3.3 Function Objects

- Instance of a class that defines the function call operator
- Same syntax as an ordinary function
- Reasons to use:
  - Stored in a variable
  - Passed as an argument
  - Returned from a function
  - Can carry state

## 24.3.3 Function Objects (cont.)

- Generalize `rand_one_hundred`
- Return values between `a` and `b`, not known until run time
- Create function objects, initialized w/the bounds:

  >     class RandomInt
  >     {
  >     public:
  >        RandomInt(int ia, int ib);
  >        int operator()();
  >     private:
  >        int a, b;
  >     };

## 24.3.3 Function Objects (cont.)

>     RandomInt::RandomInt(int ia, int ib)
>     {
>        a = ia;
>        b = ib;
>     }

>     inline int RandomInt::operator()()
>     {
>        return a + rand() % (b - a + 1);
>     }

## 24.3.3 Function Objects (cont.)

- Instantiate as needed:

  > `RandomInt r10(1,10);`

- Invoke function call operator to get random numbers in range:

  > `cout << r10() << "\n";`

## 24.3.3 Function Objects (cont.)

- Use object to fill vector:

  > `vector<int> b(20);
  > generate(b.begin(), b.end(), r10);`

- Often created as unnamed temporary:

  > `generate(b.begin(), b.end(), RandomInt(1, 10));`

## 24.3.3 Function Objects (cont.)

- Predicates often written as function objects
- Generalize `even` to divisible-by-n:

  >     class DivisibleBy {
  >     public:
  >        DivisibleBy(int in);
  >        bool operator()(int x);
  >     private:
  >        int n;
  >     };

  >     DivisibleBy::DivisibleBy(int in) : n(in) {}

  >     inline bool DivisibleBy::operator()(int x)
  >     { return 0 == x % n; }

## 24.3.3 Function Objects (cont.)

- Instantiate for each different divisor needed:

  >     list<int> a_list;
  >     . . .
  >     list<int>::iterator current = a_list.begin();
  >     DivisibleBy pred(*current); // Create the predicate
  >     ++current; // Advance to next element
  >     list<int>::iterator ele =
  >        find_if(current, a_list.end(), pred);
  >     if (ele != a_list.end()) // Found it

## 24.3.3 Function Objects (cont.)

- Use when each invocation must remember state set by earlier invocation
- To produce a sequence:

  >     class SequenceGenerator {
  >     public:
  >           // Can set starting value
  >        SequenceGenerator(int sv);
  >        int operator()();
  >     private:
  >        int current;
  >     };

  >     SequenceGenerator::SequenceGenerator(int sv)
  >     { current = sv; }

## 24.3.3 Function Objects (cont.)

>     inline int SequenceGenerator::operator()()
>     {
>        int r = current;
>        current++;
>        return r;
>     }

- Init vector w/values 1 to 20:

  > `vector<int> a(20); // Declare a new vector
  > generator(a.begin(), a.end(), SequenceGenerator(1)); // Initialize it`

- More STL function objects in sect. 24.7

## 24.4 Generic Algorithms

- Generalized to operate on a wide variety of containers
- Templates and iterators are key:
  - Templates allow different types
  - Iterators build an abstraction layer into containers
- Iterator type often template argument (recall `for_each`)
- Element type implied by iterator type

## 24.4 Generic Algorithms (cont.)

- Common algorithms presented in 4 categories:
  1. Initialize (`generate`)
  2. Transform
  3. Search (`find`, `find_if`)
  4. Remove

## 24.4.1 Initialization Algorithms

- To initialize a container
  - fill - init w/a single fixed value
  - copy - duplicate values from another container
  - generate - execute a function for each element

## 24.4.1 Initialization Algorithms - `fill`

- Two algorithms to fill a container:
  1. Given a range and a value:

     > `vector a(10);
     > fill(a.begin(), a.end(), 1);`

  2. Given a start, a count, and a value:

     > `fill_n(a.begin(), 5, 2);`

- These reassign existing elements in a container

## 24.4.1 Initialization Algorithms - `copy`

- `copy` from one collection into another
  - 1st two arguments delimit range to be copied
  - 3rd argument starts the destination range
  - Sufficient space is assumed

    > `vector<int> b(20);
    > copy(a.begin(), a.end(), b.begin());
    > // Will initialize first 10 positions of b`

## 24.4.1 Initialization Algorithms - `generate`

- Already seen `generate`:

  > `vector c(20);
  > generate(c.begin(), c.end(), RandomInt(50, 75));
  > generate_n(c.begin(), 10, RandomInt(10, 20)); // Overwrite first 10 positions`

- There is no `copy_n`
- Utility of initializers extended by inserters (sect. 24.5)

## 24.4.2 Transformations

- Transform a sequence into a new sequence
- Some change sequence in place (`reverse`)
- Others produce a new sequence (`transform`)

## 24.4.2 Transformations - `sort`

- Provides for rapid searching
- `list` provides sorting method
  - `sort` needs iterator subscripts
  - `list` doesn't support them
- `set` and `map` are already in order, can't be sorted
- To sort `vector`, `deque`, or array:

> `vector<int> a(10);
> // Create list of random numbers
> generate(a.begin(), a.end(), rand);
> sort(a.begin(), a.end()); // Then sort them`

## 24.4.2 Transformations - `reverse`

- `reverse`:

  > `vector<int> a(10);
  > generate(a.begin(), a.end(), SequenceGenerator(1));
  > // Initially 1, 2, . . . 10
  > reverse(a.begin(), a.end());
  > // Now 10, 9, 8, . . . 2, 1`

## 24.4.2 Transformations - `random_shuffle`

- `random_shuffle` - random permutation on elements
- Like a deck of cards
- Uses random access iterators
- Only useful with `vector`, `deque`, array
- E.g., vector might hold `Card`s instead of `int`s:

  > `vector<int> a(10);
  > generate(a.begin(), a.end(), SequenceGenerator(1));
  > // Initially 1, 2, . . . 10
  > random_shuffle(a.begin(), a.end());`

- Can't predict the actual sequence

## 24.4.2 Transformations - `rotate`

- Less common algorithm
- `rotate` rotates a range around a specified point
- Divides sequence into 2 sections, then swaps sections
- E.g., rotate 1..10 around 7:

  > `vector<int> a(10);
  > generate(a.begin(), a.end(), SequenceGenerator(1));
  > vector<int>::iterator rotate_point
  > = find(a.begin(), a.end(), 7);
  > rotate(a.begin(), rotate_point, a.end());`

- Yields

  `7` | `8` | `9` | `10` | `1` | `2` | `3` | `4` | `5` | `6`

## 24.4.2 Transformations - `partition`

- partition - moves all elements satisfying a predicate to one end
- Returns iterator to right-most element in left partition
- E.g., partition 1..10 with `is_even`

  > `vector<int> a(10);
  > generate(a.begin(), a.end(), SequenceGenerator(1));
  > partition(a.begin(), a.end(), is_even);`

- Yields

  `10` | `8` | `6` | `4` | `2` | `3` | `1` | `7` | `5` | `9`

- Relative order not maintained
  - Use `stable_partition` (slower)

## 24.4.2 Transformations - `transform`

- `transform` generates a new sequence
- Takes an existing sequence, a unary function, and a destination
- Applies function to each element in the source
- Assumes target is sufficiently large

## 24.4.2 Transformations - `transform` (cont.)

- E.g., form first 10 squares in `b`:

  >     int square(int n)
  >     {
  >     	return n * n;
  >     }

  >     vector<int> a(10);
  >     generate(a.begin(), a.end(), SequenceGenerator(1));
  >     vector<int> b(10);
  >     transform(a.begin(), a.end(), b.begin(), square);

## 24.4.2 Transformations - `transform` (cont.)

- Second form takes 2 sequences, a binary function, and a destination
- Applies function in pair-wise fashion
- Assumes 2nd sequence has at least as many elements
- Order of sources important (if function is not commutative)
- Target is `c`:

  > `int add(int a, int b)
  > {
  > return a + b;
  > }
  > vector<int> c(10);
  > transform(a.begin(), a.end(), b.begin(), c.begin(), add);`

## 24.4.2 Transformations - `merge`

- `merge` algorithm generalizes `list::merge` to other containers
- Takes 2 sequences to be merged, and a destination
- Optionally, takes a predicate for comparison
- Assumes sources are sorted
- Assumes target is sufficiently large

## 24.4.2 Transformations - `merge (cont.)`

- Merging `a` and `b` into `c`:

  > `vector<int> a(10);
  > vector<int> b(20);
  > generate_n(a.begin(), 10, SequenceGenerator(1));
  > generate_n(b.begin(), 20, SequenceGenerator(1));
  > vector<int> c(30);
  > merge(a.begin(), a.end(), b.begin(), b.end(), c.begin());`

## 24.4.2 Transformations - `next_permutation`

- `next_permutation` works in place
- Permutation is a reordering of values
- Sequence w/n elements has n! permutations
- An ordering can be placed on permutations:
  - Ordered sequence is "first" permutation
  - Sequence in reverse order is "last" permutation
- Returns `false` if there are no more permutations

## 24.4.2 Transformations - `next_permutation` (cont.)

>     vector<int> a(4);
>        // Initialize 1, 2, 3, 4
>     generate(a.begin(), a.end(), SequenceGenerator(1));
>     while (next_permutation(a.begin(), a.end()))
>     {
>        cout << "Output permutation ";
>        vector<int>::iterator p = a.begin();
>        while (p != a.end())
>        {
>           cout << *p << " ";
>           ++p;
>        }
>        cout << "\n";
>     }

## 24.4.3 Searching Algorithms

- Return an iterator to a position
- Return end iterator upon failure

## 24.4.3 Searching Algorithms - `max_element` and `min_element`

###

- Generalize `max` and `min` to collections

  > `vector<int> d(10);
  > // Generate ten random numbers
  > generate(d.begin(), d.end(), rand);
  > // Find largest value
  > vector<int>::iterator mx =
  > max_element(d.begin(), d.end());
  > // Find smallest value
  > vector<int>::iterator mn =
  > min_element(d.begin(), d.end());
  > if (mx != d.end()) // Will fail for empty vector
  > cout << "Largest is " << *mx
  > << " and smallest is " << *mn << "\n";`

## 24.4.3 Searching Algorithms - `find`

- Sequential (linear) search
- Identifies first element that satisfies search condition
- `find` checks for equality w/3rd argument

## 24.4.3 Searching Algorithms - `find` (cont.)

- From last chapter:

  >     void Inventory::receive(Product newp)
  >     {
  >        cout << "Received Shipment of product "
  >           << newp << "\n";
  >        list<int>::iterator we_need =
  >           find(on_order.begin(), on_order.end(), newp.get_id());
  >        if (we_need != on_order.end())
  >        {
  >           cout << "Ship " << newp
  >              << " to fill back order\n";
  >           on_order.erase(we_need);
  >        }
  >        else
  >           on_hand.push_front(newp);
  >     }

## 24.4.3 Searching Algorithms - `find_if`

- Takes a predicate
- Identifies first element that satisfies predicate
- E.g., return the first leap year in a list of years:

  > `list<int> years;
  > . . .
  > list<int>::iterator first_leap =
  > find_if( years.begin(), years.end(), is_leap_year);`

## 24.4.3 Searching Algorithms - `binary_search`, `upper_bound`, `lower_bound`

- Operate on sorted sequences
- `binary_search` returns `true` if key is found
- `lower_bound` returns iterator where key can be inserted
  - The first element larger than or equal to value, or
  - The ending iterator
- `upper_bound` locates the first element strictly larger than the key
- Subrange indicated by these 2 values describes subsequence containing the key

## 24.4.3 Searching Algorithms - `binary_search` (cont.)

>     vector<int> a(20);
>     generate(a.begin(), a.end(), RandomInt(1, 10));
>     sort(a.begin(), a.end());
>     if (binary_search(a.begin(), a.end(), 7))
>     {
>        vector<int>::iterator p
>           = lower_bound(a.begin(), a.end(), 7);
>        vector<int>::iterator q
>           = upper_bound(a.begin(), a.end(), 7);
>        while (p != q)
>        {
>           cout << "found " << *p << "\n";
>           ++p;
>        }
>     }

## 24.4.3 Searching Algorithms (cont.)

- There are algorithms that produce set union, intersection, and difference for sorted sequences
- Other algorithms search for special values:
  - `adjacent_find` - finds first element equal to element immediately following
  - `search` - finds a subsequence in a larger sequence
  - `equal` - returns `true` if corresponding elements in 2 sequences of similar size are equal
  - `mismatch` - takes a pair of similar sequences, returns pair of iterators that indicate the first positions where sequences differ

## 24.4.4 Removal and Replacement Algorithms

- 2 categories of concern:
  - Operate w/a fixed key, or predicate?
  - Work in place, or copy the result?

## 24.4.4 Removal and Replacement Algorithms - `remove_copy`

- `remove_copy` takes a specific value, copies resulting sequence to another container
- Returns an iterator to denote end of new sequence (colored in example)
- Given:

  > `a` | `1` | `2` | `3` | `2` | `4` | `2` | `5` | `6`
  > `b` | `0` | `0` | `0` | `0` | `0` | `0` | `0` | `0`

## 24.4.4 Removal and Replacement Algorithms - `remove_copy` (cont.)

- `remove_copy(a.begin(), a.end(), b.begin(), 2)` copies all values except the 2s:

  > `a` | `1` | `2` | `3` | `2` | `4` | `2` | `5` | `6`
  > `b` | `1` | `3` | `4` | `5` | `6` | `0` | `0` | `0`

- Last 3 elements in `b` untouched
- `b` was not resized (see `erase`, below)

## 24.4.4 Removal and Replacement Algorithms - `remove_copy_if`

- `remove_copy_if` takes a predicate
- `remove_copy_if(a.begin(), a.end(), b.begin(), DivisibleBy(2))` copies all values except those divisible by 2:

  > `a` | `1` | `2` | `3` | `2` | `4` | `2` | `5` | `6`
  > `b` | `1` | `3` | `5` | `0` | `0` | `0` | `0` | `0`

## 24.4.4 Removal and Replacement Algorithms - resizing

- To resize resultant array:

  > `vector<int>::iterator p;
  > p = remove_copy_if(a.begin(), a.end(),
  > b.begin(), DivisibleBy(2));
  > b.erase(p,b.end());`

- `b` is now:

  > `b` | `1` | `3` | `5`

## 24.4.4 Removal and Replacement Algorithms - `remove`

- `remove` just like `remove_copy`, but works in place
- Given:

  > `a` | `1` | `2` | `3` | `2` | `4` | `2` | `5` | `6`

  > `p = remove(a.begin(), a.end(), 2);`

- Yields:

  > `a` | `1` | `3` | `4` | `5` | `6` | `2` | `5` | `6`

## 24.4.4 Removal and Replacement Algorithms - `remove_if`

- Using `remove_if` in the Sieve of Eratosthenes (last chptr.)
  - (Less efficient. For sake of example)
  - (`sieve` on next slide)

  >     void sieve(deque<int>& numbers);

  >     deque<int> a(100);
  >     generate_n(a.begin(), 100, SequenceGenerator(2));
  >     sieve(a);

## 24.4.4 Removal and Replacement Algorithms - `remove_if` (cont.)

>     void sieve(deque<int>& numbers)
>     {
>        if (numbers.empty())
>           return;
>        int n = numbers.front();
>        numbers.pop_front();
>        deque<int>::iterator p = remove_if(numbers.begin(),
>           numbers.end(), DivisibleBy(n));
>        numbers.erase(p, numbers.end());
>        sieve(numbers);
>        numbers.push_front(n);
>     }

## 24.4.4 Removal and Replacement Algorithms - `unique`

- `unique` much like `list::unique`
- Removes successive values from adjacent, equal elements
- 5 1 3 3 3 2 2 5 4 4 becomes 5 1 3 2 5 4
- Sequence need not be sorted
- Unlike `list::unique`, container not resized

  > `list<int>::iterator p =
  > unique(a.begin(), a.end());
  > a.erase(p, a.end());
  > // Remove the remaining values`

- `unique_copy` analogous; copies resultant sequence to different container

## 24.4.4 Removal and Replacement Algorithms - `replace`

- `replace` takes a range, a value to search for, and a new value
- Replaces all occurrences of old value w/new (in range)
- `replace_if` uses predicate to find values to replace
- New value is fixed

  > `vector<int> a(10);
  > generate(a.begin(), a.end(), RandomInt(1, 5));
  > replace(a.begin(), a.end(), 3, 4);
  > replace_if(a.begin(), a.end(), is_even, 0);`

## 24.4.5 Other Algorithms

- `count` counts the occurrences of a particular value in a collection
- `count_if` counts the elements that satisfy the predicate

  > `int three_count = count(a.begin(), a.end(), 3);
  > int even_count = count_if(a.begin(), a.end(), is_even);
  > cout << "number of 3's " << three_count <<
  > " number even " << even_count << "\n";`

## 24.4.5 Other Algorithms (cont.)

- Some numeric algorithms described in `<numeric>`
- `accumulate` (described in sect. 16.5)

  > `list<double> data;
  > double sum = accumulate(data.begin(), data.end(), 0.0);
  > // Now sum contains the sum of the elements in the list`

- Other numeric algorithms include inner products and partial sums of sequences

## 24.5 Inserters

- Algorithms like `fill`, `copy`, or `generate` are normally used to overwrite contents
- inserter is an adapter, wraps iterator
- Inserts values into new locations
- `back_inserter` calls `push_back` when a value is assigned
- Create an empty list `b`, then copy `a` into it:

  > `list<int> b;
  > copy(a.begin(), a.end(), back_inserter(b));`

- `copy` inserts values, not overwrites

## 24.5 Inserters (cont.)

- `front_inserter` same, but uses `push_front`
- (Can't be used w/`vector`)

  > `list<int> c;
  > generate_n(front_inserter(c), 20, RandomInt(2, 10));`

## 24.6 Stream Iterators - Output Stream Iterators

- Another form of iterator adapter
- Converts iterator operations into I/O stream operations
- Assigning to `ostream_iterator` places value in output stream
- To print collection `c`:

  > `copy(c.begin(), c.end(), ostream_iterator(cout));`

- Takes optional 2nd argument, the separator string:

  > `copy(c.begin(), c.end(), ostream_iterator(cout, "\n"));`

## 24.6 Stream Iterators - Output Stream Iterators

- `istream_iterator` is similar
- Examining value causes a new value to be read from the stream
- Default value represents an exhausted stream
- Read values from stdin and copy into list `d`:

  > `list<int> d;
  > copy(istream_iterator<int>(cin),
  > istream_iterator<int>(), back_inserter(d));`

## 24.6 Stream Iterators - Output Stream Iterators

- Combining stream iterators with various algorithms for simple file processing
- E.g., read integers from stdin, filter out even numbers, write to stdout, one per line:

  >     int main()
  >     {
  >        vector<int> x;
  >        copy(istream_iterator<int>(cin),
  >           istream_iterator(), back_inserter(x));
  >        vector<int>::iterator p =
  >           remove_if(x.begin(), x.end(), is_even);
  >        x.erase(p, x.end());
  >        copy(x.begin(), x.end(),
  >           ostream_iterator<int>(cout, "\n"));
  >        return 0;
  >     }

## 24.7 Standard Function Objects, Predicates, and Binders

- Several function objects defined in `<functional>`
- Extend utility of algorithms w/out writing new code
- `less<T>` described last chptr.
- Predicate version of `operator<`
- Provided for all relational operators: `equal_to`, `not_equal_to`, `greater`, `less`, `greater_equal`, `less_equal`
- E.g., create a set in decreasing order:

  > `set<int, greater<int> > new_set;`

## 24.7 Standard Function Objects, Predicates, and Binders (cont.)

- Another group wraps the standard arithmetic operations
- `plus`, `minus`, `multiplies`, `divides`, `modulus`, and `negate`
- Used w/algorithms like `transform`

## 24.7 Standard Function Objects, Predicates, and Binders (cont.)

- E.g., place element-wise sum into a 3rd container:

  > `vector<int> a(100);
  > vector<int> b(100);
  > // Initialize a and b with values
  > vector<int> c(100);
  > transform(a.begin(), a.end(),
  > b.begin(), c.begin(), plus<int>());`

- E.g., use `accumulate` to multiply the product of elements of a vector:

  > `int prod = accumulate(a.begin(), a.end(),
  > 1, times<int>());`

## 24.7 Standard Function Objects, Predicates, and Binders (cont.)

- A needed predicate or function is often a slight variation on an existing one
- I.e., finding a negative value is similar to "less than", w/the 2nd argument bound to 0
- Termed binder, or curry

## 24.7 Standard Function Objects, Predicates, and Binders (cont.)

- 2 binders in C++
  1. `bind1st` takes a binary function and a value, binds that value to the first argument of the input function, producing a unary function
  2. `bind2nd` binds the 2nd argument
- E.g., to search for the first negative number:

  > `list<int>::iterator first_negative =
  > find_if( a.begin(), a.end(),
  > bind2nd(less<int>(), 0) );`

## 24.7 Standard Function Objects, Predicates, and Binders (cont.)

- negator - another category of binder
- `not1` takes a unary predicate, inverts the result
- `not2` takes a binary predicate, inverts the result
- E.g., find the first non-negative number:

  > `list<int>::iterator first_positive =
  > find_if( a.begin(), a.end(),
  > not1( bind2nd( less<int>(), 0 )) );`

## 24.8 Case Study: File Merge Sort

Problem:
  Create a list of all words in a document, removing duplicates
Caveat:
  Document too large to hold in memory
Solution:
  Merge file sort, in 2 phases

## 24.8 Case Study: File Merge Sort (cont.)

### Phase I

1. Decide on unit size that can be held in memory (1,000 words)
2. Read 1,000 words
3. Sort
4. Remove duplicates
5. Write result to temporary file
6. Store filename in queue
7. If more input, goto 1

## 24.8 Case Study: File Merge Sort (cont.)

### Phase II

1. Remove 2 files from queue, open them
2. Merge contents (can be done holding a few elements in memory), writing to new temporary file
3. Delete 2 old files
4. Make another pass over input, removing duplicates
5. Add new file to end of queue
6. If there's more than 1 file on the queue, goto 1
7. Copy final file to stdout

## 24.8 Case Study: File Merge Sort (cont.)

### Notes on implementation - Phase I

- Generator used to initialize a vector of words from stdin
  - Function object `WordGen` written to do this
  - Returns empty string on end of input
- `sort`
- `unique`
- Copy results to temporary file

- temp_name returns temp. file name
- `copy`, with output iterator, to write file

## 24.8 Case Study: File Merge Sort (cont.)

### Notes on implementation - Phase II

- 2 files from `queue` opened
- `merge`
  - 1st 2 iterators are file-input iterators
  - Output is a file-output iterator
- `unique_copy` eliminates duplicates as values are copied to output
- The last file is copied to stdout

## 24.8 Case Study: File Merge Sort (`filesort.cpp`)

## Chapter Summary

1. Iterators are high-level abstractions, serve the same role as pointers, can be applied to a variety of data structures. Each STL container provides a pair of member functions, begin and end, that return a starting and ending iterator.
2. Pairs of iterators can be used to refer to a complete collection of values, or a subportion of a collection.
3. Through the use of iterators, generic algorithms can be made to work with a variety of containers.
4. Many generic algorithms take functions or function objects as argument. A function object is a class that implements the function call operator, and hence can be used in the same manner as a function.

## Chapter Summary (cont.)

5. Some generic algorithms take generators or predicates as arguments. A generator is a function or function object that returns a different value each time it is called. A predicate is a function or function object that returns a Boolean value.
6. A large number of generic algorithms are provided in the standard library. Generic algorithms can be used to initialize a container, transform a collection, search for a value within a container, remove elements from a container, or other tasks.
7. Many algorithms assign values to a container using an iterator. An inserter can be used to replace this action with an insertion into a container. Inserters can use either push_front or push_back insertion.