c++ - 如何使 C++ 算法融合？

Question

考虑以下 C++ 程序打印给定数字 vector 的最小相邻差异:

#include <iostream>
#include <iterator>
#include <numeric>
#include <vector>

int main()
{
    std::vector<int> numbers = { 10, 1, 43, 59, 78, 46, 63, 12 };

    std::vector<int> deltas;
    std::adjacent_difference( numbers.begin(),
                              numbers.end(),
                              std::back_inserter( deltas ) );

    auto minEl = std::min_element( deltas.begin() + 1,
                                   deltas.end() );

    std::cout << *minEl;
}

我想去掉中间的 deltas vector ，但仍然继续使用 std::adjacent_difference 和 std::min_element (而不是循环自己)。

在函数式语言中，删除中间数据结构通常称为deforestation。 (或“融合”)。有没有一种通用的方法可以在 C++ 中执行相同的操作？

我想有可能设计某种迭代器包装器，它允许在 min_element 迭代范围时增量计算相邻差异。不过，我在标准库中找不到类似的东西。也许某些第 3 方库(Boost？)提供类似的东西？

Answer 1

我猜(并希望)你会得到一些更好的答案，但如果你足够热衷于充实一个小的辅助代码库，这里有一个方法:

#include <iostream>
#include <iterator>
#include <numeric>
#include <vector>
#include <algorithm>

template <typename T>
struct min
{
    typedef T element_type;
    min(int& min) : min_(min) { }
    min& operator *() { return *this; }
    min& operator=(const T& t)
    {
        if (first_)
            min_ = t, first_ = false;
        else if (t < min_)
            min_ = t;
    }
    min& operator++() { return *this; }
    bool first_ = true;
    T& min_;
};

template <typename Iterator>
struct skip_take  // i.e. skip some elements, take some elements...
{
    skip_take(Iterator i, size_t skip, size_t take = size_t(-1))
      : i_(i), skip_(skip), take_(take)
    { }
    skip_take& operator *() { return *this; }
    skip_take& operator=(const typename Iterator::element_type& t)
        { if (skip_ == 0 && take_) *i_ = t; }
    skip_take& operator++()
        { if (skip_) --skip_; else if (take_) --take_, ++i_; return *this; }
    Iterator& i_;
    size_t skip_, take_;
};

int main()
{
    std::vector<int> numbers = { 10, 1, 43, 59, 78, 46, 63, 12 };

    int result;
    std::adjacent_difference(numbers.begin(), numbers.end(),
                             skip_take<min<int>>(min<int>(result), 1));

    std::cout << result << '\n';
}

(代码在 ideone.com 上)

更一般地说，这种事情的良好实现因 C++ 缺乏协程而受挫(许多其他语言中的惰性生成器使用协程 - 有一个 boost 库或建议用于此 float - 不确定如何使用)，以及标准库对范围内迭代器的偏好(这使得一个算法更难返回下一个算法应该运行的范围)。有许多用于 C++ 的“函数式”库使用模板表达式和其他比上述代码复杂得多的技术来取得良好效果。