std::adjacent_difference

定義於標頭檔案 `<numeric>`
template< class InputIt, class OutputIt > OutputIt adjacent_difference( InputIt first, InputIt last, OutputIt d_first );	(1)	(C++20 起為 constexpr)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 > ForwardIt2 adjacent_difference( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last, ForwardIt2 d_first );	(2)	(C++17 起)
template< class InputIt, class OutputIt, class BinaryOp > OutputIt adjacent_difference( InputIt first, InputIt last, OutputIt d_first, BinaryOp op );	(3)	(C++20 起為 constexpr)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class BinaryOp > ForwardIt2 adjacent_difference( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last, ForwardIt2 d_first, BinaryOp op );	(4)	(C++17 起)

令 T 為 decltype(first) 的值型別。

1) 若 [first, last) 為空，則不執行任何操作。

否則，按順序執行以下操作：

建立一個型別為 T 的累加器 acc，並用 *first 初始化它。
將 acc 賦值給 *d_first。
對於 [++first, last) 中的每個迭代器 iter，按順序執行以下操作：

a) 建立一個型別為 T 的物件 val，並用 *iter 初始化它。

b) 計算 val - acc(C++20 前)val - std::move(acc)(C++20 起)。

c) 將結果賦值給 *++d_first。

d) 從 val 複製(C++20 前)移動(C++20 起) 賦值給 acc。

2) 若 [first, last) 為空，則不執行任何操作。

否則，按順序執行以下操作：

將 *first 賦值給 *d_first。
對於 [1, std::distance(first, last)) 中的每個整數 i，按順序執行以下操作：

a) 計算 curr - prev，其中 curr 是 first 的第 i 個迭代器，prev 是 first 的第 i - 1 個迭代器。

b) 將結果賦值給 *dest，其中 dest 是 d_first 的第 i 個迭代器。

3) 與 (1) 相同，但改為計算 op(val, acc)(C++20 前)op(val, std::move(acc))(C++20 起)。

4) 與 (2) 相同，但改為計算 op(curr, prev)。

給定 binary_op 作為實際的二元操作，

如果滿足以下任何條件，程式將不正確：

對於過載 (1,3)

T 不能從 *first 構造。
acc 不能寫入 d_first。
binary_op(val, acc)(C++20 前)binary_op(val, std::move(acc))(C++20 起) 的結果不能寫入 d_first。

對於過載 (2,4)

*first 不能寫入 d_first。
binary_op(*first, *first) 的結果不能寫入 d_first。

給定 d_last 為要返回的迭代器，若滿足以下任一條件，則行為未定義：

對於過載 (1,3)，T 不是可移動賦值 (MoveAssignable) 的。

(C++20 起)

對於過載 (2,4)，[first, last) 和 [d_first, d_last) 重疊。
binary_op 修改了 [first, last) 或 [d_first, d_last) 的任何元素。
binary_op 使 [first, last] 或 [d_first, d_last] 中的任何迭代器或子範圍失效。

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 的要求。
- `OutputIt` 必須滿足 LegacyOutputIterator 的要求。
- `ForwardIt1, ForwardIt2` 必須滿足 LegacyForwardIterator 的要求。

[編輯] 返回值

指向所寫入的最後一個元素之後的迭代器，若 [first, last) 為空則為 d_first。

[編輯] 複雜度

給定 $\scriptsize N$ $N$ 為 std::distance(first, last)

1,2) 精確執行

N-1

次 operator-。

3,4) 精確執行

N-1

次二元函式 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++20
        acc = std::move(val);
    }
 
    return ++d_first;
}

adjacent_difference (3)

template<class InputIt, class OutputIt, class BinaryOp>
constexpr // since C++20
OutputIt adjacent_difference(InputIt first, InputIt last, 
                             OutputIt d_first, BinaryOp 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++20
        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>{});

[編輯] 示例

執行此程式碼

#include <array>
#include <functional>
#include <iostream>
#include <iterator>
#include <numeric>
#include <vector>
 
void println(auto comment, const auto& sequence)
{
    std::cout << comment;
    for (const auto& n : sequence)
        std::cout << n << ' ';
    std::cout << '\n';
};
 
int main()
{
    // Default implementation - the difference between two adjacent items
    std::vector v{4, 6, 9, 13, 18, 19, 19, 15, 10};
    println("Initially, v = ", v);
    std::adjacent_difference(v.begin(), v.end(), v.begin());
    println("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<>{});
    println("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

[編輯] 缺陷報告

下列更改行為的缺陷報告追溯地應用於以前出版的 C++ 標準。

缺陷報告	應用於	釋出時的行為	正確的行為
LWG 242	C++98	op 不得有副作用	它不能修改涉及的範圍
LWG 539	C++98	結果所需型別要求評估和賦值缺失	已新增
LWG 3058	C++17	對於過載 (2,4)，每次呼叫 operator- 或 op 的結果都會賦值給一個臨時物件，然後該物件再賦值給輸出範圍	直接將結果賦值給輸出範圍

[編輯] 參閱

partial_sum	計算一個範圍元素的部分和 (函式模板) [編輯]
accumulate	對一個範圍的元素進行求和或摺疊 (函式模板) [編輯]

編譯器支援
自由（freestanding）與宿主（hosted）
語言
標準庫
標準庫標頭檔案
具名要求
特性測試宏 (C++20)
語言支援庫
概念庫 (C++20)
診斷庫
記憶體管理庫
超程式設計庫 (C++11)
通用工具庫
容器庫
迭代器庫
範圍庫 (C++20)
演算法庫
字串庫
文字處理庫
數值庫
日期和時間庫
輸入/輸出庫
檔案系統庫 (C++17)
併發支援庫 (C++11)
執行控制庫 (C++26)
技術規範
符號索引
外部庫

cppreference.com

名稱空間

變體

檢視

操作