#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年没有被触及了...)
3条答案
按热度按时间ni65a41a1#
看看Range-v3的66行take_last和373行drop_last在复杂性上的差异,我怀疑这可能只是Range-v3的take_last的暂时缺陷。
这是因为
drop_last
支持向前但不调整大小的范围,而take_last
仅支持调整大小的范围。您 * 可以 * 实现一个
take_last
来处理向前但不调整大小的问题,遵循与drop_last
实现相同的逻辑:用另一个迭代器来“探测”结束位置。基本上是这样的:
理想情况下,
cached_begin
实际上是一个条件成员,因为只有在某些情况下才需要它,但除此之外,这是一个可行的范围适配器。您可以看到这个here的示例实现,它看起来做得很好,但它不是一个完整的实现(缺少的东西包括:这可以支持输入+大小范围,如果底层范围被大小化,则这应该被大小化,如果底层范围是常量可迭代的,则这是常量可迭代的,等等)。
pkln4tw62#
你可以使用
views::counted
将原点范围转换成sized_range
(但在最坏的情况下,你需要付出O(n)的时间复杂度来计算input
的实际大小)Demo
ovfsdjhp3#
drop_last
的两个迭代器之间的范围正好是take_last(n)
不,不是的,
drop_last
的两个迭代器都是以begin()
和begin()+n
开始的,take_last
的范围是从end() - n
到end()
,这两个不是同一个范围。drop_last
可以工作,因为它一开始不需要知道end() - n
在哪里,当你遍历这个范围时,它会自然地发现它。take_last
必须以end() - n
开始。因此,它必须计算它。为了计算它,它还必须确定end() - begin()
是否小于n
。以便它可以在begin()
处对起始迭代器进行封顶。只有当范围的大小可以在常数时间内计算时,它才能在常数时间内进行计算。它被定尺寸。
这是无法回避的。如果你想让
take_last
是常数时间的,它必须被给定一个范围,其大小可以在常数时间内计算。如果你愿意忍受O(n)的运算(其中“n”是范围的大小),你可以解决这个问题。但我不认为这是一个“有效”的解决方案。