ranges_shift_left.md

shift_left

• algorithm[meta header]
• std::ranges[meta namespace]
• function template[meta id-type]
• cpp23[meta cpp]

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

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

• permutable[link /reference/iterator/permutable.md]
• sentinel_for[link /reference/iterator/sentinel_for.md]
• subrange[link /reference/ranges/subrange.md]
• iter_difference_t[link /reference/iterator/iter_difference_t.md]
• forward_range[link /reference/ranges/forward_range.md]
• iterator_t[link /reference/ranges/iterator_t.md]
• borrowed_subrange_t[link /reference/ranges/borrowed_subrange_t.md]
• range_difference_t[link /reference/ranges/range_difference_t.md]

概要

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

• (1): イテレータ範囲を指定する
• (2): Rangeを直接指定する

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

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

事前条件

n >= 0

効果

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

戻り値

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

• n > 0かつn < last - firstである場合、first + (last - first - n)を返す
• n > 0である場合、firstを返す
• いずれでもない場合、lastを返す

このとき、 {first, new_last}

計算量

最大で(last - first) - n回の代入を行う

備考

• シフト数として負数を指定することはできないが、この関数には符号付き整数型を指定することとなっている。これは、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_left(v, 2);

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

• std::ranges::shift_left[color ff0000]

出力

3,4,5,4,5,

バージョン

言語

• C++23

処理系

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

参照

• N4901 25 Algorithms library