Views Implementation

In this section we will explain some of the template techniques we use to implement the library. We use traits [7,2] and template metaprogramming [10,14] for computing internally needed types and sensible default template parameters. In particular these defaults make the flexibility of the VTL manageable and usable.

The template metaprogramming and traits techniques are used to simplify declaring views by deducing the minimum iterator functionality of two container types. For example to make a union view (concatenation head to tail of two containers) of a linked list and a vector, the iterator category would be bidirectional as the linked list has the lowest common denominator.

In order to make intelligent deductions like this in VTL we first create a template metafunction designed to select the minimum value of two integers by using the intialization of an enum.

// Compute the minimum of two
// integers at compile time.
template<int a, int b> 
struct min_traits 
{ enum { x = a<b? a: b }; };

Now we create a template which given a type sets an enum to a value. The name x for the enum value was arbitrary but must be known by the template which does the final value evaluation. Then we assign a value for each STL iterator type in ascending order from least functionality to most functionality by creating specializations of our iterator_tag_mapping template.

// Mapping iterator tags to integers.
template <class T> 
struct iterator_tag_mapping 
{ enum { x = 0 }; }; // default

template<> 
struct iterator_tag_mapping<std::input_iterator_tag>
{ enum { x = 1 }; };

template<> 
struct iterator_tag_mapping<std::forward_iterator_tag> 
{  enum { x = 2 }; };

template<> 
struct iterator_tag_mapping<std::bidirectional_iterator_tag> 
{ enum { x = 3 }; };

template<> 
struct iterator_tag_mapping<std::random_access_iterator_tag> 
{ enum { x = 4 }; };

Now we define a template class which given a value will return the iterator category associated with it. Notice that the values must be the same as those we used for the template iterator_tag_mapping. This is an inverse template question to iterator_tag_mapping.

// Mapping integers to iterator tags.
template<int x> 
struct mapping_iterator_tag 
{ typedef void type; };

template<> 
struct mapping_iterator_tag<1>   
{ typedef std::input_iterator_tag type; };

template<> 
struct mapping_iterator_tag<2>   
{ typedef std::forward_iterator_tag type; };

template<> 
struct mapping_iterator_tag<3>   
{ typedef std::bidirectional_iterator_tag type; };

template<> 
struct mapping_iterator_tag<4>   
{ typedef std::random_access_iterator_tag type; };

Next we define a template class which will take our two internal template mapping classes and do the work of defining a typename based on our lookup critera. Namely, the lesser category type of the two iterator types. This kind of technique was invented in the context of type promotion [4,15].

// Given two types and priority
// mappings to and from integers,
// compute the lower type.
template <class A, class B,
          template<class T> class map,
          template<int x>   class inv>
struct combine_traits {
  typedef typename 
      inv<min_traits<map<A>::x,
                     map<B>::x>::x
         >::type
    type;
};

In the template combine_traits, we used template template parameters instead of specifying the actual classes, iterator_tag_mapping, and mapping_iterator_tag so that we could reuse the template combine_traits for further rank selection tasks. All that would be required is to write new tag2map and map2tag templates with the appropriate specializations and values.

Now we make an intermediate template in case we only need to compare two categories, and not the iterators.

// Given two iterator categories,
// compute the lower one.
template <class cat_a, class cat_b>
struct combine_iterator_categories
  : public combine_traits<
             cat_a,
             cat_b,
             iterator_tag_mapping,
             mapping_iterator_tag
           > 
{};

Finally we create the template which combines all our internal workings so that only the two iterator types are the required inputs.

// Given two iterator types,
// compute the lower category.
template<class A, class B>
struct combine_iterator_tags
  : public combine_iterator_categories<
             iterator_traits<A>::iterator_category,
             iterator_traits<B>::iterator_category,
          > 
{};

For specifying the ownership and mutability features, VTL uses the tag classes external_ownership, shared_ownership, aggregated_ownership, and referenced_ownership, and const_view_tag, mutable_elements_tag, and mutable_view_tag, respectively.

From the container type and the actual tag classes specifying the desired features of the view, type generators deduce the correct smart pointer type for referencing the underlying container as well as correct view constructor argument types.

This is how the actual transform_view is defined:

template <class container,
          class transformation,
          class const_tag = const_view_tag,
          class ownership_tag = external_ownership,
          class T = typename transformation::result_type>
class transform_view;

A user of the transform_view with exclusive ownership by aggregation would declare it like this:

transform_view<ContainerType, 
               TransformationResult (*)(DataType),
               const_tag,
               aggregated_ownership,
               TransformationResult > OwnedTransform;

The smart pointer type selection is based on the ContainerType, the const_tag and the ownership_tag.

Of course, the smart pointer could have been defined directly by a template argument, e.g.

template <class container,
          class transformation,
          class const_tag = const_view_tag,
          class smart_pointer = container const*,
          class T = typename transformation::result_type >
class transform_view2;

A user could declare a transform_view2 with shared ownership instead of the default external ownership as

transform_view2<ContainerType, 
                TransformationResult (*)(DataType),
                const_view_tag,
                boost::shared_ptr<ContainerType const>,
                TransformationResult >

This simpler solution exposes implementation details, contains redundant information about the access properties, and does not provide intelligent defaults for the smart pointer.

Duplicate specification information is a potential source of confusion and errors and should be avoided if possible. The use of type generators, while not required to implement ownership attributes, eases their use and decouples implementation from usage.