In C ++ 20 <algorithm>
erhält der Header zwei neue Algorithmen: shift_left()
undshift_right()
. Beide akzeptieren jeden LegacyForwardIterator. Denn shift_left()
es wird spezifiziert, dass "die Bewegungen in aufsteigender Reihenfolge von i
beginnend ausgeführt werden 0
"; denn shift_right()
es wird angegeben, dass "wenn ForwardIt
die LegacyBidirectionalIterator-Anforderungen erfüllt sind, die Bewegungen in absteigender Reihenfolge von i
beginnend ausgeführt werden last - first - n - 1
".
Ich kann mir einen relativ einfachen Weg vorstellen, um Folgendes umzusetzen shift_left()
:
template <typename ForwardIt>
constexpr inline ForwardIt shift_left(ForwardIt first, ForwardIt last, typename std::iterator_traits<ForwardIt>::difference_type n) {
if (n <= 0) return last;
ForwardIt it = first;
for (; n > 0; --n, ++it) {
if (it == last) return first;
}
return std::move(it, last, first);
}
Wenn ForwardIt
die Anforderungen von LegacyBidirectionalIterator erfüllt sind, kann ich sehen, dass shift_right()
dies auf sehr ähnliche Weise implementiert werden kann wie shift_left()
. Es ist jedoch überhaupt nicht klar, wie man es shift_right()
für nicht bidirektionale Vorwärtsiteratoren implementieren könnte .
Ich habe einen Algorithmus gefunden, der das Leerzeichen [first, first+n)
als Arbeitsbereich zum Austauschen von Elementen verwendet, aber es scheint ziemlich verschwenderischer zu sein als der oben beschriebene Algorithmus shift_left()
:
template <typename ForwardIt>
constexpr inline ForwardIt shift_right(ForwardIt first, ForwardIt last, typename std::iterator_traits<ForwardIt>::difference_type n) {
if (n <= 0) return first;
ForwardIt it = first;
for (; n > 0; --n, ++it) {
if (it == last) return last;
}
ForwardIt ret = it;
ForwardIt ret_it = first;
for (; it != last; ++it) {
std::iter_swap(ret_it, it);
ret_it++;
if (ret_it == ret) ret_it = first;
}
return ret;
}
Gibt es eine bessere oder "beabsichtigte" Art der Implementierung shift_right()
?
quelle
std::move
anstelle vonstd::copy
...Antworten:
Dies ist die Beispielimplementierung für Schichten: https://github.com/danra/shift_proposal/blob/master/shift_proposal.h
Aus dem Vorschlagsdokument: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0769r0.pdf
quelle
void(++trail)
...