C++: "Iterable<T>" interface

Question

What I want to achieve is probably easily explained: Consider I have an abstract class that I know will contain multiple objects of known type. However the actual container holding these objects will be implemented in sub-classes.
In my abstract base class I now want to provide an interface to iterate over these objects. Given that I don't know (or rather don't want to fix) the type of container, I thought that iterators would probably be my best bet.

A conceptual declaration of this class might look like this:

class MyClass {
public:
    // Other interface methods, e.g. size()

    virtual Iterable<MyObject> objects() = 0;
};

The intention here is that I'll be able to iterate over the nested objects of my class like this:

MyClass *class = new ImplementationOfClass();
for (const MyObject &obj : class->objects()) {
    // Do stuff with obj
}

The issue I am facing however is that I can't seem to figure out how Iterable<MyObject> should be defined. The key property of this object is that at the time of defining this class I can only specify that the returned value will be iterable (using STL-style iterators) and will yield objects of type MyObject when the used iterator is dereferenced.

Normally I would use an abstract class on its own for this but it seems that this is very tricky (impossible?) since iterators are always passed by value and thus to my knowledge no Polymorphism is possible.

Questions dealing with how to pass arbitrary iterator types as arguments into a function always come up with the "use templates" answer. However I think in my case I can't use templates for that. This assumption might be wrong though, so feel free to correct me.

Essentially the barrier I always run into is that at some point I have to write down the iterator type explicitly which in my case I can't. I thought about using a template for that but this would then inhibit proper Polymorphism (I think?) because the user of that abstract interface seems to have the burden of explicitly initializing the correct template. The whole point of all of this however is that the caller does not have to care about the underlying structure.

---

TL;DR: Is there a way to create an interface class that only promises to be iterable and that dereferencing an iterator will yield an object of type T?

Chitterlings

Usually, this type of polymorphism isn't achieved using runtime polymorphism (i.e. using a common base class) like you see in many other languages. It's achieved at compile-time using templates. It isn't necessarily wrong to do it with inheritance in C++, but as your question shows, it can be difficult, and it can have a performance impact. Have you considered whether or not this approach is actually necessary? If you absolutely need to abstract away the concrete type at runtime, so be it, but usually this is not actually necessary. – Bureau

@FrançoisAndrieux I gues sit is not strictly necessary, but I couldn't come up with a different approach yet. Basically I need something that allows me to create a function that returns something that fits my description of an Iterable<T>. That is I want to be able to use a ranged for loop on it to iterate over the set of objects. The used container to store these objects must not be fixed at the base-class level though. Do you know of other options to achieve something like this? – Chitterlings

If your are actually passing around a base class polymorphically, then it is hard to get out of that. Try to see if you can template your code to pass concrete derived types instead. If that is possible than you may not need a base class anymore and the problem solves itself. Unless the actual type depends on user data, such as from reading a file or from cin inputs, then you can get away from it. If not, then you need a polymorphic solution. – Bureau

Form the question, I gather that the problem is you can't return a polymorphic iterator. That is true, you can't assign a derived type by value to a base type or you get slicing. But you can instead have a simple basic iterator type which, internally, has a pointer to an actual polymorphic implementation. The simple iterator type would simply forward the members to the actual implementation object. Then, the outer iterator type can be passed around by value while still maintaining polymorphic behavior. – Bureau

You might do the other way: virtual void for_each_objects(std::function<void(MyObject&)>) = 0; – Ebon

@FrançoisAndrieux In terms of templating I try to not use it whenever possible as once started it quickly happens that basically everything coming in touch with that needs to be a template as well. The pointer solution however seems quite promising. I'll try to think that through. Thank you! – Chitterlings

@Ebon Yes that is indeed a good idea. It doesn't allow for the nice syntax a range for offers but in terms of functionality this would at least get the job done. Thanks! – Chitterlings

@FrançoisAndrieux thanks to your input I was able to patch something together (see my answer). Thanks again! – Chitterlings

Answer 1

With the help of @FrançoisAndrieux and a hint from https://mcmap.net/q/1714836/-c-polymorphism-and-iterators, I was able to come up with an approach to my problem.

Essentially the idea is to create an iterator-wrapper that stores a function to obtain an object of the given type if given an index. That index is then what is iterated on.

The nice thing about this is that the iterator interface is fixed by specifying the type of object that dereferencing it should return. The polymorphism comes into play by making the member function objects() virtual so that each sub-class can construct the iterator itself, providing a custom function pointer. Thus as long as there is a way to map an index to the respective element in the container (whichever is used), this trick is usable.

Note that you can either directly use pointers to e.g.std::vector<T>::at or create a custom function that will return the respective element.

Here's the implementation for the iterator (The implementation could probably be improved upon but it seems to get the job done):

template< typename T > struct iterator_impl {
    using iterator_category = std::forward_iterator_tag;
    using difference_type   = std::ptrdiff_t;
    using value_type        = T;
    using pointer           = T *;
    using reference         = T &;

    using access_function_t = std::function< T &(std::size_t) >;

    // regular Ctor
    iterator_impl(std::size_t start, access_function_t &func, const void *id)
        : m_index(start), m_func(func), m_id(id) {}

    // function-move Ctor
    iterator_impl(std::size_t start, access_function_t &&func, const void *id)
        : m_index(start), m_func(func), m_id(id) {}

    // copy Ctor
    iterator_impl(const iterator_impl &) = default;

    // move ctor
    iterator_impl(iterator_impl &&other) {
        std::swap(m_index, other.m_index);
        m_func = std::move(other.m_func);
        std::swap(m_id, other.m_id);
    }

    // copy-assignment
    iterator_impl &operator=(const iterator_impl &other) = default;

    // prefix-increment
    iterator_impl &operator++() {
        ++m_index;
        return *this;
    }

    // postfix-increment
    iterator_impl operator++(int) {
        iterator_impl old = *this;
        ++(*this);
        return old;
    }

    bool operator==(const iterator_impl &other) { return m_index == other.m_index && m_id == other.m_id; }

    bool operator!=(const iterator_impl &other) { return !(*this == other); }

    T &operator*() { return m_func(m_index); }

    T *operator->() { return &m_func(m_index); };

protected:
    std::size_t m_index = 0;
    access_function_t m_func;
    const void *m_id = nullptr;
};

Note that I had to introduce the m_id member variable as a means to properly compare iterators (std::function can't be compared using ==). it is meant to be e.g. the address of the container the elements are contained in. Its sole purpose is to make sure that 2 iterators that happen to have the same index but are iterating over completely different sets are not considered equal.

And based on that here's an implementation of an Iterable<T>:

template< typename T > struct Iterable {
    using iterator       = iterator_impl< T >;
    using const_iterator = iterator_impl< const std::remove_const_t< T > >;

    Iterable(std::size_t start, std::size_t end, typename iterator_impl< T >::access_function_t &func, const void *id)
        : m_begin(start, func, id), m_end(end, func, id) {}

    iterator begin() { return m_begin; }
    iterator end() { return m_end; }

    const_iterator begin() const { return m_begin; }
    const_iterator end() const { return m_end; }

    const_iterator cbegin() const { return m_begin; }
    const_iterator cend() const { return m_end; }

protected:
    iterator m_begin;
    iterator m_end;
};

Chitterlings