c++ - ranges::views 如何实现 O(1) 复杂度？

Question

关于最近介绍的 C++20 范围，我知道 views通过使用 View 适配器实现可组合性。我也知道 View 不拥有它们的元素并且它们的本质是惰性的，也就是说它们只在需要时才进行实际计算。

views如何实现O(1)移动、复制和分配操作是否复杂？我得到的可能答案是， View 只是“待计算”操作的描述，它们只是指数据及其转换。

不过，这听起来像是 View 只是承担表达我们的编码序列的工作，并且只有当传递给一些急切的东西(例如算法)时，它们才会在这个特定的、单一的调用中显示所有的计算负载。

跟进问题:我能理解如何实现 O(1)复制，本质上是引用可复制对象(虽然我不知道这是否是 ranges::views 所做的)。但是我不明白这在分配操作中是如何工作的。同样，一个可能的答案是，因为所有这些都发生在编译时，那么再次只是“描述”赋值是一个 O(1)手术。但是改变 std::vector<int>由 View 查看的是运行时操作(很棒 example )。这还是一个O(1)吗？操作？

Answer 1

您认识到 View 不拥有它们引用或操纵的元素。但您似乎不明白，这就是为什么这些操作是 O(1) 的。

如果你有这个:

vector<int> v = {...};
auto *vptr = &v;

auto *vptr2 = vptr;
vptr = vptr2;

相对于v.size()，vref2的初始化复杂度如何？ vptr 相对于 v.size() 的赋值复杂度如何？

它们都是 O(1) 因为它们只是复制指针。

vptr 指向v；它不拥有它。作为一个指针是如何它不拥有v。这也是复制指针是 O(1) 操作的原因:因为指针的大小不关心它指向的数据的大小。

View 也是如此。 View 类型存储底层范围的迭代器/哨兵。指针是一种迭代器，但迭代器的工作方式很像指针，因为它们指向一个值序列而不是序列本身。范围由起始迭代器和代表该范围结束的值(有时是另一个迭代器，有时是可以针对迭代器进行测试的一般对象)定义。

迭代器类型不知道也不关心序列中有多少元素。迭代器概念模拟序列中的一个位置；从概念上讲，它不知道终点是什么。

因此，相对于它们指向的范围的大小，复制迭代器(通常)是 O(1)。移动和复制/移动分配也是如此。