namespace std {
  template <class ForwardIterator>
  constexpr ForwardIterator
    shift_right(ForwardIterator first,
                ForwardIterator last,
                typename iterator_traits<ForwardIterator>::difference_type n); // (1)

  template <class ExecutionPolicy, class ForwardIterator>
  ForwardIterator
    shift_right(ExecutionPolicy&& exec,
                ForwardIterator first,
                ForwardIterator last,
                typename iterator_traits<ForwardIterator>::difference_type n); // (2)
}

概要

イテレータ範囲[first, last)の要素をn個だけ右にシフトさせる。

この関数に符号付き整数型のシフト数として、0および負数を指定した場合はなにもしない。

この関数によって要素をn個だけ右にシフトすると、[first, first + n)の範囲は、ムーブされたあとの「使用してはいけないオブジェクト」となる。その範囲には、循環バッファ (circular buffer) のように新たな要素を代入するか、コンテナのerase()メンバ関数を使用して使わなくなった範囲を削除するなどの対応が必要になる。

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

• *firstの型がムーブ代入可能であること
• ForwardIterator型が、Bidirectional Iteratorの要件もしくはValueSwappableの要件を満たすこと

事前条件

n >= 0

効果

• n == 0である場合、なにもしない
• n >= last - firstである場合、なにもしない
• i < (last - first) - nである非負の各iについて、first + i位置の要素をfirst + n + i位置にムーブする
  • (1)では、ForwardIterator型がBidirectional Iteratorの要件を満たす場合は、i = (last - first) - n - 1からi = 0の順に処理する

戻り値

• n < last - firstである場合、first + nを返す
• そうでなければ、lastを返す

計算量

最大で(last - first) - n回の代入もしくはswap操作を行う

備考

• シフト数として負数を指定することはできないが、この関数には符号付き整数型を指定することとなっている。これは、Bidirectional Iterator向けの最適化した実装をする場合にstd::prev()関数を使用するため、そちらのパラメータ型と合わせたことによる
• shift_left()とshift_right()で関数が分かれているのは、コンパイルしたコードサイズを小さくするためと、左シフトと右シフトでは最大パフォーマンスのための実装が異なるためである

例

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
  std::vector<int> v = {1, 2, 3, 4, 5};

  std::shift_right(v.begin(), v.end(), 2);

  for (int x : v) {
    std::cout << x << ',';
  }
  std::cout << std::endl;
}

出力

1,2,1,2,3,

バージョン

言語

• C++20

処理系

• Clang: 12.0.1 ✅
• GCC: 10.1.0 ✅
• Visual C++: ??

関連項目

• shift_left
• rotate
• ranges::shift_right

参照

• P1243R4 Rangify New Algorithms
• P0769R2 | Add shift to <algorithm>
• [idea for proposal] Adding std::shift to <algorithm> - std-proposals