5
\$\begingroup\$

This is the follow-up question for A recursive_transform Function For Various Type Nested Iterable With std::variant Implementation in C++ and A get_from_variant function in C++. Thanks to G. Sliepen and Quuxplusone provide detailed review suggestions. However, the existed version of recursive_transform function assumes the return type is always the same as the input type. In other words, it works well with the lambda function like [](double x)->double { return x + 1; } (the type of both input and output are double) or [](int x)->int { return x + 1; } (the type of both input and output are int). In the next step, I want to focus on the case which the return type is different from the input type. For example, [](int x)->std::string { return std::to_string(x); }. Because the origin return type of recursive_transform is specified in T, it can not handle the case which the type of the processed output from the lambda function f is different from T. Let's change type T into auto as below. This auto syntax used here makes type deriving adaptive.

template<class T, class F>
auto recursive_transform(const T& input, const F& f) {
    return f(input);
}

The another part of this recursive_transform is the recursive structure and it is more complex than above. The container has been specified in std::vector here first.

template<class T, class F> requires is_iterable<T>
auto recursive_transform(const T& input, const F& f) {
    typedef typename std::iterator_traits<typename T::iterator>::value_type
        value_type;

    std::vector<decltype(recursive_transform(std::declval<value_type&&>(), f))> output(input.size());
    std::transform(input.begin(), input.end(), output.begin(),
        [f](auto& element)
        {
            return recursive_transform(element, f);
        }
    );
    return output;
}

The test of the above template function recursive_transform.

std::vector<int> test_vector = {
    1, 2, 3
};
auto recursive_transform_result = recursive_transform(
    test_vector,
    [](int x)->std::string { return std::to_string(x); });                          //  For testing

std::cout << "string: " + recursive_transform_result.at(0) << std::endl;            //  recursive_transform_result.at(0) is a std::string

std::vector<decltype(test_vector)> test_vector2 = {
    test_vector, test_vector, test_vector
};

auto recursive_transform_result2 = recursive_transform(
    test_vector2,
    [](int x)->std::string { return std::to_string(x); });                          //  For testing

std::cout << "string: " + recursive_transform_result2.at(0).at(0) << std::endl;     // recursive_transform_result.at(0).at(0) is also a std::string

A Godbolt link is here.

All suggestions are welcome.

  • Which question it is a follow-up to?

    A recursive_transform Function For Various Type Nested Iterable With std::variant Implementation in C++ and

    A get_from_variant function in C++

  • What changes has been made in the code since last question?

    In the previous version of recursive_transform function, it works well when the return type is as same as the input type. The main idea in this question is trying to implement a extended version which the return type is different from the input type.

  • Why a new review is being asked for?

    The previous version recursive_transform function assumes the return type is always the same as the input type. I am trying to focus on the case which the return type is different from the input type to make the function more generic. However, I know that I make my algorithms more specialized in std::vector again in this version of code. I have no idea how to implement a more generic recursive_transform function in both various output type and various container type in a simple and smart way. If there is any suggestion or possible idea about this, please let me know.

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

I'm afraid this is reaching the limits of my knowledge about templates in C++, but I'll try to answer it anyway as best as I can:

Use std::back_inserter() to fill the vectors

Instead of constructing a vector of a given size, just declare an empty vector, but reserve enough capacity, and then use std::back_inserter() to fill it:

std::vector<decltype(recursive_transform(std::declval<value_type&&>(), f))> output;
output.reserve(input.size());

std::transform(input.begin(), input.end(), std::back_inserter(output),
    [f](auto& element)
    {
        return recursive_transform(element, f);
    }
);

However, if you don't use std::vector but a different container type, reserve() and/or std::back_inserter() might not be appropriate.

Determining the container type

So ideally, we don't want to declare a std::vector, but rather the outer container of type T. You can use template template parameters to deconstruct templated types:

template<template<class> class Container, class ValueType, class Function>
requires is_iterable<Container<ValueType>>
auto recursive_transform(const Container<ValueType> &input, const Function &f)
{
    // You want to be able to write this:
    using TransformedValueType = decltype(recursive_transform(*input.begin(), f));
    Container<TransformedValueType> output;
    ...
}

Unfortunately, that doesn't work, at least not with Clang, because a std::vector actually has two template parameters, and other containers might have more or less template parameters. So the solution to that problem is to declare ValueType as a template parameter pack:

template<template<class...> class Container, class Function, class Ts...>
requires is_iterable<Container<Ts...>>
auto recursive_transform(const Container<Ts...> &input, const Function &f)
{
    using TransformedValueType = decltype(recursive_transform(*input.begin(), f));
    Container<TransformedValueType> output;
    ...
}

Although of course this doesn't forward the second template parameter. Putting everything so far together:

template<typename T>
concept is_iterable = requires(T x)
{
    *std::begin(x);
    std::end(x);
};

template<class T, class Function>
auto recursive_transform(const T &input, const Function &f)
{
    return f(input);
}

template<template<class...> class Container, class Function, class... Ts>
requires is_iterable<Container<Ts...>>
auto recursive_transform(const Container<Ts...> &input, const Function &f)
{
    using TransformedValueType = decltype(recursive_transform(*input.begin(), f));
    Container<TransformedValueType> output;

    std::transform(std::begin(input), std::end(input), std::back_inserter(output),
        [&](auto &element)
        {
            return recursive_transform(element, f);
        }
    );

    return output;
}
\$\endgroup\$
1
  • 1
    \$\begingroup\$ It turns out that you can just have a generic overload that handles single variables, and a specialization that handles anything that matches is_iterable. I had a stray typename in a template parameter that caused some compiler errors with very unhelpful error messages. I updated the answer. \$\endgroup\$
    – G. Sliepen
    Oct 26 '20 at 19:58

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.