2.1. Type Associations

In C++, the entities that can be manipulated at compile time, called metadata, are divided roughly into two categories: types and non-types. Not coincidentally, all the kinds of metadata can be used as template parameters. The constant integer values used in Chapter 1 are among the non-types, a category that also includes values of nearly everything else that can be known at compile time: the other integral types, enums, pointers and references to functions and "global" objects, and pointers to members.^[1]

^[1] The standard also allows templates to be passed as template parameters. If that's not mind-bending enough for you, these parameters are treated in the standard "as types for descriptive purposes." Templates aren't types, though, and can't be passed to another template where a type is expected.

It's easy to imagine doing calculations on some kinds of non-type metadata, but it may surprise you to learn that there is also a way to do calculations with types. To get a feeling for what that meansand why it matterswe're going to look at one of the simplest algorithms from the C++ standard library: iter_swap. It is iter_swap's humble duty to take two iterators and exchange the values of the objects they refer to. It looks something like this:

    template <class ForwardIterator1, class ForwardIterator2>


    void iter_swap(ForwardIterator1 i1, ForwardIterator2 i2)


    {


        T tmp = *i1;


        *i1 = *i2;


        *i2 = tmp;


    }

If at this point you're wondering where T came from, you've got a sharp eye. It hasn't been defined, and iter_swap can't compile if we write it that way. Informally, of course, T is the type you get when the iterator is dereferenced, what's known in the C++ standard (section 24.1) as the iterator's value type. Okay, but how do we name that type?

2.1.1. Using a Direct Approach

In case you already know the answer chosen by the authors of the standard library, we'll ask you to forget it for the time being; we have a couple of deeper points to make. Instead, imagine we're implementing the standard library ourselves and choosing its method of handling iterators. We're going to end up writing a lot of algorithms, and many of them will need to make an association between an iterator type and its value type. We could require all iterator implementations to supply a nested type called value_type, which we'd access directly:

    template <class ForwardIterator1, class ForwardIterator2>


    void iter_swap(ForwardIterator1 i1, ForwardIterator2 i2)


    {


        typename                      // (see Language Note)


          ForwardIterator1::value_type tmp = *i1;


        *i1 = *i2;


        *i2 = tmp;


    }

C++ Language Note The C++ standard requires the typename keyword when we use a dependent name as though it refers to a type. ForwardIterator1::value_type may or may not name a type, depending on the particular ForwardIterator1 that is passed. See Appendix B for more information about typename.

That's a perfectly good strategy for making type associations, but it's not very general. In particular, iterators in C++ are modeled on the design of pointers, with the intention that plain pointers should themselves be valid iterators. Unfortunately, pointers can't have nested types; that privilege is reserved for classes:

    void f(int* p1, int* p2)


    {


        iter_swap(p1,p2); // error: int* has no member 'value_type'


    }

2.1.2. Taking the Long Way Around

We can solve any problem by introducing an extra level of indirection.

Butler Lampson

Lampson's idea is so universal in programming that Andrew Koenig^[2] is fond of calling it "the Fundamental Theorem of Software Engineering" (FTSE). We may not be able to add a nested ::value_type to all iterators, but we can add it to a template that takes the iterator type as a parameter. In the standard library this template, called iterator_traits, has a simple signature:

^[2] Andrew Koenig is the co-author of Accelerated C++ and project editor for the C++ standard. For an acknowledgment that does justice to his many contributions to C++ over the years, see almost any one of Bjarne Stroustrup's C++ books.

    template <class Iterator> struct iterator_traits;

Here's how we put it to work in iter_swap:

    template <class ForwardIterator1, class ForwardIterator2>


    void iter_swap(ForwardIterator1 i1, ForwardIterator2 i2)


    {


        typename


          iterator_traits<ForwardIterator1>::value_type tmp = *i1;


        *i1 = *i2;


        *i2 = tmp;


    }

iterator_traits is so named because it describes properties (or traits) of its argument. In this case, the traits being described are the iterator's five associated types: value_type, reference, pointer, difference_type, and iterator_category.

The most important feature of traits templates is that they give us a way to associate information with a type non-intrusively. In other words, if your ornery coworker Hector gives you some iterator-like type called hands_off that refers to an int, you can assign it a value_type without disturbing the harmony of your workgroup. All you have to do is add an explicit specialization of iterator_traits, and iter_swap will see the type int when it asks about the value_type of Hector's iterator:^[3]

^[3] For a brief review of template specialization and instantiation, see the Details section at the end of this chapter.

    namespace std


    {


      template <>


      struct iterator_traits<Hector::hands_off>


      {


          typedef int value_type;


          four more typedefs...


      };


    }

This non-intrusive aspect of traits is precisely what makes iterator_traits work for pointers: the standard library contains the following partial specialization of iterator_traits, which describes the value_type of all pointers:

    template <class T>


    struct iterator_traits<T*> {


        typedef T value_type;


        ...four more typedefs


    };

Thanks to the indirection through iterator_traits, generic functions can now access an iterator's associated types uniformly, whether or not it happens to be a pointer.

2.1.3. Finding a Shortcut

While specialization is a perfectly general mechanism, it's not nearly as convenient as adding nested types to classes. Specialization comes with a lot of baggage: You may have to close the namespaces you're working in and open the namespace of the traits template, and then you'll have to write the text of the traits specialization itself. That's not a very efficient use of keystrokes: its nested typedef is the only information that really counts for anything.

Thoughtfully, the standard library provides a shortcut that allows the author of an iterator to control the types nested in its iterator_traits just by writing member types in the iterator. The primary iterator_traits template^[4] reaches into the iterator to grab its member types:

^[4] The C++ standard refers to ordinary template declarations and definitionsas opposed to partial or explicit (full) specializationsas primary templates.

    template <class Iterator>


    struct iterator_traits {


        typedef typename Iterator::value_type value_type;


        ...four more typedefs


    };

Here you can see the "extra level of indirection" at work: Instead of going directly to Iterator:: value_type, iter_swap gets there by asking iterator_traits for the iterator's value_type. Unless some specialization overrides the primary iterator_traits template, iter_swap sees the same value_type as it would have if it had directly accessed a nested type in the iterator.