STL Algorithms and Function Objects

"The second major efficiency argument is that all but the most trivial STL algorithms use computer science algorithms that are more sophisticated -- sometimes much more sophisticated -- than anything the average C++ programmer will be able to come up with. It's impossible to beat sort or its kin; the search algorithms for sorted ranges are equally good; and even such mundane tasks as eliminating some objects from contiguous memory containers are more efficiently accomplished using the erase-remove idiom than the loops most programmers come up with."

From the book Effective STL by Scott Meyers

Chapter 18 from the Stroustrup book.

Algorithms

The algorithms of the Standard Template Library are also known as the generic algorithms because they are designed and implemented to work with the standard containers.
Non-modifying Modifying Removing Mutating
for_each, count, count_if, min_element, max_element, find, find_if, search_n, search, find_end, find_first_of, adjacent_find, equal, mismatch, lexicographical_compare for_each, copy, copy_backward, transform, merge, swap_ranges, fill, fill_n, generate, generate_n, replace, replace_if, replace_copy, replace_copy_if remove, remove_if, remove_copy, remove_copy_if, unique, unique_copy reverse, reverse_copy, rotate, rotate_copy, next_permutation, prev_permutation, random_shuffle, partition, stable_partition

Sorting Sorted range Numeric
sort, stable_sort, partial_sort, partial_sort_copy, nth_element, partition, stable_partition, make_heap, push_heap, pop_heap, sort_heap binary_search, includes, lower_bound, upper_bound, equal_range, merge, set_union, set_intersection, set_difference, set_symmetric_difference, inplace_merge accumulate, inner_product, adjacent_difference, partial_sum

Some algorithms come in multiple flavors:

The capabilities of each algorithm depend on the type of iterator it accepts.
  1. InputIterator - Used to read elements; able to compare InputIterators for equality/inequality, increment them using pre/post operator++, dereference them (r-value).
  2. OutputIterator - Used to write elements; similar to InputIterator as l-values.
  3. ForwardIterator - Used to read/write elements but only in one direction (forward). Has all capabilities of InputIterator and OutputIterator as well.
  4. BidirectionalIterator - Used to read/write elements in both directions. Has all capabilities of ForwardIterators as well.
  5. RandomAccessIterator - Has all capabilities of BidirectionalIterator plus random access, comparison operators (<, >, <=, >=), and iterator arithmetic.
To use the generic algorithms, you need to include this header file:
#include <algorithm>
Our trusty Foo class for experimenting:
class Foo
{
  public:
    Foo(int x = 0) {
      x_ = x;
    };

    friend bool operator<(const Foo &lhs, const Foo &rhs);
    friend bool operator==(const Foo &lhs, const Foo &rhs);
    friend std::ostream & operator<<(std::ostream &os, const Foo &foo);

  private:
    int x_;
};

bool operator<(const Foo &lhs, const Foo &rhs)
{
  return lhs.x_ < rhs.x_;
}

bool operator==(const Foo &lhs, const Foo &rhs)
{
  return lhs.x_ == rhs.x_;
}

std::ostream & operator<<(std::ostream &os, const Foo &foo)
{
  return os << foo.x_;
}
Also, our print5 function from before so we can conveniently print any container:
template <typename T>
void print5(const T& v)
{
  typename T::const_iterator iter;
  for (iter = v.begin(); iter != v.end(); ++iter)
    std::cout << *iter << "  ";
  std::cout << std::endl;
}
Some simple examples:
#include <iostream>
#include <vector>
#include <algorithm>

void f1()
{
    // Container of integers and an iterator
  std::vector<int> cont1;
  std::vector<int>::iterator iter;

    // Add some integers
  cont1.push_back(5);
  cont1.push_back(7);
  cont1.push_back(3);
  cont1.push_back(8);
  cont1.push_back(7);
  cont1.push_back(1);

    // Print the container
    // 5  7  3  8  7  1
  print5(cont1); 

    // Find the maximum and print
    // Max: 8
  iter = std::max_element(cont1.begin(), cont1.end());
  std::cout << "Max: " << *iter << std::endl;

    // Find the minimum and print
    // Min: 1
  iter = std::min_element(cont1.begin(), cont1.end());
  std::cout << "Min: " << *iter << std::endl;

    // Find the first occurrence of the value 7  
    // Value 7 found.
  iter = std::find(cont1.begin(), cont1.end(), 7);
  if (iter != cont1.end())
    std::cout << "Value " << *iter << " found." << std::endl;

    // Find the second occurrence of the value 7  
    // Value 7 found.
  iter = std::find(++iter, cont1.end(), 7);
  if (iter != cont1.end())
    std::cout << "Value " << *iter << " found." << std::endl;

    // Reverse the elements and print
    // Reversed:  1  7  8  3  7  5
  std::reverse(cont1.begin(), cont1.end());
  std::cout << "     Reversed:  ";
  print5(cont1); 

    // Sort the elements and print
    // Sorted:  1  3  5  7  7  8
  std::sort(cont1.begin(), cont1.end());  // requires operator<
  std::cout << "       Sorted:  ";
  print5(cont1);

    // Reverse the first 3 and print
    // Reverse 1st 3:  5  3  1  7  7  8
  std::reverse(cont1.begin(), cont1.begin() + 3);
  std::cout << "Reverse 1st 3:  ";
  print5(cont1); 
}
Output:
5  7  3  8  7  1
Max: 8
Min: 1
Value 7 found.
Value 7 found.
     Reversed:  1  7  8  3  7  5
       Sorted:  1  3  5  7  7  8
Reverse 1st 3:  5  3  1  7  7  8
Notes

Algorithms with Multiple Ranges


Example: Comparing two vectors:

void f2()
{
    // Containers of integers
  std::vector<int> cont1, cont2;
  int i, size = 10;

    // Populate both with identical elements
  for (i = 0; i < size; i++)
  {
    cont1.push_back(i);
    cont2.push_back(i);
  }

    // See if the containers are the same (must be same size)
  if ( std::equal(cont1.begin(), cont1.end(), cont2.begin()) )
    std::cout << "cont1 and cont2 are equal" << std::endl;
  else
    std::cout << "cont1 and cont2 are NOT equal" << std::endl;

    // Using the overloaded '==' operator for vectors
  if (cont1 == cont2)
    std::cout << "cont1 and cont2 are equal" << std::endl;
  else
    std::cout << "cont1 and cont2 are NOT equal" << std::endl;

    // Change the first element in cont1
  cont1[0] = 100;

    // See if the containers are the same (must be same size)
  if ( std::equal(cont1.begin(), cont1.end(), cont2.begin()) )
    std::cout << "cont1 and cont2 are equal" << std::endl;
  else
    std::cout << "cont1 and cont2 are NOT equal" << std::endl;
}
Output:
cont1 and cont2 are equal
cont1 and cont2 are equal
cont1 and cont2 are NOT equal
A better (safer) way to check for equality would be something like this:
if ( cont1.size() == cont2.size() &&
     std::equal(cont1.begin(), cont1.end(), cont2.begin()) )


Example: Copying between different containers

void f4()
{
    // List/vector of integers
  std::vector<int> cont1;
  std::list<int> cont2;
  int i, size = 10;

    // Populate 
  for (i = 0; i < size; i++)
    cont1.push_back(i);

    // Make sure there is enough room in the list (elements initialized to 0)
  cont2.resize(cont1.size());

    // Copy all elements from vector to list
  std::copy(cont1.begin(), cont1.end(), cont2.begin());

    // Create a deque same size as list (elements initialized to 0)
  std::deque<int> cont3(cont2.size());

    // Copy all elements from list into deque
  std::copy(cont2.begin(), cont2.end(), cont3.begin());

    // Print the containers
  print5(cont1);
  print5(cont2);
  print5(cont3);

    // See if the containers are the same
  if ( std::equal(cont1.begin(), cont1.end(), cont2.begin()) &&
       std::equal(cont2.begin(), cont2.end(), cont3.begin()) 
     )
    std::cout << "All containers are the same" << std::endl;
  else
    std::cout << "The containers are NOT the same" << std::endl;
  
}
Output:
0  1  2  3  4  5  6  7  8  9
0  1  2  3  4  5  6  7  8  9
0  1  2  3  4  5  6  7  8  9
All containers are the same

Implementing Generic Algorithms

There are 5 categories of iterators we use: Input, Output, Forward, Bidirectional, RandomAccess

Input
(read-only)
Output
(write-only)
Forward
(read/write)
Bidirectional
(read/write)
RandomAccess
(read/write)
iter++
++iter
*iter (r-value)
iter->member
iter1 == iter2
iter1 != iter2
iter++
++iter
*iter (l-value)
iter++
++iter
*iter
iter->member
iter1 = iter2
iter1 == iter2
iter1 != iter2
iter++
++iter
iter--
--iter
*iter
iter->member
iter1 = iter2
iter1 == iter2
iter1 != iter2
iter++             iter1 > iter2
++iter             iter1 < iter2
iter--             iter1 <= iter2
--iter             iter1 >= iter2
*iter              iter + i
iter->member       iter += i
iter1 = iter2      iter - i
iter1 == iter2     iter -= i
iter1 != iter2     iter[i] 
iter1 - iter2

The find algorithm is declared as:

template<typename InputIt, typename T>
  InputIt find(InputIt first, InputIt last, const T& val)

The functionality of the find algorithm is:

... to traverse the range specified comparing each element with val using the equality operator for the corresponding type. The traversal ends when the first match is found. The iterator to the found element is returned. If no match is found, an iterator to last is returned.

Given the declaration and functional description, we can implement a version of this algorithm to deal with this code:

iter = std::find(cont1.begin(), cont1.end(), 7);
One implementation could look like this:
template<typename T1, typename T2>
T1 find(T1 first, T1 last, const T2& val)
{
  while (first != last) 
  {
    if (*first == val)
      return first;
    ++first;
  }
  return first;
}

Commonly, it will be seen like this: (note the template argument InputIt for self-documentation)

template<typename InputIt, typename T>
InputIt find(InputIt first, InputIt last, const T& val)
{
  while (first != last) 
  {
    if (*first == val)
      return first;
    ++first;
  }
  return first;
}
Refer to the simple example above.

Given these declarations, how would you implement the functions? (Obviously, some kind of loop/iteration must occur.)

Function:

  // Replace all occurrences of val with new_val within specified range.
  // There is no return value.
template<typename ForwardIt, typename T>
  void replace(ForwardIt first, ForwardIt last, const T& val, const T& new_val)
Usage:
  // Replaces all occurrences of 3 with 7 in cont1
replace(cont1.begin(), cont1.end(), 3, 7);


Function:

  // Copies elements from specified range into a container starting
  // at position specified by result. Returns iterator to one past
  // the last element copied.
template<typename InputIt, typename OutputIt>
  OutputIt copy(InputIt first, InputIt last, OutputIt result)
Usage:
  // Copies every element from cont1 to cont2
copy(cont1.begin(), cont1.end(), cont2.begin());


Function:

  // Compares each element within the specified range with value and
  // returns the number of elements that match.
template<typename InputIt, typename T>
  int count(InputIt first, InputIt last, const T& val)
Usage:
  // Counts the occurrences of the number 19 in cont1
int count = std::count(cont1.begin(), cont1.end(), 19);


Example implementations:

template<typename ForwardIt, typename T>
void replace(ForwardIt first, ForwardIt last, const T& val, const T& new_val)
{
  while (first != last) 
  {
    if (*first == val)
      *first = new_val;
    ++first;
  }
}
Why does the replace algorithm above use a ForwardIterator?
template<typename InputIt, typename OutputIt>
OutputIt copy(InputIt first, InputIt last, OutputIt result)
{
  while (first != last) 
  {
    *result = *first;
    ++result;
    ++first;
  }
  return result;
}
  1. Why does the copy algorithm above use different iterators? (InputIterator and OutputIterator) Why not just use a ForwardIterator all around?
  2. Do you see why the caller of this algorithm must ensure that the destination has enough space?
template<typename InputIt, typename T>
int count(InputIt first, InputIt last, const T& val)
{
  int result = 0;
  while (first != last) 
  {
    if (*first == val)
      ++result;
    ++first;
  }
  return result;
}
Why does the count algorithm above use an InputIterator?

Technically, the count algorithm is declared/implemented like this:

#include <iterator>

template<typename Input, typename T>
typename iterator_traits<Input>::difference_type count(Input first, Input last, const T& val)
{
  typename iterator_traits<Input>::difference_type result = 0;
  while (first != last) 
  {
    if (*first == val)
      ++result;
    ++first;
  }
  return result;
}
algorithm.h
xutility.h

MSC++ 7.1 version of algorithm.h
MSC++ 7.1 version of xutility.h

Functions as Parameters

Some simple functions:

int NextInt()
{
  static int i = 0;
  return ++i;
}
int RandomInt()
{
  return rand();
}
void TripleByRef(int& value)
{
  value *= 3;
}
int TripleByVal(int value)
{
  return value * 3;
}
bool DivBy6(int value)
{
  return !(value % 6);
}
bool IsEven(int value)
{
  return !(value % 2);
}
Note: DivBy6 and IsEven are called predicates. A predicate is simply a function that returns true or false.

This code uses the functions as parameters to the algorithms: (Notice the lack of any looping or iteration)

void f5()
{
    // Make it easy to switch containers
  typedef std::list<int> ContainerType;

    // Create a container all set to 0: 0  0  0  0  0  0  0  0  0  0
  ContainerType cont1(10);
  std::cout << "Container all set to 0\n";
  print5(cont1);

    // Fill list with the value 5: 5  5  5  5  5  5  5  5  5  5
  std::fill(cont1.begin(), cont1.end(), 5);
  std::cout << "\nContainer all set to 5\n";
  print5(cont1);

    // Fill list with values (1..10): 1  2  3  4  5  6  7  8  9  10
  std::generate(cont1.begin(), cont1.end(), NextInt);
  std::cout << "\nContainer set sequentially from 1 to 10\n";
  print5(cont1);

    // Multiply each element by 3 (incorrect): 1  2  3  4  5  6  7  8  9  10
  std::for_each(cont1.begin(), cont1.end(), TripleByVal);
  std::cout << "\nEach element multiplied by 3 (incorrect)\n";
  print5(cont1);

    // Multiply each element by 3: 3  6  9  12  15  18  21  24  27  30
  std::for_each(cont1.begin(), cont1.end(), TripleByRef);
  std::cout << "\nEach element multiplied by 3\n";
  print5(cont1);

    // Multiply each element by 3: 9  18  27  36  45  54  63  72  81  90
  std::transform(cont1.begin(), cont1.end(), cont1.begin(), TripleByVal);
  std::cout << "\nEach element multiplied by 3 (again)\n";
  print5(cont1);

    // Create another list (same size as first list)
  ContainerType cont2(cont1.size());

    // Count number of even elements: 5
  int count = std::count_if(cont1.begin(), cont1.end(), IsEven);
  std::cout << "\nNumber of even elements: " << count << std::endl;

    // Copy values from list1 to list2 where element not divisible by 6
    // 9  27  45  63  81  0  0  0  0  0
  std::cout << "\nCopy values from list1 to list2 where element not divisible by 6\n";
  std::remove_copy_if(cont1.begin(), cont1.end(), cont2.begin(), DivBy6);
  print5(cont2);

    // Copy values from list1 to list2 where element not divisible by 6
    // and trim the list
    // List1: 9  18  27  36  45  54  63  72  81  90
    // List2: 9  27  45  63  81
  std::cout << "\nCopy values from list1 to list2 where element not divisible by 6 ";
  std::cout << "and trim the list\n";
  cont2.erase(std::remove_copy_if(cont1.begin(), cont1.end(), cont2.begin(), DivBy6), 
              cont2.end());
  std::cout << "List1: ";
  print5(cont1);
  std::cout << "List2: ";
  print5(cont2);
}
Full output:
Container all set to 0
0  0  0  0  0  0  0  0  0  0

Container all set to 5
5  5  5  5  5  5  5  5  5  5

Container set sequentially from 1 to 10
1  2  3  4  5  6  7  8  9  10

Each element multiplied by 3 (incorrect)
1  2  3  4  5  6  7  8  9  10

Each element multiplied by 3
3  6  9  12  15  18  21  24  27  30

Each element multiplied by 3 (again)
9  18  27  36  45  54  63  72  81  90

Number of even elements: 5

Copy values from list1 to list2 where element not divisible by 6
9  27  45  63  81  0  0  0  0  0

Copy values from list1 to list2 where element not divisible by 6 and trim the list
List1: 9  18  27  36  45  54  63  72  81  90
List2: 9  27  45  63  81
Closer look at std::remove

void f6()
{
    // Create vector and populate
  std::vector<int> cont1(10);
  std::generate(cont1.begin(), cont1.end(), NextInt);
  cont1[1] = 50;
  cont1[2] = 50;
  cont1[5] = 50;
  cont1[8] = 50;

    // Print out size and elements: 1  50  50  4  5  50  7  8  50  10
  std::cout << "Size of cont1 is " << cont1.size() << std::endl;
  print5(cont1);

    // Remove all elements that have value of 50.
    // std::remove returns an iterator to the "new" logical end
  std::vector<int>::iterator iter = std::remove(cont1.begin(), cont1.end(), 50);

    // Print out size and elements: 1  4  5  7  8  10  7  8  50  10
  std::cout << "\nSize of cont1 is now " << cont1.size() << std::endl;
  print5(cont1);

    // This will "trim" the container to what we expected
  cont1.erase(iter, cont1.end());

    // Print out size and elements: 1  4  5  7  8  10
  std::cout << "\nSize of cont1 is now " << cont1.size() << std::endl;
  print5(cont1);
}
Output:
Size of cont1 is 10
1  50  50  4  5  50  7  8  50  10

Size of cont1 is now 10
1  4  5  7  8  10  7  8  50  10

Size of cont1 is now 6
1  4  5  7  8  10
A closer look at the modified array:
  1  4  5  7  8  10  7  8  50  10
  ^                  ^            ^
begin             new end     real end
Notes:

It's also important to notice that the remove function returns the new end (or logical end). This is important because it tells the caller where the end of the remaining elements is. Without that return value, the caller would have no way to know where the "good" elements stop.

It is techniques like this that make the STL such an efficient library for all kinds of tasks. You would do well to learn it and use it as much as possible.

Self-check Familiarize yourself with the algorithms above by experimenting with them yourself. Especially fill, for_each, generate, generate_n, and transform. These will come in handy in your daily testing.

More Implementations

Given the example usage below, how would you declare the following algorithms? Declarations
Implementations

Function Objects

The following code doesn't compile. Which of the five commented lines are problematic?
int RandomInt()
{
  return rand();
}

void f10()
{
  char *p;
  int (*pf)();
  Foo foo;      // Foo is a class

  RandomInt();  // legal?
  p();          // legal?
  pf();         // legal?
  Foo();        // legal?
  foo();        // legal?
}
General form of a class that can be used as a function object:
class ClassName
{
  public:
    ReturnType operator()(Parameters)  // can be overloaded
    {
      // implementation
    }
};

Essentially, a function object, or functor, is simply an instance of a class that has implemented the function call operator.

Example: Random integer generation (for values 10 - 99)

FunctionClass
int fRandomInt()
{
  return rand() % 90 + 10;
}
class cRandomInt1
{
  public:
    int operator()() const
    {
      return rand() % 90 + 10;
    }
};
Using the function and object to generate random numbers:

  // Instantiate object
cRandomInt1 random;

  // Call random.operator() 3 times
std::cout << random() << std::endl; // 51
std::cout << random() << std::endl; // 27
std::cout << random() << std::endl; // 44

  // Call global function 3 times
std::cout << fRandomInt() << std::endl; // 50
std::cout << fRandomInt() << std::endl; // 99
std::cout << fRandomInt() << std::endl; // 74
Using the function and object as parameters to algorithms:

void f11()
{
    // Make it easy to switch containers
  typedef std::list<int> ContainerType;

    // Create container all set to 0: 0  0  0  0  0  0  0  0  0  0
  ContainerType cont1(10);

    // Fill list with random values, using function
    // 51  27  44  50  99  74  58  28  62  84
  std::generate(cont1.begin(), cont1.end(), fRandomInt);
  print5(cont1);

    // Fill list with random values, using functor (named function object)
    // 91  34  42  73  32  62  61  96  18  15
  cRandomInt1 rnd;
  std::generate(cont1.begin(), cont1.end(), rnd);
  print5(cont1);

    // Fill list with random values, using functor (unnamed function object)
    // 45  75  71  97  71  51  35  72  67  46
  std::generate(cont1.begin(), cont1.end(), cRandomInt1());
  print5(cont1);

}
Output:
51  27  44  50  99  74  58  28  62  84
91  34  42  73  32  62  61  96  18  15
45  75  71  97  71  51  35  72  67  46
This statement:
std::generate(cont1.begin(), cont1.end(), cRandomInt1());
could be implemented as a template something like this:
template<typename ForwardIt, typename Gen>
void generate(ForwardIt first, ForwardIt last, Gen gen)
{
  while (first != last) 
  {
    *first = gen(); // same as gen.operator()()
    ++first;
  }
}
What exactly causes the code below to fail to compile?
std::generate(cont1.begin(), cont1.end(), 7);
Bonus: What is the meaning of the following code? Is it legal? What is it doing?

std::cout << cRandomInt1()() << std::endl;


A different version of the cRandomInt1 class. This allows the user to initialize the generator with a seed.

class cRandomInt2
{
public:
  cRandomInt2(int seed)
  {
    srand(seed);
  }

  int operator()() const
  {
    return rand() % 90 + 10;
  }
};
Sample program:
void f12()
{
    // Make it easy to switch containers
  typedef std::list<int> ContainerType;

    // Create containers all set to 0: 0  0  0  0  0  0  0  0  0  0
  ContainerType cont1(10);

    // Fill list with random values, using function
    // 51  27  44  50  99  74  58  28  62  84
  std::generate(cont1.begin(), cont1.end(), fRandomInt);
  print5(cont1);

    // Fill list with random values, using class (function object)
    // 45  75  71  97  71  51  35  72  67  46
  std::generate(cont1.begin(), cont1.end(), cRandomInt1());
  print5(cont1);

    // Fill list with random values, using class (function object)
    // 91  34  42  73  32  62  61  96  18  15
  std::generate(cont1.begin(), cont1.end(), cRandomInt1());
  print5(cont1);

    // Fill list with random values, using class (function object)
    // 81  79  42  24  27  36  72  52  36  19
  std::generate(cont1.begin(), cont1.end(), cRandomInt2(10));
  print5(cont1);

    // Fill list with random values, using class (function object)
    // 23  79  83  31  98  55  48  38  52  25
  std::generate(cont1.begin(), cont1.end(), cRandomInt2(20));
  print5(cont1);

    // Fill list with random values, using class (function object)
    // 81  79  42  24  27  36  72  52  36  19
  std::generate(cont1.begin(), cont1.end(), cRandomInt2(10));
  print5(cont1);

    // Fill list with random values, using class (function object)
    // 23  79  83  31  98  55  48  38  52  25
  std::generate(cont1.begin(), cont1.end(), cRandomInt2(20));
  print5(cont1);

    // Fill list with random values, using function
    // 25  11  36  27  58  85  56  53  13  61
  std::generate(cont1.begin(), cont1.end(), fRandomInt);
  print5(cont1);
}
Full output:
51  27  44  50  99  74  58  28  62  84
45  75  71  97  71  51  35  72  67  46
91  34  42  73  32  62  61  96  18  15
81  79  42  24  27  36  72  52  36  19
23  79  83  31  98  55  48  38  52  25
81  79  42  24  27  36  72  52  36  19
23  79  83  31  98  55  48  38  52  25
25  11  36  27  58  85  56  53  13  61

Self-check: Create a class, cRandomInt3, that implements operator() so as to support the code below. The class generates random numbers in a given range (inclusive).

Here's how the class should start:
class cRandomInt3
{
  public:
    cRandomInt3(int min, int max) 
    {
      // code
    }

    int operator()() const
    {
      // code
    }
  private:
    // data members
};
This code should work as described:
void f13()
{
    // Create list all set to 0
  typedef std::list<int> cont1(15);

    // Fill list with random values, using function
    // 2  8  5  1  10  5  9  9  3  5  6  6  2  8  2
  std::generate(cont1.begin(), cont1.end(), cRandomInt3(1, 10));
  print5(cont1);

    // Fill list with random values, using class (function object)
    // 23  5  8  17  2  21  18  2  23  6  6  1  22  10  5
  std::generate(cont1.begin(), cont1.end(), cRandomInt3(0, 25));
  print5(cont1);

    // Fill list with random values, using class (function object)
    // -3  -4  4  5  5  -3  -1  4  2  0  -1  2  0  1  2
  std::generate(cont1.begin(), cont1.end(), cRandomInt3(-5, 5));
  print5(cont1);
}
Note that function objects are not unique to the STL algorithms. They can be used "in the wild":
void f14()
{
  cRandomInt3 rand_int(2, 5);
  for (int i = 0; i < 10; i++)
    std::cout << rand_int() << "  ";
  std::cout << std::endl;
}
Output:
3  5  4  2  3  2  4  4  4  2

More Stateful Objects

The class below returns the next integer when its operator() method is called:
class cNextInt
{
  public:
    cNextInt(int start)
    {
      value_ = start;
    }

    int operator()()
    {
      return value_++;
    }
  private:
    int value_;
};
Sample program:
void f13()
{
    // Make it easy to switch containers
  typedef std::list<int> ContainerType;

    // Create containers all set to 0: 0  0  0  0  0  0  0  0  0  0
  ContainerType cont1(10);

    // Fill list with sequential numbers starting with 0
    // 0  1  2  3  4  5  6  7  8  9
  std::generate(cont1.begin(), cont1.end(), cNextInt(0));
  print5(cont1);

     // Fill list with sequential numbers starting with 10
    // 10  11  12  13  14  15  16  17  18  19
  std::generate(cont1.begin(), cont1.end(), cNextInt(10));
  print5(cont1);

    // Fill list with sequential numbers starting with 67
    // 67  68  69  70  71  72  73  74  75  76
  std::generate(cont1.begin(), cont1.end(), cNextInt(67));
  print5(cont1);

    // Create a NextInt object starting at 100
  cNextInt next(100);

    // Generate numbers from 100
    // 100  101  102  103  104  105  106  107  108  109
  std::generate(cont1.begin(), cont1.end(), next);
  print5(cont1);

    // Generate numbers from 110?
    // 100  101  102  103  104  105  106  107  108  109
  std::generate(cont1.begin(), cont1.end(), next);
  print5(cont1);
}
Output:
0  1  2  3  4  5  6  7  8  9
10  11  12  13  14  15  16  17  18  19
67  68  69  70  71  72  73  74  75  76
100  101  102  103  104  105  106  107  108  109
100  101  102  103  104  105  106  107  108  109
What's the problem with the second call to generate using next?

Declarations

This is an attempt at one solution:

std::generate<ContainerType::iterator, cNextInt&>(cont1.begin(), cont1.end(), next);


Example: Counting occurrences of certain letters in a list of strings.

Given the list of strings below:

  // Convenience
typedef std::list<std::string> ContainerType;

  // Make list, add 5 strings
ContainerType cont1;
cont1.push_back("one");
cont1.push_back("two");
cont1.push_back("three");
cont1.push_back("four");
cont1.push_back("five");
we want to count the occurrences of certain letters in each word. First, we need to create a LetterCounter class to be used as a function object:
class LetterCounter
{
  public:
    LetterCounter(char letter) : letter_(letter), total_(0)  
    { 
    }

      // Counts the number of occurrences of "letter_" in "word"
    void operator()(const std::string& word)
    {
      std::string::size_type pos = 0;
      while ( (pos = word.find(letter_, pos)) != std::string::npos )
      {
        ++total_;
        ++pos;
      }
    }

    int GetTotal() 
    { 
      return total_; 
    }

  private:
    char letter_;
    int total_;
};
First attempt at counting the occurrences of the letter e:
  // Create instance of LetterCounter for counting 'e'
LetterCounter lc1('e');
  
  // Count the occurrences of 'e' and print total: 0
std::for_each(cont1.begin(), cont1.end(), lc1);
std::cout << "Occurrences of e: " << lc1.GetTotal() << std::endl;

Declarations


Another attempt at counting the occurrences of the letter e (passing by reference):

  // Create instance of LetterCounter for counting 'e'
LetterCounter lc2('e');

  // Count the occurrences of 'e' and print total: 4
std::for_each<ContainerType::iterator, LetterCounter&>(cont1.begin(), cont1.end(), lc2);
std::cout << "Occurrences of e: " << lc2.GetTotal() << std::endl;
Supplying explicit types to the templated for_each function worked with the GNU and Borland compilers, but gave a warning with Microsoft's compiler and produced incorrect results.
C:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\INCLUDE\algorithm(32) : warning C4172: returning address of local variable or temporary
        main.cpp(1339) : see reference to function template instantiation '_Fn1 std::for_each,LetterCounter&>(_InIt,_InIt,_Fn1)' being compiled
        with
        [
            _Fn1=LetterCounter &,
            _Mylist=std::_List_val>,
            _InIt=std::_List_iterator>>
        ]  


What about casting instead?

std::for_each(cont1.begin(), cont1.end(), static_cast<LetterCounter &>(lc2));
In the above (casting), my tests showed that the code compiled on all compilers (GNU, Clang, and MS 6.0/7.1), but none of them gave the correct output. The compilers are calling the copy constructor when passing the object to for_each.

Recall the implementation of for_each:

template<typename InputIt, typename Op>
Op for_each(InputIt first, InputIt last, Op op)
{
  while (first != last)
  {
    op(*first);
    ++first;
  }
  return op;
}

Counting the occurrences of the letter o, using the return value of for_each

  // Count the occurrences of 'e' and print total: 3
LetterCounter lc3 = std::for_each(cont1.begin(), cont1.end(), LetterCounter('o'));
std::cout << "Occurrences of o: " << lc3.GetTotal() << std::endl;
Without the temporary:
  // Count the occurrences of 'o' and print total: 3
std::cout << "Occurrences of o: " << std::for_each(cont1.begin(), cont1.end(), LetterCounter('o')).GetTotal() << std::endl;

Predefined Classes for Function Objects

To use the predefined function objects, you need to include this header file:
#include <functional> (Newer version of functional)
A list of predefined function objects: (arithmetic, logic, relational)
Unary function objectsMeaning
logical_not<type>() 
negate<type>()
 
!value
-value
Binary function objectsMeaning
less<type>()           
greater<type>()        
equal_to<type>()       
not_equal_to<type>()   
less_equal<type>()     
greater_equal<type>()  
logical_and<type>()     
logical_or<type>()      
plus<type>()            
minus<type>()           
multiplies<type>()      
divides<type>()         
modulus<type>()
 
lhs < rhs
lhs > rhs
lhs == rhs
lhs != rhs
lhs <= rhs
lhs >= rhs
lhs && rhs
lhs || rhs
lhs + rhs
lhs - rhs
lhs * rhs
lhs / rhs
lhs % rhs
Simple example sorting with greater:
void f17()
{
    // Make it easy to switch containers
  typedef std::list<int> ContainerType;

    // Create container all set to 0
  ContainerType cont1(10);

    // Fill list with random values
    // 51  27  44  50  99  74  58  28  62  84
  std::generate(cont1.begin(), cont1.end(), cRandomInt3(10, 99));
  print5(cont1);

    // Sort using default less than operator
    // 27  28  44  50  51  58  62  74  84  99
  cont1.sort();
  print5(cont1);

    // Sort using greater<int> function object
    // 99  84  74  62  58  51  50  44  28  27
  cont1.sort(std::greater<int>());
  print5(cont1);

}
A sample implementation:

namespace std
{
  template <typename T>
  class greater
  {
    public:
      bool operator()(const T& a, const T &b) const
      {
        return a > b;
      }
  };
}
Using the function object as a named object:
  // Using as a named object
std::greater<double> gr;
bool is_greater = gr(10, 20);
if (is_greater)
  std::cout << "10 is greater than 20\n";
else
  std::cout << "10 is NOT greater than 20\n";
and as an unnamed object:
  // As an unnamed (anonymous) object
if (std::greater<int>()(10, 20))
  std::cout << "10 is greater than 20\n";
else
  std::cout << "10 is NOT greater than 20\n";


An example that adds two containers:

void f18()
{
    // Make it easy to switch containers/types
  typedef int T;
  typedef std::list<T> ContainerType;

    // Create containers all set to 0
  ContainerType cont1(10), cont2(10), cont3(10);

    // Fill lists with random values
    // 20  32  20  36  21  17  18  11  33  15
    // 11  38  10  35  20  36  29  17  32  21
  std::generate(cont1.begin(), cont1.end(), cRandomInt3(10, 40));
  std::generate(cont2.begin(), cont2.end(), cRandomInt3(10, 40));
  print5(cont1);
  print5(cont2);

    // Add cont1,cont2 put in cont3
    // 31  70  30  71  41  53  47  28  65  36
  std::transform(cont1.begin(), cont1.end(), cont2.begin(), cont3.begin(), std::plus<T>());
  print5(cont3);

    // Negate all values
    // -31  -70  -30  -71  -41  -53  -47  -28  -65  -36
  std::transform(cont3.begin(), cont3.end(), cont3.begin(), std::negate<T>());
  print5(cont3);
}
Output:
20  32  20  36  21  17  18  11  33  15
11  38  10  35  20  36  29  17  32  21
31  70  30  71  41  53  47  28  65  36
-31  -70  -30  -71  -41  -53  -47  -28  -65  -36
Note that we can instantiate a function object before-hand:
std::plus<int> add_em_up;
std::transform(cont1.begin(), cont1.end(), cont2.begin(), cont3.begin(), add_em_up);

Self-check: Implement the transform algorithms used above. Note they are different (overloaded).

A more formal implementation for the plus function object:

Using a classUsing a struct
template <typename T>
class plus : public std::binary_function<T, T, T>
{
  public:
    T operator()(const T& lhs, const T& rhs)
    {
      return lhs + rhs;
    }
};
template <typename T>
struct plus : std::binary_function<T, T, T>
{
  T operator()(const T& lhs, const T& rhs)
  {
    return lhs + rhs;
  }
};
An implementation for the base class, binary_function (and unary_function):

For binary functionsFor unary functions
template<class LeftT, class RightT , class ResultT>
struct binary_function 
{
  typedef LeftT first_argument_type;
  typedef RightT second_argument_type;
  typedef ResultT result_type;
};
template<class T, class ResultT>
struct unary_function 
{
  typedef T argument_type;
  typedef ResultT result_type;
};
Upon instantiation (with type int), the plus struct would look something like:
struct plus
{
  typedef int first_argument_type;
  typedef int second_argument_type;
  typedef int result_type;
  
  int operator()(const int& lhs, const int& rhs)
  {
    return lhs + rhs;
  }
};
An implementation for unary negate:
  template<class T>
  struct negate : unary_function<T, T> 
  {
    T operator()(const T& value) const
    {
      return (-value); 
    }
  };
Suppose we modify the function (f18) above to create a container of Foo objects instead of integers:
  // Make it easy to switch containers/types
typedef Foo T;
typedef std::list<T> ContainerType;
Will this work as is or do we need to change something else?

Upon instantiation with Foo, the plus struct would look something like:

struct plus
{
  typedef Foo first_argument_type;
  typedef Foo second_argument_type;
  typedef Foo result_type;
  
  Foo operator()(const Foo& lhs, const Foo& rhs)
  {
    return lhs + rhs;
  }
};
Notes:

Self-check: Implement several of the pre-defined function objects on your own and test them.

Function Adapters

Counting the number of occurrences of a particular value was easy (range and value):
count = std::count(cont1.begin(), cont1.end(), 19);
as is counting the number of even elements (range and predicate):
  count = std::count_if(cont1.begin(), cont1.end(), IsEven);
What about counting the occurrences of values less than 10? Greater than 10? Greater than 12? 13? Any value?

Of course, we can make functions (or function objects):

bool less_than_10(int val)
{
  return val < 10;
}
bool greater_than_10(int val)
{
  return val > 10;
}
bool greater_than_12(int val)
{
  return val > 12;
}
// etc...

or classes for function objects:

// For integers  
class greater_than_x
{
  public:
    greater_than_x(int rhs) : rhs_(rhs) {};
    bool operator()(int value)
    {
      return value > rhs_;
    }
  private:
    int rhs_;
};
// For any type  
template <typename T>
class greater_than_t
{
  public:
    greater_than_t(const T& rhs) : rhs_(rhs) {};
    bool operator()(const T& value)
    {
      return value > rhs_;
    }
  private:
    T rhs_;
};

Using them:

count = std::count_if(cont1.begin(), cont1.end(), less_than_10);
count = std::count_if(cont1.begin(), cont1.end(), greater_than_10);
count = std::count_if(cont1.begin(), cont1.end(), greater_than_12);
count = std::count_if(cont1.begin(), cont1.end(), greater_than_x(3));
count = std::count_if(cont1.begin(), cont1.end(), greater_than_t<int>(5));
// etc...
Obviously, there is a better way: the function adapter.

We'd like somehow to be able to use the greater function object, but its constructor doesn't take any parameters, and more importantly, it's a binary function, meaning it needs to compare two items in its operator() method:

template <typename T>
class greater : public binary_function<T, T, bool> 
{
  public:
    bool operator()(const T& a, const T &b) const
    {
      return a > b;
    }
};
The count_if algorithm is only supplying one parameter, so this:
count = std::count_if(cont1.begin(), cont1.end(), std::less<int>());
will generate an error because std::less::operator() requires 2 parameters. So, essentially, a function adapter is a function that wraps the function object and provides the additional parameters.

Note that a function adapter is a function. (A function object is a class object.)


There are 4 predefined function adapters: (Element is provided by the iterators over the range)

Function AdapterMeaning
bind1st(Op, Value)
bind2nd(Op, Value)
not1(Op)
not2(Op)
Op(Value, Element)
Op(Element, Value)
!Op(Element)
!Op(Element1, Element2)
Using function adapters:
  // Fill lists with random values
  // 2  8  15  1  10  5  19  19  3  5
std::generate(cont1.begin(), cont1.end(), cRandomInt3(1, 20));

  // Count elements < 10: 6
count = std::count_if(cont1.begin(), cont1.end(), std::bind2nd(std::less<int>(), 10));

  // Count elements not < 10: 4
count = std::count_if(cont1.begin(), cont1.end(), std::not1(std::bind2nd(std::less<int>(), 10)));
std::cout << "\nNumber of elements not < 10: " << count << std::endl;

  // Count elements > 10: 3
count = std::count_if(cont1.begin(), cont1.end(), std::bind2nd(std::greater<int>(), 10));

  // Count elements where 10 < element: 3
count = std::count_if(cont1.begin(), cont1.end(), std::bind1st(std::less<int>(), 10));

  // Count elements not > 10: 
count = std::count_if(cont1.begin(), cont1.end(), 
                      std::not1(std::bind2nd(std::greater<int>(), 10)));
Removing the std:: namespace qualifier:
generate(cont1.begin(), cont1.end(), cRandomInt3(1, 20));
count = count_if(cont1.begin(), cont1.end(), bind2nd(less<int>(), 10));
count = count_if(cont1.begin(), cont1.end(), not1(bind2nd(less<int>(), 10)));
count = count_if(cont1.begin(), cont1.end(), bind2nd(greater<int>(), 10));
count = count_if(cont1.begin(), cont1.end(), bind1st(less<int>(), 10));
count = count_if(cont1.begin(), cont1.end(), not1(bind2nd(greater<int>(), 10)));
We can use algorithms and function adapters on their own:

Anonymously:

  // 1. Instantiates an object of the 'less' class for ints
  // 2. Calls 'bind2nd' passing the 'less' object and integer '10'
  // 3. A function object 'temp' (unnamed) is returned from 'bind2nd'
  // 4. temp.operator() is called with integer '12'
  // 5. The return value is a boolean: (12 < 10)?
  // 6. Prints the appropriate message. 
if ( bind2nd(less<int>(), 10)(12) )
  cout << "\n12 is less than 10" << endl;
else
  cout << "\n12 is not less than 10" << endl;
By name:
  // Create a named variable 'LT_10' of type 'binder2nd'
binder2nd<less<int> > LT_10 = bind2nd(less<int>(), 10);

  // Call LT_10.operator() with int '12'
if (LT_10(12))
  cout << "\n12 is less than 10" << endl;
else
  cout << "\n12 is not less than 10" << endl;

More details about function adapters

Self-check: Rewrite the call below to count_if to use only code from the STL. In other words, remove the IsEven function pointer and replace it with function adapters and pre-defined function objects. (All of the functionality you need is already present in the STL.)

  count = std::count_if(cont1.begin(), cont1.end(), IsEven);

Calling Member Functions

Suppose we add a couple of methods to our Foo class:
  // print out the value of x_
void Foo::print() const {
  std::cout << x_;
}

  // print out the value of x_ padded with spaces
void Foo::printpad (int width) const {
  std::cout << std::setw(width) << x_;
}
To print a list of Foo elements, how would we do it? Given:

  // Create containers all set to 0
std::list<Foo> cont1(10);

  // Fill lists with random values
  // 2  8  15  1  10  5  19  19  3  5
std::generate(cont1.begin(), cont1.end(), cRandomInt3(1, 20));
"Old-style" method using a loop:

std::list<Foo>::const_iterator it;

  // 28151105191935
for (it = cont1.begin(); it != cont1.end(); ++it)
  it->print();

  //   2  8 15  1 10  5 19 19  3  5
for (it = cont1.begin(); it != cont1.end(); ++it)
  it->printpad(3);
Of course, we want to use the generic algorithms so we do this:

std::for_each(cont1.begin(), cont1.end(), Foo::print); // Compiler error
Depending on your compiler, you would get something similar to these error messages:

MS:      term does not evaluate to a function
GNU:     pointer to member function called, but not in class scope
Borland: Call of nonfunction
The for_each generic algorithm.

Member Functions vs. Ordinary Functions

Member functionOrdinary function
int Foo::member_func()
{
  return 0;
}
int ordinary_func()
{
  return 0;
}
Examples:
void f21()
{
    // pointer to function
  int (*pof)() = ordinary_func;

    // pointer to member function (& is required)
  int (Foo::*pmf)() = &Foo::member_func;

  Foo fobj;       // Create a Foo object
  Foo *pfobj;     // Pointer to Foo object
  pfobj = &fobj;  // Assign address of fobj to pfobj

  ordinary_func();     // "ordinary" function call
  pof();               // call ordinary function through pointer

  fobj.member_func();  // call member function through object
  pfobj->member_func();// call member function through pointer to object

  pmf();               // Error, pmf is not a function or pointer to function
  (fobj.*pmf)();       // call member function with pointer to member and object
  (pfobj->*pmf)();     // call member function with pointer to member and ptr to object
}

We need to use a function adapter designed for member functions:

Function AdapterMeaning
mem_fun_ref(Op)
mem_fun(Op)
Calls a method on an object: e.g. Object.*Op()
Calls a method on a pointer: e.g. pObject->*Op()
This will work as expected (Reminder: There is a conversion between integer and Foo):
  // Create containers all set to 0
std::list<Foo> cont1(10);

  // Fill lists with random values: 2  8  15  1  10  5  19  19  3  5
std::generate(cont1.begin(), cont1.end(), cRandomInt3(1, 20));
print5(cont1);

  // Print all elements: 28151105191935
std::for_each(cont1.begin(), cont1.end(), std::mem_fun_ref(&Foo::print));
Of course, we can declare the variable on its own as well:
void (Foo::*foo_print)() const = &Foo::print;
std::for_each(cont1.begin(), cont1.end(), std::mem_fun_ref(foo_print));
What about calling this method that requires a parameter?
  // print out the value of x_ with spaces
void printpad (int width) const {
  std::cout << std::setw(width) << x_;
Use another function adapter:
// Print all elements:    2    8   15    1   10    5   19   19    3    5
std::for_each(cont1.begin(), cont1.end(), 
              std::bind2nd(std::mem_fun_ref(&Foo::printpad), 5));

Using Ordinary Functions with Adapters

Counting the number of elements divisible by 6:
int count = std::count_if(cont1.begin(), cont1.end(), DivBy6);
Counting the number of elements NOT divisible by 6:
  // Compiler error
int count = std::count_if(cont1.begin(), cont1.end(), std::not1(DivBy6));
The problem is that DivBy6 is not a function object. It's an ordinary function, which has limited use.

Of course, there's yet another function adapter to handle this situation.

Function AdapterMeaning
ptr_fun(Op)
*Op(Element)
*Op(Element1, Element2)
This leads to this correct version:
int count = std::count_if(cont1.begin(), cont1.end(), std::not1(std::ptr_fun(DivBy6)));
Full example:
void f22()
{
    // Create containers all set to 0
  std::list<int> cont1(10);

    // Fill lists with random values between 1 and 30
    // 12  18  5  11  30  5  19  19  23  15
  std::generate(cont1.begin(), cont1.end(), cRandomInt3(1, 30));
  print5(cont1);

    // Count elements divisible by 6: 3
  int count = std::count_if(cont1.begin(), cont1.end(), DivBy6);
  std::cout << "\nNumber of elements divisible by 6: " << count << std::endl;
  
    // Count elements NOT divisible by 6: 7
  count = std::count_if(cont1.begin(), cont1.end(), std::not1(std::ptr_fun(DivBy6)));
  std::cout << "\nNumber of elements NOT divisible by 6: " << count << std::endl;
}
Output:
14  17  28  26  24  26  17  13  10  2  

Number of elements divisible by 6: 1

Number of elements NOT divisible by 6: 9