The std::transform-like function that returns transformed container

c++, c++11, stl, templates

Solution

Simplest cases: matching container types

For the simple case where the input type matches the output type (which I've since realized is not what you're asking about) go one level higher. Instead of specifying the type `T` that your container uses, and trying to specialize on a `vector<T>`, etc., just specify the type of the container itself:

template <typename Container, typename Functor>
Container transform_container(const Container& c, Functor &&f)
{
    Container ret;
    std::transform(std::begin(c), std::end(c), std::inserter(ret, std::end(ret)), f);
    return ret;
}

More complexity: compatible value types

Since you want to try to change the item type stored by the container, you'll need to use a template template parameter, and modify the `T` to that which the returned container uses.

template <
    template <typename T, typename... Ts> class Container,
    typename Functor,
    typename T, // <-- This is the one we'll override in the return container
    typename U = std::result_of<Functor(T)>::type,
    typename... Ts
>
Container<U, Ts...> transform_container(const Container<T, Ts...>& c, Functor &&f)
{
    Container<U, Ts...> ret;
    std::transform(std::begin(c), std::end(c), std::inserter(ret, std::end(ret)), f);
    return ret;
}

What of incompatible value types?

This only gets us partway there. It works fine with a transform from `signed` to `unsigned` but, when resolving with `T=int` and `U=std::string`, and handling sets, it tries to instantiate `std::set<std::string, std::less<int>, ...>` and thus doesn't compile.

To fix this, we want to take an arbitrary set of parameters and replace instances of `T` with `U`, even if they are the parameters to other template parameters. Thus `std::set<int, std::less<int>>` should become `std::set<std::string, std::less<std::string>>`, and so forth. This involves some custom template meta programming, as suggested by other answers.

Template metaprogramming to the rescue

Let's create a template, name it `replace_type`, and have it convert `T` to `U`, and `K<T>` to `K<U>`. First let's handle the general case. If it's not a templated type, and it doesn't match `T`, its type shall remain `K`:

template <typename K, typename ...>
struct replace_type { using type = K; };

Then a specialization. If it's not a templated type, and it does match `T`, its type shall become `U`:

template <typename T, typename U>
struct replace_type<T, T, U> { using type = U; };

And finally a recursive step to handle parameters to templated types. For each type in a templated type's parameters, replace the types accordingly:

template <template <typename... Ks> class K, typename T, typename U, typename... Ks>
struct replace_type<K<Ks...>, T, U> 
{
    using type = K<typename replace_type<Ks, T, U>::type ...>;
};

And finally update `transform_container` to use `replace_type`:

template <
    template <typename T, typename... Ts> class Container,
    typename Functor,
    typename T,
    typename U = typename std::result_of<Functor(T)>::type,
    typename... Ts,
    typename Result = typename replace_type<Container<T, Ts...>, T, U>::type
>
Result transform_container(const Container<T, Ts...>& c, Functor &&f)
{
    Result ret;
    std::transform(std::begin(c), std::end(c), std::inserter(ret, std::end(ret)), f);
    return ret;
}

Is this complete?

The problem with this approach is it is not necessarily safe. If you're converting from `Container<MyCustomType>` to `Container<SomethingElse>`, it's likely fine. But when converting from `Container<builtin_type>` to `Container<SomethingElse>` it's plausible that another template parameter shouldn't be converted from `builtin_type` to `SomethingElse`. Furthermore, alternate containers like `std::map` or `std::array` bring more problems to the party.

Handling `std::map` and `std::unordered_map` isn't too bad. The primary problem is that `replace_type` needs to replace more types. Not only is there a `T` -> `U` replacement, but also a `std::pair<T, T2>` -> `std::pair<U, U2>` replacement. This increases the level of concern for unwanted type replacements as there's more than a single type in flight. That said, here's what I found to work; note that in testing I needed to specify the return type of the lambda function that transformed my map's pairs:

// map-like classes are harder. You have to replace both the key and the key-value pair types
// Give a base case replacing a pair type to resolve ambiguities introduced below
template <typename T1, typename T2, typename U1, typename U2>
struct replace_type<std::pair<T1, T2>, std::pair<T1, T2>, std::pair<U1, U2>>
{
    using type = std::pair<U1, U2>;
};

// Now the extended case that replaces T1->U1 and pair<T1,T2> -> pair<T2,U2>
template <template <typename...> class K, typename T1, typename T2, typename U1, typename U2, typename... Ks>
struct replace_type<K<T1, T2, Ks...>, std::pair<const T1, T2>, std::pair<const U1, U2>>
{
    using type = K<U1, U2, 
        typename replace_type< 
            typename replace_type<Ks, T1, U1>::type,
            std::pair<const T1, T2>,
            std::pair<const U1, U2>
        >::type ...
    >;
};

What about std::array?

Handling `std::array` adds to the pain, as its template parameters cannot be deduced in the template above. As Jarod42 notes, this is due to its parameters including values instead of just types. I've gotten partway by adding specializations and introducing a helper `contained_type` that extracts `T` for me (side note, per Constructor this is better written as the much simpler `typename Container::value_type` and works for all types I've discussed here). Even without the `std::array` specializations this allows me to simplify my `transform_container` template to the following (this may be a win even without support for `std::array`):

template <typename T, size_t N, typename U>
struct replace_type<std::array<T, N>, T, U> { using type = std::array<U, N>; };

// contained_type<C>::type is T when C is vector<T, ...>, set<T, ...>, or std::array<T, N>.
// This is better written as typename C::value_type, but may be necessary for bad containers
template <typename T, typename...>
struct contained_type { };

template <template <typename ... Cs> class C, typename T, typename... Ts>
struct contained_type<C<T, Ts...>> { using type = T; };

template <typename T, size_t N>
struct contained_type<std::array<T, N>> { using type = T; };

template <
    typename Container,
    typename Functor,
    typename T = typename contained_type<Container>::type,
    typename U = typename std::result_of<Functor(T)>::type,
    typename Result = typename replace_type<Container, T, U>::type
>
Result transform_container(const Container& c, Functor &&f)
{
    // as above
}

However the current implementation of `transform_container` uses `std::inserter` which does not work with `std::array`. While it's possible to make more specializations, I'm going to leave this as a template soup exercise for an interested reader. I would personally choose to live without support for `std::array` in most cases.

View the cumulative live example

Full disclosure: while this approach was influenced by Ali's quoting of Kerrek SB's answer, I didn't manage to get that to work in Visual Studio 2013, so I built the above alternative myself. Many thanks to parts of Kerrek SB's original answer are still necessary, as well as to prodding and encouragement from Constructor and Jarod42.

Problem

I'm trying to implement a function similar to `std::transform` algorithm but instead of taking the output iterator by an argument I want to create and return a container with transformed input elements. Let's say that it's named `transform_container` and takes two arguments: container and functor. It should return the same container type but possibly parametrized by a different element type (the Functor can return element of different type). I'd like to use my function as in the example below: ``` std::vector<int> vi{ 1, 2, 3, 4, 5 }; auto vs = transform_container(vi, [] (int i) { return std::to_string(i); }); //vs will be std::vector<std::string> assert(vs == std::vector<std::string>({"1", "2", "3", "4", "5"})); std::set<int> si{ 5, 10, 15 }; auto sd = transform_container(si, [] (int i) { return i / 2.; }); //sd will be of type std::set<double> assert(sd == std::set<double>({5/2., 10/2., 15/2.})); ``` I was able two write two functions — one for `std::set` and one for `std::vector` — that seem to work properly. They are identical, except of the container typename. Their code is listed below. ``` template<typename T, typename Functor> auto transform_container(const std::vector<T> &v, Functor &&f) -> std::vector<decltype(f(*v.begin()))> { std::vector<decltype(f(*v.begin()))> ret; std::transform(std::begin(v), std::end(v), std::inserter(ret, ret.end()), f); return ret; } template<typename T, typename Functor> auto transform_container(const std::set<T> &v, Functor &&f) -> std::set<decltype(f(*v.begin()))> { std::set<decltype(f(*v.begin()))> ret; std::transform(std::begin(v), std::end(v), std::inserter(ret, ret.end()), f); return ret; } ``` However, when I attempted to merge them into a single general function that works with any container, I encountered numerous issues. The `set` and `vector` are class templates, so my function template must take a template template parameter. Moreover, set and vector templates have a different number of type parameters that needs to be properly adjusted. What is the best way to generalize the two function templates above into a function that works with any compatible container type?

Original source

Related problems