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

履歴 編集

function template
<algorithm>

std::ranges::shift_right(C++23)

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

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

概要

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

  • (1): イテレータペアで範囲を指定する
  • (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 > 0かつn < last - firstである場合、first + nを返す
  • n > 0である場合、lastを返す
  • いずれでもない場合、firstを返す

このとき、 {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++23

処理系

参照