15.1 An Example: Accumulating a Sequence

Ru-Brd

Computing the sum of a sequence of values is a fairly common computational task. However, this seemingly simple problem provides us with an excellent example to introduce various levels at which policy classes and traits can help.

15.1.1 Fixed Traits

Let's first assume that the values of the sum we want to compute are stored in an array, and we are given a pointer to the first element to be accumulated and a pointer one past the last element to be accumulated . Because this book is about templates, we wish to write a template that will work for many types. The following may seem straightforward by now ^[1] :

^[1] Most examples in this section use ordinary pointers for the sake of simplicity. Clearly, an industrial-strength interface may prefer to use iterator parameters following the conventions of the C++ standard library (see [JosuttisStdLib]). We revisit this aspect of our example later.

  // traits/accum1.hpp  #ifndef ACCUM_HPP  #define ACCUM_HPP  template <typename T>  inline  T accum (T const* beg, T const* end)  {      T total = T();  // assume  T()  actually creates a zero value  while (beg != end) {          total += *beg;          ++beg;      }      return total;  }  #endif  // ACCUM_HPP  

The only slightly subtle decision here is how to create a zero value of the correct type to start our summation. We use the expression T() here, which normally should work for built-in numeric types like int and float (see Section 5.5 on page 56).

To motivate our first traits template, consider the following code that makes use of our accum() :

  // traits/accum1.cpp  #include "accum1.hpp"  #include <iostream>  int main()  {  // create array of 5 integer values  int num[]={1,2,3,4,5};  // print average value  std::cout << "the average value of the integer values is "            << accum(&num[0], &num[5]) / 5            << '\n';  // create array of character values  char name[] = "templates";  int length = sizeof(name)-1;  // (try to) print average character value  std::cout << "the average value of the characters in \""            << name << "\" is "            << accum(&name[0], &name[length]) / length            << '\n';  } 

In the first half of the program we use accum() to sum five integer values:

 int num[]={1,2,3,4,5};   accum(&num[0], &num[5]) 

The average integer value is then obtained by simply dividing the resulting sum by the number of values in the array.

The second half of the program attempts to do the same for all letters in the word template (provided the characters from a to z form a contiguous sequence in the actual character set, which is true for ASCII but not for EBCDIC ^[2] ). The result should presumably lie between the value of a and the value of z . On most platforms today, these values are determined by the ASCII codes: a is encoded as 97 and z is encoded as 122. Hence, we may expect a result between 97 and 122. However, on our platform the output of the program is as follows :

^[2] EBCDIC is an abbreviation of Extended Binary-Coded Decimal Interchange Code, which is an IBM character set that is widely used on large IBM computers.

 the average value of the integer values is 3  the average value of the characters in "templates" is -5 

The problem here is that our template was instantiated for the type char , which turns out to be too by introducing an additional template parameter AccT that describes the type used for the variable total (and hence the return type). However, this would put an extra burden on all users of our template: They would have to specify an extra type in every invocation of our template. In our example we may, therefore, need to write the following:

 accum<int>(&name[0],&name[length]) 

This is not an excessive constraint, but it can be avoided.

An alternative approach to the extra parameter is to create an association between each type T for which accum() is called and the corresponding type that should be used to hold the accumulated value. This association could be considered characteristic of the type T , and therefore the type in which the sum is computed is sometimes called a trait of T . As is turns out, our association can be encoded as specializations of a template:

  // traits/accumtraits2.hpp  template<typename T>  class AccumulationTraits;  template<>  class AccumulationTraits<char> {    public:      typedef int AccT;  };  template<>  class AccumulationTraits<short> {    public:      typedef int AccT;  };  template<>  class AccumulationTraits<int> {    public:      typedef long AccT;  };  template<>  class AccumulationTraits<unsigned int> {    public:      typedef unsigned long AccT;  };  template<>  class AccumulationTraits<float> {    public:      typedef double AccT;  }; 

The template AccumulationTraits is called a traits template because it holds a trait of its parameter type. (In general, there could be more than one trait and more than one parameter.) We chose not to provide a generic definition of this template because there isn't a great way to select a good accumulation type when we don't know what the type is. However, an argument could be made that T itself is often a good candidate for such a type (although clearly not in our earlier example).

With this in mind, we can rewrite our accum() template as follows:

  // traits/accum2.hpp  #ifndef ACCUM_HPP  #define ACCUM_HPP  #include "accumtraits2.hpp"  template <typename T>  inline  typename AccumulationTraits<T>::AccT accum (T const* beg,                                              T const* end)  {  // return type is traits of the element type  typedef typename AccumulationTraits<T>::AccT AccT;      AccT total = AccT();  // assume  T()  actually creates a zero value  while (beg != end) {          total += *beg;          ++beg;      }      return total;  }  #endif  // ACCUM_HPP  

The output of our sample program then becomes what we expect:

 the average value of the integer values is 3  the average value of the characters in "templates" is 108 

Overall, the changes aren't very dramatic considering that we have added a very useful mechanism to customize our algorithm. Furthermore, if new types arise for use with accum() , an appropriate AccT can be associated with it simply by declaring an additional explicit specialization of the AccumulationTraits template. Note that this can be done for any type: fundamental types, types that are declared in other libraries, and so forth.

15.1.2 Value Traits

So far, we have seen that traits represent additional type information related to a given "main" type. In this section we show that this extra information need not be limited to types. Constants and other classes of values can be associated with a type as well.

Our original accum() template uses the default constructor of the return value to initialize the result variable with what is hoped to be a zero-like value:

 AccT total = AccT();  // assume  T()  actually creates a zero value    return total; 

Clearly, there is no guarantee that this produces a good value to start the accumulation loop. Type T may not even have a default constructor.

Again, traits can come to the rescue. For our example, we can add a new value trait to our AccumulationTraits:

  // traits/accumtraits3.hpp  template<typename T>  class AccumulationTraits;  template<>  class AccumulationTraits<char> {    public:      typedef int AccT;      static AccT const zero = 0;  };  template<>  class AccumulationTraits<short> {    public:      typedef int AccT;      static AccT const zero = 0;  };  template<>  class AccumulationTraits<int> {    public:      typedef long AccT;      static AccT const zero = 0;  };   

In this case, our new trait is a constant that can be evaluated at compile time. Thus, accum() becomes:

  // traits/accum3.hpp  #ifndef ACCUM_HPP  #define ACCUM_HPP  #include "accumtraits3.hpp"  template <typename T>  inline  typename AccumulationTraits<T>::AccT accum (T const* beg,                                              T const* end)  {  // return type is traits of the element type  typedef typename AccumulationTraits<T>::AccT AccT;      AccT total = AccumulationTraits<T>::zero;      while (beg != end) {          total += *beg;          ++beg;      }      return total;  }  #endif  // ACCUM_HPP  

In this code, the initialization of the accumulation variable remains straightforward:

 AccT total = AccumulationTraits<T>::zero; 

A drawback of this formulation is that C++ allows us to initialize only a static constant data member inside its class if it has an integral or enumeration type. This excludes our own classes, of course, and floating-point types as well. The following specialization is, therefore, an error:

   template<>  class AccumulationTraits<float> {  public:      typedef double AccT;      static double const zero = 0.0;  // ERROR: not an integral type  }; 

The straightforward alternative is not to define the value trait in its class:

   template<>  class AccumulationTraits<float> {  public:      typedef double AccT;      static double const zero;  }; 

The initializer then goes in a source file and looks something like the following:

   double const AccumulationTraits<float>::zero = 0.0; 

Although this works, it has the disadvantage of being more opaque to compilers. While processing client files, compilers are typically unaware of definitions in other files. In this case, for example, a compiler would not be able to take advantage of the fact that the value zero is really 0.0 .

Consequently, we prefer to implement value traits, which are not guaranteed to have integral values as inline member functions. ^[3] For example, we could rewrite AccumulationTraits as follows:

^[3] Most modern C++ compilers can "see through" calls of simple inline functions.

  // traits/accumtraits4.hpp  template<typename T>  class AccumulationTraits;  template<>  class AccumulationTraits<char> {    public:      typedef int AccT;      static AccT zero() {          return 0;      }  };  template<>  class AccumulationTraits<short> {    public:      typedef int AccT;      static AccT zero() {          return 0;      }  };  template<>  class AccumulationTraits<int> {    public:      typedef long AccT;      static AccT zero() {          return 0;      }  };  template<>  class AccumulationTraits<unsigned int> {    public:      typedef unsigned long AccT;      static AccT zero() {          return 0;      }  };  template<>  class AccumulationTraits<float> {    public:      typedef double AccT;      static AccT zero() {          return 0;      }  };   

For the application code, the only difference is the use of function call syntax (instead of the slightly more concise access to a static data member):

 AccT total = AccumulationTraits<T>::zero(); 

Clearly, traits can be more than just extra types . In our example, they can be a mechanism to provide all the necessary information that accum() needs about the element type for which it is called. This is the key of the traits concept: Traits provide an avenue to configure concrete elements (mostly types) for generic computations .

15.1.3 Parameterized Traits

The use of traits in accum() in the previous sections is called fixed , because once the decoupled trait is defined, it cannot be overridden in the algorithm. There may be cases when such overriding is desirable. For example, we may happen to know that a set of float values can safely be summed into a variable of the same type, and doing so may buy us some efficiency.

In principle, the solution consists of adding a template parameter but with a default value determined by our traits template. In this way, many users can omit the extra template argument, but those with more exceptional needs can override the preset accumulation type. The only bee in our bonnet for this particular case is that function templates cannot have default template arguments. ^[4]

^[4] This is almost certainly going to change in a revision of the C++ standard, and compiler vendors are likely to provide the feature even before this revised standard is published (see Section 13.3 on page 207).

For now, let's circumvent the problem by formulating our algorithm as a class. This also illustrates the fact that traits can be used in class templates at least as easily as in function templates. The drawback in our application is that class templates cannot have their template arguments deduced . They must be provided explicitly. Hence, we need the form

 Accum<char>::accum(&name[0], &name[length]) 

to use our revised accumulation template:

  // traits/accum5.hpp  #ifndef ACCUM_HPP  #define ACCUM_HPP  #include "accumtraits4.hpp"  template <typename T,            typename AT = AccumulationTraits<T> >  class Accum {    public:      static typename AT::AccT accum (T const* beg, T const* end) {          typename AT::AccT total = AT::zero();          while (beg != end) {              total += *beg;              ++beg;          }          return total;      }  };  #endif  // ACCUM_HPP  

Presumably, most users of this template would never have to provide the second template argument explicitly because it can be configured to an appropriate default for every type used as a first argument.

As is often the case, we can introduce convenience functions to simplify the interface:

 template <typename T>  inline  typename AccumulationTraits<T>::AccT accum (T const* beg,                                              T const* end)  {      return Accum<T>::accum(beg, end);  }  template <typename Traits, typename T>  inline  typename Traits::AccT accum (T const* beg, T const* end)  {      return Accum<T, Traits>::accum(beg, end);  } 

15.1.4 Policies and Policy Classes

So far we have equated accumulation with summation . Clearly we can imagine other kinds of accumulations. For example, we could multiply the sequence of given values. Or, if the values were strings, we could concatenate them. Even finding the maximum value in a sequence could be formulated as an accumulation problem. In all these alternatives, the only accum() operation that needs to change is total += *start . This operation can be called a policy of our accumulation process. A policy class, then, is a class that provides an interface to apply one or more policies in an algorithm. ^[5]

^[5] We could generalize this to a policy parameter , which could be a class (as discussed) or a pointer to a function.

Here is an example of how we could introduce such an interface in our Accum class template:

  // traits/accum6.hpp  #ifndef ACCUM_HPP  #define ACCUM_HPP  #include "accumtraits4.hpp"  #include "sumpolicy1.hpp"  template <typename T,            typename Policy = SumPolicy,            typename Traits = AccumulationTraits<T> >  class Accum {    public:      typedef typename Traits::AccT AccT;      static AccT accum (T const* beg, T const* end) {          AccT total = Traits::zero();          while (beg != end) {              Policy::accumulate(total, *beg);              ++beg;          }          return total;      }  };  #endif  // ACCUM_HPP  

With this a SumPolicy could be written as follows:

  // traits/sumpolicy1.hpp  #ifndef SUMPOLICY_HPP  #define SUMPOLICY_HPP  class SumPolicy {    public:      template<typename T1, typename T2>      static void accumulate (T1& total, T2 const & value) {          total += value;      }  };  #endif  // SUMPOLICY_HPP  

In this example we chose to make our policy an ordinary class (that is, not a template) with a static member function template (which is implicitly inline). We discuss an alternative option later.

By specifying a different policy to accumulate values we can compute different things. Consider, for example, the following program, which intends to determine the product of some values:

  // traits/accum7.cpp  #include "accum6.hpp"  #include <iostream>  class MultPolicy {    public:      template<typename T1, typename T2>      static void accumulate (T1& total, T2 const& value) {          total *= value;      }  };  int main()  {  // create array of 5 integer values  int num[]={1,2,3,4,5};  // print product of all values  std::cout << "the product of the integer values is "                << Accum<int,MultPolicy>::accum(&num[0], &num[5])                << '\n';  } 

However, the output of this program isn't what we would like:

 the product of the integer values is 0 

The problem here is caused by our choice of initial value: Although works well for summation, it does not work for multiplication (a zero initial value forces a zero result for accumulated multiplications). This illustrates that different traits and policies may interact, underscoring the importance of careful template design.

In this case we may recognize that the initialization of an accumulation loop is a part of the accumulation policy. This policy may or may not make use of the trait zero() . Other alternatives are not to be forgotten: Not everything must be solved with traits and policies. For example, the accumulate() function of the C++ standard library takes the initial value as a third (function call) argument.

15.1.5 Traits and Policies: What's the Difference?

A reasonable case can be made in support of the fact that policies are just a special case of traits. Conversely, it could be claimed that traits just encode a policy.

The New Shorter Oxford English Dictionary (see [NewShorterOED]) has this to say:

• trait n. ... a distinctive feature characterizing a thing

• policy n. ... any course of action adopted as advantegous or expedient

Based on this, we tend to limit the use of the term policy classes to classes that encode an action of some sort that is largely orthogonal with respect to any other template argument with which it is combined. This is in agreement with Andrei Alexandrescu's statement in his book Modern C++ Design (see page 8 of [AlexandrescuDesign]) ^[6] :

^[6] Alexandrescu has been the main voice in the world of policy classes, and he has developed a rich set of techniques based on them.

Policies have much in common with traits but differ in that they put less emphasis on type and more on behavior.

Nathan Myers, who introduced the traits technique, proposed the following more open -ended definition (see [MyersTraits]):

Traits class: A class used in place of template parameters. As a class, it aggregates useful types and constants; as a template, it provides an avenue for that "extra level of indirection" that solves all software problems.

In general, we therefore tend to use the following (slightly fuzzy) definitions:

• Traits represent natural additional properties of a template parameter.

• Policies represent configurable behavior for generic functions and types (often with some commonly used defaults).

To elaborate further on the possible distinctions between the two concepts, we list the following observations about traits:

• Traits can be useful as fixed traits (that is, without being passed through template parameters).

• Traits parameters usually have very natural default values (which are rarely overridden, or simply cannot be overridden).

• Traits parameters tend to depend tightly on one or more main parameters.

• Traits mostly combine types and constants rather than member functions.

• Traits tend to be collected in traits templates .

For policy classes, we make the following observations:

• Policy classes don't contribute much if they aren't passed as template parameters.

• Policy parameters need not have default values and are often specified explicitly (although many generic components are configured with commonly used default policies).

• Policy parameters are mostly orthogonal to other parameters of a template.

• Policy classes mostly combine member functions.

• Policies can be collected in plain classes or in class templates.

However, there is certainly an indistinct line between both terms. For example, the character traits of the C++ standard library also define functional behavior such as comparing, moving, and finding characters. And by replacing these traits you can define string classes that behave in a case-insensitive manner (see Section 11.2.14 in [JosuttisStdLib]) while keeping the same character type. Thus, although they are called traits , they have some properties associated with policies.

15.1.6 Member Templates versus Template Template Parameters

To implement an accumulation policy we chose to express SumPolicy and MultPolicy as ordinary classes with a member template. An alternative consists of designing the policy class interface using class templates, which are then used as template template arguments. For example, we could rewrite SumPolicy as a template:

  // traits/sumpolicy2.hpp  #ifndef SUMPOLICY_HPP  #define SUMPOLICY_HPP  template <typename T1, typename T2>  class SumPolicy {    public:      static void accumulate (T1& total, T2 const & value) {          total += value;      }  };  #endif  // SUMPOLICY_HPP  

The interface of Accum can then be adapted to use a template template parameter:

  // traits/accum8.hpp  #ifndef ACCUM_HPP  #define ACCUM_HPP  #include "accumtraits4.hpp"  #include "sumpolicy2.hpp"  template <typename T,            template<typename,typename> class Policy = SumPolicy,            typename Traits = AccumulationTraits<T> >  class Accum {    public:      typedef typename Traits::AccT AccT;      static AccT accum (T const* beg, T const* end) {          AccT total = Traits::zero();          while (beg != end) {              Policy<AccT,T>::accumulate(total, *beg);              ++beg;          }          return total;      }  };  #endif  // ACCUM_HPP  

The same transformation can be applied to the traits parameter. (Other variations on this theme are possible: For example, instead of explicitly passing the AccT type to the policy type, it may be advantageous to pass the accumulation trait and have the policy determine the type of its result from a traits parameter.)

The major advantage of accessing policy classes through template template parameters is that it makes it easier to have a policy class carry with it some state information (that is, static data members) with a type that depends on the template parameters. (In our first approach the static data members would have to be embedded in a member class template.)

However, a downside of the template template parameter approach is that policy classes must now be written as templates, with the exact set of template parameters defined by our interface. This, unfortunately , disallows any additional template parameters in our policies. For example, we may want to add a Boolean nontype template parameter to SumPolicy that selects whether summation should happen with the += operator or whether + only should be used. In the program using a member template we can simply rewrite SumPolicy as a template:

  // traits/sumpolicy3.hpp  #ifndef SUMPOLICY_HPP  #define SUMPOLICY_HPP  template<bool use_compound_op = true>  class SumPolicy {    public:      template<typename T1, typename T2>      static void accumulate (T1& total, T2 const & value) {          total += value;      }  };  template<>  class SumPolicy<false> {    public:      template<typename T1, typename T2>      static void accumulate (T1& total, T2 const & value) {          total = total + value;      }  };  #endif  // SUMPOLICY_HPP  

With implementation of Accum using template template parameters such an adaptation is no longer possible.

15.1.7 Combining Multiple Policies and/or Traits

As our development has shown, traits and policies don't entirely do away with having multiple template parameters. However, they do reduce their number to something manageable. An interesting question, then, is how to order such multiple parameters.

A simple strategy is to order the parameters according to the increasing likelihood of their default value to be selected. Typically, this would mean that the traits parameters follow the policy parameters because the latter are more often overridden in client code. (The observant reader may have noticed this strategy in our development.)

If we are willing to add a significant amount of complexity to our code, an alternative exists that essentially allows us to specify the nondefault arguments in any order. Refer to Section 16.1 on page 285 for details. Chapter 13 also discusses potential future template features that could simplify the resolution of this aspect of template design.

15.1.8 Accumulation with General Iterators

Before we end this introduction to traits and policies, it is instructive to look at one version of accum() that adds the capability to handle generalized iterators (rather than just pointers), as expected from an industrial-strength generic component. Interestingly, this still allows us to call accum() with pointers because the C++ standard library provides so-called iterator traits . (Traits are everywhere!) Thus, we could have defined our initial version of accum() as follows (ignoring our later refinements):

  // traits/accum0.hpp  #ifndef ACCUM_HPP  #define ACCUM_HPP  #include <iterator>  template <typename Iter>  inline  typename std::iterator_traits<Iter>::value_type  accum (Iter start, Iter end)  {      typedef typename std::iterator_traits<Iter>::value_type VT;      VT total = VT();  // assume  T()  actually creates a zero value  while (start != end) {          total += *start;          ++start;      }      return total;  }  #endif  // ACCUM_HPP  

The iterator_traits structure encapsulates all the relevant properties of iterator. Because a partial specialization for pointers exists, these traits are conveniently used with any ordinary pointer types. Here is how a standard library implementation may implement this support:

 namespace std {      template <typename T>      struct iterator_traits<T*> {          typedef T                          value_type;          typedef ptrdiff_t                  difference_type;          typedef random_access_iterator_tag iterator_category;          typedef T*                         pointer;          typedef T&                         reference;      };  } 

However, there is no type for the accumulation of values to which an iterator refers; hence we still need to design our own AccumulationTraits .

Ru-Brd