Can I avoid template recursion here?

问题:

I've written a for_each for tuples:

template <typename Tuple, typename F, size_t begin, size_t end>
enable_if_t<begin == end || tuple_size<Tuple>::value < end> for_each(Tuple&, F&&) {
}

template <typename Tuple, typename F, size_t begin = 0U, size_t end = tuple_size<Tuple>::value>
enable_if_t<begin < end && tuple_size<Tuple>::value >= end> for_each(Tuple& t, F&& f) {
    f(get<begin>(t));
    for_each<Tuple, F, begin + 1, end>(t, forward<F>(f));
}

[Live Example]

But Yakk's answer to this question gives a wonderful example of how to handle running a lambda on all tuple values non-recursively:

namespace detail {
    template<class F, class...Args>
    void for_each_arg(F&& f, Args&&...args) {
        using detail = int[];

        static_cast<void>(detail{((f(std::forward<Args>(args))), void(), 0)..., 0});
    }
}

template <typename F, typename Tuple>
void for_each_tuple_element(F&& f, Tuple&& t) {
    return experimental::apply([&](auto&&...args) { detail::for_each_arg(forward<F>(f), decltype(args)(args)... ); }, forward<Tuple>(t));   
}

This requires apply. You can see my simplification of Yakk's answer here: http://ideone.com/yAYjmw

My question is this: Is there a way to somehow retrofit for_each_tuple_element with a range, avoiding the recursion that my code incurs? I've tried constructing the subset of the tuple defined by the range, but I can't seem to do that without using recursion, and then why not just my for_each?

回答1:

You could avoid recursion by generating a sequence of calls to the std::get<Is>(t)... function, with Is indices ranging from begin up to end-1. It's fairly easy to generate a sequence of consecutive numbers starting at a given index, as it's enough to make the starting point an offset that is then added to each item of a regular index sequence, e.g.:

std::get<begin + 0>(t), std::get<begin + 1>(t), ... std::get<begin + n>(t)

where the length of the sequence is equal to the distance between begin and end.

#include <tuple>
#include <type_traits>
#include <utility>
#include <cstddef>
#include <limits>

template <std::size_t begin, typename Tuple, typename F, std::size_t... Is>
void for_each(Tuple&& t, F&& f, std::index_sequence<Is...>)
{
    using expand = int[];
    static_cast<void>(expand{ 0, (f(std::get<begin + Is>(std::forward<Tuple>(t))), void(), 0)... });
}

template <std::size_t begin = 0U, std::size_t end = std::numeric_limits<std::size_t>::max(), typename Tuple, typename F>
void for_each(Tuple&& t, F&& f)
{
    for_each<begin>(std::forward<Tuple>(t), std::forward<F>(f)
                  , std::make_index_sequence<(end==std::numeric_limits<std::size_t>::max()?std::tuple_size<std::decay_t<Tuple>>::value:end)-begin>{});
}

Test:

int main()
{
    auto t = std::make_tuple(3.14, "Hello World!", -1);
    auto f = [](const auto& i) { std::cout << i << ' '; };

    for_each<1>(t, f);

    for_each<1,3>(t, f);

    for_each<0,2>(t, f);
}

DEMO

Also, note that defaulted template parameters of a function template don't have to be placed at the end of a template parameter list, hence, you can avoid the ugly decltype(t), decltype(f) part. This implies that end cannot be defaulted to std::tuple_size<Tuple>::value (since Tuple goes after end), but at this point all you need is some default magic number.

回答2:

You could implement a make_index_range metafunction like so:

template <std::size_t Start, std::size_t End>
struct index_range {
    template <std::size_t... Idx>
    static std::index_sequence<(Idx + Start)...>
    make_range (std::index_sequence<Idx...>);

    using type = decltype(make_range(std::make_index_sequence<End-Start>{}));
};

template <std::size_t Start, std::size_t End>
using make_index_range = typename index_range<Start, End>::type;

Then you can use this to generate your std::index_sequence:

template <typename Tuple, typename F, std::size_t... Idx>
void for_each(Tuple& t, F&& f, std::index_sequence<Idx...>) {
    (void)std::initializer_list<int> {
        (std::forward<F>(f)(std::get<Idx>(t)), 0)...
    };
}

template <typename Tuple, size_t begin = 0U, 
          size_t end = tuple_size<Tuple>::value, typename F>
enable_if_t<begin < end && tuple_size<Tuple>::value >= end> 
for_each(Tuple& t, F&& f) {
    for_each(t, std::forward<F>(f), make_index_range<begin, end>{});
}

You would use this like so:

auto t = std::make_tuple(1, 42.1, "hello world");
for_each<decltype(t), 2, 3>(t,[](auto e){std::cout << e << '\n';});
//outputs hello world

Note that you need to pass decltype(t) in if you want to give a begin and end. You could avoid that by using the technique in Peter Skotnicki's answer.

Live Demo

回答3:

Inspired by @Piotr, but with extra prettiness :-)

#include <tuple>
#include <utility>
#include <tuple>
#include <cstddef>
#include <string>
#include <iostream>

template<class Tuple, size_t I>
struct tuple_iterator
{
    constexpr tuple_iterator(Tuple& p) : _p(p) {}

    static constexpr auto index() { return I; }
    constexpr auto operator++() const { return tuple_iterator<Tuple, I+1>(_p); }
    constexpr auto operator--() const { return tuple_iterator<Tuple, I-1>(_p); }
    constexpr decltype(auto) deref() const { return _p; }

    Tuple& _p;
};

template<class...Ts>
constexpr auto begin(const std::tuple<Ts...>& t) {
    return tuple_iterator<const std::tuple<Ts...>, 0>(t);
}

template<class...Ts>
constexpr auto end(const std::tuple<Ts...>& t) {
    return tuple_iterator<const std::tuple<Ts...>, sizeof...(Ts)>(t);
}

template<class Tuple, size_t I>
constexpr auto prev(tuple_iterator<Tuple, I> it) { return --it; }

template<class Tuple, size_t I>
constexpr auto next(tuple_iterator<Tuple, I> it) { return ++it; }

namespace detail
{
    template <
    std::size_t begin,
    typename Tuple,
    typename F,
    std::size_t... Is
    >
    void for_each(Tuple&& t, F&& f, std::index_sequence<Is...>)
    {
        using expand = int[];
        static_cast<void>(expand{ 0, (f(std::get<begin + Is>(std::forward<Tuple>(t))), void(), 0)... });
    }
}

template<class Tuple, size_t First, size_t Last, class Func>
void for_each(tuple_iterator<Tuple, First> first, tuple_iterator<Tuple, Last> last, Func&& f)
{
    constexpr auto dist = Last - First;
    constexpr auto base = First;
    constexpr auto extent = std::make_index_sequence<dist>();
    detail::for_each<base>(first.deref(), std::forward<Func>(f), extent);
}

int main()
{
    using namespace std;

    auto x = make_tuple("dont print me", 1, "two", "three"s, "or me");

    for_each(next(begin(x)), prev(end(x)), [](const auto& x) { cout << x << endl; });

    return 0;
}

expected results:

1
two
three

回答4:

Sorry about the second answer, but I felt that this was worth it.

Presenting the function make_poly_tuple_iterator() which returns an iterator that will iterate over elements in a tuple, working with all algorithms in the std namespace.

de-referencing the iterator results in a boost::variant< reference types... > so the functors will have to be specialisations of boost::static_visitor<>.

Demo below, use like this:

int main()
{
    using namespace std;

    auto x = make_tuple(tagged_string<tag1>("dont print me"),
                        1,
                        2.0,
                        tagged_string<tag2>("three"),
                        tagged_string<tag3>("or me"));

    // this is the statically typed version
    for_each(next(begin(x)), 
             prev(end(x)), 
             [](const auto& x) { cout << x << endl; });

    // and the polymorphic version
    auto first = std::next(make_poly_tuple_iterator(begin(x)));
    auto last = std::prev(make_poly_tuple_iterator(end(x)));
    // note: std::for_each ;-)
    std::for_each(first, last, print_it()); 

    return 0;
}

expected results:

1
2
three
printing: 1
printing: 2
printing: three

Complete code:

Yes I know, there are many, many improvements that can be made....

#include <tuple>
#include <utility>
#include <tuple>
#include <cstddef>
#include <string>
#include <iostream>
#include <boost/variant.hpp>
#include <stdexcept>
#include <exception>


template<class Tuple, size_t I>
struct tuple_iterator
{
    constexpr tuple_iterator(Tuple& p) : _p(p) {}

    static constexpr auto index() { return I; }
    static constexpr auto upper_bound() { return std::tuple_size<Tuple>::value; }
    static constexpr auto lower_bound() { return 0; }
    template<size_t I2> static constexpr auto ValidIndex = I2 >= lower_bound() && I2 < upper_bound();
    template<size_t I2, typename = void>
    struct de_ref_type { using type = decltype(std::get<0>(std::declval<Tuple>())); };
    template<size_t I2>
    struct de_ref_type<I2, std::enable_if_t<ValidIndex<I2>>>
    { using type = decltype(std::get<I2>(std::declval<Tuple>())); };

    template<size_t I2> using DerefType = typename de_ref_type<I2>::type;

    constexpr auto operator++() const { return make_like_me<I+1>(); }
    constexpr auto operator--() const { return make_like_me<I-1>(); }

    template<size_t I2, std::enable_if_t<(I2 < lower_bound())>* = nullptr>
    constexpr auto make_like_me() const { return tuple_iterator<Tuple, lower_bound()>(_p); }

    template<size_t I2, std::enable_if_t<(I2 >= upper_bound())>* = nullptr>
    constexpr auto make_like_me() const { return tuple_iterator<Tuple, upper_bound()>(_p); }

    template<size_t I2, std::enable_if_t<ValidIndex<I2>>* = nullptr>
    constexpr auto make_like_me() const { return tuple_iterator<Tuple, I2>(_p); }

    constexpr decltype(auto) deref() const { return _p; }

    template<size_t X> bool operator==(const tuple_iterator<Tuple, X>& r) const { return false; }
    bool operator==(const tuple_iterator<Tuple, I>& r) const {
        return std::addressof(_p) == std::addressof(r._p);
    }

    template<size_t I2, std::enable_if_t<ValidIndex<I2>>* =nullptr>
    DerefType<I2> impl_star() const { return std::get<I2>(_p); }

    template<size_t I2, std::enable_if_t<not ValidIndex<I2>>* =nullptr>
    DerefType<I2> impl_star() const
    { throw std::logic_error("out of range"); }

    decltype(auto) operator*() const {
        return impl_star<index()>();
    }

    Tuple& _p;
};

template<class...Ts>
constexpr auto begin(const std::tuple<Ts...>& t) {
    return tuple_iterator<const std::tuple<Ts...>, 0>(t);
}

template<class...Ts>
constexpr auto end(const std::tuple<Ts...>& t) {
    return tuple_iterator<const std::tuple<Ts...>, sizeof...(Ts)>(t);
}

template<class Tuple, size_t I>
constexpr auto prev(tuple_iterator<Tuple, I> it) { return --it; }

template<class Tuple, size_t I>
constexpr auto next(tuple_iterator<Tuple, I> it) { return ++it; }

namespace detail
{
    template <
    std::size_t begin,
    typename Tuple,
    typename F,
    std::size_t... Is
    >
    void for_each(Tuple&& t, F&& f, std::index_sequence<Is...>)
    {
        using expand = int[];
        static_cast<void>(expand{ 0, (f(std::get<begin + Is>(std::forward<Tuple>(t))), void(), 0)... });
    }
}

template<class Tuple, size_t First, size_t Last, class Func>
void for_each(tuple_iterator<Tuple, First> first, tuple_iterator<Tuple, Last> last, Func&& f)
{
    constexpr auto dist = Last - First;
    constexpr auto base = First;
    constexpr auto extent = std::make_index_sequence<dist>();
    detail::for_each<base>(first.deref(), std::forward<Func>(f), extent);
}

namespace detail {

    template<class Tuple>
    struct variant_of_tuple;

    template<class...Ts>
    struct variant_of_tuple<std::tuple<Ts...>>
    {
        // todo: some work to remove duplicates
        using type = boost::variant<std::add_lvalue_reference_t<Ts>...>;
    };

    template<class...Ts>
    struct variant_of_tuple<const std::tuple<Ts...>>
    {
        // todo: some work to remove duplicates
        using type = boost::variant<std::add_lvalue_reference_t<std::add_const_t<Ts>>...>;
    };
}

template<class Tuple>
using ToVariant = typename detail::variant_of_tuple<Tuple>::type;

template<class Tuple>
struct poly_tuple_iterator
{
    using tuple_type = Tuple;
    using value_type = ToVariant<std::remove_reference_t<tuple_type>>;
    using difference_type = std::ptrdiff_t;
    using pointer = value_type*;
    using reference = value_type&;
    using iterator_category = std::random_access_iterator_tag;


    struct concept {
        virtual ~concept() = default;
        virtual const std::type_info& type() const = 0;
        virtual const void* address() const = 0;
        virtual bool equal(const void* p) const = 0;
        virtual std::unique_ptr<concept> clone() const = 0;
        virtual std::unique_ptr<concept> next() const = 0;
        virtual std::unique_ptr<concept> prev() const = 0;
        virtual value_type deref() const = 0;
    };

    template<size_t I>
    struct model : concept {
        using my_type = tuple_iterator<tuple_type, I>;
        model(my_type iter) : _iter(iter) {}
        const std::type_info& type() const override { return typeid(_iter); }
        const void* address() const override { return std::addressof(_iter); }
        std::unique_ptr<concept> clone() const override { return std::make_unique<model<I>>(_iter); };
        std::unique_ptr<concept> next() const override {
            auto next_iter = ++_iter;
            return std::make_unique<model<next_iter.index()>>(next_iter);
        };
        std::unique_ptr<concept> prev() const override {
            auto next_iter = --_iter;
            return std::make_unique<model<next_iter.index()>>(next_iter);
        };
        value_type deref() const override { return { *_iter }; }
        bool equal(const void* p) const override {
            return _iter == *reinterpret_cast<const my_type*>(p);
        }
        my_type _iter;
    };

    template<size_t I>
    poly_tuple_iterator(tuple_iterator<tuple_type, I> iter)
    : _impl(std::make_unique<model<I>>(iter))
    {}

    poly_tuple_iterator(const poly_tuple_iterator& r) : _impl(r._impl->clone()) {};
    poly_tuple_iterator(poly_tuple_iterator&& r) : _impl(std::move(r._impl)) {};
    poly_tuple_iterator& operator=(const poly_tuple_iterator& r) {
        _impl = r._impl->clone();
        return *this;
    }
    poly_tuple_iterator& operator=(poly_tuple_iterator&& r) {
        auto tmp = r._impl->clone();
        std::swap(tmp, _impl);
        return *this;
    }

    value_type operator*() const { return _impl->deref(); }
    poly_tuple_iterator& operator++() { _impl = _impl->next(); return *this; }
    poly_tuple_iterator operator++(int) { auto tmp = *this; _impl = _impl->next(); return tmp; }
    poly_tuple_iterator& operator--() { _impl = _impl->prev(); return *this; }
    poly_tuple_iterator operator--(int) { auto tmp = *this; _impl = _impl->prev(); return tmp; }
    poly_tuple_iterator& operator+=(difference_type dist) {
        while (dist > 0) {
            ++(*this);
            --dist;
        }
        while(dist < 0) {
            --(*this);
            ++dist;
        }
        return *this;
    }
    bool operator==(const poly_tuple_iterator& r) const {
        return _impl->type() == r._impl->type()
        and _impl->equal(r._impl->address());
    }
    bool operator!=(const poly_tuple_iterator& r) const {
        return not (*this == r);
    }

private:
    std::unique_ptr<concept> _impl;
};

template<class Tuple, size_t I>
auto make_poly_tuple_iterator(tuple_iterator<Tuple, I> iter) {
    return poly_tuple_iterator<Tuple>(iter);
}

struct print_it : boost::static_visitor<void>
{

    template<class T>
    void operator()(const T& t) const {
        std::cout << "printing: " << t << std::endl;
    }

    template<class...Ts>
    void operator()(const boost::variant<Ts...>& v) const {
        boost::apply_visitor(*this, v);
    }
};

// to differentiate string types for this demo
template<class tag>
struct tagged_string : std::string
{
    using std::string::string;
};

struct tag1 {};
struct tag2 {};
struct tag3 {};

int main()
{
    using namespace std;

    auto x = make_tuple(tagged_string<tag1>("dont print me"),
                        1,
                        2.0,
                        tagged_string<tag2>("three"),
                        tagged_string<tag3>("or me"));

    for_each(next(begin(x)), prev(end(x)), [](const auto& x) { cout << x << endl; });

    auto first = std::next(make_poly_tuple_iterator(begin(x)));
    auto last = std::prev(make_poly_tuple_iterator(end(x)));
    std::for_each(first, last, print_it());

    return 0;
}