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 に代入します。
イテレータ iter を [++first, last) の範囲で順番に処理し、各イテレータに対して以下の操作を順番に実行します。

a) 型 T のオブジェクト val を作成し、*iter で初期化します。

b) val - acc(until C++20)val - std::move(acc)(since C++20) を計算します。

c) 結果を *++d_first に代入します。

d) val(until C++20)val(since C++20) から acc へコピー代入（until C++20）、またはムーブ代入（since C++20）します。

2) [first, last) が空の場合、何も行いません。

それ以外の場合、以下の操作を順番に実行します。

*first を *d_first に代入します。
整数 i を [1, std::distance(first, last)) の範囲で順番に処理し、各整数に対して以下の操作を順番に実行します。

a) curr を first の次の i 番目のイテレータ、prev を first の次の i - 1 番目のイテレータとして、curr - prev を計算します。

b) 結果を dest、すなわち d_first の次の i 番目のイテレータに代入します。

3) (1) と同じですが、op(val, acc)(until C++20)op(val, std::move(acc))(since C++20) を計算します。

4) (2) と同じですが、op(curr, prev) を計算します。

実際のバイナリ操作として binary_op が与えられた場合

以下のいずれかの条件が満たされる場合、プログラムは不適格です。

オーバーロード (1,3) について

T は *first から構築可能ではありません。
acc は d_first に書き込み可能ではありません。
binary_op(val, acc)(until C++20)binary_op(val, std::move(acc))(since 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 の要件を満たさなければなりません。

[edit] 戻り値

[first, last) が空の場合、d_first を返します。それ以外の場合、書き込まれた最後の要素の次のイテレータを返します。

[edit] 計算量

std::distance(first, last) を $\scriptsize N$ $N$ とする

1,2)

N-1

回の operator- の適用。

3,4)

N-1

回の二項演算子 op の適用。

[edit] 例外

ExecutionPolicy というテンプレートパラメータを持つオーバーロードは、次のようにエラーを報告します。

アルゴリズムの一部として呼び出された関数の実行が例外をスローし、ExecutionPolicy が標準ポリシーのいずれかである場合、std::terminate が呼び出されます。その他の ExecutionPolicy の場合、動作は実装定義です。
アルゴリズムがメモリの割り当てに失敗した場合、std::bad_alloc がスローされます。

[edit] 実装例

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

[edit] 注釈

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

[edit] 例

このコードを実行

#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

[edit] 不具合報告

以下の動作変更を伴う欠陥報告が、以前に公開されたC++標準に遡って適用されました。

DR	適用対象	公開された動作	正しい動作
LWG 242	C++98	op には副作用があってはなりません。	以下を変更することはできません。関連する範囲。
LWG 539	C++98	結果に必要な型要件。評価および代入が有効であることに関する記述が欠落していました。	追加された
LWG 3058	C++17	オーバーロード (2,4) について、各 operator- または op の呼び出し結果が一時オブジェクトに代入され、そのオブジェクトが出力範囲に代入されていました。各呼び出し結果を一時オブジェクトに代入する。	結果を代入する。出力へ範囲へ直接。

[edit] 関連項目

partial_sum	範囲の要素の部分和を計算する (関数テンプレート) [編集]
accumulate	範囲の要素を合計または畳み込む (関数テンプレート) [編集]

コンパイラサポート
フリースタンディングとホスト
言語
標準ライブラリ
標準ライブラリヘッダー
名前付き要件
機能テストマクロ (C++20)
言語サポートライブラリ
コンセプトライブラリ (C++20)
診断ライブラリ
メモリ管理ライブラリ
メタプログラミングライブラリ (C++11)
汎用ユーティリティライブラリ
コンテナライブラリ
イテレータライブラリ
Rangesライブラリ (C++20)
アルゴリズムライブラリ
文字列ライブラリ
テキスト処理ライブラリ
数値ライブラリ
日付と時刻ライブラリ
入出力ライブラリ
ファイルシステムライブラリ (C++17)
並行サポートライブラリ (C++11)
実行制御ライブラリ (C++26)
Technical specifications (技術仕様)
シンボルインデックス
外部ライブラリ

cppreference.com

名前空間

変種

表示

操作