8
\$\begingroup\$

Python has itertools.chain(), but C++ has nothing. This is my attempt to implement such a thing. Looking mainly for comments about potentially smarter ways of doing things or potential pitfalls this code falls into based on its current implementation.

Currently, the objects that chain() will give back will be a reference if all the corresponding containers dereference to the same type, otherwise it will be a value (e.g. chaining a vector<int> and deque<int> will give an int&, but if the second was a deque<long> instead would give an int).

First, some metaprogramming boilerplate:

namespace adl_details {
    using std::begin;
    using std::end;

    template <typename C>
    auto adl_begin(C&& c) {
        return begin(std::forward<C>(c));
    }

    template <typename C>
    auto adl_end(C&& c) {
        return end(std::forward<C>(c));
    }    
}

using adl_details::adl_begin;
using adl_details::adl_end;

template <typename C>
using iter_t = decltype(adl_begin(std::declval<C>()));

template <typename C>
using iter_pair_t = std::pair<iter_t<C>, iter_t<C>>;

template <typename C>
using deref_t = decltype(*std::declval<iter_t<C>>());

template <typename T>
struct type_is { using type = T; };

template <typename... T>
struct nondecay_common_type;

template <typename... T>
using nondecay_common_type_t = typename nondecay_common_type<T...>::type;

template <typename T>
struct nondecay_common_type<T> : type_is<T> { };

template <typename T>
T makeT();

template <typename T, typename... U>
struct nondecay_common_type<T, U...>
: type_is<decltype(true ? makeT<T>() : std::declval<nondecay_common_type_t<U...>>())>
{ };

(nondecay_common_type is necessary because std::common_type_t<int&, int&> yields int but I want it to yield int&. makeT is necessary because if I use std::declval, std::common_type_t<int, int> would yield int&& but I want it to yield int).

And now the main event:

template <typename... Containers>
class Chainer {
    using sequence = std::make_index_sequence<sizeof...(Containers)>;
    using deref_type = nondecay_common_type_t<deref_t<Containers>...>;

public:
    Chainer(Containers&&... c)
    : containers(std::forward<Containers>(c)...)
    { }

    class iterator 
    {
    public:
        iterator(iter_pair_t<Containers>... pairs)
        : iter_pairs(pairs...)
        { }

        deref_type operator*() {
            return dereference(sequence{});
        }

        iterator& operator++() {
            increment(sequence{});
            return *this;
        }

        iterator operator++(int ) {
            iterator tmp(*this);
            ++*this;
            return tmp;
        }

        bool operator==(iterator const& rhs) {
            return iter_pairs == rhs.iter_pairs;
        }

        bool operator!=(iterator const& rhs) {
            return iter_pairs != rhs.iter_pairs;
        }        

    private:
        void increment(std::index_sequence<> ) {
        }

        template <size_t I, size_t... Is>
        void increment(std::index_sequence<I, Is...> ) {
            auto& cur_pair = std::get<I>(iter_pairs);
            if (cur_pair.first != cur_pair.second) {
                ++cur_pair.first;
            }
            else {
                increment(std::index_sequence<Is...>{});
            }
        }

        template <size_t I>
        deref_type dereference(std::index_sequence<I> ) {
            return *std::get<I>(iter_pairs).first;
        }

        template <size_t I, size_t... Is>
        deref_type dereference(std::index_sequence<I, Is...> ) {
            auto& cur_pair = std::get<I>(iter_pairs);
            if (cur_pair.first != cur_pair.second) {
                return *cur_pair.first;
            }
            else {
                return dereference(std::index_sequence<Is...>{});
            }
        }

        std::tuple<iter_pair_t<Containers>...> iter_pairs;
    };

    iterator begin() { return begin_impl(sequence{}); }
    iterator end() { return end_impl(sequence{}); }

private:
    template <size_t... Is>
    iterator begin_impl(std::index_sequence<Is...> ) {
        return iterator{std::make_pair(adl_begin(std::get<Is>(containers)),
                                       adl_end(std::get<Is>(containers)))...};
    }

    template <size_t... Is>
    iterator end_impl(std::index_sequence<Is...> ) {
        return iterator{std::make_pair(adl_end(std::get<Is>(containers)),
                                       adl_end(std::get<Is>(containers)))...};
    }    

    std::tuple<Containers...> containers;
};

Examples:

int main() {
    std::vector<int> v{1, 2, 3};
    std::deque<int> d{4, 5, 6};

    for (int& i : chain(v, d)) {
        ++i;
    }

    for (int j : chain(std::vector<int>{1, 2}, std::deque<int>{3, 4, 5}, std::list<int>{6, 7})) {
        std::cout << j << " ";
    }
}
\$\endgroup\$
1
  • 1
    \$\begingroup\$ I wouldn't say C++ has nothing. See CppIterTools. \$\endgroup\$
    – Snowhawk
    Commented Sep 20, 2015 at 3:10

1 Answer 1

3
\$\begingroup\$

Try using ranges instead of iterators. E.g. using Eric Niebler's range-v3 library, you can write

#include <iostream>
#include <vector>
#include <range/v3/view/concat.hpp>

int main()
{
    using namespace ranges;

    std::vector<std::string> his_face{"this", "is", "his", "face"};
    std::vector<std::string> another_mess{"another", "fine", "mess"};
    std::cout << view::concat(his_face, another_mess);
}

Live Example. Using Boost.Range, a similar result can be obtained, but it's not as clean as using range-v3.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.