返回转换容器的std :: transform-like函数

Question

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

让我们说它的名称transform_container并带有两个参数:容器和仿函数.它应返回相同的容器类型,但可能由不同的元素类型进行参数化(Functor可以返回不同类型的元素).

我想使用我的函数,如下例所示:

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

我能够写两个函数 - 一个for std::set和one for std::vector- 似乎正常工作.它们是相同的,除了容器类型名称.他们的代码如下所示.

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是类模板,所以我的函数模板必须采取模板的模板参数.此外,集合和矢量模板具有需要适当调整的不同数量的类型参数.

将上述两个函数模板概括为适用于任何兼容容器类型的函数的最佳方法是什么？

Answer 1

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

对于输入类型与输出类型匹配的简单情况(我已经意识到这不是你要问的),更高一级.而不是指定T容器使用的类型,并尝试专门研究a vector<T>等,只需指定容器本身的类型:

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返回的容器使用的参数.

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和S=std::string,和处理组,它试图实例std::set<std::string, std::less<int>, ...>,因此不会进行编译.

要解决这个问题,我们希望获取一组任意参数并替换Twith的实例U,即使它们是其他模板参数的参数.因此std::set<int, std::less<int>>应该成为std::set<std::string, std::less<std::string>>,等等.这包括一些自定义模板元编程,如其他答案所示.

模板元编程到救援

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

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

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

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

最后一个递归步骤来处理模板化类型的参数.对于模板化类型参数中的每种类型,请相应地替换类型:

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<MyCustomType>成Container<SomethingElse>,那很可能.但是当从转换Container<builtin_type>为Container<SomethingElse>合理时,另一个模板参数不应该转换builtin_type为SomethingElse.此外,替代容器喜欢std::map或std::array给聚会带来更多问题.

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

// 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了(旁注,根据构造函数,这更好地编写为更简单typename Container::value_type,适用于我在这里讨论过的所有类型).即使没有std::array专业化,这也允许我将transform_container模板简化为以下(即使没有支持,这可能是一个胜利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在大多数情况下,我个人会选择在没有支持的情况下生活.

查看累积的实例

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

Answer 2

一些评论

以下方法允许从标准库转换任何类型的容器(存在问题std::array,请参见下文).为容器的唯一要求是,它应该使用默认std::allocator类std::less,std::equal_to和std::hash函数对象.所以我们从标准库中有3组容器:

1. 具有一个非默认模板类型参数(值类型)的容器:

   • std::vector,std::deque,std::list,std::forward_list,[ std::valarray]
   • std::queue,std::priority_queue,std::stack
   • std::set, std::unordered_set

2. 具有两个非默认模板类型参数的容器(键的类型和值的类型):

   • std::map,std::multi_map,std::unordered_map,std::unordered_multimap

3. 具有两个非默认参数的容器:类型参数(值类型)和非类型参数(大小):

   • std::array

履行

convert_containerhelper类将已知输入容器类型(InputContainer)和输出值类型(OutputType)的类型转换为输出容器(typename convert_container<InputContainer, Output>::type)的类型:

template <class InputContainer, class OutputType>
struct convert_container;

// conversion for the first group of standard containers
template <template <class...> class C, class IT, class OT>
struct convert_container<C<IT>, OT>
{
    using type = C<OT>;
};

// conversion for the second group of standard containers
template <template <class...> class C, class IK, class IT, class OK, class OT>
struct convert_container<C<IK, IT>, std::pair<OK, OT>>
{
    using type = C<OK, OT>;
};

// conversion for the third group of standard containers
template
    <
        template <class, std::size_t> class C, std::size_t N, class IT, class OT
    >
struct convert_container<C<IT, N>, OT>
{
    using type = C<OT, N>;
};

template <typename C, typename T>
using convert_container_t = typename convert_container<C, T>::type;

transform_container 功能实现:

template
    <
        class InputContainer,
        class Functor,
        class InputType = typename InputContainer::value_type,
        class OutputType = typename std::result_of<Functor(InputType)>::type,
        class OutputContainer = convert_container_t<InputContainer, OutputType>
    >
OutputContainer transform_container(const InputContainer& ic, Functor f)
{
    OutputContainer oc;

    std::transform(std::begin(ic), std::end(ic), std::inserter(oc, oc.end()), f);

    return oc;
}

使用示例

查看包含以下转化的实时示例:

• std::vector<int> -> std::vector<std::string>,
• std::set<int> -> std::set<double>,
• std::map<int, char> -> std::map<char, int>.

问题

std::array<int, 3> -> std::array<double, 3>转换无法编译,因为std::array没有insert所需的方法std::inserter).transform_container函数不应该也是因为这个原因与以下容器的工作:std::forward_list,std::queue,std::priority_queue,std::stack,[ std::valarray].

Answer 3

总的来说这样做会非常困难.

首先,考虑一下std::vector<T, Allocator=std::allocator<T>>,让我们说你的函子转换T->U.我们不仅需要映射第一个类型参数,而且我们应该使用它Allocator<T>::rebind<U>来获得第二个参数.这意味着我们需要知道第二个参数首先是一个分配器......或者我们需要一些机制来检查它是否有一个rebind成员模板并使用它.

接下来考虑一下std::array<T, N>.在这里我们需要知道第二个参数应该从字面上复制到我们的std::array<U, N>.也许我们可以不加改变地使用非类型参数,重新绑定具有重新绑定成员模板的类型参数,并T用U？替换文字？

现在,std::map<Key, T, Compare=std::less<Key>, Allocator=std::allocator<std::pair<Key,T>>>.我们应该采取Key不改变,取代T有U,采取Compare不改变和重新绑定Allocator到std::allocator<std::pair<Key, U>>.那有点复杂了.

那么......你能没有任何灵活性吗？您是否乐于忽略关联容器并假设您的转换输出容器的默认分配器是可以的？

Answer 4

主要的困难是以某种方式Container从Conainer<T>. 我无耻地从模板元编程中窃取了代码：（trait for？）将指定的模板分解为类型 T<T2,T3 N,T4, ...>，特别是Kerrek SB 的答案（接受的答案），就像我一样不熟悉模板元编程。

#include <algorithm>
#include <cassert>
#include <type_traits>

// stolen from Kerrek SB's answer
template <typename T, typename ...>
struct tmpl_rebind {
    typedef T type;
};

template <template <typename ...> class Tmpl, typename ...T, typename ...Args>
struct tmpl_rebind<Tmpl<T...>, Args...> {
    typedef Tmpl<Args...> type;
};
// end of stolen code

template <typename Container,
          typename Func,
          typename TargetType = typename std::result_of<Func(typename Container::value_type)>::type,
          typename NewContainer = typename tmpl_rebind<Container, TargetType>::type >
NewContainer convert(const Container& c, Func f) {

    NewContainer nc;

    std::transform(std::begin(c), std::end(c), std::inserter(nc, std::end(nc)), f);

    return nc;
}

int main() {

    std::vector<int> vi{ 1, 2, 3, 4, 5 };
    auto vs = convert(vi, [] (int i) { return std::to_string(i); });
    assert( vs == std::vector<std::string>( {"1", "2", "3", "4", "5"} ) );

    return 0;
}

我已经用 gcc 4.7.2 和 clang 3.5 测试了这段代码，并按预期工作。

作为Yakk指出，有相当这段代码虽然几个注意事项：“......你应该重新绑定替换所有的参数，或者只是第一个不确定它应该递归代替？T0用T1在随后的参数IE浏览器？std::map<T0, std::less<T0>>- > std::map<T1, std::less<T1>>？” 我也看到了上面代码的陷阱（例如，如何处理不同的分配器，另见无用的回答）。

尽管如此，我相信上面的代码对于简单的用例已经很有用了。如果我们正在编写要提交给 boost 的效用函数，那么我会更有动力进一步调查这些问题。但是已经有一个可以接受的答案，所以我认为这个案例已经结束。

非常感谢 Constructor、dyp 和 Yakk 指出我的错误/错失的改进机会。