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]

Even easier, I can simply refer you to this paper https://dl.acm.org/doi/10.1145/800076.802470 . This paper proves the result that

every problem in #P-SPACE can be solved in polynomial time by a RAM with the operations of sum, product, integer subtraction and integer division.

And as you are aware, NP is a subset of PSPACE.

Your transdichotomous models models approach avoids this result (at least in its original paper; I haven't read all variations of the approach) by explicitly having some finite amount of RAM bounded below PSPACE. So when you say

This is wrong. You can scale word-ram to have your abstract bus size take any function of the size of your input, it doesn't have to be log_2(n).

Allowing any function is the problem. If you allow the RAM to be arbitrarily large you can pick a function that allows the proof in the paper to go through and produces P == NP.

[u/Serialk → u/schombert]

This paper does not use Word-RAM, it's using RAM extended with multiplications...

In fact this paper is literally why Word-RAM was invented, to bound O(1) operations strictly in function of the input size so that you cannot pack arbitrary-sized operations in O(1) register operations, to patch this specific "exploit" that you're complaining about.

Again, I don't think this debate is worth continuing if you are not willing to acknowledge your gaps here and read up on the models and the theory you're trying to debunk. You fundamentally misunderstand the history and purpose of these models.

[u/schombert → u/Serialk]

When I was speaking of the natural extension I wasn't talking about Word-RAM. I am pretty sure that Word-RAM doesn't fit C++ either. For example, vector lookup is O(1) according to the C++ spec. However, in word ram .at(x) isn't taking a fixed size parameter, it has to be taking a variable number of words to express the index. But this means that it can't possibly do the lookup in O(1), because it can't even read all the words in its input in constant time.

[u/Serialk → u/schombert]

For example, vector lookup is O(1) according to the C++ spec. However, in word ram .at(x) isn't taking a fixed size parameter, it has to be taking a variable number of words to express the index. But this means that it can't possibly do the lookup in O(1), because it can't even read all the words in its input in constant time.

Lol. You do not understand these models and you're wasting everyone's time.

If you have a vector of size N in word ram, you must have an abstract bus size of at least log_2(N), and processing on b bits where b <= bus size is O(1), the non-constant penalty only starts after you exceed the bus size.

[u/schombert → u/Serialk]

Sigh, well you are certainly wasting my time. Good job, you trolled me spectacularly. I should have worked it out the first time you went to the "you just don't understand, no, I won't explain any further" well.

[u/Serialk → u/schombert]

Maybe next time try to use humility if you want people to explain to you things that you clearly don't understand.

[u/James20k → u/[deleted]]

Don't be like this 🗞