std::rotate
| Definiert in Header <algorithm> |
||
| template< class ForwardIt > ForwardIt rotate( ForwardIt first, ForwardIt middle, ForwardIt last ); |
(1) | (constexpr seit C++20) |
| template< class ExecutionPolicy, class ForwardIt > ForwardIt rotate( ExecutionPolicy&& policy, |
(2) | (seit C++17) |
std::rotate die Elemente im Bereich [first, last) so aus, dass die Elemente in [first, middle) nach den Elementen in [middle, last) platziert werden, während die Reihenfolge der Elemente in beiden Bereichen erhalten bleibt.|
std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> ist true. |
(bis C++20) |
|
std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>> ist true. |
(seit C++20) |
Wenn eine der folgenden Bedingungen erfüllt ist, ist das Verhalten undefiniert
-
[first,middle)oder[middle,last)ist kein gültiger Bereich.
|
(bis C++11) |
|
(seit C++11) |
Inhalt |
[edit] Parameter
| first, last | - | das Iteratorenpaar, das den zu rotierenden Elementbereich definiert |
| middle | - | das Element, das am Anfang des rotierten Bereichs erscheinen soll |
| policy | - | die Ausführungsrichtlinie, die verwendet werden soll |
| Typanforderungen | ||
-ForwardIt muss die Anforderungen von LegacyForwardIterator erfüllen. | ||
[edit] Rückgabewert
Der Iterator auf das Element, auf das ursprünglich von *first verwiesen wurde, d. h. der std::distance(middle, last)te nächste Iterator von first.
[edit] Komplexität
Höchstens std::distance(first, last) Vertauschungen.
[edit] Ausnahmen
Die Überladung mit einem Template-Parameter namens ExecutionPolicy meldet Fehler wie folgt
- Wenn die Ausführung einer Funktion, die als Teil des Algorithmus aufgerufen wird, eine Ausnahme auslöst und
ExecutionPolicyeine der Standardrichtlinien ist, wird std::terminate aufgerufen. Für jede andereExecutionPolicyist das Verhalten implementierungsabhängig. - Wenn dem Algorithmus der Speicher zur Neuzuweisung fehlt, wird std::bad_alloc ausgelöst.
[edit] Mögliche Implementierung
Siehe auch die Implementierungen in libstdc++, libc++ und MSVC STL.
template<class ForwardIt> constexpr // since C++20 ForwardIt rotate(ForwardIt first, ForwardIt middle, ForwardIt last) { if (first == middle) return last; if (middle == last) return first; ForwardIt write = first; ForwardIt next_read = first; // read position for when “read” hits “last” for (ForwardIt read = middle; read != last; ++write, ++read) { if (write == next_read) next_read = read; // track where “first” went std::iter_swap(write, read); } // rotate the remaining sequence into place rotate(write, next_read, last); return write; } |
[edit] Hinweise
std::rotate hat auf gängigen Implementierungen eine bessere Effizienz, wenn ForwardIt LegacyBidirectionalIterator oder (besser) LegacyRandomAccessIterator erfüllt.
Implementierungen (z.B. MSVC STL) können Vektorisierung aktivieren, wenn der Iteratortyp LegacyContiguousIterator erfüllt und das Vertauschen seines Wertetyps weder eine nicht-triviale spezielle Member-Funktion noch eine über ADL gefundene swap-Funktion aufruft.
[edit] Beispiel
std::rotate ist ein gängiger Baustein in vielen Algorithmen. Dieses Beispiel demonstriert Insertion Sort.
#include <algorithm> #include <iostream> #include <vector> auto print = [](const auto remark, const auto& v) { std::cout << remark; for (auto n : v) std::cout << n << ' '; std::cout << '\n'; }; int main() { std::vector<int> v{2, 4, 2, 0, 5, 10, 7, 3, 7, 1}; print("before sort:\t\t", v); // insertion sort for (auto i = v.begin(); i != v.end(); ++i) std::rotate(std::upper_bound(v.begin(), i, *i), i, i + 1); print("after sort:\t\t", v); // simple rotation to the left std::rotate(v.begin(), v.begin() + 1, v.end()); print("simple rotate left:\t", v); // simple rotation to the right std::rotate(v.rbegin(), v.rbegin() + 1, v.rend()); print("simple rotate right:\t", v); }
Ausgabe
before sort: 2 4 2 0 5 10 7 3 7 1 after sort: 0 1 2 2 3 4 5 7 7 10 simple rotate left: 1 2 2 3 4 5 7 7 10 0 simple rotate right: 0 1 2 2 3 4 5 7 7 10
[edit] Fehlerberichte
Die folgenden Verhaltensändernden Fehlerberichte wurden rückwirkend auf zuvor veröffentlichte C++-Standards angewendet.
| DR | angewendet auf | Verhalten wie veröffentlicht | Korrigiertes Verhalten |
|---|---|---|---|
| LWG 488 | C++98 | Der neue Speicherort des Elements, auf das von first gezeigt wurde, wurde nicht zurückgegeben. | zurückgegeben |
[edit] Siehe auch
| Kopiert und rotiert einen Bereich von Elementen (Funktionstemplate) | |
| (C++20) |
Rotiert die Reihenfolge der Elemente in einem Bereich (Algorithmus-Funktionsobjekt) |
