Generic programming in C++ part 2b: A better example with CComSafeArray and standard containers

In the last post I asked the question "How do you normally copy containers". Let’s explore that.

A typical way would be to use the standard algorithm copy. (Note that there are many ways to copy containers, some are even more efficient, but this one suits the purposes of my explanation)

std::list<long> listOfLongs;

// Fill list here

std::vector<long> vectorOfLongs;
std::copy(listOfLongs.begin(), listOfLongs.end(), std::back_inserter(vectorOfLongs));

copy takes a range and an output iterator. The range is iterated over and each element is copied to the output iterator – after each copy the output iterator is incremented. It’s expected that the ‘thing’ that the ouptut iterator points to can hold all of the elements in the range.

For a vector (or, in fact, any automatically-sized container) this often isn’t what you want. Instead, you often want elements to be added to the container. But how should the algorithm add elements to a container? In fact how can an algorithm add elements to a container when, I’m sure you remember, algorithms don’t know anything about containers! Algorithms only know how to use iterators.

This may not be crystal clear yet so I’m going to make a point of it. Algorithms only know about iterators. They know nothing about containers. This is intentional and A Good Thing. Why? Because by enforcing that limitation algorithms can work for any container you provide – assuming you also provide iterators for that container (and that the iterators meet the requirements of the algorithm).

Now, we were trying to figure out how an algorithm can add elements to a container. The C++ way to do that is via an inserter which, in standardese, is a form of iterator adaptor. An inserter provides an iterator interface for a container. The algorithm ‘sees’ an iterator. But when the algorithm tries to assign to that iterator, the inserter kicks in and does something different. That ‘something different’ depends on what inserter you’re using but ultimately it (usually) adds an element to the container. It also does nothing when the iterator is incremented. If you think about that for a second that’s exactly what we were trying to do.

So how does the inserter know how to add elements to the container? Doesn’t that mean that it needs to know about the specific container type? No. Well, kind of. Inserters are templated on the container type. If we look at the example above, we’re using back_inserter. That particular inserter requires that the supplied container has a push_back method. Conveniently, vector does. Had the inserter been front_inserter, which requires push_front, compilation would have failed because vectors can’t insert elements at the front (efficiently).

So what does all this have to do with CComSafeArray? CComSafeArray is (almost) a container and we’re going to write an inserter to allow us to use them in algorithms when an output iterator is required. That means that we’ll be able to use the standard copy algorithm to copy elements from any container to a CComSafeArray.

template <typename Container>
class add_iterator : public std::iterator<std::output_iterator_tag, void, void, void, void>
{
protected:
    Container& container;

public:
    explicit add_iterator(Container & c) : container(c) {}

    template <typename ValueType>
    add_iterator<Container>&
    operator=(const ValueType& value)
    {
        container.Add(value);
        return *this;
    }

    add_iterator<Container>& operator*()
    {
        return *this;
    }

    add_iterator<Container>& operator++()
    {
        return *this;
    }

    add_iterator<Container>& operator++(int)
    {
        return *this;
    }
};

template <typename Container>
inline add_iterator<Container> add_inserter(Container& c)
{
    return add_iterator<Container>(c);
}

OK, so what’s going on here? An inserter has two parts. There is a class that is the iterator and does all the grunt work. There’s also a templated convenience function that creates and returns an instance of the iterator. That’s a fairly common idiom in the standard (see make_pair) and permits nicer syntax by taking advantage of the fact that templated functions can infer types. We mentioned back_inserter and front_inserter before, these are actually convenience functions that create an instance of the iterator classes back_insert_iterator and front_insert_iterator respectively. Without those convenience functions the syntax would be less appealing and more prone to error. For example, the code above would look like this:

std::copy(listOfLongs.begin(), listOfLongs.end(), std::back_insert_iterator<vector<long> >(vectorOfLongs));

So that explains the add_inserter function. Digging deeper, the add_iterator is actually pretty straightforward. It publically inherits from iterator which is a standard library class that defines a number of useful typedefs that all iterators are required to define. It’s just a convenience class saving you from defining a few things yourself. Assigning does what we described above, that is, it just calls Add (which must exist) on the container (you’ll notice that Add is the method that CComSafeArray provides to append elements). Incrementing (and dereferencing) are no-ops.

I glossed over the fact that assignment operator is a templated function. This usually isn’t necessary because containers are meant to expose the type that they contain. If you dig into any of the standard library provided iterators you’ll find that the type that the assignment operator takes is known. Normally we could have defined the assignment operator like so:

add_iterator<Container>&
operator=(const Container::value_type& value)
{
    container.Add(value);
    return *this;
}

Containers are meant to provide a definition for value_type.

Unfortunately, CComSafeArray doesn’t (hence the reason it’s almost a container) so we have to make the assignment operator a function template. No big problem, it just means that if you try to assign the wrong type via the inserter then your error message may be fairly cryptic – something like: “cannot convert type X to CComSafeArray<T>.Add() where T is Y”.

You may also have picked up that this inserter isn’t actually tied to CComSafeArrays. If you have any other containers that use an Add method to add elements then this inserter will work just as well for them.

And that’s it! We’ve harnessed one of the great strengths of the STL design – extensibility – and created an inserter, a form of iterator adaptor, to a container-like class so that we can make use of existing standard algorithms. Sweet!

Stay tuned for Part 3 where we give the age-old interview question “isPalindrome” a generic workover!