C++11构造的Map函数

Question

我希望通过实现比基本模板构造更高级的模板构造来学习，并且因为它们在许多情况下都很有用，所以我正在尝试使用C++11构造（如decltype）实现函数式编程中常见的map、filter和类似函数。

我遇到了一些问题，无法创建编译器可以处理的函数原型，所以我必须问一下您如何创建这样的东西：

//
// Takes an iterable, applies a function to every element, and returns a vector of the results
//
template <typename T, typename Func>
auto map(const T& iterable, Func func) -> std::vector< decltype(  func( *iterable.cbegin() ) ) >
{
    // body snipped
}

换句话说，这个函数应该接受任何可迭代对象和一个以可迭代对象的值类型为参数并返回某种类型值的函数。无论传入的可迭代对象类型如何，函数调用的结果都将是一个向量，向量的类型与传入的函数返回的类型相同。

map函数应该接受任何具有有效原型的函数作为参数，无论它是函数指针、函数符或lambda表达式。

使用上述函数与此测试代码：

std::vector<int> intVector;
intVector.push_back(1);
intVector.push_back(2);

map(intVector, [](int& value) { return value + 1; });

使Visual Studio报出C2893（“无法特化函数模板”）错误，我不确定出了什么问题。

更新： 根据评论和答案提出的更改建议进行了修改，测试了新的原型，但仍出现相同的错误。

- OnePie

---

我可能错了，但在我看来，您要求Func是一个以迭代器为参数的函数，而不是迭代器上的值。尝试用decltype(func( *(iterable.cbegin())))替换掉它。 - NtscCobalt

你可能还需要在lambda中使用const引用，因为你正在使用返回const迭代器的cbegin()。 - NtscCobalt

值得注意的是，算法通常采用两个迭代器参数而不是完整的容器。 - Joseph Mansfield

@sftrabbit 基于范围的算法是最新的热门技术。 :) - Yakk - Adam Nevraumont

你的map函数使用cbegin并从解引用迭代器获得const引用，但是你的lambda因某种不可理解的原因想要一个非const引用。这就是为什么当前版本无法工作的原因。 - Sebastian Redl

Answer 1

这可能是你想要的。它内部使用std :: transform，基本上完成了整个工作。我编写的函数只是一个容器的简单包装器（不适用于C风格数组，这需要一些额外的类型特征）：

#include <vector>
#include <algorithm>
#include <type_traits>

//
// Takes an iterable, applies a function to every element, 
// and returns a vector of the results
//
template <typename T, typename Func>
auto map_container(const T& iterable, Func&& func) ->
    std::vector<decltype(func(std::declval<typename T::value_type>()))>
{
    // Some convenience type definitions
    typedef decltype(func(std::declval<typename T::value_type>())) value_type;
    typedef std::vector<value_type> result_type;

    // Prepares an output vector of the appropriate size
    result_type res(iterable.size());

    // Let std::transform apply `func` to all elements
    // (use perfect forwarding for the function object)
    std::transform(
        begin(iterable), end(iterable), res.begin(),
        std::forward<Func>(func)
        );

    return res;
}

然而需要注意的是，您的lambda表达式应该使用const引用来传递变量，在int的情况下最好通过值传递变量。

此外，我将函数从map重命名为map_container：在程序中重复使用C++标准库的标准容器名称作为函数、变量或其他任何内容是一种不好的编程习惯。

对我来说，这将输出所需的结果:

#include <iostream>

int main()
{
    std::vector<int> intVector;

    intVector.push_back(1);
    intVector.push_back(2);

    auto v = map_container(intVector, [] (int value) { return value + 1; });

    for (int i : v) { std::cout << i << " "; }
}

- Andy Prowl

---

无法处理基本的C数组int x[5] = {0};。这是可迭代的，正如for(auto i:x){std::cout<<i<<" ";}所示。 - Yakk - Adam Nevraumont

怎么样？你仍然直接检查 T::value_type。 - Yakk - Adam Nevraumont

你可以在这里提高效率。不要使用result_type res(iterable.size())进行初始化，因为它会将iterable.size()个元素默认构造到输出向量中，而是只需默认构造res，执行res.reserve(iterable.size())，并将输出迭代器设置为std::back_inserter(res)。(完整代码请参见我对这个优秀答案的小改进。) - s3cur3

Answer 2

因此，这里有许多要处理的细节问题。我首先尝试构建一些container_traits模板，以尽可能抽象出大部分工作。

如果一个类型允许调用begin和end自由函数，并通过using引入了std::begin和std::end，并且这两个类型相同（最后一个可能不是必需的），则该类型是一个container。 container的特性主要来自于容器具有的iterator及其类型，再加上像size（甚至是size_at_least - 请参见下文）等常见特征。

如果一个类型的const是一个container，则称该类型为可迭代的iterable。

接下来的问题是，“哪种类型实例可以用于映射容器的元素？”这也稍微有点复杂，因此我添加了一些特征类来处理它。

因此，这导致了以下实现：

#include <algorithm>
#include <type_traits>
#include <utility>

namespace aux {
  // calculate the type that calling `begin` and `end` on a type will return
  // in a scope where `std::begin` and `std::end` are visible.  This hack is
  // required to enable argument-dependent lookup.
  using std::begin;
  using std::end;
  template<typename T>
  auto adl_begin(T&&t)->decltype( begin(std::forward<T>(t)) );
  template<typename T>
  auto adl_end(T&&t)->decltype( end(std::forward<T>(t)) );
  template<typename T>
  auto adl_cbegin(T const&t)->decltype( begin(t) );
  template<typename T>
  auto adl_cend(T const&t)->decltype( end(t) );
}

// What is a container?  Something with a `begin`ing and an `end`ing...
template<typename C,typename=void>
struct is_container:std::false_type {};
template<typename C>
struct is_container<C, typename std::enable_if<
   std::is_same<
      decltype(aux::adl_begin(std::declval<C>())),
      decltype(aux::adl_end(std::declval<C>()))
   >::value
>::type >:std::true_type {};


// Default container_traits is empty for SFINAE ease of use:
template<typename C, typename=void>
struct container_traits {};

// if it is a container, go in whole hog:
template<typename C>
struct container_traits<C, typename std::enable_if< is_container<C>::value >::type >
{
   typedef decltype( aux::adl_begin(std::declval<C>()) ) iterator;
   typedef decltype( aux::adl_cbegin(std::declval<C>()) ) const_iterator;
   // I'm lazy, so I'll copy typedefs from `iterator_traits` below:
   typedef typename std::iterator_traits<iterator>::value_type value_type;
   typedef typename std::iterator_traits<iterator>::reference reference;
   // etc

   // TODO: size_at_least is a helper function
   // it returns 0 if it is expensive to calculate the size (say, a range
   // if iterators into a `std::list`), and the size if it is cheap to
   // calculate (say, a `std::vector`, any class with a `.size()` method,
   // or a pair of pointers or other random-access iterators)
   // template<typename C2, typename=typename std::enable_if< std::is_convertable< C2, C const&>::value>::type
   // static std::size_t size_at_least( C2&& c ) { ... }
};

// Can Functor map the elements of C into something we can store elsewhere?
template<typename C, typename Functor, typename=void>
struct can_map:std::false_type {};
// Yes, if the result of calling Functor on C's elements is non-void:
template<typename C, typename Functor>
struct can_map<C, Functor, typename std::enable_if<
  !std::is_same< decltype(std::declval<Functor>()(std::declval<typename container_traits<C>::value_type>())), void >::value
>::type>: std::true_type {};

// The result of mapping the elements of C under Functor
template<typename C, typename Functor, typename=void>
struct map_result {};
template<typename C, typename Functor>
struct map_result<C,Functor,typename std::enable_if< can_map<C,Functor>::value>::type>
{
  typedef
    decltype(
      std::declval<Functor>()(
        *std::declval<
          typename container_traits<C>::const_iterator
        >()
      )
    )
  type;
};

// The actual implementation
// we std::decay the map_result because we want to store
// instances of the type, and std::decay does that quite nicely
// note that some pathological Functors may break this, ie ones
// that return pseudo-references that are intended to be read from
// yet are not std-container safe
template <typename T, typename Func>
auto map_container(T&& iterable, Func&& func) ->
  std::vector<
    typename std::decay<
      typename map_result<T, Func>::type
    >::type
  >
{
  std::vector<
    typename std::decay<
      typename map_result<T, Func>::type
    >::type
  > retval;
  // TODO: use container_traits<T>::size_at_least to reserve space in retval
  // that will bring the efficiency of this function up to near-hand-crafted-C.
  for (auto&& s:iterable) {
    retval.push_back( func(s) );
  }
  return retval;
}

这就是全部内容了。接下来是测试代码。我们应该能够在C风格数组、传统类型和布尔值（使用伪引用并紧密打包位）的vectors以及用户定义类型上映射map_container，无论是通过.begin()方法还是通过自由浮动的begin(C)函数。

我在处理数组时遇到的一个问题是，C const&似乎会导致指针衰减，使其不再是容器：我必须绑定到C&&才能获得真正的数组类型。

#include <iostream>

void test1() {
   std::vector<int> src{1,2,3,4,5};
   auto r = map_container( src, [](int x){return x*2;});
   for (auto&& x:r) {
      std::cout << x << "\n";
   }
}
struct test_buffer {
  int foo[5];
  int* begin() { return foo; }
  int* end() { return &foo[5]; }
  int const* begin() const { return foo; }
  int const* end() const { return &foo[5]; }
};
test_buffer buff1={{1,2,3,4,5}};
struct test_buffer_2 {
  int foo[5];
};
test_buffer_2 buff2={{1,2,3,4,5}};
int* begin(test_buffer_2& t) { return t.foo; }
int* end(test_buffer_2& t) { return &t.foo[5]; }
int const* begin(test_buffer_2 const& t) { return t.foo; }
int const* end(test_buffer_2 const& t) { return &t.foo[5]; }
std::vector<bool> bits{true, false, true, false};   

template<typename Container>
void tester(Container&& c) {
   Container const& src = c;
   auto r = map_container( src, [](int x){return x*2;});
   for (auto&& x:r) {
      std::cout << x << "\n";
   }
}
void test2() {
   tester(buff1);
   tester(buff2);
   tester(bits);
}
template<typename C>
bool is_container_test(C&&) {
   return is_container<C>::value;
}
template<typename C, typename F>
bool can_map_test( C&&, F&& ) {
   return can_map<C, F>::value;
}
template<typename C, typename F>
bool can_map_test2( C const&, F&& ) {
   return can_map<C, F>::value;
}
int array[] = {1,2,3,4,5};
void test3() {
   std::cout << "Array is container:" << is_container_test(array) << "\n";
   auto x2 = [](int x){return x*2;};
   std::cout << "Double can map:" << can_map_test(array, x2) << "\n";
   std::cout << "Double can map:" << can_map_test2(array, x2) << "\n";
}
void test4() {
   tester(array);
}
int main() {
   test1();
   test2();
   test3();
   test4();
}

或者类似的东西。在函数本身中不要使用复杂的SFINAE，而是创建能为您完成工作的特征类。

上面使用的其他技术：我使用了std::begin和std::end来获取起始/结束迭代器。这意味着现在支持原始C数组。然后我将其包装在一些参数相关的查找助手中，其目的是允许您在相同的命名空间中定义begin和end的类覆盖。

请注意，“container_traits”的“无接受”版本是一个空结构体，而不是未定义的结构体。这使我们可以在其他地方使用container_traits中的SFINAE。

哦，还有一个效率提高的方法是编写“智能储备”，它接受具有reserve方法和您希望复制大小的容器。如果您想要复制的容器缺少随机访问迭代器并且缺少.size()方法，则不执行任何操作，但如果它确实存在，则执行.reserve(end(...) - begin(...))或.reserve(src.size())。我们可以通过将其添加到container_traits中作为static size_t size_at_least(Container const&)来为其他算法抽象，该函数以O(1)时间返回不大于Container大小的size_t。

- Yakk - Adam Nevraumont

Answer 3

对Andy Prowl上面的优秀答案进行了一些小改进：

1. 我们可以提前保留所需的大小，而不实际调整向量的大小（从而避免默认构造n个元素）。这有两个优点：
   1. 它允许您映射根本无法默认构造的类型
   2. 它可能具有显着的性能优势（因为编译器很少能够省略那些未使用的默认构造），具体取决于元素数量以及构造它们的成本。
2. 我们可以提供一个重载，该重载适用于迭代器范围，以便您可以操作容器的一部分。

您可以在编译器资源管理器中尝试此代码，但代码本身如下：

template <typename Iterator, typename Func> [[nodiscard]]
auto functional_map(Iterator begin, Iterator end, Func && func) ->
std::vector<decltype(func(std::declval<typename Iterator::value_type>()))>
{
    using value_type = decltype(func(std::declval<typename Iterator::value_type>()));

    std::vector<value_type> out_vector;
    out_vector.reserve(std::distance(begin, end));
    
    std::transform(begin, end, std::back_inserter(out_vector),
                   std::forward<Func>(func));
    
    return out_vector;
}

template <typename T, typename Func> [[nodiscard]]
auto functional_map(const T & iterable, Func && func) ->
std::vector<decltype(func(std::declval<typename T::value_type>()))>
{
    return functional_map(std::begin(iterable), std::end(iterable),
                          std::forward<Func>(func));
}

请注意，我在这些声明中使用了C++17的[[nodiscard]]属性，但如果您使用的是C++17之前的版本，则可以放弃该属性而不会出现问题。

编译器浏览器链接还包括一些演示测试：

TEST_CASE("Mapping ints to string")
{
    const std::vector<int> int_version{0, 1, 2, 3, 4};
    const std::vector<std::string> string_version{"0", "1", "2", "3", "4"};

    CHECK(functional_map(int_version, 
                         [](int i) { return std::to_string(i); }) == string_version);
    
    CHECK(functional_map(string_version, 
                         [](const std::string & s) { return std::stoi(s); }) == int_version);
}

TEST_CASE("Mapping over only part of a container")
{
    const std::vector<int> int_version{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    const std::vector<std::string> string_version{"0", "1", "2", "3", "4", "5", "6", "7", "8", "9"};

    const std::vector<std::string> first_four_strings(string_version.begin(), string_version.begin() + 4);
    CHECK(functional_map(int_version.begin(), int_version.begin() + 4, 
                         [](int i) { return std::to_string(i); }) == first_four_strings);
    
    const std::vector<int> first_four_ints(int_version.begin(), int_version.begin() + 4);
    CHECK(functional_map(string_version.begin(), string_version.begin() + 4, 
                         [](const std::string & s) { return std::stoi(s); }) == first_four_ints);
}

- s3cur3