C++ discourages base class of collection - is there anyway to fake it?

Question

There are no similar concept of (Java) Collection in C++.

I can understand the reason, but I want to know whether there is any way to fake it elegantly.

Example

I have implemented many custom Collections.
They all have Iterator that works correctly, similar to std::vector, std::unordered_set, etc.

They are MyArray<T> , MyBinaryTree<T> and MySet<T>.

Here I will show a working code that show the location I want to fake it.

Let's say that I have 2 levels of program : library and user.
It does only one thing - User commands Library to eat all Orange*s in a bucket.

Library.h

class Library{
    public: static void eatAll(const MyArray<Orange*>& bucket);
};

Library.cpp

#include "Orange.h"
void Library::eatAll(const MyArray<Orange*>& bucket){
    for(auto orange:bucket){
        orange->eaten();
    }
}

User.h

MyArray<Orange*> bucket;
Library::eatAll(bucket);    

It is OK.

Now, I want Library::eatAll to also support MyBinaryTree<Orange*>, I have some not-so-desirable approaches as below.

My poor solution

1. Java way

• Make MyBinaryTree<T> and MyArray<Orange*> (and their iterator) inherit from a new class Collection<T> (and CollectionIterator<T>).
• change signature to Library::eatAll(const Collection<T>&)

Disadvantage : performance penalty from "virtual" of some functions in Collection<T>.

2. Template v1

//Library.h
template<class T> void eatAll(const T&t ){
    for(auto orange : t){
        orange->eaten();
    }
}

• make eatAll a template function

Disadvantage : The implementation of the eatAll must be in header.
I have to #include orange.h in Library.h.
Sometimes, I really want to just forward declaration.

3. Template v2

//Library.h
template<class T> void eatAll(const T&t ){
    for(auto orange : t){
        eatAnOrange(orange)
    }
}
private: void eatAnOrange(Orange* orange){
    //below implementation is inside Library.cpp
    orange->eaten();
}

• create a middle-man function eatAnOrange

Disadvantage :

• Code is less readable, not concise, cause a little maintainability problem.
• If there are a lot of other functions e.g. squeezeAll(), I probably have to create a lot of middle-man functions, e.g. squeezeAnOrange().

4. Operator=()

Create converter among the 3 collection classes via implicit constructor.
Disadvantage : Suffer performance from creating a new instance of collection.

//Here is what it will do, internally (roughly speaking)
MyBinaryTree<Orange*> bucket;
Library::eatAll(MyArray<Orange*>(bucket)); 

I believe my solutions are inelegant.
Are there any solutions that don't suffer the mentioned disadvantage?

Edit:
Both of current answers are elegant than my approaches (thank!), but still has disadvantage :-
- Oliv's requires #include "orange.h" in User.h.
- Richard Hodges's has virtual function calling.

Answer 1

In C++, collections are traversed using the iterator design pattern. The entire STL is designed around this concept. It may fit your needs:

You could define eatAll as a function that accept two iterators:

template<class Iterator,class Sentinel>
void eatAll(Iterator it, Sentinel s){
    for (;it!=s;++it)
      it->eaten();
}

Or the range like algorithm interface:

template<class Range>
void eatAll(Range& r){
    for (auto& v:r)
      v.eaten();
}

You will have to define you binary tree as a range (it must implement begin() and end()). Hopefully trees are kind of graph that can be linearised. All the smart work will then go in the iterator implementation!

Answer 2

If you want it truly polymorphic, then we have to deal with 2 things:

1. the actual type of the container

2. The fact that the result of dereferencing a map is a pair containing key and value references.

My view is that the answer to this is not to derive from containers, which is limiting, but to create a polymorphic "value iterator", which models all iterators and extracts their values correctly.

Then we can write code like this:

int main()
{

    std::vector<Orange> vo {
            Orange(), Orange()
    };

    std::map<int, Orange> mio {
            { 1, Orange() },
            { 2, Orange() },
            { 3, Orange() }
    };

    std::cout << "vector:\n";
    auto first = makePolymorphicValueIterator(vo.begin());
    auto last = makePolymorphicValueIterator(vo.end());
    do_orange_things(first, last);

    std::cout << "\nmap:\n";
    first = makePolymorphicValueIterator(mio.begin());
    last = makePolymorphicValueIterator(mio.end());
    do_orange_things(first, last);
}

To get this:

vector:
Orange
Orange

map:
Orange
Orange
Orange

Here's a minimal, complete implementation:

#include <typeinfo>
#include <memory>
#include <iostream>
#include <vector>
#include <map>
#include <iterator>

// define an orange
struct Orange {
};

// a meta-function to get the type of the value of some iterated value_type    
template<class ValueType> struct type_of_value
{
    using type = ValueType;
};

// specialise it for maps and unordered maps
template<class K, class V> struct type_of_value<std::pair<K, V>>
{
    using type = V;
};

template<class ValueType> using type_of_value_t = typename type_of_value<ValueType>::type;

// function to extract a value from an instance of a value_type    
template<class ValueType> struct value_extractor
{
    template<class V>
    auto& operator()(V&& v) const {
        return v;
    }
};

// specialised for maps    
template<class K, class V> struct value_extractor<std::pair<K, V>>
{
    template<class Arg>
    auto& operator()(Arg&& v) const {
        return std::get<1>(v);
    }
};

template<class Iter>
auto extract_value(Iter const& iter) ->  auto&
{
    using value_type = typename std::iterator_traits<Iter>::value_type;
    auto e = value_extractor<value_type> {};
    return e(*iter);
}

// a polymorphic (forward only at the moment) iterator
// which delivers the value (in the case of maps) or the element (every other container)
template<class ValueType>
struct PolymorphicValueIterator {

    using value_type = type_of_value_t<ValueType>;

private:
    struct iterator_details {
        std::type_info const &type;
        void *address;
    };

    struct concept {

        virtual std::unique_ptr<concept> clone() const = 0;

        virtual value_type& invoke_deref() const = 0;

        virtual void invoke_next(std::size_t distance = 1) = 0;

        virtual iterator_details get_details() = 0;

        virtual bool is_equal(const iterator_details &other) const = 0;

        virtual ~concept() = default;

    };

    template<class Iter>
    struct model final : concept {

        model(Iter iter)
                : iter_(iter)
        {}

        std::unique_ptr<concept> clone() const override
        {
            return std::make_unique<model>(iter_);
        }


        virtual value_type& invoke_deref() const override {
            return extract_value(iter_);
        }

        void invoke_next(std::size_t distance = 1) override
        {
            iter_ = std::next(iter_, distance);
        }

        iterator_details get_details() override {
            return {
                    typeid(Iter),
                    std::addressof(iter_)
            };
        }

        bool is_equal(const iterator_details &other) const override {
            if (typeid(Iter) != other.type) {
                return false;
            }
            auto pother = reinterpret_cast<Iter const*>(other.address);
            Iter const& iother = *pother;
            return iter_ == iother;
        }

        Iter iter_;
    };


    std::unique_ptr<concept> concept_ptr_;

public:
    bool operator==(PolymorphicValueIterator const &r) const {
        return concept_ptr_->is_equal(r.concept_ptr_->get_details());
    }

    bool operator!=(PolymorphicValueIterator const &r) const {
        return not concept_ptr_->is_equal(r.concept_ptr_->get_details());
    }

    PolymorphicValueIterator &operator++() {
        concept_ptr_->invoke_next(1);
        return *this;
    }

    value_type& operator*() const {
        return concept_ptr_->invoke_deref();
    }

    template<class Iter>
    PolymorphicValueIterator(Iter iter)
    {
        concept_ptr_ = std::make_unique<model<Iter>>(iter);
    }

    PolymorphicValueIterator(PolymorphicValueIterator const& r)
            : concept_ptr_(r.concept_ptr_->clone())
    {}

    PolymorphicValueIterator& operator=(PolymorphicValueIterator const& r)
    {
        concept_ptr_ = r.concept_ptr_->clone();
        return *this;
    }

};

template<class Iter>
auto makePolymorphicValueIterator(Iter iter)
{
    using iter_value_type = typename std::iterator_traits<Iter>::value_type;
    using value_type = type_of_value_t<iter_value_type>;
    return PolymorphicValueIterator<value_type>(iter);
}

// a test
void do_orange_things(PolymorphicValueIterator<Orange> first, PolymorphicValueIterator<Orange> last)
{
    while(first != last) {
        std::cout << "Orange\n";
        ++first;
    }
}

int main()
{

    std::vector<Orange> vo {
            Orange(), Orange()
    };

    std::map<int, Orange> mio {
            { 1, Orange() },
            { 2, Orange() },
            { 3, Orange() }
    };

    std::cout << "vector:\n";
    auto first = makePolymorphicValueIterator(vo.begin());
    auto last = makePolymorphicValueIterator(vo.end());
    do_orange_things(first, last);

    std::cout << "\nmap:\n";
    first = makePolymorphicValueIterator(mio.begin());
    last = makePolymorphicValueIterator(mio.end());
    do_orange_things(first, last);
}