namespace std {
template <class ForwardIterator>
void
rotate(ForwardIterator first,
ForwardIterator middle,
ForwardIterator last); // (1) C++03
template <class ForwardIterator>
ForwardIterator
rotate(ForwardIterator first,
ForwardIterator middle,
ForwardIterator last); // (1) C++11
template <class ForwardIterator>
constexpr ForwardIterator
rotate(ForwardIterator first,
ForwardIterator middle,
ForwardIterator last); // (1) C++20
template<class ExecutionPolicy, class ForwardIterator>
ForwardIterator
rotate(ExecutionPolicy&& exec,
ForwardIterator first,
ForwardIterator middle,
ForwardIterator last); // (2) C++17
}
概要
middle
の要素が先頭、middle-1
の要素が末尾となるように、イテレータ範囲[first,last)
の要素の並びを回転させる。
要件
ForwardIterator
はValueSwappable
の要件を満たしていること*first
の型はMoveConstructible
とMoveAssignable
の要件を満たしていること
事前条件
[first,middle)
と[middle,last)
は有効な範囲であること
効果
0 以上 last - first
未満の整数 i
について、first + i
の要素を first + (i + (last - middle)) % (last - first)
の位置へ移動させる。
戻り値
- C++03 まで
無し - C++11 から
回転前の先頭の要素を指すイテレータfirst + (last - middle)
備考
これは左への回転である
計算量
最大で last - first
回 swap する。
例
基本的な使い方
#include <algorithm>
#include <iostream>
#include <string>
int main() {
std::string str = "rotate";
std::rotate(str.begin(), str.begin() + 2, str.end());
std::cout << str << std::endl;
}
11
#include <algorithm>
#include <iostream>
#include <string>
int main() {
std::string str = "rotate";
std::rotate(str.begin(), str.begin() + 2, str.end());
std::cout << str << std::endl;
}
出力
tatero
swapをフックして可視化した例
#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>
#include <utility>
class Elem
{
public:
Elem() : c_('\0') {}
explicit Elem(char c) : c_(c) {}
Elem& operator=(const char c) { c_ = c; return *this; }
operator char() const { return c_; }
private:
char c_;
};
std::vector<Elem> seq;
void swap(Elem& lhs, Elem& rhs)
{
// std::rotate内部で実行されるswapを可視化できる。
// ライブラリの実装によってスワップの順番が異なることがある。
std::cout << "swapping "
<< &lhs << "(" << lhs << ") <-> "
<< &rhs << "(" << rhs << ")" << std::endl;
std::swap(lhs, rhs);
std::copy(seq.begin(), seq.end(), std::ostream_iterator<char>(std::cout));
std::cout << "\n\n";
}
int main()
{
char str[] = "012345";
seq.assign(str, str + sizeof(str) - 1);
std::rotate(seq.begin(), seq.begin() + 2, seq.end());
}
xxxxxxxxxx
#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>
#include <utility>
class Elem
{
public:
Elem() : c_('\0') {}
explicit Elem(char c) : c_(c) {}
Elem& operator=(const char c) { c_ = c; return *this; }
operator char() const { return c_; }
private:
char c_;
};
std::vector<Elem> seq;
出力例
swapping 0x1806040(0) <-> 0x1806042(2)
210345
swapping 0x1806041(1) <-> 0x1806043(3)
230145
swapping 0x1806042(0) <-> 0x1806044(4)
234105
swapping 0x1806043(1) <-> 0x1806045(5)
234501
実装例
処理系
- Clang: ??
- GCC: 4.7.0 ✅
- ICC: ??
- Visual C++: 2005 ✅, 2008 ✅, 2010 ✅, 2012 ✅, 2013 ✅, 2015 ✅
- C++11への対応(戻り値の変更)は2010から。