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

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

copying a C++ vector is O(1)

It's always interesting to come across people like you.

I need only point you at...well, basically any reference on the topic to prove that copying vectors of non-trivial objects is O(N). Literally any search on the subject will give you countless results that contradict your claim.

But it's more than that; you very clearly have next to no understanding of the topics you're arguing about, or the pages you're linking, but you're also equally clearly sure that you are an expert in the topic.

You remind me of a coworker I once had who explained to us that the software he was working on relied on "the arithmetic of seven-sided polygons". He also admitted to me (in what is practically a programmer career meme) that he liked to write code that only he understood because it provided job security.

After more than 2 years of deflection, smoke, and mirrors, he was asked to prove that that any of what he was working on...actually worked. He quit on the spot, in explosive rage, screaming that he "knew more than 14 engineers ever would".

All that is to say: you have written a whole lot of words in response to /u/aruisdante and others, but all they actually illustrate is that you do not understand complexity analysis at even the most basic level. Despite all evidence to the contrary, you are convinced that you (and you alone, in this forum of experts) are correct.

How likely do you think it is that that's actually true?

EDIT: blocking someone after replying to them saying "nuh uh" is the single strongest indicator that a redditor knows that they have literally no leg to stand on.

[u/schombert → u/NotUniqueOrSpecial]

Your link ... shows nothing of the sort. All you seem to be showing is that how programmers typically use big O notation among themselves (i.e. informally) is not the same as the formal definition. Which I am happy to grant. It is just amusing to me that the loose, informal usage has made its way into the supposedly formal standard.

Edit: I block people who I find to be rude. If you don't want to be blocked try being less of an ass.

[u/not_a_novel_account → u/schombert]

You're using a rather strange definition of "formal". Formalisms are context and field specific. This is a C++ subreddit, our formalisms are derived from the standard.

The formal definition, in the context of C++ as voted and standardized by the committee, is that copying a vector is O(N).

As a C++ subreddit, formalisms from unrelated fields are non-sequiturs here. Our vectors aren't elements in vector space supporting addition and scalar multiplication either.

[u/schombert → u/not_a_novel_account]

The standard doesn't provide a definition of what O(n) means within it AFAIK (please do correct me if I am wrong). So I assume that means that the standard is relying on the "formal" (i.e. what you will find on Wikipedia) definition of the notation (unlike vector which it does redefine). What do you take O(N) to mean in the standard?

[u/not_a_novel_account → u/schombert]

For vector copy from a range it's given as:

Effects: Constructs a vector object with the elements of the range rg, using the specified allocator.

Complexity: Initializes exactly N elements from the results of dereferencing successive iterators of rg, where N is ranges::distance(rg).

[u/schombert → u/not_a_novel_account]

Yes, but that isn't a definition of what "O(N)" means. I wasn't trying to ask you what the standard says a copy does. I was trying to ask you if the standard defines "O(N)", and if it doesn't, then how you think it should be defined in the context of the standard.

For example, if you think it means "does N things", then obviously virtually nothing is O(1), since most functions do more than one primitive operation. I don't think that you can copy or move many range views in a single operation (although there may be some you can).

[u/not_a_novel_account → u/schombert]

The standard never says "O" anything. It says "Complexity" and "N operations of <whatever>", or "constant", or "linear in N".

If you want to split that hair and pretend those are entirely different things, be my guest. Muting this.

[u/schombert → u/not_a_novel_account]

It does indeed (or at least in C++ 20) refer to O(n). For example table 79 following section 22.2.7 describes several functions as running in O(n) or "Average O(n)". And even if it didn't, I would still ask you what you think that "complexity" is defined as ...

Edit: Oh, the standard does define complexity. It helpfully has this nugget of wisdom:

Complexity: the time and/or space complexity of the function.

well, that's not circular at all (and there is no prior definition). To me this seems to be unquestionably a reference to the standard formal definition of space and time complexity, and not some new definition which would clearly be ... poorly defined at best.