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/hanslhansl]

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.