0

我有这个 Haskell 风格map的高阶函数，它已经在调用方使用模板类型推导来获得干净的语法，但结果类型除外：

template<class ResultingContainer, class R, class Fn>
ResultingContainer map(const R &range, const Fn &f) {
    ResultingContainer result;
    using value_type = decltype(*std::begin(range));
    for_each(range, [&](const value_type &v){
        result.push_back(f(v));
    });
    return result;
}

（我更喜欢一些decltype(*std::begin(range))迭代R::value_type器特征，因为我使用不提供此类接口的容器：Qt 容器。）

使用这个功能很简单，但并不像我想要的那么简单，你们都知道我的意思：

std::vector<int> result = map<std::vector<int>>(otherVector, someFunction);

当然，我希望它是：

std::vector<int> result = map(otherVector, someFunction);

如果我按照以下方式设计 API，类型推导将完美运行。但我不希望它是这样的，因为这是 C++ 标准库风格（迭代器对/范围之间的区别除外），但我希望它是“Haskell 风格”：

std::vector<int> result;
map(otherVector, result, someFunction);

鉴于otherVector不一定与结果的类型相同（例如，它们可能是字符串，我想要它们的长度，所以someFunction返回给定字符串的长度），我不能ResultingContainer只使用已知类型（特别是输入的值类型）。

如果我（而且我不想）坚持一种单一类型的容器，我可以表达它。但是还有一个希望：编译器已经知道结果应该是什么，除非auto用于返回类型。（当结果类型有多种可能性时，例如当用作重载函数的参数时，它会令人困惑）。

所以我想到了一个代理容器，这是默认的ResultingContainer（但如果用户需要，可以覆盖，这不是我的问题）。但是，以我目前的知识，我只能实现一些ProxyContainer<T>（T作为结果类型f，在 中使用的谓词map），它暂时保存所有结果项。这听起来像是不必要的开销。但是，实现可能如下所示：

template<typename T>
class ProxyContainer : public std::vector<T> {
    template<typename FinalContainer>
    operator FinalContainer() const {
        FinalContainer result;
        for (auto x : *this)
            result.push_back(x);
        return result;
    }
};

但这只是感觉不对。

你能想出更好的解决方案吗？

4

2 回答 2

2

正如 Xeo 建议的那样，我使用“惰性适配器”解决了这个问题。但我没有使用 Boost ，而是写了一个非常简单的：

template<class R, class Fn>
class MapAdaptor
{
    const R &range;
    const Fn &f;

public:
    MapAdaptor(const R &range, const Fn &f) :
        range(range), f(f)
    {
    }

    template<class ResultingContainer>
    operator ResultingContainer() const {
        ResultingContainer result;
        for(const auto &v : range)
            result.push_back(f(v));
        return result;
    }
};

那么，实际的map函数就变成了下面这样：

template<class R, class Fn>
MapAdaptor<R,Fn> map(const R &range, const Fn &f) {
    return MapAdaptor<R,Fn>(range, f);
}

我还没有让适配器本身成为一个范围，但我会添加这个功能，以便能够链接/嵌套操作。

于 2013-03-26T21:48:24.167 回答
1

这是一个通用的惰性适配器实现，以及一些container_traits允许您将数据返回到 astd::set等的实现。

#include <tuple>
#include <iterator>
#include <utility>
#include <algorithm>

// Standard metaprogramming boilerplate:
template<std::size_t...>
struct seq {};
template<std::size_t max, std::size_t... s>
struct make_seq:make_seq<max-1, max-1, s...> {};
template<std::size_t... s>
struct make_seq<0, s...> {
  typedef seq<s...> type;
};
// helper to make creating a sequence from 0,...,max-1 take less typing:
template<std::size_t max>
using MakeSeq = typename make_seq<max>::type;

// takes a sequence of indexes, a tuple, a Result type, and a Functor, and calls the Functor passing
// in the Result type with the fowarded args in the tuple, as indicated by the sequence of indexes:
template<typename Result, template<typename Result>class Functor, typename... Args, std::size_t... s>
Result apply( seq<s...>, std::tuple<Args...>& args ) {
  return Functor<Result>()(std::forward<Args>(std::get<s>(args))...);
}

// and here it is, a generic lazy evaluator:
template<template<typename Result>class Functor, typename... Args>
struct LazyEvaluation {
  std::tuple<Args...> stored_args;
  LazyEvaluation( Args... args ):stored_args(std::forward<Args>(args)...) {};
  template<typename R>
  operator R() {
    return apply<R, Functor>( MakeSeq<sizeof...(Args)>(), stored_args );
  }
};

// The start of some container traits templates:
template<typename T, typename=void>
struct const_iterator_type:std::false_type {};
template<typename T>
struct const_iterator_type<T, typename std::enable_if<
  std::is_same< typename T::const_iterator, typename T::const_iterator >::value
>::type>:std::true_type {
   typedef typename T::const_iterator const_iterator;
};
template<typename T, size_t n>
struct const_iterator_type< T[n] >:std::true_type {
   typedef T const* const_iterator;
};


template<typename T,typename=void>
struct has_push_back:std::false_type {};
template<typename T>
struct has_push_back<T, typename std::enable_if<
  std::is_same<
     decltype(std::declval<T>().push_back(*std::declval<typename const_iterator_type<T>::const_iterator>())),
     decltype(std::declval<T>().push_back(*std::declval<typename const_iterator_type<T>::const_iterator>()))
  >::value
>::type>:std::true_type{};
template<typename T,typename=void>
struct has_insert:std::false_type {};
template<typename T>
struct has_insert<T, typename std::enable_if<
  std::is_same<
     decltype(std::declval<T>().insert(*std::declval<typename const_iterator_type<T>::const_iterator>())),
     decltype(std::declval<T>().insert(*std::declval<typename const_iterator_type<T>::const_iterator>()))
  >::value
>::type>:std::true_type {};

template<typename Container, typename=void>
struct container_traits;

template<typename Container>
struct container_traits<Container, typename std::enable_if<has_push_back<Container>::value>::type> {
   template<typename V>
   static void add_to_container( Container& c, V&& v ) {
     c.push_back( std::forward<V>(v) );
   }
};
template<typename Container>
struct container_traits<Container, typename std::enable_if<!has_push_back<Container>::value && has_insert<Container>::value>::type> {
   template<typename V>
   static void add_to_container( Container& c, V&& v ) {
     c.insert( std::forward<V>(v) );
   }
};

// supporting emplace_back and emplace is harder, but probably worth it.
// the trick with both of them is that you only know if they exist or are valid
// after you try to call add_to_container with the arguments!  So instead of
// "does it exist", you end up with "can we call emplace_back with these arguments".
// This requires a bit of slight of hand in the template code, as we want to fall back
// on insert and push_back if emplace_back doesn't exist.

// Another improvement to the above might be to have the const_iterator traits class
// fall back on a decltype( std::begin(std::declval<C const>()) ) -- or even better,
// do full ADL with a private namespace and a using std::begin.

// your code, basically verbatim, but uses container_traits to figure out
// how to add an element to the container:
template<class ResultingContainer, class Range, class Fn>
ResultingContainer map_now(const Range &range, const Fn &f) {
  ResultingContainer result;
  using value_type = decltype(*std::begin(range));
  for_each(std::begin(range), std::end(range), [&](const value_type &v){
    container_traits<ResultingContainer>::add_to_container(result, f(v));
  });
  return result;
}

// could make this easier if I could pass in a pointer-to-template-function
// or the equivalent directly.  Know the syntax by any chance?
template<typename Range, typename Fn>
struct map_lazy_helper {
  template<typename ResultingContainer>
  struct Func {
    ResultingContainer operator()(const Range &range, const Fn &f) const {
      return map_now<ResultingContainer>( range, f );
    }
  };
};

// Map lazy is mostly repeating type information:
template<typename Range, typename Fn>
LazyEvaluation<map_lazy_helper<Range, Fn>::template Func, Range, Fn>
map_lazy(Range&&range, Fn&&f) {
  return {std::forward<Range>(range), std::forward<Fn>(f)};
}

#include <iostream>
#include <vector>
#include <set>

int main() {
   std::vector<int> tester {3,2,1};

   std::vector<double> vd = map_lazy( tester, [](int x) { return x*0.5; } );
   std::set<double> sd = map_lazy( tester, [](int x) { return x*0.5; } );
   std::vector<int> vs = map_lazy( tester, [](int x) { return x*2; } );
   for(auto&& x:vd)
     std::cout << x << "\n";
   for(auto&& x:sd)
     std::cout << x << "\n";
   for(auto&& x:vs)
     std::cout << x << "\n";
}

这和你可能喜欢的一样有效。:)

有趣的是，虽然这个答案很大，但其中 40% 是处理的通用“添加到容器”代码set，10% 是元编程样板，30% 是通用LazyEvaluation代码，10% 是测试代码，只有 10% 是所需的代码去实际写map_lazy。

现在我想了想，你想要的是一个通用的“将东西插入容器”迭代器，这样你就可以支持写入std::array足够大小的 a 、 a std::set、 astd::vector或自制容器。它应该探测back_insert_iterator，如果失败了insert_iterator( C.end() )，则专门针对固定大小的容器，例如std::array（即使是空的也有大小！）。那会container_traits更复杂，它已经占据了这篇文章的一半！

最后，这是一个启用 ADL 的“容器支持开始了吗”：

namespace aux_adl {
  using std::begin; using std::end;
  template<typename C>
  auto adl_begin( C&& c )->decltype( begin(std::forward<C>(c)) );
  template<typename C>
  auto adl_end( C&& c )->decltype( end(std::forward<C>(c)) );
  template<typename C>
  auto adl_cbegin( C const& c )->decltype( begin(c) );
  template<typename C>
  auto adl_cend( C const& c )->decltype( end(c) );
}
template<typename C, typename=void>
struct container_iterator {}
template<typename C>
struct container_iterator<C, std::enable_if<
  std::is_same<
    decltype( adl_aux::adl_begin(std::declval<C>()),
    decltype( adl_aux::adl_end(std::declval<C>())
  >::value
>::type> {
  typedef adl_aux::adl_begin(std::declval<C>()) iterator;
};
template<typename C>
struct container_const_iterator<C, std::enable_if<
  std::is_same<
    decltype( adl_aux::adl_cbegin(std::declval<C>()),
    decltype( adl_aux::adl_cend(std::declval<C>())
  >::value
>::type> {
  typedef adl_aux::adl_cbegin(std::declval<C>()) const_iterator;
};

请注意，adl_end类型函数仅执行正确的 ADL 类型查找，它们实际上不能被调用。

是的，这是一个黑客。显然有人在窃听 C++ 委员会允许using内部声明decltype来修复这个 hack。

于 2013-03-27T02:07:44.147 回答