CODEWITHSUNDEEP
c++complexity-theoryc++20range-v3std-ranges
gonidelis
gonidelis

Reputation: 1063

How do ranges::views achieve O(1) complexity?

On the recently introduced to C++20 Ranges, I know that views achieve composability by using view adaptors. I also know that views don't own their elements and that their nature is lazy, that is to say they only do the actual computation when it's needed.

How do views achieve O(1) complexity on move, copy and assign operations though? The probable answer that comes to me is, views being just descriptions of "to be computed" operations, they just refer to the data and their transformations.

That, though, sounds like views are just taking on the job of expressing our coding sequences and only when passed to some eager thing (e.g. an algorithm) do they manifest all the computational load in this particular, single call.

Follow up question: I can understand how one would achieve a O(1) copy, in the essence of referring to the copiable object (although I don't know if that's what ranges::views do). But I cannot understand how this will work in assignment operations. Again, a probable answer would be, since all these happen in compile time, then again just "describing" the assignment is an O(1) operation. But mutating an std::vector<int> that's viewed by a view, is a runtime operation instead (great example). Is this still an O(1) operation?

Upvotes: 2

Views: 641

Answers (1)

Nicol Bolas
Nicol Bolas

Reputation: 473272

You recognize that views don't own the elements that they reference or manipulate. But you don't seem to understand that this is why these operations are O(1).

If you have this:

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

auto *vptr2 = vptr;
vptr = vptr2;

What is the complexity of the initialization of vref2 relative to v.size()? What is the complexity of the assignment to vptr relative to v.size()?

They're both O(1) because they're just copying pointers.

vptr points to v; it doesn't own it. Being a pointer is how it doesn't own v. It is also how copying a pointer is an O(1) operation: because the size of the pointer doesn't care about the size of the data it points to.

The same goes for views. View types store iterators/sentinels for the underlying range. Pointers are a kind of iterator, but iterators work a lot like pointers in that they point into a sequence of values rather than being the sequence itself. A range is defined by a starting iterator and a value which represents the end of that range (sometimes another iterator, other times a general object that can be tested against an iterator).

Iterator types don't know or care about how many elements are in the sequence. The iterator concept models a position in a sequence; conceptually, it has no idea what the end point is.

So copying an iterator is (usually) O(1) relative to the size of the range they point to. The same is true of movement and copy/move assignment.

Upvotes: 7

Related Questions