返回转换容器的 std::transform-like 函数 [英] The std::transform-like function that returns transformed container

问题描述

我正在尝试实现一个类似于 std::transform 算法的函数，但我想创建并返回一个包含转换后的输入元素的容器，而不是通过参数获取输出迭代器.

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.

假设它名为 transform_container 并带有两个参数:container 和 functor.它应该返回相同的容器类型，但可能由不同的元素类型参数化(函子可以返回不同类型的元素).

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

我能够编写两个函数 — 一个用于 std::set，另一个用于 std::vector — 似乎可以正常工作.除了容器类型名称之外，它们是相同的.下面列出了它们的代码.

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

然而，当我尝试将它们合并为一个适用于任何容器的通用函数时，我遇到了许多问题.set 和 vector 是类模板，因此我的函数模板必须采用模板模板参数.此外，set 和 vector 模板具有不同数量的类型参数，需要适当调整.

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?

推荐答案

最简单的情况:匹配容器类型

对于输入类型与输出类型匹配的简单情况(我已经意识到这不是您要问的)，请提高一级.与其指定容器使用的类型 T，并尝试专门针对 vector 等，只需指定容器本身的类型:

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

更复杂:兼容的值类型

由于您想尝试更改容器存储的项目类型，您需要使用模板模板参数，并将 T 修改为返回容器使用的类型.>

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

什么是不兼容的值类型?

这只会让我们走到一半.它适用于从 signed 到 unsigned 的转换，但是，当使用 T=int 和 U=std::string<解析时/code> 和处理集合，它尝试实例化 std::set<std::string, std::less<int>, ...> 并且因此不会编译.

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.

为了解决这个问题，我们想要采用任意一组参数并将 T 的实例替换为 U，即使它们是其他模板参数的参数.因此 std::set> 应该变成 std::set>; 等等.正如其他答案所建议的那样，这涉及一些自定义模板元编程.

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.

让我们创建一个模板，将其命名为replace_type，并让它将T 转换为U，并且K 到 K.首先让我们处理一般情况.如果它不是模板类型，并且与 T 不匹配，则其类型应保持为 K:

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

然后是专业化.如果它不是模板类型，并且确实匹配 T，则其类型应变为 U:

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

最后更新transform_container以使用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;
}

完成了吗?

这种方法的问题在于它不一定安全.如果您要从 Container 转换为 Container，那可能没问题.但是当从 Container 转换为 Container 时，另一个模板参数不应该从 builtin_type 转换为 是合理的>别的东西.此外，像 std::map 或 std::array 这样的替代容器给派对带来了更多问题.

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.

处理std::map 和std::unordered_map 还不错.主要问题是replace_type需要替换更多的类型.不仅有 T ->U 替换，还有一个 std::pair ->std::pair 替换.这增加了对不需要的类型替换的关注程度，因为飞行中的类型不止一种.也就是说，这就是我发现的工作；请注意，在测试中，我需要指定转换我的地图对的 lambda 函数的返回类型:

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

std::array 怎么样?

处理 std::array 增加了痛苦，因为它的模板参数不能在上面的模板中推导出来.正如 Jarod42 所指出的，这是因为它的参数包括值而不仅仅是类型.我已经通过添加专业化并引入一个帮助程序 contained_type 来为我提取 T(旁注，每个构造函数这更好地编写为更简单的 typenameContainer::value_type 并适用于我在这里讨论过的所有类型).即使没有 std::array 特化，这也允许我将我的 transform_container 模板简化为以下内容(即使不支持 std::array 这也可能是一个胜利):

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
}

然而，transform_container 的当前实现使用了 std::inserter，它不适用于 std::array.虽然可以进行更多的专业化，但我将把它作为模板汤练习留给感兴趣的读者.在大多数情况下，我个人会选择不支持 std::array.

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.

查看累积直播示例

完全披露:虽然这种方法受到 Ali 引用 Kerrek SB 答案的影响，但我没有设法让它在 Visual Studio 2013 中工作，所以我自己构建了上述替代方案.非常感谢 Kerrek SB 的原始答案 的部分内容仍然是必要的，以及来自 Constructor 和 Jarod42 的刺激和鼓励.

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.

这篇关于返回转换容器的 std::transform-like 函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！