std::adjacent_difference() 算法

自 C++20 起

// (1)
template< class InputIt, class OutputIt >
constexpr OutputIt adjacent_difference( InputIt first, InputIt last, OutputIt d_first );

// (2)
template< class InputIt, class OutputIt, class BinaryOperation >
constexpr OutputIt adjacent_difference( InputIt first, InputIt last, OutputIt d_first, BinaryOperation op );

// (3)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >
ForwardIt2 adjacent_difference( ExecutionPolicy&& policy,
                                ForwardIt1 first, ForwardIt1 last, ForwardIt2 d_first );

// (4)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class BinaryOperation >
ForwardIt2 adjacent_difference( ExecutionPolicy&& policy,
                                ForwardIt1 first, ForwardIt1 last, ForwardIt2 d_first, BinaryOperation op );

自 C++17 起

// (1)
template< class InputIt, class OutputIt >
OutputIt adjacent_difference( InputIt first, InputIt last, OutputIt d_first );

// (2)
template< class InputIt, class OutputIt, class BinaryOperation >
OutputIt adjacent_difference( InputIt first, InputIt last, OutputIt d_first, BinaryOperation op );

// (3)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >
ForwardIt2 adjacent_difference( ExecutionPolicy&& policy,
                                ForwardIt1 first, ForwardIt1 last, ForwardIt2 d_first );

// (4)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class BinaryOperation >
ForwardIt2 adjacent_difference( ExecutionPolicy&& policy,
                                ForwardIt1 first, ForwardIt1 last, ForwardIt2 d_first, BinaryOperation op );

C++17 之前

// (1)
template< class InputIt, class OutputIt >
OutputIt adjacent_difference( InputIt first, InputIt last, OutputIt d_first );

// (2)
template< class InputIt, class OutputIt, class BinaryOperation >
OutputIt adjacent_difference( InputIt first, InputIt last, OutputIt d_first, BinaryOperation op );

如果 [first; last) 不为空，则计算其元素每个相邻对的第二个和第一个元素之间的差值，并将差值写入从 d_first + 1 开始的范围。
*first 的未修改副本被写入 *d_first。

• (1, 3) 使用 operator- 来计算差值。
• (2, 4) 使用给定的二元函数 op，所有这些函数都将其右侧的操作数应用 std::move (自 C++11 起)。

重载 (1) 的等效操作，如果 [first; last) 不为空，则使用累加器 acc 存储要减去的值

std::iterator_traits<InputIt>::value_type acc = *first;
*d_first = acc;

std::iterator_traits<InputIt>::value_type val1 = *(first + 1);
*(d_first + 1) = val1 - std::move(acc);
// or *(d_first + 1) = op(val1, std::move(acc)); for overload (2)
acc = std::move(val1);

std::iterator_traits<InputIt>::value_type val2 = *(first + 2);
*(d_first + 2) = val2 - std::move(acc);
acc = std::move(val2);

std::iterator_traits<InputIt>::value_type val3 = *(first + 3);
*(d_first + 3) = val3 - std::move(acc);
acc = std::move(val3);
// ...

重载 (2) 的等效操作，如果 [first; last) 不为空

// performed first
*d_first = *first;

// performed after the initial assignment, might not be sequenced
*(d_first + 1) = *(first + 1) - *(first);
// or *(d_first + 1) = op(*(first + 1), *(first)); for overload (4)
*(d_first + 2) = *(first + 2) - *(first + 1);
*(d_first + 3) = *(first + 3) - *(first + 2);
...

未定义行为

如果 op 使任何迭代器（包括任何尾迭代器）失效或修改所涉及范围的任何元素，则行为未定义

.

未定义行为

对于重载 (1 - 2)，如果 std::iterator_traits<InputIt>::value_type 不是 可复制赋值 (直到 C++11)可移动赋值 (自 C++11 起)，则行为未定义

.

参数

first last	元素的范围。
d_first	目标范围的开头。
policy	要使用的执行策略。有关详细信息，请参阅执行策略。
op	将应用的二元操作函数对象。函数的签名应等同于以下内容 Ret fun(const Type1 &a, const Type2 &b); 签名不需要包含 const&。 类型 Type1 和 Type2 必须是这样的：iterator_traits<InputIt>::value_type 类型的对象可以隐式转换为它们两者。 类型 Ret 必须使得类型为 OutputIt 的对象可以被解引用并赋值为类型 Ret 的值。

类型要求

InputIt 必须满足 LegacyInputIterator 的要求。

InputIt	LegacyInputIterator
OutputIt	LegacyOutputIterator
ForwardIt1 ForwardIt2	LegacyOutputIterator
T	CopyAssignable CopyConstructible

• 对于重载 (1 - 2)，InputIt 的值类型必须能够从 *first 构造。

• acc 和

  • (1) val - acc (直到 C++11)val - std::move(acc) (自 C++11 起)
  • (2) op(val, acc) (直到 C++11)op(val, std::move(acc) (自 C++11 起)

  的结果必须是可写入 d_first 的。

• *first 的结果和

  • (3) *first - *first
  • (4) op(*first, *first)

  的结果必须是可写入 d_first 的。

返回值

指向写入的最后一个元素之后的元素的迭代器，如果 [first; last) 为空，则为 d_first。

复杂度

给定 N 为 std::distance(first, last) - 1

• (1, 3) 恰好 N 次 operator- 的应用。
• (2, 4) 恰好 N 次二元函数 op 的应用。

异常

带有模板参数 ExecutionPolicy 的重载报告错误如下

• 如果在算法执行过程中调用的函数抛出异常，并且 ExecutionPolicy 是标准策略之一，则调用std::terminate。对于任何其他 ExecutionPolicy，行为是实现定义的.
• 如果算法未能分配内存，则抛出 std::bad_alloc。

可能的实现

adjacent_difference(1)

template<class InputIt, class OutputIt>
constexpr // since C++20
OutputIt adjacent_difference(InputIt first, InputIt last, OutputIt d_first)
{
    if (first == last)
        return d_first;

    typedef typename std::iterator_traits<InputIt>::value_type value_t;
    value_t acc = *first;
    *d_first = acc;

    while (++first != last)
    {
        value_t val = *first;
        *++d_first = val - std::move(acc); // std::move since C++11
        acc = std::move(val);
    }

    return ++d_first;
}

adjacent_difference(2)

template<class InputIt, class OutputIt, class BinaryOperation>
constexpr // since C++20
OutputIt adjacent_difference(InputIt first, InputIt last, OutputIt d_first, BinaryOperation op)
{
    if (first == last)
        return d_first;

    typedef typename std::iterator_traits<InputIt>::value_type value_t;
    value_t acc = *first;
    *d_first = acc;

    while (++first != last)
    {
        value_t val = *first;
        *++d_first = op(val, std::move(acc)); // std::move since C++11
        acc = std::move(val);
    }

    return ++d_first;
}

备注

acc 是由于 LWG issue 539 的解决而引入的。

使用 acc 而不是直接计算差值的原因是，如果以下类型不匹配，后者的语义会令人困惑

• InputIt 的值类型
• OutputIt 的可写类型
• operator- 或 op 的参数类型
• operator- 或 op 的返回类型

acc 用作中间对象来缓存迭代元素的值

• 其类型是 InputIt 的值类型
• 写入 d_first 的值（即 operator- 或 op 的返回值）被赋值给它
• 其值被传递给 operator- 或 op

char i_array[4] = {100, 100, 100, 100};
int  o_array[4];

// OK: performs conversions when needed
// 1. creates `acc` of type char (the value type)
// 2. `acc` is assigned to the first element of `o_array`
// 3. the char arguments are used for long multiplication (char -> long)
// 4. the long product is assigned to the output range (long -> int)
// 5. the next value of `i_array` is assigned to `acc`
// 6. go back to step 3 to process the remaining elements in the input range
std::adjacent_difference(i_array, i_array + 4, o_array, std::multiplies<long>{});

示例

Main.cpp

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

auto print = [](auto comment, auto const& sequence)
{
    std::cout << comment;
    for (const auto& n : sequence)
        std::cout << n << ' ';
    std::cout << '\n';
};

int main()
{
    // Default implementation - the difference b/w two adjacent items
    std::vector v {4, 6, 9, 13, 18, 19, 19, 15, 10};
    print("Initially, v = ", v);
    std::adjacent_difference(v.begin(), v.end(), v.begin());
    print("Modified v = ", v);

    // Fibonacci
    std::array<int, 10> a {1};
    std::adjacent_difference(std::begin(a), std::prev(std::end(a)),
                             std::next(std::begin(a)), std::plus<>{});
    print("Fibonacci, a = ", a);
}

输出

Initially, v = 4 6 9 13 18 19 19 15 10 
Modified v = 4 2 3 4 5 1 0 -4 -5 
Fibonacci, a = 1 1 2 3 5 8 13 21 34 55