C++ class hierarchy for collection providing iterators

Question

I'm currently working on a project in which I'd like to define a generic 'collection' interface that may be implemented in different ways. The collection interface should specify that the collection has methods that return iterators by value. Using classes that wrap pointers I came up with the following (greatly simplified):

Collection.h

class Collection
{
    CollectionBase *d_base;
public:
    Collection(CollectionBase *base);

    Iterator begin() const;
};

inline Iterator Collection::begin() const
{
    return d_base->begin();
}

CollectionBase.h

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

Iterator.h

class Iterator
{
    IteratorBase *d_base;
public:
    bool operator!=(Iterator const &other) const;
};

inline bool Iterator::operator!=(Iterator const &other) const
{
    return d_base->operator!=(*other.d_base);
}

IteratorBase.h

class IteratorBase
{
public:
    virtual bool operator!=(IteratorBase const &other) const = 0;
};

Using this design, different implementations of the collection derive from CollectionBase and can return their custom iterators by returning an Iterator that wraps some specific implementation of IteratorBase.

All is fine and dandy so far. I'm currently trying to figure out how to implement operator!= though. Iterator forwards the call to IteratorBase, but how should the operator be implemented there? One straightforward way would be to just cast the IteratorBase reference to the appropriate type in implementations of IteratorBase and then perform the specific comparison for the implementation of IteratorBase. This assumes that you will play nice and not pass two different types of iterators though.

Another way would be to perform some type of type checking that checks if the iterators are of the same type. I believe this check will have to be made at run-time though, and considering this is an iterator I'd rather not perform expensive run time type checking in operator!=.

Am I missing any nicer solutions here? Perhaps there are better alternative class designs (the current design is an adaptation from something I learned in a C++ course I'm taking)? How would you approach this?

Edit: To everyone pointing me to the STL containers: I am aware of their existence. I cannot use these in all cases however, since the amounts of data I need to process are often enormous. The idea here is to implement a simple container that uses the disk as storage instead of memory.

Answer 1

I can advice you add to iterator a virtual 'entiy-id' function, and in operator!= checks this->entity_id () and other.entity_id () (my example, 'position' function is such 'entity-id' function).

Answer 2

If you want to use inheritance for your iterators, I would recommend you to use a different approach than STL's begin()/end().

Have a look on IEnumerator from .NET framework, for example. (MSDN documentation)

Your base classes can look like this:

class CollectionBase
{
    // ... 
    virtual IteratorBase* createIterator() const = 0;
};

class IteratorBase
{
public:
    virtual bool isEnd() const = 0;
    virtual void next() const = 0;
};

// usage:
for (std::auto_ptr<IteratorBase> it = collection.createIterator(); !it->isEnd(); it->next)
    {
    // do something
    }

If you want to stay with begin()/end(), you can use dynamic_cast to check that you have a right type:

class MyIteratorBaseImpl
{
public:
    virtual bool operator!=(IteratorBase const &other) const
    {
       MyIteratorBaseImpl * other2 = dynamic_cast<MyIteratorBaseImpl*>(&other);
       if (!other2)
          return false; // other is not of our type

       // now you can compare to other2
    }
}

Answer 3

This is not the way you should be using C++. I strongly suggest you investigate the standard library container classes, such as std::vector and std::map, and the use of templates. Inheritance should always be the design tool of last resort.

Answer 4

Please do mimic the STL way of doing containers. That way, it would be possible to e.g. use <algorithm> with your containers.