4. adjacent_difference

最終更新日時(UTC):
が更新

履歴 編集

function template
<numeric>

std::adjacent_difference

namespace std {
  template <class InputIterator, class OutputIterator>
  OutputIterator
    adjacent_difference(InputIterator first,
                        InputIterator last,
                        OutputIterator result);     // (1) C++03
  template <class InputIterator, class OutputIterator>
  constexpr OutputIterator
    adjacent_difference(InputIterator first,
                        InputIterator last,
                        OutputIterator result);     // (1) C++20

  template <class InputIterator, class OutputIterator, class BinaryOperation>
  OutputIterator
    adjacent_difference(InputIterator first,
                        InputIterator last,
                        OutputIterator result,
                        BinaryOperation binary_op); // (2) C++03
  template <class InputIterator, class OutputIterator, class BinaryOperation>
  constexpr OutputIterator
    adjacent_difference(InputIterator first,
                        InputIterator last,
                        OutputIterator result,
                        BinaryOperation binary_op); // (2) C++20

  template <class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
  ForwardIterator2
    adjacent_difference(ExecutionPolicy&& exec,
                        ForwardIterator1 first,
                        ForwardIterator1 last,
                        ForwardIterator2 result);   // (3) C++17

  template <class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
            class BinaryOperation>
  ForwardIterator2
    adjacent_difference(ExecutionPolicy&& exec,
                        ForwardIterator1 first,
                        ForwardIterator1 last,
                        ForwardIterator2 result,
                        BinaryOperation binary_op); // (4) C++17
}

概要

隣接する要素間の差を計算する。

この関数に与えられたイテレータ範囲[first, last)をrとして、その範囲の隣接する要素同士の差を、{r[0], r[1] - r[0], r[2] - r[1], r[3] - r[2], r[4] - r[3]}のように演算して求められた新たな範囲を返す。

  • (1), (3) : 各隣接要素aとbをoperator-(b, a)で減算した結果を、result出力イテレータに書き込む
  • (2), (4) : 各隣接要素aとbをbinary_op(b, a)で減算した結果を、result出力イテレータに書き込む

要件

  • (2) :
    • C++03まで : 関数オブジェクトbinary_opの呼び出しは、副作用を起こしてはならない
    • C++11から : 関数オブジェクトbinary_opの呼び出しが、イテレータ範囲[first, last]およびイテレータ範囲[result, result + (last - first)]の要素変更、イテレータの無効化をしてはならない
  • (3), (4) :

テンプレートパラメータ制約

  • (1) :
    • C++11から : InputIteratorが指す値の型が、ムーブ代入可能であり、*firstで初期化でき、result出力イテレータに書き込めること
    • C++11からC++17まで : InputIteratorが指す値の型のオブジェクトaとbにおいて、式b - aの結果がresult出力イテレータに書き込めること
    • C++20から : InputIteratorが指す値の型のオブジェクトaとbにおいて、式b - std::move(a)の結果がresult出力イテレータに書き込めること
  • (2)
    • C++11から : InputIteratorが指す値の型が、ムーブ代入可能であり、*firstで初期化でき、result出力イテレータに書き込めること
    • C++11からC++17まで : InputIteratorが指す値の型のオブジェクトaとbにおいて、式binary_op(b, a)の結果がresult出力イテレータに書き込めること
    • C++20から : InputIteratorが指す値の型のオブジェクトaとbにおいて、式binary_op(b, std::move(a))の結果がresult出力イテレータに書き込めること
  • (3) :
    • ForwardIterator1が指す値の型が、ムーブ代入可能であり、*firstで初期化でき、ForwardIterator2が指す値の型に対して代入できること
    • ForwardIterator1が指す値の型のオブジェクトaとbにおいて、式b - aの結果が、ForwardIterator2が指す値の型に対して代入できること
  • (4) :
    • ForwardIterator1が指す値の型が、ムーブ代入可能であり、*firstで初期化でき、ForwardIterator2が指す値の型に対して代入できること
    • ForwardIterator1が指す値の型のオブジェクトaとbにおいて、式binary_op(b, a)の結果が、ForwardIterator2が指す値の型に対して代入できること

効果

  • (1), (2) : 非空のイテレータ範囲[first, last)について、
    1. *result = *firstで結果の初期値を書き込む。acc = *firstとしてひとつ前の位置の値を保持する
    2. イテレータ範囲[first + 1, last)の各イテレータをi、そのイテレータが指す値をvalとして定義する 3.
      • C++17 : (1)であればval - acc、(2)であればbinary_op(val, acc)で隣接値を求めて、その結果を*resultに代入する
      • C++20 : (1)であればval - std::move(acc)、(2)であればbinary_op(val, std::moved(acc))で隣接値を求めて、その結果を*resultに代入する
    3. valをaccにムーブ代入し、ひとつ前の位置の値を更新する
  • (3), (4) : 非空のイテレータ範囲[first, last)について、
    1. *result = *firstで結果の初期値を代入する
    2. インデックス範囲[1, last - first - 1]のそれぞれの値dとして定義する
    3. (3)であればval = *(first + d) - *(first + d - 1)、(4)であればval = binary_op(*(first + d), *(first + d - 1))として、隣接値を求める
    4. *(result + d) = valで各隣接値を出力する

戻り値

result + (last - first)

計算量

ちょうど(last - first) - 1回の2項演算を適用する

備考

  • (1), (2) : resultはfirstと同値になるだろう

例

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

template <class Range>
void print(const Range& r)
{
  for(const auto& x : r)
    std::cout << x << " --> ";
  std::cout << "end" << std::endl;
}

int main()
{
  std::vector<double> v = {0.0, 0.2, 0.4, 0.6, 0.8};
  std::vector<double> diffs(v.size());

  // (1) : operator-()を使用して、隣接要素の差を計算する
  std::adjacent_difference(v.cbegin(), v.cend(), diffs.begin());
  print(diffs);

  // (2) : 最後の引数として与えた任意の2項演算関数によって、
  //       隣接要素の差を計算する
  std::adjacent_difference(v.cbegin(), v.cend(), diffs.begin(),
    [](double a, double b) {
      return a*a - b*b; // 2点間の距離の計算
    });
  print(diffs);
}

出力

0 --> 0.2 --> 0.2 --> 0.2 --> 0.2 --> end
0 --> 0.04 --> 0.12 --> 0.2 --> 0.28 --> end

実装例

#include <iterator>
#include <functional>

// (2)
template <class InputIterator, class OutputIterator, class BinaryOperation>
OutputIterator adjacent_difference(InputIterator first,
                                   InputIterator last,
                                   OutputIterator result,
                                   BinaryOperation binary_op)
{
  if (first == last)
    return result;

  using value_type = typename std::iterator_traits<InputIterator>::value_type;

  value_type acc = *first;
  *result = acc;
  ++result;
  ++first;

  while (first != last) {
    value_type val = *first;
    *result = binary_op(val, std::move(acc));
    acc = std::move(val);

    ++result;
    ++first;
  }
  return result;
}

// (1)
template <class InputIterator, class OutputIterator>
OutputIterator adjacent_difference(InputIterator first, InputIterator last, OutputIterator result)
{
  using value_type = typename std::iterator_traits<InputIterator>::value_type;
  return adjacent_difference(first, last, result, std::minus<value_type>());
}

参照