W C ++ 20 <algorithm>
nagłówek zyskuje dwa nowe algorytmy: shift_left()
ishift_right()
. Oba akceptują dowolny LegacyForwardIterator. W przypadku shift_left()
, podano, że „ruchy są wykonywane w rosnącej kolejności i
poczynając od 0
”; dla shift_right()
, określono, że „jeżeli ForwardIt
spełnia wymagania LegacyBidirectionalIterator, a następnie przemieszcza wykonywane są w kolejności malejącej i
począwszy od last - first - n - 1
”.
Mogę wymyślić dość łatwy sposób wdrożenia 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);
}
Jeśli ForwardIt
spełnia wymagania LegacyBidirectionalIterator, widzę, że shift_right()
można je zaimplementować w bardzo podobny sposób shift_left()
. Jednak nie jest wcale jasne, jak można zaimplementować shift_right()
dla dwukierunkowego iteratora do przodu.
Wymyśliłem algorytm, który wykorzystuje tę przestrzeń [first, first+n)
jako przestrzeń do rysowania do zamiany elementów, ale wydaje się nieco bardziej marnotrawny niż algorytm dla shift_left()
powyższego:
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;
}
Czy byłby lepszy lub „zamierzony” sposób wdrożenia shift_right()
?
źródło
std::move
zamiaststd::copy
...Odpowiedzi:
To jest przykładowa implementacja zmian: https://github.com/danra/shift_proposal/blob/master/shift_proposal.h
Z dokumentu wniosku: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0769r0.pdf
źródło
void(++trail)
...