gpt4 book ai didi

c++ - shift_right() 在 C++20 中如何实现?

转载 作者:行者123 更新时间:2023-12-02 10:33:09 28 4
gpt4 key购买 nike

在 C++20 中,<algorithm> header 获得了两个新算法: shift_left() and shift_right() 。它们都接受任何 LegacyForwardIterator。对于 shift_left() ,指定“从i开始按​0的升序执行移动”​;对于 shift_right() ,指定“如果 ForwardIt 满足 LegacyBi DirectionIterator 要求,则从 i 开始按 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满足 LegacyBi DirectionIterator 要求,我可以看到 shift_right()可以以与 shift_left() 非常相似的方式实现。然而,目前还不清楚如何实现 shift_right()对于非双向前向迭代器。

我已经想出了一种使用 [first, first+n) 处空间的算法作为交换元素的临时空间,但它似乎比 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;
}

是否有更好的或“预期的”实现方式 shift_right()

最佳答案

这是轮类的示例实现:https://github.com/danra/shift_proposal/blob/master/shift_proposal.h

链接来自提案文件: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++ - shift_right() 在 C++20 中如何实现?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59783706/

28 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com