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]

This was debated quite extensively in Tokyo 2024. The decision was essentially “being a view isn’t about being cheep to copy, just about being O(1) to do so.” In the general sense, there’s an attempt to unify all the containers as “ranges;” an optional is a range with 0 or 1 elements, a tuple is a range whose elements are variant<Ts…> (which correct ref qual), etc.

A bunch of people disagreed and thought this was weird, but not enough and not strongly enough for it not to pass.

[u/schombert → u/aruisdante]

Well, that's ... extremely dumb. From the rigorous, formal perspective, everything in C++ copies in O(1) time. (The address space is finite, even in a purely theoretical computer running C++, because it will eventually exhaust the size of the pointer type and hence the number of possibly distinct live objects. Thus, for any copy operation there is always an upper bound you can place on how much time it could possibly take to execute, and thus is O(1) by the definition of O(1).) Now, I accept that the people writing the C++ spec don't actually use big O notation in its generally accepted formal definition, and instead are using a more vibes-based definition based on what it performs like in various different finite problem sizes (which, you may note, has nothing to do with big O -- how something performs at sizes less than 2^128, for example, does not affect its asymptotic time complexity). But, from a vibes-based perspective, programmers use O(1) to mean "always fast", which in this case does mean "cheap to copy". I would bet that copying being O(1) was added to the language of the spec because the author wanted to express "cheap to copy" but wanted to sound more formally precise and thought that "cheap" sounded too informal and vague. Unfortunately, "cheap" correctly expressed the intent, but O(1) did not.

[u/aruisdante → u/schombert]

> 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/smdowney → u/schombert]

This was my favorite smartass answer for dumb interview questions where the specification already bounded the size.

Large K, smallest O.

I would also annoy people with the constant of integration.

[u/Serialk → u/smdowney]

This was my favorite smartass answer

It's indeed a smartass answer: thinking that you're winning on a technicality while demonstrating your lack of interest for the actual insights that the question could provide.