C++, polymorphism and iterators

Question

I want to have a Storage interface(abstract class) and a set of Storage implementations (SQLite, MySQL, Memcached..) for storing objects of a known class and retrieving subsets from the Storage.
To me the clear interface would be:

class Storable{int id; blah; blah; blah; string type;};
class Storage{
    virtual Storage::iterator get_subset_of_type(string type) = 0;
    virtual Storage::iterator end)_ = 0;
    virtual void add_storable(Storable storable) = 0;
};

And then create implementations of Storage that fulfill the interface. Now, my problem is the following:

• Iterators can't be polymorphic as they are returned by value.
• I can't just subclass Storage::iterator for my given Storage implementation
• I thought about having a wrapper iterator that wraps and does pimpl over a polymorphic type that the Storage implementations subclass, but then I need to use dynamic memory and allocate all over the place.

Any hint?

Tuckie

Answer 1

If you want a virtual interface for iteration, something like this?

#include <iostream>
#include <iterator>

struct Iterable {
    virtual int current() = 0;
    virtual void advance() = 0;
  protected:
    ~Iterable() {}
};

struct Iterator : std::iterator<std::input_iterator_tag,int> {
    struct Proxy {
        int value;
        Proxy(const Iterator &it) : value(*it) {}
        int operator*() { return value; }
    };
    Iterable *container;
    Iterator(Iterable *a) : container(a) {}
    int operator*() const { return container->current(); }
    Iterator &operator++() { container->advance(); return *this; }
    Proxy operator++(int) { Proxy cp(*this); ++*this; return cp; }
};

struct AbstractStorage : private Iterable {
    Iterator iterate() {
        return Iterator(this);
    }
    // presumably other virtual member functions...
    virtual ~AbstractStorage() {}
};

struct ConcreteStorage : AbstractStorage {
    int i;
    ConcreteStorage() : i(0) {}
    virtual int current() { return i; }
    virtual void advance() { i += 10; }
};

int main() {
    ConcreteStorage c;
    Iterator x = c.iterate();
    for (int i = 0; i < 10; ++i) {
        std::cout << *x++ << "\n";
    }
}

This isn't a complete solution - I haven't implemented Iterator::operator==, or Iterator::operator-> (the latter is needed if the contained type is a class type).

I'm storing state in the ConcreteStorage class, which means we can't have multiple iterators on the same Storage at the same time. So probably rather than Iterable being a base class of Storage, there needs to be another virtual function of Storage to return a new Iterable. The fact that it's only an input iterator means that copies of an iterator can all point to the same Iterable, so that can be managed with a shared_ptr (and either Itertable should have a virtual destructor, or the newIterator function should return the shared_ptr, or both).

Schizogenesis

Answer 2

I fail to see the benefit in Storage being polymorphic.

Anyway, note that the iterator doesn't have to polymorphic at all.

It just has to use virtual methods from the Storage class for it's functionality. These methods can be then easily overridden in the descendants (creating desired functionality).

Sidky

The polymorphic behaviour is needed because I'll have several storages wich will need to be swapable at runtime, like primary<=>secondary and they can be of different type. – Tuckie

@Arkaitz You still don't need polymorphism for that, you would need polymorphism if you had no idea what the specific storages actually are/do. – Palladian

thats the point, I might be working with a primary(sqlite) and a secondary(memcached) and then swap them on runtime, so I need to use the common interface and thus polymorphism there, because at any given moment I don't know which type my primary or secondary are. – Tuckie

Thanks to this hint I was able to figure out how to implement something like a Iterable<T> "interface": https://mcmap.net/q/1775819/-c-quot-iterable-lt-t-gt-quot-interface – Sentence

Answer 3

I'm not exactly sure why this is a problem. You just need to implement all the iterator operators (increment, dereference, etc.) so that they call a virtual method of the Storage object.

Heteropterous

Answer 4

The fact that you're using a database engine to do the storing doesn't change the fact that what you have here is fundamentally a container class.

In short, you should almost certainly be using a class template that's instantiated over the type of object being stored. The variation in storage engines could be handled either via inheritance or by a second template argument. Using a template argument gives compile-time polymorphism, while inheritance gives run-time polymorphism (i.e., you can change storage engines at run-time).

You might want to look at DTL for some inspiration (or you might save yourself a lot of trouble, and just use it until or unless you run into a problem with it).

Sling

Well, thats exactly what I am trying to do, use inheritance to handle the different engines, I am just having problems on how to iterate the subsets properly as I can't just inherit and override iterators. – Tuckie

@Arkaitz: like I said, you should probably look at the general design of DTL. In any case, storage engine variation is orthogonal to variation in the type stored, and the latter is the one that determines the type of an iterator. – Sling

you can, if the state in the iterators is the same (i.e. just override methods of the iterator) – Cache

@jerry, i think his point is that the iterator is specific to the Storage, rather than the Storable? – Cache

@Jerry Coffin, you are stating that the stored type dictates the iterator? by itself? As I see thats not true as vector<int>::iterator is not the same as list<int>::iterator although the stored type is the same. In the end the iterator ::operators have to deal with the storage internals or delegate somehow. – Tuckie

@Arkaitz: yes, but that's because list::iterator and vector::iterator deal directly with underlying data. In your case, you have a hierarchy of storage engine classes, and the iterator is just going to use the abstract interface defined in the base class. Therefore an iterator needs the type of the stored object, and an instance of a storage object, but (as long as it's in the hierarchy) it doesn't care which storage object it uses. – Sling

Yes, if you assume that the solution to my problem is making the iterators use the abstract class, then you are right. But my first approach was to find a way of each Storage to provide an iterator implementation to avoid cluttering the Storage Interface with iterator tasks. – Tuckie

@Arkaitz: your public Storage interface doesn't have to contain the functions used by the iterator. You could for example define a separate, private base class to contain those pure virtual functions, and have the Storage object pass itself to the iterator as a pointer to that base class. – Schizogenesis

@Arkaitz: 1) for the most part, the iterator is the interface to the underlying class. 2) the iterator is normally nested in (or made a friend of) what it's iterating, so what it uses doesn't need to be part of the (public) interface. – Sling

Answer 5

It seems to be a case of dynamic allocation versus ability to change the iterator's state size (without recompiling clients).

Cache

Specifically, if an ability to change the iterator's state's size without recompiling code that uses the iterator is necessary, then dynamic allocation is unavoidable. Otherwise, using some variant of codesynthesis.com/~boris/blog/2010/07/20/… might be not-too-ugly. – Cache

Answer 6

You may try boost::iterator, several adapters and facades are provided.

http://www.boost.org/doc/libs/1_45_0/libs/iterator/doc/index.html

Onehorse

Answer 7

Take a look at adobe::any_iterator or some other implementation of any_iterator (http://thbecker.net/free_software_utilities/type_erasure_for_cpp_iterators/any_iterator.html). It implements a polymorphic iterator concept but you still deal with any_iterator by value (return by value, pass by value, etc).

Fitzger

Answer 8

Your algorythms' code that actualy uses different types of containers has to be written in template functions (possibly member functions), who get the types through the template's parameters. That resolves at compile time. And the exact iterator type is known for each instanciation of that template function.

If you really need a runtime resolution, you need to add a dispatch to call different instanciations of the above template function. A virtual function should call the actual algorythm template function, but that would be a virtual function override in some template class (i.e. the virtual function will be compiled separately for each instanciation and call a different instanciation of the algorythm template function). If you need a double/multiple dispatch, so be it. Too bad that c++ doesn't support function to be virtual on multiple parameters, you'll have to use any of the common idioms for double dispatch. But the call for the actual algorythm function should be after the dispatch is resolved.

Rosemarierosemary