Robert Jones presents an alternative implementation of C++'s std::vector that can be used the absence of templates and exceptions.
Introduction
Templates and the STL are aspects of modern C++ that I'd imagine few of us would want to be without. However that was exactly the environment I encountered in a recent role at an embedded software house.
The company I worked for produced a re-useable software platform, which was required to compile under numerous compilers (some known and some not yet known), and so the company had taken the route of writing their software in a subset of C++ that was known by experience to be supported reliably by all the compilers under consideration. This subset, broadly modeled on Embedded C++, did not include templates, and by implication the STL, nor did it include exceptions.
| Embedded development and compiler features |
|
C++ compilers for embedded environments often lack support for some of the relatively recent additions to the C++ language, most notably templates and exceptions. There can be a number of reasons for this. Some embedded environments are now very mature, and may now have only a small active tool development community. As a result it may not be commercially viable to update their compilers to support these features. Supporting templates and exceptions adds significantly to the complexity of the compiler, so the commercial case to make the investment may not be attractive. However, probably the most common reason for not supporting these features is the obscurity they introduce to the runtime performance. Even with a basic C++ implementation, the apparently simple act of exiting a scope can cause a great deal of activity as a result of stack unwinding and all the destructor calls that may be made. By including exceptions and templates this unseen activity penalty is exacerbated. In the kind of environments where the system must respond within a handful of microseconds this kind of 'under-the-hood' activity can be problematic. |
Lack of access to the STL was a source of frustration to some of the more progressive programmers in the company, most notably the lack of comprehensive and predictable generic containers.
This article looks at providing a substitute for the STL's vector container, which behaves as much like the STL version as possible. Some the techniques used could equally be applied to other containers and other template classes.
Syntax
The syntax of declaring and using the vector should be as close to the STL syntax as possible, and in particular not impose unexpected requirements and dependencies on the build system (e.g., not demanding that scripts generate code). Vectors should be declarable in any scope, for any type (including built-ins) without special syntax or conditions. This is rather harder than it first appears, since to mimic the STL containers the vector must exhibit copy-in/copy-out and copy-internally semantics, but the built-in types do not have copy constructors. Listing 1 shows examples of vector usage.
#include "vector.hpp"
vector(int) myIntVec;
typedef vector( int ) IntVec;
vector(IntVec) myIntVecVec;
namespace MySpace {
typedef vector(char) myCharVec; }
class X { /* ... */ };
vector(X) myXVec;
class Y { vector(X) myNestedXVec; };
|
| Listing 1 |
Design choices
Back in the old days (which I can't recall, of course), the standard way to handle anything generically was void* pointers, and this is the approach used here. A core implementation is written using void* pointers, which is then wrapped in a presentation layer to respect type. To faithfully implement STL vector semantics, the void* implementation must be provided with the means to create and destroy instances of the client type, and this is provided by the presentation layer through callback functions. As an implementation detail, the void* implementation is written to use the Pimpl idiom, both to more fully hide implementation details and to facilitate an efficient no-throw swap() method. The presentation layer is finally implemented by a large macro of single line inline methods which cast type and then call the corresponding method in the core implementation.
Implementation
The core implementation is mainly predicable and straight-forward (Listing 2: VectorCore interface).
class VectorCore
{
public:
typedef void * value_type;
typedef const void * const_value_type;
typedef void * iterator;
typedef const void * const_iterator;
// ...
VectorCore( Traits const & );
VectorCore( VectorCore const & );
~VectorCore( );
VectorCore & operator = (
VectorCore const & );
unsigned size( ) const; // ... and empty
// capacity, etc
value_type operator[]( unsigned ) const;
value_type front( ) const; // ... and back.
iterator begin( ); // ... and end (const
// and non-const)
iterator insert( iterator, const_value_type );
// ...various other function signatures.
void swap( VectorCore & );
private:
struct Impl;
Impl * pimpl;
};
|
| Listing 2 |
All the methods and method signatures in this implementation are easily deducible from an examination of any STL reference, such as Josuttis, with the exception of the constructor signature:
VectorCore::VectorCore( Traits const & )
This is where the characteristics of the client type are made available to the generic implementation, and it turns out that the only information needed by the generic code is the copy constructor, destructor and client type size. To implement the STL's resize(unsigned) method signature would also require that a default constructor be provided, which seems too onerous a requirement to demand of all types when only some types will require the resize() . Using templates, the default constructor and resize signature can be provided or not on a per type basis, but using this implementation technique it is for all types or none. It is of course only that specific signature which is affected, the full resize(unsigned, const_value_type) signature is supported.
The Traits type packages the necessary functions and presents them with void* interfaces for the implementation (Listing 3: Declaration of type traits).
class VectorCore
{
public:
// ...
struct Traits
{
typedef void ( * Ctor )
( value_type, const_value_type );
typedef void ( * Dtor )
( value_type );
Traits( Ctor ctor, Dtor dtor, unsigned size );
Ctor ctor;
Dtor dtor;
unsigned size;
};
// ...
};
|
| Listing 3 |
The method signatures of the Impl pimpl implementation class closely mirror signatures of the VectorCore class, including respecting constness down to the lowest possible level. The final implementation is done with no knowledge of the ultimate client type beyond that passed in generically through the Traits structure. Any copying or deletion of vector elements must manually invoke the appropriate functions to maintain correct copy semantics. In accordance with the requirements of STL vector implementations, this implementation ultimately uses a C-style array, although since the implementation is unaware of type it is an array of char appropriately sized using the size parameter passed in the type traits . It is unnecessary to present the full implementation here, but most of the interesting characteristics of the implementation are illustrated by the reserve() method (Listing 4: Example of a VectorCore method implementation).
bool VectorCore :: Impl :: reserve(
unsigned capacity )
{
if ( capacity > m_capacity )
{
void * data = :: operator new (
capacity * m_traits.size );
for ( unsigned i = 0; i < m_size; ++ i )
{
value_type to = addressOf( data, i );
value_type from = addressOf( m_data, i );
m_traits.ctor( to, from );
m_traits.dtor( from );
}
delete reinterpret_cast<char *>( m_data );
m_data = data;
m_capacity = capacity;
}
return true;
}
|
| Listing 4 |
Wrapping the implementation
With the implementation in place, attention now turns to how to present the functionality to the user in a useful and useable way. In the absence of templates, it is the old and much derided mechanism of the trusty macro to which we now turn (Listing 5: Presenting the container using a macro).
#define vector( TYPE ) \
class VectorOf##TYPE \
{ \
. \
. \
. \
}
|
| Listing 5 |
The core implementation is the only data member of the macro generated class, and made private. An obvious alternative wrapping is to inherit privately from the implementation class, and this was in fact the first approach considered. However, the number of identifiers that it was convenient to reuse from the base class produced lots of name clashes, which could easily be resolved, but which made the macro textually longer and rather more intimidating. On balance, and taking in to account human factors, such as willingness of uptake, this seemed the better alternative. (Listing 6: Introducing the embedded VectorCore .)
#include "VectorCore.hpp"
#define vector ( TYPE ) \
Class VectorOf##TYPE \
{ \
Public: \
typedef VectorCore core_type; \
. \
. \
. \
Private: \
core_type core; \
}
|
| Listing 6 |
This macro generated class must also capture the type's traits and pass them to the implementation. There is a subtlety here in that the built in types do not have a named constructor. To overcome this difficulty, a nested type is declared which has only one data member, which is of the client type. The underlying vector thus becomes a vector of this nested Element type, which always has a named constructor and destructor. (Listing 7: Fulfilling the traits requirements.)
#define vector ( TYPE ) \
class VectorOf##TYPE \
{ \
// ... \
private: \
struct Element \
{ \
static void ctor( \
core_type :: value_type to, \
core_type :: const_value_type from \
) \
{ new ( to ) Element( \
* static_cast<Element const *>( from ) \
); \
} \
static void dtor( core_type :: value_type p )\
{ static_cast<Element *>( p ) -> \
Element :: ~Element( ); } \
\
value_type client; \
}; \
// ... \
}
|
| Listing 7 |
The interesting parts of this structure are the parts we can't see! The default generated copy constructor and destructor provide access to the corresponding methods of the client type, but allow the compiler to handle the special cases of the built-in types. Using this wrapping technique does not impose any penalty of additional copy operations on the client type.
The named methods provided by this wrapping can then be packaged into static methods, with generic ( void* ) signatures. This repackaging makes implicit assumptions, which will also be made by the iterator type, that a pointer to void , client type or Element type can be freely cast between the three types with no corruption introduced. This is broadly equivalent to assuming the wrapping and typing do not impose additional padding or alignment restrictions.
We now have all the basic mechanisms necessary to complete the vector class. To construct a default vector, the constructor must package the necessary traits and pass them down to the core implementation. (Listing 8: Passing traits to the implementation.)
#define vector ( TYPE ) \
class VectorOf##TYPE \
{ \
public: \
// ... \
VectorOf##TYPE ( ) : core( core_type :: Traits( \
Element :: ctor, \
Element :: dtor, \
Element :: assign, \
sizeof( Element ) \
) ) { } \
// ... \
}
|
| Listing 8 |
And provide a full complement of method signatures consistent with the STL vector implementation (Listing 9: Populating the macro class).
#define vector ( TYPE ) \
class VectorOf##TYPE \
{ \
public: \
// ... \
typedef value_type * iterator; \
typedef value_type const * const_iterator; \
// ... \
size_type size( ) const { return core.size( );} // etc,...\
\
value_type & operator[]( unsigned idx ) \
{ return * static_cast<value_type *>( \
core[ idx ] ); } \
value_type const & operator[]( unsigned idx ) const \
{ return * static_cast<value_type const *>( \
core[ idx ] ); } \
value_type front( ) const \
{ return * static_cast<value_type *>( core.front( ) ); } \
value_type back( ) const \
{ return * static_cast<value_type *>( core.back( ) ); } \
\
iterator begin( ) // ... + end, const & non-const \
{ return static_cast<iterator>( core.begin( ) ); } \
void insert( iterator pos, \
const_iterator begin, const_iterator end ) \
{ core.insert( pos, begin, end ); } \
// ...various other function signatures. \
void swap(VectorOf##TYPE & other ) \
{ core.swap( other.core ); } \
// ... \
}
|
| Listing 9 |
Limitations
So what have we achieved, and is it fit for purpose? Well, we have a 'template' for a generic vector , that looks and feels much like the STL's vector , however we should not be misled into believing it is more than it is. This is only a generic container, not a poor man's version of templates. There are many specific limitations.
- The vector may only be instantiated with a type represented by a single identifier. This is only true because the type is used to form the name of the vector type, and if an alternative naming strategy were used, it would possible to instantiate the vector with derived types.
- The vector may only be instantiated once for a given type in a given scope. Again this is because of the vector naming strategy. If multiple instances of an instantiated vector type are required, a typedef may be employed.
- Each instantiation of the vector is a distinct type, unrelated to any other instantiation.
Conclusion
In this article a techniques has been presented to fabricate a template-like generic container in circumstances where templates are not available. Although being far from a perfect solution, the resulting container permits code to be written in a more familiar and contemporary style, and is an advance on the previous home-grown container that it superseded.
