Creating an STL container of `container< container<Base> >`

Question

Is there a way to do

container< container<Base> >

When you have a bunch of container<Derived>s that you wish to keep together (to iterator over?)

A concrete example follows.

Say you have

struct Animal { } ;
struct Dog : public Animal { } ;
struct StripedDog : public Dog { } ;
struct Cat : public Animal { } ;
struct SpottedCat : public Cat { } ;

You wish to keep collections of Cats, SpottedCats, Dogs & StripedDogs, in vectors or lists naturally,

vector<Dog*> doggies ;
vector<StripedDog*> stripedDoggies ;
vector<Cat*> catties ;
vector<SpottedCat*> spottedCatties ;

You wish to iterate over ALL animals, however, so you wish to slam references to all dogs & cats collections into a single object,

vector< vector<Animal *>* > zoo ;

zoo.push_back( &doggies ) ;
zoo.push_back( &stripedDoggies ) ;
zoo.push_back( &catties ) ;
zoo.push_back( &spottedCatties ) ;

So now you can

feed( zoo ) ;

Of course, this doesn't compile. The vectors of cats & dogs are not vector<Animal*>, but rather vectors of their concrete types. Without retaining redundant lists and without losing the concrete type info (ie NOT using lists of base type Animal* as in vector<Animal*> stripedDoggies), is there a way to achieve equivalent behavior from C++?

Answer 1

Polymorphic iterators? shudder

Usage example:

#include <iostream>
struct Animal
{
    virtual void print() = 0;
};

struct Elephant : Animal
{
    virtual void print() override { std::cout << "toot"; }
};
struct Cat : Animal
{
    virtual void print() override { std::cout << "meow"; }
};
struct Fox : Animal
{
    virtual void print() override
    { std::cout << "ring-ding-ding-ding-dingeringeding"; }
};

#include <vector>

template<class T>
using simple_vector = std::vector<T>;

int main()
{
    std::vector<Elephant> elephants(5);
    std::vector<Cat> cats(3);
    std::vector<Fox> foxes(1);

    polymorphic_range_container<simple_vector, Animal> animals;
    animals.push_back( std::make_pair(elephants.begin(), elephants.end()) );
    animals.push_back( std::make_pair(cats.begin(), cats.end()) );
    animals.push_back( std::make_pair(foxes.begin(), foxes.end()) );

    for(auto& animal : animals)
    {
        animal.print(); std::cout << ", ";
    }
    std::cout << std::endl;
}

Implementation (basics):

#include <memory>
#include <algorithm>
#include <iterator>
#include <utility>

template<class T>
struct iterator_base
{
    virtual void advance(int i) = 0;
    virtual T& get() const = 0;
    virtual bool equal(iterator_base const&) const = 0;
};

template<class ValueType, class Container, class Id>
struct polymorphic_iterator
{
    polymorphic_iterator& operator++()
    {
        impl->advance(1);
        if(container->is_end(*impl, id))
        {
            impl = container->next(id);
        }

        return *this;
    }

    ValueType& operator*() const {  return impl->get();  }

    friend bool operator==(polymorphic_iterator const& l,
                           polymorphic_iterator const& r)
    {
        if(l.impl == nullptr) return r.impl == nullptr;
        if(r.impl == nullptr) return false;

        return l.impl->equal( *(r.impl) );
    }
    friend bool operator!=(polymorphic_iterator const& l,
                           polymorphic_iterator const& r)
    {
        return not (l == r);
    }

private:
    std::unique_ptr< iterator_base<ValueType> > impl;
    Container* container;
    Id id;

    friend Container;
    polymorphic_iterator(Container* pc, Id pid, decltype(impl) p)
    : impl( std::move(p) ), container(pc), id(std::move(pid))
    {}
};

template<template<class> class Container, class Base>
class polymorphic_range_container
{
private:
    using self = polymorphic_range_container;

    struct IRange
    {
        using piterator = std::unique_ptr < iterator_base<Base> >;
        virtual piterator begin() = 0;
        virtual piterator end() = 0;
    };

    template<class It>
    struct range : IRange
    {
        range(It p_begin, It p_end) : m_begin(p_begin), m_end(p_end) {}

        using typename IRange::piterator;
        piterator begin() override { return piterator{new iterator_impl(m_begin)}; }
        piterator end() override { return piterator{new iterator_impl(m_end)}; }

    private:
        struct iterator_impl : iterator_base<Base>
        {
            iterator_impl(It p) : it(p) {}

            virtual void advance(int i) override { std::advance(it, i); }
            virtual Base& get() const override { return *it; }
            virtual bool equal(iterator_base<Base> const& other) const override
            {
                iterator_impl const* pOther
                    = dynamic_cast<iterator_impl const*>(&other);
                if(nullptr == pOther) return false;
                else return it == pOther->it;
            }
        private:
            It it;
        };

        iterator_impl m_begin;
        iterator_impl m_end;
    };

    using container_type = Container< std::unique_ptr<IRange> >;
    container_type ranges;

public:
    template<class T>
    void push_back(std::pair<T, T> p_range)
    {
        ranges.push_back( std::unique_ptr<IRange>{new range<T>(p_range.first, p_range.second)} );
    }

    using iterator = polymorphic_iterator<Base, self, typename container_type::const_iterator>;
    iterator begin()
    {
        return iterator{this, ranges.cbegin(), ranges.front()->begin()};
    }
    iterator end()
    {
        return iterator{this, ranges.cend(), {nullptr}};
    }

private:
    friend iterator;
    std::unique_ptr< iterator_base<Base> > next(typename container_type::const_iterator& p)
    {
        ++p;

        if(p == ranges.end()) return {nullptr};
        else return (**p).begin();
    }
    bool is_end(iterator_base<Base> const& it, typename container_type::const_iterator const& id)
    {
        if(ranges.end() == id) return false;
        else return (**id).end()->equal(it);
    }
};

Answer 2

I think you're looking at something like this, but not quite sure. Let me know if it isn't near to what you need and I'll drop it for favor of someone that does. The output demonstrates the virtual feed() operation does its business appropriately. Arranging a potential variadic parameter pack to that function would take me some time to cook on for awhile, and I'm not even sure it is possible.

But this should get you close.

#include <iostream>
#include <algorithm>
#include <type_traits>
#include <vector>

// base. enforces inheritance by SFINAE
template<typename Base, typename T, template<typename, typename...> class V>
typename std::enable_if<std::is_base_of<Base, T>::value>::type
invoke(void (Base::*func)(), const class V<T*>& vec)
{
    std::cout << __PRETTY_FUNCTION__ << std::endl;
    for (auto p : vec)
        (p->*func)();
}

// chain.
template<typename Base, typename T, template<typename, typename...> class V, typename... Args>
typename std::enable_if<std::is_base_of<Base, T>::value>::type
invoke(void (Base::*func)(), const class V<T*>& vec, Args... args)
{
    invoke(func, vec);
    invoke(func, args...);
}

int main()
{
    struct Animal
    {
        virtual void feed()
        {
            std::cout << __PRETTY_FUNCTION__ << std::endl;
        }
    } ;

    struct Dog : public Animal
    {
        void feed()
        {
            std::cout << __PRETTY_FUNCTION__ << std::endl;
        }
    } ;
    struct StripedDog : public Dog {};
    struct Cat : public Animal {};
    struct SpottedCat : public Cat {};

    std::vector<Dog*> doggies ;
    std::vector<StripedDog*> stripedDoggies ;
    std::vector<Cat*> catties ;
    std::vector<SpottedCat*> spottedCatties ;

    Dog dog;
    doggies.push_back(&dog);

    StripedDog sdog;
    stripedDoggies.push_back(&sdog);

    Cat cat;
    catties.push_back(&cat);

    invoke(&Animal::feed, doggies, stripedDoggies, catties, spottedCatties);

    return 0;
}

Output

typename std::enable_if<std::is_base_of<Base, T>::value>::type invoke(void (Base::*)(), const class V<T *> &) [Base = Animal, T = Dog, V = vector]
virtual void main()::Dog::feed()
typename std::enable_if<std::is_base_of<Base, T>::value>::type invoke(void (Base::*)(), const class V<T *> &) [Base = Animal, T = StripedDog, V = vector]
virtual void main()::Dog::feed()
typename std::enable_if<std::is_base_of<Base, T>::value>::type invoke(void (Base::*)(), const class V<T *> &) [Base = Animal, T = Cat, V = vector]
virtual void main()::Animal::feed()
typename std::enable_if<std::is_base_of<Base, T>::value>::type invoke(void (Base::*)(), const class V<T *> &) [Base = Animal, T = SpottedCat, V = vector]

Sorry about having to scroll to the right to see the types in that pretty-print, but they're pretty telling and should be looked at to see how this works. Note that both Dog and StripedDog containers properly fire the Dog::feed() member, while the Cat container properly fires the Animal::feed() base member since it provides no override.

Good luck, and I hope it helps.

Answer 3

In general, if you are doing something like this, you would store them all in a single vector:

std::vector<std::shared_ptr<Animal>> animals;

If Animal defines a feed method, iterating over it simply means calling that function:

animals[i]->feed();

If you want to call specific functions based on types, you'll need to do some casting:

std::shared_ptr<Dog> pDog = std::dynamic_pointer_cast<Dog>(animals[i]);
std::shared_ptr<Cat> pCat = std::dynamic_pointer_cast<Cat>(animals[i]);
// other casts
if (pDog)
{
    // do something with a dog
}
else if (pCat)
{
    // do something with a cat
}
// etc

If you really wanted to store all of the animals in additional vectors, you can do that by wrapping the whole zoo:

class Zoo
{
private:
    std::vector<std::shared_ptr<Animal>> animals;
    std::vector<std::shared_ptr<Dog>> dogs;
    // other vectors
public:
    void AddDog(const Dog& d)
    {
        std::shared_ptr<Dog> pD = std::make_shared<Dog>(d);
        dogs.push_back(pD);
        std::shared_ptr<Animal> pA = std::static_pointer_cast<Animal>(pD);
        animals.push_back(pA);
    }
};

It doubles the number of pointers you are storing in memory, but pointers are fairly cheap. Then you can pass the whole zoo, or individual animal types without the need to do the casting every time.

Answer 4

Since you are using pointers, which are quite cheap to copy, you could probably do:

vector< Animal * > zoo;

zoo.append( zoo.end(), doggies.begin(), doggies.end() );
// ditto with the others

feed( zoo ); // just receives *one* vector with animals to feed

---

Another option if you don't want to copy/merge the vectors:

void feed() {}

template< typename V >
void feed( const V& v )
{
    for( A* a : v )
    {
        // ...do something with 'a'
    }
}

template< typename V, typename V2, typename... Vs >
void feed( const V& v, const V2& v2, const Vs&... vs )
{
    feed( v );
    feed( v2, vs... );
}

Now you can call feed( doggies, stripedDoggies, catties, spottedCatties );.