You need to throw out inheritance based polymorphism. C++ iteration in the standard library and in for(:) loops assumes value-based iterators, and inheritance based polymorphism doesn't work with value-based iterators.
Instead of inheritance-based polymorphism, you should use type-erasure based polymorphism. This requires a bit of boilerplate, because the need abstractly deal with an iterable range was found to be not that common in C++ and often a serious performance hit.
But I'll show you how.
Type erasure based polymorphism is like std::function.
One concrete approach to type-erased polymorphism:
You determine what interface you want to support. Call this your "type erasure target". Your type erasure target is not a class with virtual and =0, but rather a set of functions, methods and operations you want to support, and their signature, and a description of what each does.
Then you write a value class that implements that interface (again, no inheritance) that contains a pImpl (see pImpl pattern) that it dispatches its operations to (the pImpl need not match the same interface, it just needs primitives that you can implement the operations in terms of. Being minimal here is worthwhile).
The pImpl type does have virtual methods and =0 abstract methods.
Then you write a constructor or factory function that takes an object that supports the interface you want to, and generates a concrete instance of the pImpl, then wraps the value class around it.
Suppose the type erasure target was "print to a stream".
My type erasure target is std::ostream& << foo works, and prints stuff.
struct printable_view {
// dispatch to pimpl:
friend std::ostream& operator<<( std::ostream& o, printable_view const& p ) {
p->print(o);
return o;
}
// pimpl:
private:
struct printable_view_impl {
virtual ~printable_view_impl() {}
virtual void print(std::ostream& o) = 0;
};
std::unique_ptr<printable_view_impl> pImpl;
private:
template<class T>
struct printer:printable_view_impl {
printer( T const* p ):ptr(p) {}
T const* ptr; // just a view, no ownership
virtual void print( std::ostream& o ) final override {
o << *ptr;
}
};
public:
// create a pimpl:
printable_view(printable_view&&)=default;
printable_view(printable_view const&)=delete;
printable_view()=delete;
template<class T>
printable_view( T const& t ):
pImpl( std::make_unique<printer<T>>( std::addressof(t) ) )
{}
};
which may have typos, but you get the idea.
Boost has a generic iterator and range that your base class can return, if you want to find a sample implementation.
There are significant performance hits to using type erasure based iteration: you'll end up with C++ code that is as slow as C#/Java code.
In your case you need to take every thing that iterator requires (copy, increment, move, dereference, etc) as mandated by the standard, and erase it like I did copy. In this case it isn't a view, so your impl impl will likely hold a T not a T*.
Here is a really simple toy for(:) supporing toy pseudo-iterator that will permit your List base to be used in for(:) loops.
template<class T>
struct any_iterator_sorta {
T operator*()const { return pImpl->get(); }
void operator++() { pImpl->next(); }
any_iterator_sorta(any_iterator_sorta const& o):
any_iterator_sorta( o.pImpl?any_iterator_sorta(o.pImpl->clone()):any_iterator_sorta() )
{}
friend bool operator==(any_iterator_sorta const& lhs, any_iterator_sorta const& rhs ) {
if (!lhs.pImpl || ! rhs.pImpl)
return lhs.pImpl == rhs.pImpl;
return lhs.pImpl->equals( *rhs.pImpl );
}
friend bool operator!=(any_iterator_sorta const& lhs, any_iterator_sorta const& rhs ) {
return !(lhs==rhs);
}
any_iterator_sorta(any_iterator_sorta&& o) = default;
any_iterator_sorta() = default;
any_iterator_sorta& operator=(any_iterator_sorta const& o) {
any_iterator_sorta tmp=o;
std::swap(tmp.pImpl, o.pImpl);
return *this;
}
any_iterator_sorta& operator=(any_iterator_sorta&& o) = default;
private:
struct pimpl {
virtual ~pimpl() {}
virtual void next() = 0;
virtual T get() const = 0;
virtual std::unique_ptr< pimpl > clone() const = 0;
virtual bool equals( pimpl const& rhs ) const = 0;
};
std::unique_ptr< pimpl > pImpl;
template<class It>
struct pimpl_impl:pimpl {
It it;
virtual void next() final override { ++it; }
virtual T get() const final override { return *it; }
virtual std::unique_ptr< pimpl > clone() const final override {
return std::make_unique<pimpl_impl>( it );
}
virtual bool equals( pimpl const& rhs ) const final override {
if (auto* r = dynamic_cast<pimpl_impl const*>(&rhs))
return it == r->it;
return false;
}
pimpl_impl( It in ):it(std::move(in)) {}
};
any_iterator_sorta( std::unique_ptr< pimpl > pin ):pImpl(std::move(pin)) {}
public:
template<class It,
std::enable_if_t< !std::is_same<It, any_iterator_sorta>{}, int>* =nullptr
>
any_iterator_sorta( It it ):
pImpl( std::make_unique<pimpl_impl<It>>( std::move(it) ) )
{}
};
If your interface class returned an any_iterator_sorta<T> where T is the type you iterate over, and the child classes did the same (but returned a class that supports ++, *, copy construct and ==), it would behave polymorphically with values.
The any_iterator_sorta is an C++ pseudo-iterator that is good enough to work in for(:) loops, but does not satisfy all the axioms of a real C++ iterator as mandated by the standard.
live example
Test case:
void test( any_iterator_sorta<int> begin, any_iterator_sorta<int> end )
{
for (auto it = begin; it != end; ++it) {
std::cout << *it << '\n';
}
}
std::vector<int> v{1,2,3};
std::list<int> l{10,11};
test( begin(v), end(v) );
test( begin(l), end(l) );
same code, iterating using two different iterator implementations.
To be concrete, assuming your code iterates over ints:
virtual any_iterator_sorta<int> begin() = 0;
virtual any_iterator_sorta<int> end() = 0;
in List. Then in ArrayList:
any_iterator_sorta<int> begin() final override {
return ArrayListIterator{};
}
any_iterator_sorta<int> end() final override {
return ArrayListIterator{};
}
finally, implement ArrayListIterator:
class ArrayListIterator{
public:
int operator*() const { return 0; }
bool operator==( ArrayListIterator const& o ){return true;}
void operator++() { /* do nothing for now */ }
};
the above just contains "stub" versions of the 4 required operations (copy construct, ==, ++ and unary *), so the ArrayList will appear "empty" to C++ for(:) loops.
