A recursive_transform for std::vector with various return type

Question

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.

Answer 1

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