STL容器如何折叠？

Question

我需要一个类似于 Haskell 的 foldl 函数来折叠任何 STL 容器。预期的签名如下：

template Iterator, FoldingFunction, Result
Result foldl(
  Iterator begin, 
  Iterator end, 
  FoldingFunction f, 
  Result initValue);

标准STL没有这样的功能。 Boost 有吗？

我知道它实现起来非常简单，但我想知道是否有任何现成的标准化实现。

还有一个问题：您通常如何在 C++/STL 中折叠数据列表？

Answer 1

STL确实有这样的功能： std::accumulate。但是，它位于标头 中，而不是 中。

实际上关于“Fold”的维基百科页面已经列出了foldl/foldr 适用于大多数编程语言，包括 C++。

Answer 2

您是否看过 std::accumulate 中的 标头？

Answer 3

这是我使用 std::accumulate 实现的

template<typename collection, typename operation>
typename collection::value_type reduce(collection col, operation op)
{
    return accumulate(col.begin(),  col.end(), typename collection::value_type(), op);
}

reduce 意思是 Haskell 中的折叠。而且这个函数模板可能会让程序的功能更加丰富:)

Answer 4

尽管 std::accumulate 似乎是最好的候选者，但我认为使用旧的 for_each 也可以实现该要求。

我从KennyTM的答案中的链接中获取了示例，并且全部翻译了
到for_each。 完整代码发布在键盘上，以下是一些摘录：

struct result_functor {
    result_functor( int initial, int multiplier ) :
        result_( initial ), multiplier_( multiplier ) {
    }
    int operator()( int x ) {
        result_ += multiplier_ * x;
        return result_;
    }
    int result_;
    int multiplier_;
};

const int init = 100;
const int numbers[] = { 10, 20, 30 };

const int accum_sum = std::accumulate( numbers, numbers + 3, init );
const result_functor for_sum = for_each( 
    numbers, numbers + 3, result_functor( init, +1 ) );
assert( accum_sum == for_sum.result_ );

Answer 5

为什么不只是；

b_t foldl(b_t (*f)(b_t,a_t),b_t base_case,a_t * in_list){
 int l = sizeof(inList)/sizeof(a_t);
 b_t carry = base_case;
 for(int i = 0;i<l;i++){
   carry = f(carry,in_list[i]);
  }
 return carry;
}

或递归地； // 也许你可以帮助我正确的语法...

b_t foldl(b_t (*f)(b_t,a_t),b_t base_case,a_t * in_list){
 return foldl(f,f(base_case,in_list[0]),in_list + 1);      
}