Although you may still be growing accustomed to templates, it’s time to explore two common, related use patterns: traits and policies. Programming with traits and policies is probably a new style for you, but it is common in C++. As you will discover in this Exploration, this technique is extremely flexible and powerful. Traits and policies underlie much of the C++ standard library. This Exploration looks at some of the traits and policies in the standard library, so that you can learn how to take advantage of them. It then helps you take the first steps toward writing your own.

Case Study: Iterators

Consider the humble iterator. Consider the std::advance function (Exploration 44). The advance function changes the position to which an iterator points. The advance function knows nothing about container types; it knows only about iterators. Yet somehow, it knows that if you try to advance a vector’s iterator, it can do so simply by adding an integer to the iterator. But if you advance a list’s iterator, the advance function must step the iterator one position at a time until it arrives at the desired destination. In other words, the advance function implements the optimal algorithm for changing the iterator’s position. The only information available to the advance function must come from the iterators themselves, and the key piece of information is the iterator kind. In particular, only random access iterators permit rapid advancement via addition. All other iterators must follow the step-by-step approach. So how does advance know what kind of iterator it has?

In most OOP languages, an iterator would derive from a common base class, which would implement a virtual advance function. The advance algorithm would call that virtual function and let normal object-oriented dispatching take care of the details. C++ certainly could take that approach, but it doesn’t.

Instead, C++ uses a technique that does not require looking up a virtual function and making an extra function call. Rather, C++ uses a technique that does not force you to derive all iterators from a single base class. If you implement a new container, you get to pick the class hierarchy. C++ provides the std::iterator base class template, which you can use if you want, but you don’t have to use it. Instead, the advance algorithm (and all other code that uses iterators) relies on a traits template.

Traits are attributes or properties of a type. In this case, an iterator’s traits describe the iterator kind (random access, bidirectional, forward, input, or output), the type that the iterator points to, and so on. The author of an iterator class specializes the std::iterator_traits class template to define the traits of the new iterator class. Iterator traits make more sense with an example, so let’s take a look at Listing 67-1, which shows one possible implementation of std::advance.

Listing 67-1.  One Possible Implementation of std::advance

#include <iostream>
#include <iterator>
#include <ostream>
#include <string>
 
void trace(std::string const& msg)
{
   std::cout << msg << '
';
}
 
// Default implementation: advance the slow way
template<class Kind>
class iterator_advancer
{
public:
   template<class InIter, class Distance>
   void operator()(InIter& iter, Distance distance)
   {
      trace("iterator_advancer<>");
      for ( ; distance != 0; --distance)
         ++iter;
   }
};
 
// Partial specialization for bi-directional iterators
template<>
class iterator_advancer<std::bidirectional_iterator_tag>
{
public:
   template<class BiDiIter, class Distance>
   void operator()(BiDiIter& iter, Distance distance)
   {
      trace("iterator_advancer<bidirectional_iterator_tag>");
      if (distance < 0)
         for ( ; distance != 0; ++distance)
            --iter;
      else
         for ( ; distance != 0; --distance)
            ++iter;
   }
};
 
template<class InIter, class Distance>
void my_advance(InIter& iter, Distance distance)
{
    iterator_advancer<typename std::iterator_traits<InIter>::iterator_category>{}
 
        (iter, distance);
}

This code is not as difficult to understand as it appears. The iterator_advancer class template provides one function, the function call operator. The implementation advances an input iterator distance times. This implementation works for a non-negative distance with any kind of iterator.

Bidirectional iterators permit a negative value for distance. Partial template specialization permits a separate implementation of iterator_advancer just for bidirectional iterators. The specialization checks whether distance is negative; negative and non-negative values are handled differently.

Let’s assemble the pieces. The my_advance function creates an instance of iterator_advancer and calls its function call operator, passing the iter and distance arguments. The magic is the std::iterator_traits class template. This class template has a few member typedefs, including iterator_category.

All bidirectional iterators must define the member typedef, iterator_category, as std::bidirectional_iterator_tag. Thus, when your program calls my_advance, and passes a bidirectional iterator (such as a std::list iterator) as the first argument, the my_advance function queries iterator_traits to discover the iterator_category. The compiler uses template specialization to decide which implementation of iterator_advancer to choose. The compiler then generates the code to call the correct function. The compiler takes care of all this magic—your program pays no runtime penalty.

Now try running the program in Listing 67-2 to see which iterator_advancer specialization is called in each situation.

Listing 67-2.  Example Program to Use the my_advance Function

#include <fstream>
#include <iostream>
#include <istream>
#include <iterator>
#include <list>
#include <ostream>
#include <string>
#include <vector>
 
#include "advance.hpp" // Listing 67-1
 
int main()
{
   std::vector<int> vector{ 10, 20, 30, 40 };
   std::list<int> list(vector.begin(), vector.end());
   std::vector<int>::iterator vector_iterator{vector.begin()};
   std::list<int>::iterator list_iterator{list.begin()};
   std::ifstream file{"advance.hpp"};
   std::istream_iterator<std::string> input_iterator{file};
 
   my_advance(input_iterator, 2);
   my_advance(list_iterator, 2);
   my_advance(vector_iterator, 2);
}

Notice any problems? What kind of iterator does a vector use? ________________ Which specialization does the compiler pick? ________________ The compiler does not follow class hierarchies when picking template specializations, so the fact that random_access_iterator_tag derives from bidirectional_iterator_tag is irrelevant in this case. If you want to specialize iterator_advancer for random access iterators, you must provide another specialization, this time for random_access_iterator_tag. Remember from Exploration 44 that random access iterators permit arithmetic on iterators. Thus, you can advance an iterator rapidly by adding the distance. Implement a partial specialization ofiterator_advancer for random access iterators.

Compare your solution with the snippet in Listing 67-3.

Listing 67-3.  Specializing iterator_advancer for Random Access Iterators

// Partial specialization for random access iterators
template<>
class iterator_advancer<std::random_access_iterator_tag>
{
public:
   template<class RandomIter, class Distance>
   void operator()(RandomIter& iter, Distance distance)
   {
      trace("iterator_advancer<random_access_iterator_tag>");
      iter += distance;
   }
};

Now rerun the sample program to see that the compiler picks the correct specialization.

A good optimizing compiler can take the my_advance function with the random-access specialization of iterator_advancer and easily compile optimal code, turning a call to the my_advance function into a single addition, with no function-call overhead. In other words, the layers of complexity that traits and policies introduce do not necessarily equate to bloated code and poor runtime performance. The complexity is conceptual, and once you understand what the traits do and how they work, you can let them abstract away the underlying complexity. They will make your job easier.

Iterator Traits

The class template, iterator_traits (defined in <iterator>), is an example of a traits type. A traits type provides traits, or characteristics, of another type. In this case, iterator_traits informs you about several traits of an iterator exposed via typedefs.

• difference_type: A signed integer type that represents the difference between two iterators. If you have two iterators that point into the same container, the distance function returns the distance between them—that is, the number of positions that separate the iterators. If the iterators are bidirectional or random access, the distance can be negative.
• iterator_category: The iterator kind, which must be one of the following types (also defined in <iterator>):

• bidirectional_iterator_tag
• forward_iterator_tag
• input_iterator_tag
• output_iterator_tag
• random_access_iterator_tag

Some of the standard algorithms use template specialization and the iterator_category to provide optimal implementations for different kinds of iterators.

• pointer: A typedef that represents a pointer to a value.
• reference: A typedef that represents a reference to a value.
• value_type: The type of values to which the iterator refers.

Can you think of another traits type in the standard library? ________________ The first one that I introduced in Exploration 2 is std::numeric_limits (Exploration 25). Another traits class that I’ve mentioned without explanation is std::char_traits (defined in <string>). But most of the interesting traits are the type traits.

Type Traits

The <type_traits> header defines a suite of traits templates that describe the characteristics of a type. They range from simple queries, such as std::is_integral<>, which tells you whether a type is one of the built-in integral types, to more sophisticated queries, such as std::is_nothrow_move_constructible<>, which tells you whether a class has a noexcept move constructor. Some traits modify types, such as std::remove_reference<>, which transforms int& to int, for example.

The std::move() function uses type traits, just to name one use of type traits in the standard library. Remember that all it does is change an lvalue to an rvalue. It uses remove_reference to strip the reference from its argument and then adds && to turn the result into an rvalue reference, as follows:

template<class T>
typename std::remove_reference<T>::type&& move(T&& t) noexcept
{
   return static_cast<typename std::remove_reference<T>::type&&>(t);
}

Notice the use of the type member typedef. That is how the type traits expose the result of their transformation. The query traits declare type to be a typedef for std::true_type or std::false_type; these classes declare a value member to be true or false at compile time. Although you can create an instance of true_type or false_type and evaluate them at runtime, the typical use is to use them to specialize a template.

The <type_traits> header has much more to offer, and Exploration 70 will delve deeper into its mysteries. For now, let’s tackle a more mundane traits class, std::char_traits.

Case Study: char_traits

Among the difficulties in working with characters in C++ is that the char type may be signed or unsigned. The size of a char relative to the size of an int varies from compiler to compiler. The range of valid character values also varies from one implementation to another and can even change while a program is running. A time-honored convention is to use int to store a value that may be a char or a special value that marks end-of-file, but nothing in the standard supports this convention. You may need to use unsigned int or long.

In order to write portable code, you need a traits class to provide a typedef for the integer type to use, the value of the end-of-file marker, and so on. That’s exactly what char_traits is for. When you use std::char_traits<char>::int_type, you know you can safely store any char value or the end-of-file marker (which is std::char_traits<char>::eof()).

The standard istream class has a get() function that returns an input character or the special end-of-file marker when there is no more input. The standard ostream class offers put(c) to write a character. Use these functions withchar_traits to write a function that copies its standard input to its standard output, one character at a time. Call eof() to obtain the special end-of-file value and eq_int_type(a,b) to compare two integer representations of characters for equality. Both functions are static member functions of the char_traits template, which you must instantiate with the desired character type. Call to_char_type to convert the integer representation back to a char. Compare your solution with Listing 67-4.

Listing 67-4.  Using Character Traits When Copying Input to Output

#include <iostream>
#include <istream>
#include <ostream>
#include <string>        // for char_traits
 
int main()
{
   typedef std::char_traits<char> char_traits; // for brevity and clarity
   char_traits::int_type c{};
   while (c = std::cin.get(), not char_traits::eq_int_type(c, char_traits::eof()))
      std::cout.put(char_traits::to_char_type(c));
}

First, notice the loop condition. Recall from Exploration 46 that the comma can separate two expressions; the first sub-expression is evaluated, then the second. The result of the entire expression is the result of the second sub-expression. In this case, the first sub-expression assigns get() to c, and the second sub-expression calls eq_int_type, so the result of the loop condition is the return value from eq_int_type, testing whether the result of get, as stored in c, is equal to the end-of-file marker. Another way to write the loop condition is as follows:

not char_traits::eq_int_type(c = std::cin.get(), char_traits::eof())

I don’t like to bury assignments in the middle of an expression, so I prefer to use the comma operator in this case. Other developers have a strong aversion to the comma operator. They prefer the embedded assignment style. Another solution is to use a for loop instead of a while loop, as follows:

for (char_traits::int_type c = std::cin.get();
      not char_traits::eq_int_type(c, char_traits::eof());
      c = std::cin.get())

The for-loop solution has the advantage of limiting the scope of the variable, c. But it has the disadvantage of repeating the call to std::cin.get(). Any of these solutions is acceptable; pick a style and stick with it.

In this case, char_traits seems to make everything more complicated. After all, comparing two integers for equality is easier and clearer when using the == operator. On the other hand, using a member function gives the library-writer the opportunity for added logic, such as checking for invalid character values.

In theory, you could write a char_traits specialization that, for instance, implements case-insensitive comparison. In that case, the eq() (which compares two characters for equality) and eq_int_type() functions would certainly require extra logic. On the other hand, you learned in Exploration 19 that such a traits class cannot be written for many international character sets, at least not without knowing the locale.

In the real world, specializations of char_traits are rare.

The char_traits class template is interesting nonetheless. A pure traits class template would implement only typedef members, static data members, and sometimes a member function that returns a constant, such as char_traits::eof(). Functions such as eq_int_type() are not traits, which describe a type. Instead, they are policy functions. A policy class template contains member functions that specify behavior, or policies. The next section looks at policies.

Policy-Based Programming

A policy is a class or class template that another class template can use to customize its behavior. The line between traits and policy is fuzzy, but to me, traits are static characteristics and policies are dynamic behavior. In the standard library, the string and stream classes use the char_traits policy class template to obtain type-specific behavior for comparing characters, copying character arrays, and more. The standard library provides policy implementations for the char and wchar_t types.

Suppose you are trying to write a high-performance server. After careful design, implementation, and testing, you discover that the performance of std::string introduces significant overhead. In your particular application, memory is abundant, but processor time is at a premium. Wouldn’t it be nice to be able to flip a switch and change your std::string implementation from one that is optimized for space into one that is optimized for speed? Instead, you must write your own string replacement that meets your needs. In writing your own class, you end up rewriting the many member functions, such as find_first_of, that have nothing to do with your particular implementation but are essentially the same for most string implementations. What a waste of time.

Imagine how simple your job would be if you had a string class template that took an extra template argument with which you could select a storage mechanism for the string, substituting memory-optimized or processor-optimized implementations according to your needs. That, in a nutshell, is what policy-based programming is all about.

A possible implementation of std::string is to keep a small character array in the string object for small strings and use dynamic memory allocation for larger strings. In order to conform to the C++ standard, these implementations cannot offer up a menu of policy template arguments that would let you pick the size of the character array. So let us free ourselves from this limitation and write a class that implements all the members of the std::string class but breaks the standard interface by adding a policy template argument. For the sake of simplicity, this book implements only a few functions. Completing the interface of std::string is left as an exercise for the reader. Listing 67-5 shows the new string class template and a few of its member functions. Take a look, and you can see how it takes advantage of the Storage policy.

Listing 67-5.  The newstring Class Template

#include <algorithm>
#include <cstddef>
 
template<class Char, class Storage, class Traits = std::char_traits<Char>>
class newstring {
public:
   typedef Char value_type;
   typedef std::size_t size_type;
   typedef typename Storage::iterator iterator;
   typedef typename Storage::const_iterator const_iterator;
 
   newstring() : storage_() {}
   newstring(newstring&&) = default;
   newstring(newstring const&) = default;
   newstring(Storage const& storage) : storage_(storage) {}
   newstring(Char const* ptr, size_type size) : storage_() {
      resize(size);
      std::copy(ptr, ptr + size, begin());
   }
  
   static const size_type npos = static_cast<size_type>(-1);
 
   newstring& operator=(newstring const&) = default;
   newstring& operator=(newstring&&) = default;
 
   void swap(newstring& str) { storage_.swap(str.storage_); }
 
   Char operator[](size_type i) const { return *(storage_.begin() + i); }
   Char& operator[](size_type i)      { return *(storage_.begin() + i); }
 
   void resize(size_type size, Char value = Char()) {
     storage_.resize(size, value);
   }
   void reserve(size_type size)    { storage_.reserve(size); }
   size_type size() const noexcept { return storage_.end() - storage_.begin(); }
   size_type max_size() const noexcept { return storage_.max_size(); }
   bool empty() const noexcept     { return size() == 0; }
   void clear()                    { resize(0); }
   void push_back(Char c)          { resize(size() + 1, c); }
 
   Char const* c_str() const { return storage_.c_str(); }
   Char const* data() const  { return storage_.c_str(); }
 
   iterator begin()              { return storage_.begin(); }
   const_iterator begin() const  { return storage_.begin(); }
   const_iterator cbegin() const { return storage_.begin(); }
   iterator end()                { return storage_.end(); }
   const_iterator end() const    { return storage_.end(); }
   const_iterator cend() const   { return storage_.end(); }
 
   size_type find(newstring const& s, size_type pos = 0) const {
      pos = std::min(pos, size());
      const_iterator result( std::search(begin() + pos, end(),
                             s.begin(), s.end(), Traits::eq) );
      if (result == end())
         return npos;
      else
         return result - begin();
   }
          
private:
   Storage storage_;
};
 
template<class Traits>
class newstringcmp
{
public:
   bool operator()(typename Traits::value_type a, typename Traits::value_type b)
   const
   {
      return Traits::cmp(a, b) < 0;
   }
};
 
template<class Char, class Storage1, class Storage2, class Traits>
bool operator <(newstring<Char, Storage1, Traits> const& a,
                newstring<Char, Storage2, Traits> const& b)
{
   return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end(),
                                       newstringcmp<Traits>());
}
 
template<class Char, class Storage1, class Storage2, class Traits>
bool operator ==(newstring<Char, Storage1, Traits> const& a,
                 newstring<Char, Storage2, Traits> const& b)
{
   return std::equal(a.begin(), a.end(), b.begin(), b.end(), Traits::eq);
}

The newstring class relies on Traits for comparing characters and Storage for storing them. The Storage policy must provide iterators for accessing the characters themselves and a few basic member functions (data, max_size, reserve, resize, swap), and the newstring class provides the public interface, such as the assignment operator and search member functions.

Public comparison functions use standard algorithms and Traits for comparisons. Notice how the comparison functions require their two operands to have the same Traits (otherwise, how could the strings be compared in a meaningful way?) but allow different Storage. It doesn’t matter how the strings store their contents if you want to know only whether two strings contain the same characters.

The next step is to write some storage policy templates. The storage policy is parameterized on the character type. The simplest Storage is vector_storage, which stores the string contents in a vector. Recall from Exploration 62, that a C character string ends with a null character. The c_str() member function returns a pointer to a C-style character array. In order to simplify the implementation of c_str, the vector stores a trailing null character after the string contents. Listing 67-6 shows part of an implementation of vector_storage. You can complete the implementation on your own.

Listing 67-6.  The vector_storage Class Template

#include <vector>
 
template<class Char>
class vector_storage {
public:
   typedef std::size_t size_type;
   typedef Char value_type;
   typedef typename std::vector<Char>::iterator iterator;
   typedef typename std::vector<Char>::const_iterator const_iterator;
 
   vector_storage() : string_(1, Char()) {}
 
   void swap(vector_storage& storage) { string_.swap(storage.string_); }
   size_type max_size() const { return string_.max_size() - 1; }
   void reserve(size_type size) { string_.reserve(size + 1); }
   void resize(size_type newsize, value_type value) {
      // if the string grows, overwrite the null character, then resize
      if (newsize >= string_.size()) {
         string_[string_.size() - 1] = value;
         string_.resize(newsize + 1, value);
      }
      else
         string_.resize(newsize + 1);
      string_[string_.size() - 1] = Char();
   }
   Char const* c_str() const { return &string_[0]; }
 
   iterator begin()             { return string_.begin(); }
   const_iterator begin() const { return string_.begin(); }
   // Skip over the trailing null character at the end of the vector
   iterator end()               { return string_.end() - 1; }
   const_iterator end() const   { return string_.end() - 1; }
 
private:
   std::vector<Char> string_;
};

The only difficulty in writing vector_storage is that the vector stores a trailing null character, so the c_str function can return a valid C-style character array. Therefore, the end function has to adjust the iterator that it returns.

Another possibility for a storage policy is array_storage, which is just like vector_storage, except it uses an array. By using an array, all storage is local. The array size is the maximum capacity of the string, but the string size can vary up to that maximum. Writearray_storage. Compare your result with mine in Listing 67-7.

Listing 67-7.  The array_storage Class Template

#include <algorithm>
#include <cstdlib>
#include <stdexcept>
#include <array>
 
template<class Char, std::size_t MaxSize>
class array_storage {
public:
   typedef std::array<Char, MaxSize> array_type;
   typedef std::size_t size_type;
   typedef Char value_type;
   typedef typename array_type::iterator iterator;
   typedef typename array_type::const_iterator const_iterator;
 
   array_storage() : size_(0), string_() { string_[0] = Char(); }
 
   void swap(array_storage& storage) {
      string_.swap(storage.string_);
      std::swap(size_, storage.size_);
   }
   size_type max_size() const { return string_.max_size() - 1; }
   void reserve(size_type size) {
     if (size > max_size()) throw std::length_error("reserve");
   }
   void resize(size_type newsize, value_type value) {
      if (newsize > max_size())
         throw std::length_error("resize");
      if (newsize > size_)
         std::fill(begin() + size_, begin() + newsize, value);
      size_ = newsize;
      string_[size_] = Char();
   }
   Char const* c_str() const { return &string_[0]; }
 
   iterator begin()             { return string_.begin(); }
   const_iterator begin() const { return string_.begin(); }
   iterator end()               { return begin() + size_; }
   const_iterator end() const   { return begin() + size_; }
 
private:
   size_type size_;
   array_type string_;
};

One difficulty when writing new string classes is that you must write new I/O functions too. Unfortunately, this takes a fair bit of work and a solid understanding of the stream class templates and stream buffers. Handling padding and field adjustment is easy, but there are subtleties to the I/O streams that I have not covered, such as integration with C stdio, tying input and output streams so that prompts appear before the user is asked for input, etc. So just copy my solution in Listing 67-8 into newstring.hpp.

Listing 67-8.  Output Function for newstring

template<class Char, class Storage, class Traits>
std::basic_ostream<Char, Traits>&
  operator<<(std::basic_ostream<Char, Traits>& stream,
             newstring<Char, Storage, Traits> const& string)
{
   typename std::basic_ostream<Char, Traits>::sentry sentry{stream};
   if (sentry)
   {
      bool needs_fill{stream.width() != 0 and string.size() > stream.width()};
      bool is_left_adjust{
         (stream.flags() & std::ios_base::adjustfield) == std::ios_base::left };
      if (needs_fill and not is_left_adjust)
      {
         for (std::size_t i{stream.width() - string.size()}; i != 0; --i)
            stream.rdbuf()->sputc(stream.fill());
      }
      stream.rdbuf()->sputn(string.data(), string.size());
      if (needs_fill and is_left_adjust)
      {
         for (std::size_t i{stream.width() - string.size()}; i != 0; --i)
            stream.rdbuf()->sputc(stream.fill());
      }
   }
   stream.width(0);
   return stream;
}

The sentry class manages some bookkeeping on behalf of the stream. The output function handles padding and adjustment. If you are curious about the details, consult a good reference.

The input function also has a sentry class, which skips leading white space on your behalf. The input function has to read characters until it gets to another whitespace character or the string fills or the width limit is reached. See Listing 67-9 for my version.

Listing 67-9.  Input Function for newstring

template<class Char, class Storage, class Traits>
std::basic_istream<Char, Traits>&
  operator>>(std::basic_istream<Char, Traits>& stream,
             newstring<Char, Storage, Traits>& string)
{
   typename std::basic_istream<Char, Traits>::sentry sentry{stream};
   if (sentry)
   {
      std::ctype<Char> const& ctype(
         std::use_facet<std::ctype<Char>>(stream.getloc()) );
      std::ios_base::iostate state{ std::ios_base::goodbit };
      std::size_t max_chars{ string.max_size() };
      if (stream.width() != 0 and stream.width() < max_chars)
         max_chars = stream.width();
      string.clear();
      while (max_chars-- != 0) {
         typename Traits::int_type c{ stream.rdbuf()->sgetc() };
         if (Traits::eq_int_type(Traits::eof(), c)) {
            state |= std::ios_base::eofbit;
            break; // is_eof
         }
         else if (ctype.is(ctype.space, Traits::to_char_type(c)))
            break;
         else {
            string.push_back(Traits::to_char_type(c));
            stream.rdbuf()->sbumpc();
         }
      }
      if (string.empty())
         state |= std::ios_base::failbit;
      stream.setstate(state);
      stream.width(0);
   }
   return stream;
}

The break statement exits a loop immediately. You are probably familiar with this statement or something similar. Experienced programmers may be surprised that no example has required this statement until now. One reason is that I gloss over error-handling, which would otherwise be a common reason to break out of a loop. In this case, when the input reaches end of file or white space, it is time to exit the loop. The partner to break is continue, which immediately reiterates the loop. In a for loop, continue evaluates the iterate part of the loop header and then the condition. I have rarely needed to use continue in real life and could not think of any reasonable example that uses continue, but I mention it only for the sake of completeness.

As you know, the compiler finds your I/O operators by matching the type of the right-hand operand, newstring, with the type of the function parameter. In this simple case, you can easily see how the compiler performs the matching and finds the right function. Throw some namespaces into the mix, and add some type conversions, and everything gets a little bit more muddled. The next Exploration delves more closely into namespaces and the rules that the C++ compiler applies in order to find your overloaded function names (or not find them, and, therefore, how to fix that problem).