12
\$\begingroup\$

C++ doesn't (yet) have a 'map' higher-order function, certainly not one which applies to a compile-time sequence of values like a tuple. We have std::transform, and there's an equivalent of it for tuples listed on SO, but that's iterator-based, and anyway - I don't want to use any reference to the output. I want to pass a tuple and a function / variadic lambda, and get another tuple of the same length with the function applied to each element.

I'm also sure this has been implemented multiple times, but since I want to build up some "tuple confidence", I've done it myself. Here's what I got:

namespace detail {

template <class F, typename Tuple, size_t... Is>
auto transform_each_impl(Tuple t, F f, std::index_sequence<Is...>) {
    return std::make_tuple(
        f(std::get<Is>(t) )...
    );
}

} // namespace detail

template <class F, typename... Args>
auto transform_each(const std::tuple<Args...>& t, F f) {
    return detail::transform_each_impl(
        t, f, std::make_index_sequence<sizeof...(Args)>{});
}

And this works in the cases I've tried - I haven't tested extensively.

I'd like general feedback/suggestions, but also:

  • When is the function resolved or instantiated in the case of different-type arguments? In what cases will it be the same (instantiated) function with forced conversion, as opposed to different instantiations for the different types? Am I really getting the latter at all?
  • Is there any std::forward'ing that I need to do?
  • Can I avoid a helper function somehow?
  • What do you think about the name?
\$\endgroup\$
  • \$\begingroup\$ Not enough time for full review, but you seem to be copying the tuple in the helper function unnecessarily. Demo. \$\endgroup\$ – nwp May 2 '18 at 11:35
6
\$\begingroup\$

transform, or map ?

I wouldn't name this function transform, because it's very different from that stl algorithm. std::transform can be used to modify a range in place, and can be called with either unary or binary operations. What you implement is generally called map and has its roots in functional languages; so I would call it tuple_map, for instance. Then the convention is to put the function first in the argument list, and the sequence second.

Or, you could try to implement transform, but then it gets tricky, because there are three "semantic inputs" to be considered: the tuple, its elements and the function signature. I haven't had the time to consider it thoroughly, but I believe that using decltype(fn(std::get<0>(tuple))) as a semantic clue is a good approximation. If it's void, you know that the semantic is at the tuple level; if it's an lvalue reference, you use std::tie to return a tuple of references; if it's an rvalue reference, std::forward_as_tuple is the most adapted; and if it's a value, you can return a new tuple.

A sketch for transform

For instance, with C++ 17 enabled:

#include <tuple>
#include <type_traits>

template <typename Fn, typename Argument, std::size_t... Ns>
auto tuple_transform_impl(Fn&& fn, Argument&& argument, std::index_sequence<Ns...>) {
    if constexpr (sizeof...(Ns) == 0) return std::tuple<>(); // empty tuple
    else if constexpr (std::is_same_v<decltype(fn(std::get<0>(argument))), void>) {
        (fn(std::get<Ns>(argument)),...); // no return value expected
        return;
    }
    // then dispatch lvalue, rvalue ref, temporary
    else if constexpr (std::is_lvalue_reference_v<decltype(fn(std::get<0>(argument)))>) {
        return std::tie(fn(std::get<Ns>(argument))...);
    }
    else if constexpr (std::is_rvalue_reference_v<decltype(fn(std::get<0>(argument)))>) {
        return std::forward_as_tuple(fn(std::get<Ns>(argument))...);
    }
    else {
        return std::tuple(fn(std::get<Ns>(argument))...);
    }
}

template <typename Fn, typename... Ts>
auto tuple_transform(Fn&& fn, const std::tuple<Ts...>& tuple) {
    return tuple_transform_impl(std::forward<Fn>(fn), tuple,
                          std::make_index_sequence<sizeof...(Ts)>());
}

Helper function

I can't see how you would avoid to use a helper function (besides using a tuple_transform function, which you're currently implementing).

You'll see I use a forwarding reference for the function argument, since it can be expensive to copy.

I keep the const lvalue reference for the tuple argument, because it's more simple (a forwarding reference wouldn't allow to constrain the type, and sizeof... wouldn't be possible either), but mainly because I can't see a case where the tuple would be consumed differently as a rvalue reference.

\$\endgroup\$
  • \$\begingroup\$ This is a good answer, but consider using std::invoke and std::invoke_result_t to handle (for instance) a member function pointer and a tuple of derived classes. \$\endgroup\$ – Thomas Russell May 2 '18 at 10:10
  • \$\begingroup\$ 1. I'd like to stick to C++14 if possible (which is how I tagged the question) - can't yet rely on C++17-capable compilers everywhere. 2. Your alternative solution is not really a review of my code. Also - why use recursive instantiation? I mean, what's the benefit? 3. If I called it tuple_map,, it might get confused with the map data structures in C++, don't you think? \$\endgroup\$ – einpoklum - reinstate Monica May 2 '18 at 11:03
  • \$\begingroup\$ @einpoklum: 1. C++14 is just a bit less readable, that's why I chose to use C++17, but there isn't any major difficulty to overcome. Just use std::conditional and tag dispatching. 2. I wasn't sure what your aim was, I intended to show you what a transform adaptation to tuple could be so that the alternative map vs transform would be clear. I don't see any recursive instantiation here? 3. well they are the same when you think of it (I mean, a function is a list of key / value pairs). The signature should help others to figure out which is which. \$\endgroup\$ – papagaga May 2 '18 at 12:17
5
\$\begingroup\$

Code review

I agree with @papagaga that the name could be better, though I would choose perform_mappping. I just obfuscated name map, which is mostly thought of as std::map. I hope it will do more good than bad.

If the code doesn't have forwarding (or, as some call it, universal reference), don't use std::forward. In the case in question, there is none.

The code will generate a new function for each permutation of the types passed in. It might create a binary bloat if compiler will not be able to inline the function. Though, I believe in compilers. No conversions will ever happen, unless SFINAE kicks in.

With C++20's full templates on lambdas, the code might be able to hide the helper inside of itself, thus not exposing it.


Alternative

std::array and std::pair are tuples too, from the point of view of standard library. I thought "hey, lets make the function to work uniformly on every tuple by standard library". I thought it's gonna be easy ... unless I realized that std::array has non-type argument in it. This turned things to be verbose and not as elegant as I thought. Yet, the caller side is still good.

Implementation

The small problem is distinguishing tuples from non-tuples. std::tuple_size helps out with this. The harder one is identifying which type to return. Unfortunately I had to specialize it for tuple + pair and for array.


Code

#include <tuple>
#include <array>
#include <utility>

namespace details
{
    template <typename Tuple, typename Mapping>
    struct return_type;

    template <template <typename ...> typename Tuple, typename ... Types, typename Mapping>
    struct return_type<Tuple<Types...>, Mapping>
    {
        using type = Tuple<std::invoke_result_t<Mapping, Types>...>;
    };
    template <template <typename, std::size_t> typename Array, 
              typename T, std::size_t Size, typename Mapping>
    struct return_type<Array<T, Size>, Mapping>
    {
        using type = Array<std::invoke_result_t<Mapping, T>, Size>;
    };

    template <typename Tuple, typename Mapping>
    using return_type_t = typename return_type<Tuple, Mapping>::type;

    template <typename Tuple, typename Mapping, std::size_t ... Indices>
    return_type_t<std::decay_t<Tuple>, 
                  std::decay_t<Mapping>> perform_mapping(Tuple&& tup, 
                                                         Mapping&& mapping, 
                                                         std::index_sequence<Indices...>)
    {
        return {mapping(std::get<Indices>(std::forward<Tuple>(tup)))...};
    }
}

template <typename Tuple, typename Mapping, 
          std::size_t Size = std::tuple_size<std::decay_t<Tuple>>::value>
auto perform_mapping(Tuple&& tup, Mapping&& mapping)
{
    return details::perform_mapping(std::forward<Tuple>(tup), 
                                    std::forward<Mapping>(mapping), std::make_index_sequence<Size>{});
}

#include <algorithm>
#include <iterator>
#include <iostream>
#include <string>

int main()
{
    auto mapper = [](int x) {return x * 2;};
    std::array<int, 3> a{1, 2, 3};
    auto b = perform_mapping(a, mapper);

    std::copy(b.begin(), b.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';

    auto tuple = std::make_tuple(1, std::string{"a"});
    auto self_adder = [](const auto& x) {return x + x;};
    auto another_tuple = perform_mapping(tuple, self_adder);
    std::cout << std::get<0>(another_tuple) << ' ' << std::get<1>(another_tuple) << '\n';
}

Demo.


In theory, if one specializes std::tuple_size for their own tuple (as long as it behaves like std::tuple or like std::array), it should simply work.

For better or for worse, the new function allows mutation and side effects.

\$\endgroup\$
3
\$\begingroup\$

Boost’s implementation has a few details I spot:

// tuple_for_each
namespace detail
{

template<class Tp, std::size_t... J, class F> BOOST_CONSTEXPR F tuple_for_each_impl( Tp && tp, integer_sequence<std::size_t, J...>, F && f )
{
    using A = int[sizeof...(J)];
    return (void)A{ ((void)f(std::get<J>(std::forward<Tp>(tp))), 0)... }, std::forward<F>(f);
}

template<class Tp, class F> BOOST_CONSTEXPR F tuple_for_each_impl( Tp && /*tp*/, integer_sequence<std::size_t>, F && f )
{
    return std::forward<F>(f);
}

} // namespace detail

template<class Tp, class F> BOOST_CONSTEXPR F tuple_for_each( Tp && tp, F && f )
{
    using seq = make_index_sequence<std::tuple_size<typename std::remove_reference<Tp>::type>::value>;
    return detail::tuple_for_each_impl( std::forward<Tp>(tp), seq(), std::forward<F>(f) );
}
  • it uses remove_reference
  • it forwards the tuple by reference to the helper rather than copying it
  • it uses constexpr

It doesn’t return the tuple of results though, but rather just returns the function object. So you would make_tuple instead of (void)-int the results.

Incomputable: In your version, can you use return type deduction and avoid the horrendous meta-computation for the return type? Let make_tuple do the argument deduction on the results and figure it out.

\$\endgroup\$
  • \$\begingroup\$ Isn't the remove_reference only used to choose the tuple size type? And isn't that type only size_t with std::tuple? \$\endgroup\$ – einpoklum - reinstate Monica May 3 '18 at 9:03
  • \$\begingroup\$ Yea, I guess it's to support compilers that didn’t have sizeof...(Args) No... but the top function does use it. Maybe because it can handle tuple-like objects that have the get<n> protocol and doesn’t assume size_t? \$\endgroup\$ – JDługosz May 3 '18 at 9:14
  • \$\begingroup\$ No... make_index_sequence just takes the number, not a type. It is sanitizing the metacall to tuple_size, maybe because it fails on references since that is the wrong type? Try calling yours with a tuple reference variable as an argument. \$\endgroup\$ – JDługosz May 3 '18 at 9:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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