如何折叠STL容器？

Question

我需要一个类似于Haskell的foldl函数的模拟函数，可以对任何STL容器进行折叠操作。预期的函数签名如下：

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

标准STL没有这样的函数。 Boost 有吗？

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

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

- Andrey

---

你说的"fold"是什么意思？ - Konrad

@Konrad：折叠 = reduce = accumulate. - kennytm

处理一个数据结构中的元素，并按照一定顺序组合它们并返回结果。参考链接：http://www.haskell.org/haskellwiki/Fold - DumbCoder

Answer 1

STL确实有这样一个函数：std::accumulate。然而，它在头文件<numeric>中，而不是<algorithm>。

实际上，Wikipedia页面“Fold”已经列出了大多数编程语言，包括C++的foldl/foldr函数。

- kennytm

---

请注意，accumulate 使用迭代器参数的 value_type 作为内部累加器变量，尽管它接受并返回不同类型，并允许在函数对象参数中使用其他类型。 - Potatoswatter

@Potatoswatter：我在累加的定义中没有看到这个：TYPE accumulate（input_iterator start，input_iterator end，TYPE val，BinaryFunction f）; - Andrey

@Andrey：没事了。我在想缺陷报告539（http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#539）。`accumulate`使用了正确的内部类型。 - Potatoswatter

顺便提一下，accumulate 是一个左折叠；可以将其看作是 (1 + 2) + 3 而不是 1 + (2 + 3)；类似于 Haskell 中的 foldl。 - user2023370

请使用反向迭代器来进行foldr操作。 - kennytm

@KennyTM 是的，请将 x.begin() 和 x.end() 替换为 x.rbegin() 和 x.rend()。 - user2023370

Answer 2

你看过在<numeric>头文件中的std::accumulate吗？

- wheaties

---

这是std::accumulate。它在std命名空间中，但在<numeric>头文件中。 :) - jalf

@jalf 继续发表。这是我保持队形的唯一方式。:P - wheaties

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 中意味着折叠。而这个函数模板可以让程序更加函数化 :)

- Panic Fred

---

使用begin(col)和end(col)会更通用，但是这个函数仍然相当冗余，因为直接调用accumulate也很简单。 - sim642

Answer 4

虽然 std::accumulate 似乎是最佳选择，但我认为可以通过使用老式的 for_each 来实现要求。

我从 KennyTM 的答案链接 中获取了示例，并将它们全部转换为了 for_each。完整代码已发布在 codepad 上，以下是一些摘录：

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_ );

- Arun

---

有状态的函数对象 result_functor 表示未定义行为。 - Loom

@Loom 这个答案表明状态函数符对于 std::for_each 是可以的：https://dev59.com/4G025IYBdhLWcg3wRDq8#6113053，这是不正确的吗？ - PeterSW

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

- error

---

因为这仅适用于b_t、a_t和函数指针。此外，它比标准库实现中更广泛使用和经过测试的替代方案不够可靠。 - PeterSW