c++ 'take_last(n)'一个无大小范围的最佳方法是什么?

zynd9foi  于 2022-12-24  发布在  其他
关注(0)|答案(3)|浏览(119)

Godbolt:

#include <range/v3/all.hpp>

namespace views3 = ranges::views;

int main()
{
    std::string_view sv = "Hello world! Goodbye world!";
    auto notBang = [](char ch) { return ch != '!'; };
    auto input = std::views::take_while(sv, notBang);
    static_assert(!std::ranges::sized_range<decltype(input)>);
    static_assert(!std::ranges::common_range<decltype(input)>);
    static_assert(std::ranges::contiguous_range<decltype(input)>);

    auto v1 = input | views3::take_last(3);  // ERROR
    std::cout << (v1 | ranges::to<std::string>) << "\n";  // rld

    auto v2 = input | views3::drop_last(3);  // OK
    std::cout << (v2 | ranges::to<std::string>) << "\n";  // Hello wo
}

这里的input是一个连续的、非公共的、无大小限制的范围。range-v3的take_last(n)不适用于这样的范围,因为它的策略只是在构造时计算ranges::begin(input) + (ranges::size(input) - n),而无大小限制的范围没有ranges::size
但是drop_last(n) * 确实 * 适用于无大小的范围,因为 * 它的 * 策略是将两个迭代器n元素分开,并将它们一前一后推进。在迭代之后]正好是take_last(n)-但是我们无法得到它。
使用C20、C23和Range-v3工具获取一个非大小范围的最后n元素的最简单(也不是疯狂的低效)方法是什么?
(看看Range-v3的66行take_last和373行drop_last在复杂性上的差异,我怀疑这可能只是Range-v3的take_last的暂时缺陷。尽管它们都已经3年没有被触及了...)

ni65a41a

ni65a41a1#

看看Range-v3的66行take_last和373行drop_last在复杂性上的差异,我怀疑这可能只是Range-v3的take_last的暂时缺陷。
这是因为drop_last支持向前但不调整大小的范围,而take_last仅支持调整大小的范围。
您 * 可以 * 实现一个take_last来处理向前但不调整大小的问题,遵循与drop_last实现相同的逻辑:用另一个迭代器来“探测”结束位置。
基本上是这样的:

template <forward_range V> requires view<V>
struct take_last_view {
    V base;
    int n;

    // only necessary if not (sized + random access)
    optional<iterator_t<V>> cached_begin;
    

    auto begin() -> iterator_t<V> {
        if constexpr (random_access_range<V> and sized_range<V>) {
            auto s = ranges::size(base);
            if (s <= n) {
                // if I want to take the last 5 out of 3 elements, that's all 3
                return ranges::begin(base);
            } else {
                return ranges::begin(base) + (s - n);
            }
        } else {
            if (not cached_begin) {
                auto it = ranges::begin(base);
                auto probe = ranges::next(it, n, ranges::end(base));
                while (probe != ranges::end(base)) {
                    ++it;
                    ++probe;
                }
                cached_begin.emplace(it);
            }
            return *cached_begin;
        }
    }

    auto end() -> sentinel_t<V> {
        return ranges::end(base);
    }
};

理想情况下,cached_begin实际上是一个条件成员,因为只有在某些情况下才需要它,但除此之外,这是一个可行的范围适配器。
您可以看到这个here的示例实现,它看起来做得很好,但它不是一个完整的实现(缺少的东西包括:这可以支持输入+大小范围,如果底层范围被大小化,则这应该被大小化,如果底层范围是常量可迭代的,则这是常量可迭代的,等等)。

pkln4tw6

pkln4tw62#

你可以使用views::counted将原点范围转换成sized_range(但在最坏的情况下,你需要付出O(n)的时间复杂度来计算input的实际大小)

auto v1 = views3::counted(input.begin(), std::ranges::distance(input))
        | views3::take_last(3);

Demo

ovfsdjhp

ovfsdjhp3#

drop_last的两个迭代器之间的范围正好是take_last(n)
不,不是的,drop_last的两个迭代器都是以begin()begin()+n开始的,take_last的范围是从end() - nend(),这两个不是同一个范围。
drop_last可以工作,因为它一开始不需要知道end() - n在哪里,当你遍历这个范围时,它会自然地发现它。take_last必须以end() - n开始。因此,它必须计算它。为了计算它,它还必须确定end() - begin()是否小于n。以便它可以在begin()处对起始迭代器进行封顶。
只有当范围的大小可以在常数时间内计算时,它才能在常数时间内进行计算。它被定尺寸。
这是无法回避的。如果你想让take_last是常数时间的,它必须被给定一个范围,其大小可以在常数时间内计算。如果你愿意忍受O(n)的运算(其中“n”是范围的大小),你可以解决这个问题。但我不认为这是一个“有效”的解决方案。

相关问题