• 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

• 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

• 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

• 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";

• 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

• 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

• 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

• 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;
     }
  }

• 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);

• 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;
  }

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
}

• 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

• 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);

• 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);

• 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

• 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;
  };

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

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

• Instantiate as needed:

  RandomInt r10(1,10);

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

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

• 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));

• 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; }

• 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

• 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; }

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

• 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

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

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

• 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

• 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

• 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)

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

• 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

• 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

• 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 Cards instead of ints:

  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

• 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

• 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)

• 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

• 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);

• 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);

• 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

• 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());

• 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

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";
}

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

• 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";

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

• 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);
  }

• 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);

• 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

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;
   }
}

• 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

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

• 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

• 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)

• 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

• 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

• 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

• 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);

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);
}

• 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

• 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);

• 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";

• 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

• 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

• 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));

• 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"));

• 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));

• 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;
  }

• 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;

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

• 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>());

• 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

• 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) );

• 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 )) );

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

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

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

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

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

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.

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.