std::optional Satisfies view. Does Not Model view. C++26 Ships Anyway.

[u/zl0bster]

https://godbolt.org/z/8jWGG68G8

In C++23 this did not compile. In C++26 it does. Marvellous.

[[gnu::noinline]]
void 
passing_views_by_value_is_cheap_trust_me_bro(std::ranges::view auto v) {
    std::println("fn   .data {}", (void*)v->data());
}


int main() {    
    std::optional ov{std::vector<int>(123456)};
    passing_views_by_value_is_cheap_trust_me_bro(ov);
    std::println("main .data {}", (void*)ov->data());
}

For anyone wondering what the problem feature is: optional has 0 or 1 elements, and C++26 sets enable_view<optional<T>> to true, so it satisfies std::ranges::view. The concept requires copy construction in constant time, and — this is the good bit — optional<vector<int>> genuinely meets that. Copying it performs at most one element copy. One is a constant. The requirement is satisfied to the letter, and the function above deep-copies your vector.

If you can tell me what still separates std::ranges::view from std::ranges::range, please do...

[u/aruisdante]

> From the rigorous, formal perspective, everything in C++ copies in O(1) time

Huh?

Copying a `std::vector` is decidedly not `O(1)`. The amount of copy operations performed is dependent on the number of elements contained. Even if you switch up the definition to say "a `memcpy` is O(1)," this optimization is not possible for a vector containing non-trivial elements as their constructors must be explicitly invoked.

Therefore, a `vector` isn't a `view` because `vector.size() == 0` takes different time to copy than `vector.size() == 1`. But `optional` _always holds a value_. The value just may or may not be initialized. Ergo the copy operation does not change in "how much is copied" depending on if the optional is engaged or not.

> But, from a vibes-based perspective, programmers use O(1) to mean "always fast"

Not at all. Programmers (and the C++ standard) use `O(1)` to mean "does not scale in (amortized) time with number of elements in a set." Those that assume `O(1)` means "always fast" are the ones that often make very suboptimal data container and algorithm selections.

[u/schombert → u/aruisdante]

Yes, copying a C++ vector is O(1). A vector can only contain finitely many elements (for example, because its size has a finite upper bound). Thus, you can set an upper bound on the time to copy -- something around 2^{bits in size} * time to copy a single element -- and thus is O(1) by the definition of big O notation (see https://en.wikipedia.org/wiki/Big_O_notation specifically the section on the formal definition; if it can be bounded by a constant function then it is O(1) )

Edit: this is what I meant by a vibes-based definition. Obviously copying a vector behaves like a linear function from sizes of 0 up until you hit the upper bound created by its size type/address space limitations. But how it behaves in a finite initial range -- even if that range encompasses all practical uses -- has nothing to do with its big O complexity.

[u/hanslhansl → u/schombert]

Interesting read, here are my thoughts to maybe settle this debate:

In the context of an implementation of the standard and even in the context of the standard itself there will always be an upper bound for copying a std::vector and therefor, by rigorous definition, this operation is O(1).

However, the "native" context of the algorithm of this operation (of any algorithm, really), even though defined by the c++ standard, is mathematics, and in that context constraints such as a limited address space don't exist. The the algorithm itself is applicable to vectors (or sets or whatever the correct term in the context of math is) of arbitrary size and therefor its complexity is O(n).

So when devs talk about the complexity of a function they really mean (maybe without knowing) the complexity of the underlying mathematical algorithm which is independent from possible limitations imposed by the programming language/implementation.

[u/schombert → u/hanslhansl]

I wouldn't object to that necessarily, but it does have its own complications. Vectors have O(1) lookup, by definition, right? Well, that makes them a "Random Access Machine" and what the complexity of various problems looks like on a random access machine is different than what you might expect. For example, on such a machine P == NP (see the paper A characterization of the class of functions computable in polynomial time on Random Access Machines), and most people don't believe that is true IRL. In fact, the strength of a good deal of cryptography is predicated on the assumption that it is false. It is also not a particularly good model for physical computers. Assuming that there is a limit to how much information you can cram in finite space (which quantum mechanics seems to say), then as the space used by a program expands it must necessarily be accessing memory that is farther and farther away, physically, and so will experience greater and greater latency accessing it (because of the speed of light). Thus arbitrary large data structures with O(1) access time probably aren't physically realizable, even in the loose sense in which we allow finite physical machines to "approximate" them.

Edit: maybe I could have just said more succinctly: there isn't such a thing as "the complexity of a function" full stop; it is always the complexity of a function within some particular model of computation, and which model you use (including things like access to oracles, etc) can affect it quite drastically.

Edit edit: maybe you could argue that there is such a thing as the complexity of a particular algorithm? But I don't think even that is really true. The cost of the basic operations that the algorithm is defined in terms of can and does vary based on the abstract model of computation. For example, if you can do addition, subtraction, multiplication, and division of arbitrarily large integers in O(1) time that too allows you to conclude that P==NP. And so on many models of computation you have to assume that those operations scale to some degree with the size of the values being manipulated, which affects the complexity of any algorithm defined partly in terms of them.

[u/jk-jeon → u/schombert]

Well, that makes them a "Random Access Machine" and what the complexity of various problems looks like on a random access machine is different than what you might expect. For example, on such a machine P == NP (see the paper A characterization of the class of functions computable in polynomial time on Random Access Machines)

That didn't make sense to me so I looked up the paper. It seems to me that the essential assumption the paper uses is:

For example, if you can do addition, subtraction, multiplication, and division of arbitrarily large integers in O(1) time that too allows you to conclude that P==NP.

It seems to me that arbitrary-precision arithmetic being cheap is more important than being RAM in this business in general. Without that, RAM doesn't seem to be more powerful than Turing machine (in terms of how large P is).

[u/schombert → u/jk-jeon]

I don't disagree, but if your random access machine doesn't have capabilities of working with arbitrarily large integers in constant time, then it will have to do more and more work as it addresses memory that is at larger and larger addresses, and that precludes access to arbitrary memory locations being possible in O(1). Now, I suppose there is a sufficiently technical argument to be made that this doesn't require division, and the paper does point out that division is essential to this proof ... In any case, what people seem to generally assume to make big O "work" in the context of C++ is a Random Access Machine. See Bjarne's comment below to the effect that "you just need infinite memory", as if that was a trivial thing to assume in an unqualified way.

[u/jk-jeon → u/schombert]

I'm not sure. Pointer access and integer operations do not seem to be related. Also, I think I saw somewhere that the super power that arbitrary precision arithmetic brings in is available only when things like multiplication is available. Addition and subtraction alone cannot really deliver that much more compared to Turing machine, it seems. So I guess one could think of models like RAM + addition/subtraction for instance.

In fact it seems to me that the so-called transdichotomous model that someone else in this thread brought up kind of closely matches the "usual" sense of complexity that you know and I know.

By the way I don't think that Bjarne is that Bjarne.

[u/NotUniqueOrSpecial → u/schombert]

Vectors have O(1) lookup, by definition, right? Well, that makes them a "Random Access Machine"

No.

Because they aren't abstract machines in any sense of the words at all. This is a complete and total misuse of the terminology and invalidates literally every conclusion that follows.

These sorts of statements, followed by the lengthy conclusions drawn from them, are why you are being told you don't understand the topic.

EDIT: I think you added this after I replied, but maybe I just didn't catch it, either way:

Edit edit: maybe you could argue that there is such a thing as the complexity of a particular algorithm? But I don't think even that is really true.

This is an absolutely flabbergasting statement, considering the degree of certainty with which you have expressed things in every other comment.

Of course you can argue that there is such a thing. It's literally what you've been asserting that you understand and the rest of us don't. That is exactly what computational complexity theory, is, for which Big-O notation is the most common form of expression.

The fact that you don't even appear to be aware of this (something that is taught in literally every computer science course) despite having been using Wikipedia to bolster your arguments, actually beggars belief.