C++ : Using different iterator types in subclasses without breaking the inheritance mechanism

Question

I'm trying to achieve the following: Given an abstract class MemoryObject, that every class can inherit from, I have two subclasses: A Buffer and a BigBuffer:

template <typename T>
class MemoryObject
{
public:

    typedef typename std::vector<T>::iterator iterator;
    typedef typename std::vector<T>::const_iterator const_iterator;

    [...] //Lot of stuff

    virtual iterator begin() = 0;
    virtual iterator end() = 0;
};

A Buffer:

template <typename T>
class Buffer: public MemoryObject<T>
{
public:
    typedef typename std::vector<T>::iterator iterator;
    iterator begin() { return buffer_.begin(); }
    iterator end() { return buffer_.end(); };

    [...] //Lot of stuff

private:
    std::vector<T> buffer_;
};

And finally:

template <typename T>
class BigBuffer: public MemoryObject<T>
{
public:
    [...] //Omitted, for now

private:
    std::vector<Buffer<T>*> chunks_;
};

As you can see, a BigBuffer holds a std::vector of Buffer<T>*, so you can view a BigBuffer as an aggregation of Buffer(s). Futhermore, I have a bunch of functions that must work of every MemoryObject, so this is a real signature:

template <class KernelType, typename T>
void fill(CommandQueue<KernelType>& queue, MemoryObject<T>& obj, const T& value)
{
   //Do something with obj
}

What's the point? - You may ask. The point is that I must implement iterators over these classes. I've already implemented them for Buffer, and is exactly what I need: be able to iterate over a Buffer, and access to ranges (for example b.begin(), b.begin() + 50). Obviously I can't do the same for BigBuffer, because the real data (that is inside each Buffer' private variable buffer_) is scattered accross the memory. So I need a new class, let's call it BigBufferIterator, which can overload operator like * or +, allowing me to "jump" from a memory chunk to another without incurring in in segmentation fault.

The problems are two:

1. The iterator type of MemoryObject is different from the iterator type of BigBuffer: the former is a std::vector<T>::iterator, the latter a BigBufferIterator. My compiler obviously complains
2. I want be able to preserve the genericity of my functions signatures passing to them only a MemoryObject<T>&, not specializing them for each class type.

I've tried to solve the first problem adding a template parameter classed Iterator, and giving it a default argument to each class, with a model loosely based to Alexandrescu's policy-based model. This solution solved the first issue, but not the second: my compiled still complains, telling me: "Not known conversion from BigBuffer to MemoryObject", when I try to pass a BigBuffer to a function (for example, the fill() ). This is because Iterator types are different..

I'm really sorry for this poem, but It was the only way to proper present my problem to you. I don't know why someone would even bother in reading all this stuff, but I'll take pot luck.

Thanks in advance, only just for having read till this point.

Humbly, Alfredo

Answer 1

I encountered the same problem in a different context; let me restate it.

1. You have a Base class (which could be abstract), which is iterable via its BaseIterator.
2. You have a Child subclass, which differs in implementation slightly, and for which you have a different specialized ChildIterator.
3. You have custom functions that work with Base, and rely on its iterability.
4. It is not feasible to generate a template specialization of the custom functions for each subclass of Base. Possible reasons may be:
   • huge code duplication;
   • you distribute this code as a library and other developers are going to subclass Base;
   • other classes will take some reference or pointer to Base and apply those custom functions, or more generically:
   • Base implements some logic that is going to be uses in contexts where do not know any of the subclasses (and writing completely templated code is too cumbersome).

---

Edit: Another possibility would be using type erasure. You would hide the real iterator that you're using behind a class of a fixed type. You would have to pay the cost of the virtual functions call though. Here is an implementation of a any_iterator class which implements exactly iterator type erasure, and some more background on it.

---

The only effective solution I could find was to write a multi-purpose iterator that can iterate over all possible containers, possibly exploiting their internals (to avoid copy-pasting the iterator code for every subclass of Base):

// A bigger unit of memory
struct Buffer;

class Iterator {
    // This allows you to know which set of methods you need to call
    enum {
        small_chunks,
        big_chunks
    } const _granularity;

    // Merge the data into a union to save memory
    union {
        // Data you need to know to iterate over ints
        struct {
            std::vector<int> const *v;
            std::vector<int>::const_iterator it;
        } _small_chunks;

        // Data you need to know to iterate over buffer chunks
        struct {
            std::vector<Buffer *> const *v;
            std::vector<Buffer *>::const_iterator it;
        } _big_chunks;
    };

    // Every method will have to choose what to do
    void increment() {
        switch (_granularity) {
            case small_chunks:
                _small_chunks.it++;
                break;
            case big_chunks:
                _big_chunks.it++;
                break;
        }
    }

public:
    // Cctors are almost identical, but different overloads choose
    // different granularity
    Iterator(std::vector<int> const &container)
        : _granularity(small_chunks) // SMALL
    {
        _small_chunks.v = &container;
        _small_chunks.it = container.begin();
    }
    Iterator(std::vector<Buffer *> const &container)
        : _granularity(big_chunks) // BIG
    {
        _big_chunks.v = &container;
        _big_chunks.it = container.begin();
    }

    // ... Implement all your methods
};

You can use the same class for both Base and Child, but you need to initialize it differently. At this point you can make begin and end virtual and return an Iterator constructed differently in each subclass:

class Base {
public:
    virtual Iterator begin() const = 0;
};

class IntChild : public Base {
    std::vector<int> _small_mem;
public:
    virtual Iterator begin() const {
        // Created with granularity 'small_chunks'
        return Iterator(_small_mem);
    }
    // ...
};

class BufferChild : public Base {
    std::vector<Buffer *> _big_mem;
public:
    virtual Iterator begin() const {
        // Created with granularity 'big_chunks'
        return Iterator(_big_mem);
    }
    // ...
};

You will pay a small price in performance (because of the switch statements) and in code duplication, but you will be able to use any generic algorithm from <algorithm>, to use range-loop, to use Base only in every function, and it's not stretching the inheritance mechanism.

// Anywhere, just by knowing Base:
void count_free_chunks(Base &mem) {
    // Thanks to polymorphism, this code will always work
    // with the right chunk size
    for (auto const &item : mem) {
        // ...this works
    }
    // This also works:
    return std::count(mem.begin(), mem.end(), 0);
}

Note that the key point here is that begin() and end() must return the same type. The only exception would be if Child's methods would shadow Base's method (which is in general not a good practice).

One possible idea would be to declare an abstract iterator, but this is not so good. You would have to use all the time a reference to the iterator. Iterator though are supposed to be carried around as lightweight types, to be assignable and easily constructible, so it would make coding a minefield.

Answer 2

They way to go is to use the most general definition as the iterator type of the base. That is, you want to treat the data in a Buffer as just one segment while the BigBuffer is a sequence of the corresponding segments. This is a bit unfortunate because it means that you treat your iterator for the single buffer in Buffer as if it may be multiple buffers, i.e. you have a segmented structure with just one segment. However, compared to the alternative (i.e. a hierarchy of iterators with virtual functions wrapped by a handle giving value semantics to this mess) you are actually not paying to bad a cost.