Generics without Templates - Revisited

In my last article on this topic [Jones08], I explored a method of creating an STL-like vector container, without making use of templates, for circumstances in which the template features C++ are not available.

In this article I shall extend the techniques explored previously, to include other containers and more importantly their ability to inter-operate, and finally examine a restricted, but still useful, implementation of some basic STL algorithms using these containers.

Review

By the conclusion of the first part of this article we had seen how to create an STL-like vector container, using a macro to generate a typed interface and then exploiting code-hoisting techniques to abstract a single, common implementation.

The resulting vector type could be used in this fashion, and offered the dynamic resizing and iteration capabilities of the STL vector (Listing 1).

    #include "vector.hpp"
    typedef vector( unsigned ) IntVector;
    IntVector v;
    // Populate v;
    for (
       IntVector::iterator i=v.begin();
       v!=v.end(); ++i )
    {
      printf( "%u\n", *i );
    }
 

Using similar techniques it is possible to create an analogue of the STL list container, and then things become rather more interesting.

Both the vector and list containers have methods such as

      void insert( position, first, last );

in which the range first...last may be bounded by iterators of any type, including pointers. In the vector, iterators are indeed typedef'd as pointers (although there are exceptions to this, e.g. checked iterators), so the issue does not usually arise, but for other containers the semantics of their iterators are quite different. Iterators themselves must contain the semantics of how to move and compare them.

Towards a better Iterator

The behaviour required of iterators is essentially polymorphic - the concept of moving or comparing is common to all iterators, but the implementation of that concept for different iterators (aka different containers) varies.

The natural approach to implementing polymorphic behaviour would be to use inheritance - an abstract base iterator class, and various concrete derived classes to iterate over the various containers; however this approach is fatally flawed. Firstly, iterators are passed by value, and to do otherwise would be a sufficiently subtle departure from expected behaviour based on the STL to be folly, and consequently suffer from the slicing problem [Meyers]. Secondly, the ultimate intent of this work includes implementing some elementary STL-like algorithms, such as find(). find() returns an iterator of the same type as its range parameters. While, in the absence of templates, it is inevitable that find() must be overloaded for containers of many different types, it is undesirable to have to overload find() for many different containers of many different types, since this is an unbounded group in two orthogonal directions. Consequently, iterators over a collection of a single given type must be of a single given type.

However, inheritance still provides the mechanism for customization of behaviour, through a policy class wrapped by an iterator facade. The policy class expresses the essential operations necessary to implement a sufficiently general iterator (Listing 2).

    struct AnyIteratorPolicy
    {
      typedef int difference_type;
      virtual void const * client(
         void const * ) const = 0;
      virtual void increment(
         void const * & ) const = 0;
      // & decrement, advance etc.,
      // all const & non-const
      virtual bool equal(
         void const *, void const * ) const = 0;
      virtual difference_type distance(
         void const *, void const * ) const = 0;
      virtual ~AnyIteratorPolicy( ) { }
    };

A pointer to policy is then wrapped by a generic void * iterator core (Listing 3).

    struct iterator_core
    {
      iterator_core( AnyIteratorPolicy const *,
         void * );
      iterator_core & operator ++ ( );
      iterator_core & operator -- ( );
      // & +=, -=, +, -, equal etc.
      void * value( ) const;
    private:
      AnyIteratorPolicy const * m_policy;
      void * m_value;
    };

And finally a type-aware macro is wrapped around the core iterator to provide the necessary type information, which turns out to be just the size of the type for iterators. See Listing 4.

    #define DEFINERANDOMITERATOR( const_iterator,  \
       iterator, type )                            \
    struct iterator                                \
    {                                              \
      typedef type value_type;                     \
      typedef iterator_core core_type;             \
      typedef core_type :: difference_type         \
         difference_type;                          \
      iterator(                                    \
         value_type * value,                       \
         AnyIteratorPolicy const * policy ) :      \
         m_core( policy, value )                   \
         { }                                       \
      iterator & operator ++ ( )                   \
         { ++ m_core; return * this; }             \
      /* also --, +=, -=, +, -, ->, deref etc. */  \
    private:                                       \
      core_type m_core;                            \
    }

For the sake of brevity much has been omitted from these code snippets; both iterator core and wrapper must also exist in const versions, both need the full gamut of comparison operators, and a chain of methods must also be present to facilitate dereferencing, which must also be supported in the policy since dereferencing a vector iterator may be very different to dereferencing a list iterator.

Naturally nothing comes for free, and there is a price to pay for this flexibility. Iterators are now at least twice the size of a pointer, and every dereference introduces at least an extra virtual function call.

All of this can now be packaged to make it more useable with a few macros (Listing 5).

    #define concat3( a, b, c ) a ## _ ## b ## _ ## c
    #define i_category( category, type ) concat3(    \
       category, type, iterator )
    #define const_i_category( category, type )       \
       concat3( category, type, const_iterator )
    #define random_iterator( type ) i_category(      \
       random, type )
    #define random_const_iterator( type )            \
       const_i_category( random, type )
    #define ITERATORS( type )                        \
       DEFINERANDOMITERATOR(
       random_const_iterator( type ),
    random_iterator( type ), type );                 \
       DEFINERANDOMCONSTITERATOR(                    \
       random_const_iterator( type ),
    random_iterator( type ), type );
    ITERATORS( bool );
    ITERATORS( char );
    ITERATORS( short );
    ITERATORS( int );
    ITERATORS( unsigned );
    ITERATORS( long );
    ITERATORS( float );
    ITERATORS( double );

Subsequently, when creating a new type over which it may be required to iterate, all that is required for a type A is that its header file #includes the iterator header, and appends a single line:

      ITERATORS( A );

Inspection of the names chosen in the macros above suggests that in practice the definition of the full set of iterators is a little more complex, and this is true. However, the additional complexity is essentially rote-repetition of the approach described, and presents no new issues.

Iterator policy lifetime

The core iterator illustrated above contains a pointer to iterator policy, which naturally raises the issue of ownership and lifetime of the pointee. The policy may not, of course, be a contained member of the iterator, since the precise type of the policy varies for different containers, whereas the iterator must be a constant type for all containers of a given type. For iterators over containers the policy may be a member of the container, since the valid lifetime of the iterator can never exceed the lifetime of the container over which it iterates. Native pointers converted to iterators present a special case which will be examined separately.

Container changes

Changes to the container interfaces are now very minor, although reflecting more substantial changes to the implementation. Previously the vector container simply typedef'd pointers to create its nested iterator type (Listing 6). Now, using the macros above this becomes Listing 7.

    #define vector ( TYPE )                        \
      class VectorOf##TYPE                         \
      {                                            \
      public:                                      \
        // ...                                     \
        typedef value_type * iterator;             \
        typedef value_type const * const_iterator; \
        // ...                                     \
      }

   #define vector ( TYPE )                        \
      class VectorOf##TYPE                         \
      {                                            \
       public:                                     \
         // ...                                    \
         typedef random_iterator( TYPE ) iterator; \
         typedef random_const_iterator( TYPE )     \
         const_iterator;                           \
         // ...                                    \
        }

With iterators as common types across all containers, and with each iterator containing the knowledge of how to iterate over its owning container, we can now use our containers in this fashion. (See Listing 8.)

    #include "vector.hpp"
    #include "list.hpp"

    list( unsigned ) l;
    vector( unsigned ) v;
    //...populate l...
    v.assign( l.begin( ), l.end( ) );

Algorithms

The containers and iterators of the STL would be of little use without the algorithms that operate on them. Simulating STL algorithms without using templates in general is beyond the scope of this article, and presents some difficult challenges. The root cause of difficulty is that algorithms are functions, in contrast to containers which are classes, and so benefit from implicit instantiation.

However by imposing some fairly draconian restrictions on the facility, and explicitly specifying types in circumstances where a templated facility could deduce them, some usefulness can be gained. Specifically, many useful algorithms, such as find_if(), accept unary predicates, i.e., functions taking one parameter and returning bool, and that is a sufficiently specific signature to make a macro generated base class acceptable. (Listing 9.)

    #define unary_function( arg, ret ) concat4(     \
       unary, ret, fn, arg )
    #define unary_functor( arg, ret )  concat4(   \
       unary, ret, ftor, arg )
    #define DEFINE_FUNCTION( fn, arg, ret )       \
        typedef ret ( * fn )( arg & );            \
    #define DEFINE_FUNCTOR( STRUCT, arg, ret )    \
      struct STRUCT                               \
      {                                           \
        typedef arg argument_type;                \
        typedef ret return_type;                  \
        virtual return_type operator( )(          \
        argument_type & ) = 0;                    \
        virtual ~STRUCT( ) { }                    \
      }
    #define DEFINE_FUNCTORS( arg_type, ret_type ) \
    DEFINE_FUNCTION(                              \
       unary_function( arg_type, ret_type ),      \
       arg_type, ret_type );                      \
    DEFINE_FUNCTOR(                               \
       unary_functor( arg_type, ret_type ),       \
       arg_type, ret_type );
    DEFINE_FUNCTORS( bool, bool );
    DEFINE_FUNCTORS( char, bool );
    DEFINE_FUNCTORS( short, bool );
    DEFINE_FUNCTORS( int, bool );
    DEFINE_FUNCTORS( unsigned, bool );
    DEFINE_FUNCTORS( long, bool );
    DEFINE_FUNCTORS( float, bool );
    DEFINE_FUNCTORS( double, bool );

This kind of approach can be extended arbitrarily, but quickly becomes unwieldy and difficult to maintain. However, defining sufficient unary predicates to implement some basic algorithms is manageable and useful.

With solid iterators and predicates written, algorithms follow a similar pattern, and are fairly straightforward. (Listing 10.)

    #define DEFINE_FIND_IF_FTOR( Iterator,         \
      Predicate )                                  \
      Iterator find_if(                            \
      Iterator first,                              \
      Iterator last,                               \
      Predicate & p                                \
      )                                            \
      {                                            \
        for ( ; first != last; ++ first )          \
          if ( ( p( * first ) )                    \
            break;                                 \
          return first;                            \
      }

These, as with functors, must be explicitly 'instantiated' before use. There are some subtleties here to do with constness of iterators, predicate arguments, and whether the algorithm is a mutating one, which makes a full working implementation of these techniques quite extensive. However, with care, and a few encapsulated const casts, STL-like behaviour can be substantially achieved.

Dealing with pointers

Pointers present some special challenges because the semantics of their operators cannot be changed. One possible approach would be to make iterators implicitly constructible from the corresponding pointer, but this would require the iterator to 'own' its own pointer policy, and so necessitate either copying the policy each time the iterator is copied, or holding it by counted pointer, which would involved a memory allocation for each iterator construction. Neither of these is considered an attractive option.

Instead, it is quite simple to overload all algorithms taking a range, and similarly all container methods taking ranges, with pointer versions. These versions are thin wrappers, but most importantly supply the iterator policy, and use the knowledge that the policy need only exist for the lifetime of the algorithm call.

Conclusion

With all of these facilities defined, some remarkably STL-like code can be compiled.

      #include "vector.hpp"
      int a[] = { 0, 1, 2, 3, 4 };
      vector(int) v( a, a + sizeof(a)/sizeof(int) );
      v.erase( remove( v.begin(), v.end(), 3 ),
         v.end() );

To this extent this work has met the original objectives of providing STL-like containers and the algorithms to use them in environments that do not support templates. The alternative techniques employed, those of nested macros and virtual functions, have their own costs and drawbacks, and in the environments where templates are unavailable may be equally unacceptable. The resulting code is brittle, and the macro generation techniques that make this even moderately amenable to comprehension produces a lot of redundant code artefacts.

However it is achieved, the flexibility and interoperability of iterators comes at a cost.

Author's note

Since producing the code described in this article I have moved on to other work, and in particular have become very much more familiar with the state of the art of template programming, and in particular the amazing work that has been done in the Boost libraries. Having had the opportunity to understand the full capabilities of templates, the work described here seems a very poor imitation of compiler templates.

If I were in this position again, I would push much harder for adoption of templates, with far greater understanding of the productivity benefits they can bring.

References

[Jones08] 'Generics Without Templates', Overload 83

[Meyers] Effective STL, item 38