shift_right() 打算如何在 C++20 中实现?
How is shift_right() intended to be implemented in C++20?
在 C++20 中,<algorithm>
header 获得了两个新算法:shift_left()
and shift_right()
。它们都接受任何 LegacyForwardIterator。对于shift_left()
,指定"the moves are performed in increasing order of i
starting from 0
" ;对于shift_right()
,指定"if ForwardIt
meets the LegacyBidirectionalIterator requirements, then the moves are performed in decreasing order of i
starting from last - first - n - 1
".
我能想到一个相当简单的实现方法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);
}
如果 ForwardIt
满足 LegacyBidirectionalIterator 要求,我可以看到 shift_right()
可以用与 shift_left()
非常相似的方式实现。但是,完全不清楚如何为 non-bidirectional 前向迭代器实现 shift_right()
。
我想出了一个算法,它使用 [first, first+n)
处的 space 作为 scratch space 来交换元素,但它似乎比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;
}
是否有更好的或 "intended" 实施方式 shift_right()
?
这是班次的实施示例:https://github.com/danra/shift_proposal/blob/master/shift_proposal.h
link 来自提案文件:http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0769r0.pdf
#include <algorithm>
#include <iterator>
#include <type_traits>
#include <utility>
template<class I>
using difference_type_t = typename std::iterator_traits<I>::difference_type;
template<class I>
using iterator_category_t = typename std::iterator_traits<I>::iterator_category;
template<class I, class Tag, class = void>
constexpr bool is_category = false;
template<class I, class Tag>
constexpr bool is_category<I, Tag, std::enable_if_t<
std::is_convertible_v<iterator_category_t<I>, Tag>>> = true;
/// Increment (decrement for negative n) i |n| times or until i == bound,
/// whichever comes first. Returns n - the difference between i's final position
/// and its initial position. (Note: "advance" has overloads with this behavior
/// in the Ranges TS.)
template<class I>
constexpr difference_type_t<I> bounded_advance(
I& i, difference_type_t<I> n, I const bound)
{
if constexpr (is_category<I, std::bidirectional_iterator_tag>) {
for (; n < 0 && i != bound; ++n, void(--i)) {
;
}
}
for(; n > 0 && i != bound; --n, void(++i)) {
;
}
return n;
}
template<class ForwardIt>
ForwardIt shift_left(ForwardIt first, ForwardIt last, difference_type_t<ForwardIt> n)
{
if (n <= 0) {
return last;
}
auto mid = first;
if (::bounded_advance(mid, n, last)) {
return first;
}
return std::move(std::move(mid), std::move(last), std::move(first));
}
template<class ForwardIt>
ForwardIt shift_right(ForwardIt first, ForwardIt last, difference_type_t<ForwardIt> n)
{
if (n <= 0) {
return first;
}
if constexpr (is_category<ForwardIt, std::bidirectional_iterator_tag>) {
auto mid = last;
if (::bounded_advance(mid, -n, first)) {
return last;
}
return std::move_backward(std::move(first), std::move(mid), std::move(last));
} else {
auto result = first;
if (::bounded_advance(result, n, last)) {
return last;
}
// Invariant: next(first, n) == result
// Invariant: next(trail, n) == lead
auto lead = result;
auto trail = first;
for (; trail != result; ++lead, void(++trail)) {
if (lead == last) {
// The range looks like:
//
// |-- (n - k) elements --|-- k elements --|-- (n - k) elements --|
// ^-first trail-^ ^-result last-^
//
// Note that distance(first, trail) == distance(result, last)
std::move(std::move(first), std::move(trail), std::move(result));
return result;
}
}
for (;;) {
for (auto mid = first; mid != result; ++lead, void(++trail), ++mid) {
if (lead == last) {
// The range looks like:
//
// |-- (n - k) elements --|-- k elements --|-- ... --|-- n elements --|
// ^-first mid-^ result-^ ^-trail last-^
//
trail = std::move(mid, result, std::move(trail));
std::move(std::move(first), std::move(mid), std::move(trail));
return result;
}
std::iter_swap(mid, trail);
}
}
}
}
在 C++20 中,<algorithm>
header 获得了两个新算法:shift_left()
and shift_right()
。它们都接受任何 LegacyForwardIterator。对于shift_left()
,指定"the moves are performed in increasing order of i
starting from 0
" ;对于shift_right()
,指定"if ForwardIt
meets the LegacyBidirectionalIterator requirements, then the moves are performed in decreasing order of i
starting from last - first - n - 1
".
我能想到一个相当简单的实现方法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);
}
如果 ForwardIt
满足 LegacyBidirectionalIterator 要求,我可以看到 shift_right()
可以用与 shift_left()
非常相似的方式实现。但是,完全不清楚如何为 non-bidirectional 前向迭代器实现 shift_right()
。
我想出了一个算法,它使用 [first, first+n)
处的 space 作为 scratch space 来交换元素,但它似乎比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;
}
是否有更好的或 "intended" 实施方式 shift_right()
?
这是班次的实施示例:https://github.com/danra/shift_proposal/blob/master/shift_proposal.h
link 来自提案文件:http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0769r0.pdf
#include <algorithm>
#include <iterator>
#include <type_traits>
#include <utility>
template<class I>
using difference_type_t = typename std::iterator_traits<I>::difference_type;
template<class I>
using iterator_category_t = typename std::iterator_traits<I>::iterator_category;
template<class I, class Tag, class = void>
constexpr bool is_category = false;
template<class I, class Tag>
constexpr bool is_category<I, Tag, std::enable_if_t<
std::is_convertible_v<iterator_category_t<I>, Tag>>> = true;
/// Increment (decrement for negative n) i |n| times or until i == bound,
/// whichever comes first. Returns n - the difference between i's final position
/// and its initial position. (Note: "advance" has overloads with this behavior
/// in the Ranges TS.)
template<class I>
constexpr difference_type_t<I> bounded_advance(
I& i, difference_type_t<I> n, I const bound)
{
if constexpr (is_category<I, std::bidirectional_iterator_tag>) {
for (; n < 0 && i != bound; ++n, void(--i)) {
;
}
}
for(; n > 0 && i != bound; --n, void(++i)) {
;
}
return n;
}
template<class ForwardIt>
ForwardIt shift_left(ForwardIt first, ForwardIt last, difference_type_t<ForwardIt> n)
{
if (n <= 0) {
return last;
}
auto mid = first;
if (::bounded_advance(mid, n, last)) {
return first;
}
return std::move(std::move(mid), std::move(last), std::move(first));
}
template<class ForwardIt>
ForwardIt shift_right(ForwardIt first, ForwardIt last, difference_type_t<ForwardIt> n)
{
if (n <= 0) {
return first;
}
if constexpr (is_category<ForwardIt, std::bidirectional_iterator_tag>) {
auto mid = last;
if (::bounded_advance(mid, -n, first)) {
return last;
}
return std::move_backward(std::move(first), std::move(mid), std::move(last));
} else {
auto result = first;
if (::bounded_advance(result, n, last)) {
return last;
}
// Invariant: next(first, n) == result
// Invariant: next(trail, n) == lead
auto lead = result;
auto trail = first;
for (; trail != result; ++lead, void(++trail)) {
if (lead == last) {
// The range looks like:
//
// |-- (n - k) elements --|-- k elements --|-- (n - k) elements --|
// ^-first trail-^ ^-result last-^
//
// Note that distance(first, trail) == distance(result, last)
std::move(std::move(first), std::move(trail), std::move(result));
return result;
}
}
for (;;) {
for (auto mid = first; mid != result; ++lead, void(++trail), ++mid) {
if (lead == last) {
// The range looks like:
//
// |-- (n - k) elements --|-- k elements --|-- ... --|-- n elements --|
// ^-first mid-^ result-^ ^-trail last-^
//
trail = std::move(mid, result, std::move(trail));
std::move(std::move(first), std::move(mid), std::move(trail));
return result;
}
std::iter_swap(mid, trail);
}
}
}
}