Functions That Operate on Any Sequence

A major use of function templates is with parametrized classes like list. As you saw in the last section, specialized templates can be defined that will work with a container class such as list, for any type. The standard algorithms themselves are all function templates, so that they can be used with arguments of any type.

The idea of input and output sequences is very important in understanding and using the standard algorithms.

Sequences and for_each()

The standard algorithm for_each() is very simple. In the following implementation, it is given an input sequence and a function to apply to each element of that sequence:

template <class In, class Fn>
  void for_each(In i, In iend, Fn f) {
     for(; i != iend; ++i) f(*i);
  }
;> void show(int i) {  cout << i << endl; }
;> for_each(ls.begin(), ls.end(), show);
1
2
;> for_each(ls.begin(), ls.end(), dump);
1
2
;> list<int>::iterator li;
;> for(li = ls.begin(); li != ls.end(); ++li) dump(*li);
1
2

This example shows three ways of saying the same thing, and the last way involves explicitly writing out the loop. It is clumsy because you must explicitly declare a list iterator. In contrast, when you instantiate for_ each(), the compiler binds the type parameter In to the type ls.begin(), which is in fact list<int>::iterator. for_each() simply assumes that it is passed objects that behave like forward iterators. That is, *i gives the current value, and ++i moves to the next value. These are precisely the properties of C++ pointers.

Standard Algorithms

The idea behind standard algorithms is to avoid writing out loops, which are “tedious and error prone,” as Bjarne Stroustrup says in The C++ Programming Language. However, typing ls.begin(),ls.end() all the time seems equally tedious. Why is for_each() not defined as follows?

template <class C, class Fn>
  void for_each(const C& c, Fn f) {
    typename C::iterator i = c.begin(), iend = c.end();
    for(; i != iend; ++i) f(*i);
  }
;> for_each(ls,dump);
1
2

This example indeed does the job for any standard container or for any type that shares this part of the container interface (such as std::string). But these assumptions are too strict. The following example shows two things that the standard for_each() can do that the preceding version cannot. First, the standard for_each() happily operates on built-in arrays. Second, it's very useful to specify the input sequence. The second for_each() applies its function to every element after the first occurance of 10:

;> int arr[] = { 1,10,3};
;> for_each(arr,arr+3,dump);
1
10
3
;> int *p = find(arr,arr+3,10), p_end = arr+3;
;> for_each(p,p_end,dump);
10
3

The standard algorithms efficiently use compile-time polymorphism. All standard iterators behave like C++ pointers, so ordinary pointers work fine as well. The standard library emphasis is on both speed and elegance. But an old engineering proverb says you can only have two out of three desirables. Aggressive optimization for speed, involving wholesale inlining, can produce bulky code. One solution to this problem is outlined in the section “The Standard Containers as Class Templates.”

Objects That Act Like Functions

C programmers are pleasantly surprised to discover that std::sort() can be considerably faster than the old-fashioned qsort() routine. The reason is, again, that the compiler can often inline a function directly into the sort algorithm. In fact, any standard algorithm that requires a function is satisfied by anything that behaves like a function. In C++, the action of calling a function is an operator, and it can be overloaded. That is, if obj is some object of class C, obj() can be defined to mean anything we like by overloading C::operator[]. The following is a class that behaves like a function:

class Sum {
  double m_sum;
public:
  Sum()
   : m_sum(0.0) { }

  void   operator() (double v) {  m_sum += v; }

  double value()
  {  return m_sum; }
};
;> Sum s;
;> s(2.0);
;> s(3.0);
;> s.value();
(double) 5.0
;> double arr[] = { 2.0,3.0};
;> Sum t;
;> for_each(arr,arr+2, t);
;> t.value();
(double) 5.0
;> #include <numeric>
;> double val = 0.0;
;> accumulate(arr,arr+2,val);
(double) 5.0

Templates turn this party trick into a genuinely useful technique. Remember that templates are instantiated through a sophisticated kind of macro substitution that binds the function parameter Fn to the type Sum. The expression f(*i) is finally compiled as the method call f.operator()(*i). The advantage of function-like objects is that they carry their own context around with them. With ordinary functions, finding the sum would require a global variable.

In the example, a specific numerical algorithm (accumulate()) does the same job as using for_each() with Sum. You need to pass it a final argument so that the compiler can deduce what the return type must be. Generally, you should use the most specific algorithm you can find.