Ответ 1

В С++ коллекции перемещаются с использованием шаблона проектирования итератора. Вся эта STL разработана вокруг этой концепции. Он может соответствовать вашим потребностям:

Вы можете определить eatAll как функцию, которая принимает два итератора:

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

Или диапазон, как интерфейс алгоритма:

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

Вам нужно определить бинарное дерево как диапазон (он должен реализовывать begin() и end()). Надеемся, что деревья - это своего рода граф, который можно линеаризовать. Вся умная работа будет идти в реализации итератора!

Ответ 2

Если вы хотите, чтобы он был действительно полиморфным, мы должны иметь дело с двумя вещами:

• фактический тип контейнера

• Тот факт, что результатом разыменования карты является пара, содержащая ссылки на ключевые слова и значения.

Мое мнение состоит в том, что ответ на этот вопрос заключается не в том, чтобы выводить из контейнеров, что является ограничивающим, а для создания полиморфного "итератора значений", который моделирует все итераторы и извлекает их значения правильно.

Затем мы можем написать код следующим образом:

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);
}

Чтобы получить следующее:

vector:
Orange
Orange

map:
Orange
Orange
Orange

Здесь минимальная полная реализация:

#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);
}