namespace std::ranges {
  template <permutable I,
            sentinel_for<I> S>
  constexpr subrange<I>
    shift_right(I first,
                S last,
                iter_difference_t<I> n); // (1) C++23

  template <forward_range R>
    requires permutable<iterator_t<R>>
  constexpr borrowed_subrange_t<R>
    shift_right(R&& r,
                range_difference_t<R> n); // (2) C++23

  template <execution-policy Ep,
            random_access_iterator I,
            sized_sentinel_for<I> S>
    requires permutable<I>
  subrange<I>
    shift_right(Ep&& exec,
                I first,
                S last,
                iter_difference_t<I> n); // (3) C++26

  template <execution-policy Ep,
            sized-random-access-range R>
    requires permutable<iterator_t<R>>
  borrowed_subrange_t<R>
    shift_right(Ep&& exec,
                R&& r,
                range_difference_t<R> n); // (4) C++26
}

概要

範囲の要素をn個だけ右にシフトさせる。

• (1): イテレータ範囲を指定する
• (2): Rangeを直接指定する
• (3): (1)の並列アルゴリズム版。実行ポリシーを指定する
• (4): (2)の並列アルゴリズム版。実行ポリシーを指定する

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

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

事前条件

n >= 0

効果

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

戻り値

new_firstを次のように定義する。

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

このとき、 {new_first, 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::ranges::shift_right(v, 2);

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

出力

1,2,1,2,3,

並列アルゴリズムの例 (C++26)

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

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

  // 並列に2つ右シフト
  auto result = std::ranges::shift_right(std::execution::par, v, 2);

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

出力

1 2 3

バージョン

言語

• C++23

処理系

• Clang: ??
• GCC: ??
• Visual C++: ??

参照

• N4901 25 Algorithms library
• P3179R9 C++ parallel range algorithms