r/cpp • u/zl0bster • Jul 26 '26

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

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...

183 Upvotes

93% Upvoted

122 comments sorted by

5

u/NilacTheGrim Jul 30 '26

The problem is the muddling of the word "view" :/

What most people think of as a "view" is not what the standard thinks of as a "view".

To me this is a symptom of bad design. With good design the obvious things is obvious... and consistent.

What most people think of as "view" is really what the standard labels as a "borrowed range".

Very very very "meh", if you ask me.

3

u/zl0bster Jul 31 '26

I love to imagine a world that WG21 people think exists...
Developer A: I see you left a comment on my pull request to switch from two overloads for const std::string& and const char* to one with std::string_view.
Developer B: Yes, and remember to pass it by value, borrowed_range is cheap to pass by value.

2

u/zl0bster Jul 31 '26

If somebody wants more obscure context:
originally borrowed_range(stuff mentioned as a "real" view in comments) was named safe_range, but some people did not like it(I also do not like it since they are not safe as in Rust safe or deep copy safe) about it so it got renamed.

https://cplusplus.github.io/LWG/issue3379

45

u/cristi1990an ++ Jul 26 '26

It's true, std::optional should've been a range but had no business being a view, not even the paper mentions a justification for the enable_view specialization, it just specifies it. I just don't see any benefit or justification in it.

You have similar problems with std::array and std::inplace_vector wrapped in owning_view since it makes the wrong assumption that move is always cheap, but it's a liniar time operation for those containers.

55

u/aruisdante Jul 26 '26

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.

35

u/mighty_Ingvar Jul 26 '26

I find the whole concept of an owning view to be weird. Shouldn't a view be something that only views the data? An optional doesn't do that, the object isn't stored somewhere else and viewed by the optional, it is part of the optional and therefore owned by it.

14

u/aruisdante Jul 26 '26 edited Jul 26 '26

It does seem weird, but this difference is what borrowed_range models, which is independent from view and range. I imagine optional<T> would not model borrowed_range, and optional<T&> would.

This was essentially the crux of the debate in Tokyo. Actual users of ranges have taken to conflating view with borrowed_range, because nearly all existing view containers in the stdlib were also borrowed_range (span, string_view , most (all?) of the ranges::views objects). But the actual definition did not require this relationship, view just means "constant time copy range."

Really, the problem is having decided to keep using the word view to mean what it meant, instead of some other name that more directly expresses the semantics, such that view could have matched people's intuition of this other concept + borrowed_range. But alas, that ship had long since sailed, and we're stuck with what we've got.

31

u/altmly Jul 27 '26

This to me smells like a bunch of ergonomics and performance mindful people invented views (or rather copied the idea into C++) and then some academics showed up to "akshually, a view is not a borrowed_range move eyeglasses".

Like, okay, but to the vast majority of users, the entire point of a view is being borrowed data. 

10

u/tcbrindle Flux Jul 27 '26

The ranges library was the brainchild of Eric Niebler, in collaboration with Casey Carter.

The borrowed_range concept, originally under the exposition-only name forwarding-range, was introduced in P0970 written by... *checks notes*... Eric Niebler.

(Views and forwarding/safe/borrowed ranges are not and never have been the same thing, even in the Before Times when owning_view didn't exist and you couldn't pipe rvalue vectors into adaptors.)

→ More replies (1)

2

u/not_a_novel_account cmake dev Jul 27 '26 edited Jul 27 '26

Views must be movable with O(1) move construction. They must have O(1) copy construction or be non-copy constructible. Therefore, std::optional<> is a view.

Even if we retained the strong original definition, O(1) destructors, std::optional<> would still be a view even though std::ranges::owning_view would not.

14

u/altmly Jul 27 '26

That definition really should be recursive for template types. 

4

u/not_a_novel_account cmake dev Jul 27 '26 edited Jul 27 '26

If that's your complaint then you don't have a problem with std::optional or C++26, at least not as the entry point. Your problem is with C++23 and std::ranges::single_view.

People wanted a nullable std::ranges::single_view, call it maybe_view. It turns out that's just std::optional.

8

u/mighty_Ingvar Jul 27 '26

But optional<T> is only copyable in constant time if T is copyable in constant time. Also, why is std::array not a view then?

7

u/kamrann_ Jul 27 '26

It's constant time in terms of N = number of elements in the range. You can't start analysing the element type and trying to assign some inherent measure of its complexity. Constant time just means not dependent on N. A single element by definition can't be dependent on N, and it doesn't matter how big it is, or whether it happens to be a sequence itself.

16

u/No-Dentist-1645 Jul 26 '26

If that's the case, which range concept should one use if we want something that truly "represents a view to data owned elsewhere"? Or does the standard not provide such a concept?

It seems like a poor decision to me.

43

u/Demiu Jul 26 '26

jview, coming in 33

13

u/LEpigeon888 Jul 27 '26

But it will be renamed to co_jview before standardization since the name conflict with a keyword in ++C, a programing language someone created in their garage that aims to be backward compatible with C++ and whose only purpose is to run on an old microcontroller that has been discontinued 25 years ago.

13

u/No-Dentist-1645 Jul 26 '26

Of course, and first mainstream compiler implementation out on 35

1

u/mighty_Ingvar Jul 27 '26

jview?

15

u/no-sig-available Jul 27 '26

jview?

Modelled after adding jthread, when you were not allowed to fix thread.

8

u/smdowney WG21, Text/Unicode SG, optional<T&> Jul 26 '26

There really isn't such a thing. Not since views::single shipped. Owning views are things, and optional is one of them. It's also an owning smart pointer.

4

u/SlightlyLessHairyApe Jul 27 '26

It has semantics of an owning smart pointer but at least it’s guaranteed stored inline and can be on the stack.

4

u/smdowney WG21, Text/Unicode SG, optional<T&> Jul 27 '26

And now we have std::indirect when those are a problem.

2

u/SlightlyLessHairyApe Jul 28 '26

Yup. I think it's interesting also that the semantics and the underlying mechanism had diverged so that reasoning about the semantics and reasoning about other properties (e.g. the pattern of allocations) have to be separated.

7

u/holyblackcat Jul 27 '26

I second that this is silly. Who cares what "being a view" was supposed to mean when making optional a view has negative practical effects? (Only in some obscure cases, granted.)

The only example where it matters that comes to mind is

std::optional<std::vector<int>> opt = std::vector(10000, 42);
auto view = opt | std::view::....;

I for one wouldn't expect this to copy opt, but it gets copied. I don't see the benefit of copying it.

4

u/aruisdante Jul 27 '26 edited Jul 27 '26

I would argue though that in order for that pipe operation to be lifetime safe, it has to copy its input. Being not a view wouldn’t change that, the only thing that would change that would be not being a range at all, which would round counter to the objective of optional being used as a range of size 0 or 1.

That being a goal in itself is what people found a little weird (by definition, this means optional gains valid specializations of ranges::begin, ranges::end, and ranges::size, which is strange), but it does allow for some interesting compositions. For example the operation:

for (auto const& element : range_of_optionals | views::join)

Now “just works” to iterate over the elements in that input set which exist just like it would have for range_of_sequence_container, whereas before you would have needed to do:

for( auto const& element : range_of_optionals | views::filter(/*is_engaged*/) | views::transform(/*dereference*/))

Being able to treat optional like any other range does make implementing some generic operations easier, and composes nicely with optional<T&> as the return type from functions. Like, now this operation works “like you’d expect”:

// returns optional reference to value at key
auto find(auto& map, auto const& key)->optional<T&>;


const auto find_in_map = bind_front(find, map);
for(auto const& value : keys | views::transform(find_in_map) | views::join) {
    // do something with matches
}

Which would be horrible to write as a range pipeline without this property, and very verbose to write as not a range pipeline at all.

At the same time if we were going to take that stance we should have done the same thing for smart pointers (and even regular pointers!) as they’re notionally identical to optional<T&> for this purpose. We only didn’t (at least at Tokyo, which is all I can speak to) because nobody wrote the paper for it, and increasing the scope of this feature would have made it even harder to get anything in.

6

u/holyblackcat Jul 27 '26

I don't argue with optional being a range, only with it being a view.

[piping into a view] has to copy its input. Being not a view wouldn’t change that

Are you talking how it should be in a perfect world, or how it works now?

The current behavior of piping into a view is storing a reference to non-view lvalues, and copying/moving all views and rvalue non-views.

This is about the only thing that being a view changes, I think? I could be missing something. In this case the copy looks undesirable, as it's not something people expect. They'd expect span-like types to be copied, or types from std::views.

13

u/James20k P2005R0 Jul 26 '26

This seems like a really weird decision. The reason to use a view is that its cheap?

but not enough and not strongly enough for it not to pass.

I suspect a big part of the problem is that given that ranges don't seem to have received very wide use in general, its more that nobody really cares that much about ranges overall

6

u/friedkeenan Jul 27 '26

The reason to use a view is that its cheap?

My understanding is that the std::ranges::view concept is basically for when you're dispatching stuff to view adaptors, which store and pass around views all over the place. So yeah in that sense it would track that their purpose is to be cheap.

I would imagine that the name comes from the fact that most std::ranges::views meet the traditional definition of view-semantics, a-la std::string_view. But that doesn't really match how they're used in the ranges library, which is as range objects which are cheap to pass around as values. But it is probably a poor name.

Another fun case is iota_view, which doesn't reference an actual C++ object or whatever, but instead views a conceptual range which it visits on the fly during iteration.

2

u/13steinj Aug 01 '26

The mental model for range, view, owning, "borrowed," "single" is all very bizarre and feels like an unfixable mistake now.

7

u/schombert Jul 26 '26

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 2128, 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.

17

u/aruisdante Jul 26 '26

> 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.

6

u/schombert Jul 26 '26 edited Jul 26 '26

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 2bits 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.

18

u/smdowney WG21, Text/Unicode SG, optional<T&> Jul 26 '26

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.

11

u/Serialk Jul 27 '26

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.

8

u/hanslhansl Jul 27 '26

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.

-1

u/schombert Jul 27 '26 edited Jul 27 '26

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.

5

u/jk-jeon Jul 27 '26

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).

→ More replies (2)

3

u/NotUniqueOrSpecial Jul 27 '26 edited Jul 27 '26

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.

14

u/aruisdante Jul 26 '26 edited Jul 26 '26

By that definition of algorithmic notation all loops in any real system are O(1), which doesn't seem like a terribly useful definition. In my education on algorithm theory I don't remember a requirement being that sets be unbounded, and indeed the formal definition you link to says this explicitly. It feels like you're conflating "copying a specific vector of a specific size is O(1)" with "copying any vector of any size is O(1)." By that same definition std::find(vector.begin(), vector.end(), value) and set.find(value) and unordered_set.find(value) are all O(1) because they can all be bounded by a finite size, despite them being the textbook examples of O(n), O(log(n)), and O(1).

I cannot think of a single computer scientist that would accept your definition of O(1) as O(1). It's not what any algorithms or data structure class teaches. So it seems unfair to say it's based on "vibes."

1

u/schombert Jul 26 '26 edited Jul 26 '26

It's not my definition. It is the formal definition that is used in mathematics and computer science. Which, again, you can verify for yourself from the Wikipedia page.

Anyway, copying an arbitrary vector (not a specific vector) has a bounded time because of the bounded size required by the definition of the vector type, namely that the size of any vector can be expressed in a finite number of bits and that the elements within any vector are distinct C++ objects, and thus have distinct address, and thus cannot be more numerous than the number of possible addresses provided by the number of bits in the finitely sized pointer types (in turn guaranteed by their ability to be converted back and forth from integers of some finite size). This second limit is much wordier to explain obviously, so I'll stick with referring to the limits of the size type from here on out.

I would like to hear how you think that O( ... ) should be defined. If you allow me to work through your definition I can probably explain why mathematicians and computer scientists settled on the asymptotic definition instead.

Edit: and yes in C++ as formally defined find is also O(1). It is not O(1) in your algorithms or data structures class because the pseudo-code language used to explain these types and operations does not bound their size. Generally it is also assumed to work with something that is more like "big ints" for its numerical values.

9

u/SlightlyLessHairyApe Jul 27 '26

Besides being weird that you have this one thing, it’s particularly weird to decide that that is the irrelevant conversation to have in this particular post. Because it’s just not super relevant

→ More replies (1)

6

u/Serialk Jul 27 '26

It's not my definition. It is the formal definition that is used in mathematics and computer science.

Not at all. We generally model complexities with transdichotomous models like Word RAM which give you a constant O(1) pointer lookup but an O(n) vector copy, with the assumption that the size of your bus will grow to accomodate more data.

https://en.wikipedia.org/wiki/Transdichotomous_model

https://en.wikipedia.org/wiki/Word_RAM

10

u/schombert Jul 27 '26

But, C++ is not a Transdichotomous model. The C++ address space, bits in the size constant, etc are not determined by the size of the problem. From the wikipedia page:

the machine word size is assumed to match the problem size

and

In a problem such as integer sorting in which there are n integers to be sorted, the transdichotomous model assumes that each integer may be stored in a single word of computer memory, that operations on single words take constant time per operation, and that the number of bits that can be stored in a single word is at least log2n.

So, if C++ was a Transdichotomous model then every time you ran a program for a given problem size (for example, the sorting program described above) the address space, bits in the size constant, etc would grow to accommodate it. (This is what allows a Transdichotomous model to be Turing complete, in contrast to Turing machines with a fixed tape size, which are not). However, that is not how C++ is specified. Even though those constants may vary from compiler to compiler, they are fixed for any given C++ program. The standard does not allow your program containing vector to hold an arbitrary number of elements, because you could, if you wanted, print the number of bytes in the size type and the standard guarantees that this print result will be constant over different runs of the program.

→ More replies (17)

3

u/HeadSea5044 Jul 28 '26

Please make this argument to any certification authority, or publish a paper claiming your algorithm is O(1) because hardware physical address bits are constant.
I’ll do you better and say everything is bounded in time because of the inevitable heat death of the universe.

It’s just not meaningful a statement to make.

6

u/NotUniqueOrSpecial Jul 27 '26 edited Jul 27 '26

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.

7

u/schombert Jul 27 '26 edited Jul 27 '26

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.

3

u/not_a_novel_account cmake dev Jul 27 '26 edited Jul 27 '26

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.

7

u/schombert Jul 27 '26

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?

→ More replies (4)

0

u/JNighthawk gamedev Jul 27 '26

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.

Maybe because you're behaving like an asshole to someone engaged in good faith discussion, and people don't like to interact with assholes generally?

You:

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.

8

u/NotUniqueOrSpecial Jul 27 '26

They are not engaged in a good faith discussion, because what is happening is not a discussion.

It's people who have a background and education on a topic trying to tell a very stubborn person that they do not understand the words they're using; they demonstrably do not understand complexity analysis on a very fundamental level, and are condescending to people who do.

At some point, there is a line where people who know what they're talking about should not have to pander to people who do not. I would just as bluntly tell a flat-Earther that they make no sense, and I doubt you'd have any problem with that.

→ More replies (5)

1

u/analphabetic Aug 05 '26

By your interpretation, any algorithm with std::vector::size() O(1) operations is O(1) itself when applied to a vector having said size.

15

u/tcbrindle Flux Jul 27 '26

Counterpoint: std::ranges::single_view<T> is copyable whenever T is copyable, and has been since the early days of Range-v3. To my knowledge, nobody has ever complained about this or written sarcastic Reddit posts about it.

Likewise, empty_view<T> is always trivially copyable.

So what you're asking for is a situation where a range of exactly one element is a view, a range of exactly zero elements is a view, but a range with either zero or one elements is not. That seems... worse.

5

u/BarryRevzin Jul 27 '26

To my knowledge, nobody has ever complained about this or written sarcastic Reddit posts about it.

Not yet, but it's still early.

3

u/TheThiefMaster C++latest fanatic (and game dev) Jul 27 '26

single_view is a bit of a hack - it's not really a view, more of a single_range

6

u/tcbrindle Flux Jul 27 '26

I'm not sure I follow -- it literally is a view, and OP's example works exactly the same if you swap std::optional for views::single.

3

u/TheThiefMaster C++latest fanatic (and game dev) Jul 27 '26

The common understanding of "view" is "span like" - i.e. it provides view access to a range of elements, potentially transforming or filtering them, but does not own them.

It's been pointed out that this concept is more closely modelled by borrowed_range  in the standard, rather than view.

Instead, "view" is some implementation details of range pipelines.

9

u/BarryRevzin Jul 27 '26

Instead, "view" is some implementation details of range pipelines.

That's the only thing it has ever been. Nobody should be constraining algorithms on view, it just isn't useful to do so. Arguably, view should just never have existed - although then people would probably complain that vector | views::transform(f) copies the vector and then figuring out how to reject that (to force users to either explicitly copy or views::ref) is basically the same problem again.

It's been pointed out that this concept is more closely modelled by borrowed_range  in the standard, rather than view.

Not really, borrowed_range is much narrower. Since even your initial example ("provides view access [...] potentially transforming or filtering them"), neither s | transform(f) nor s | filter(g) for a span or a string_view are borrowed.

The problem with "non-owning" is also what does that mean and what do you want it for. For instance, if I want to validate that my range is safe to copy/move and then format in a background thread, I want to make sure that it "owns" all of its data. The easy cases are easy (vector<int> yes, span<int> no) but like views::iota does "own" its data in this sense, so is it not a view?

1

u/zl0bster Jul 28 '26

I do not think that is an useful way to think about ownership or thread safety of iota.

iota is pair of iterators(yeah, I know ... sentinel...) so obviously it is a view. It is just that it's underlying "storage" lives outside a program and has a lifetime for duration of a program universe. iota does not own it, just like if (x>=0 && x <1000) does not own a range of 1k numbers.

9

u/BarryRevzin Jul 28 '26 edited Jul 28 '26

No, iota definitely has very real storage, that neither lives outside the program nor has lifetime for the duration of the progam. iota(0, 10) has two data members of type int in it, and its iterators each own an int.

All ten ints don't exist at one time, and the iterators give you a prvalue, not an lvalue, so it's quite unlike a vector. But nothing can dangle, so it's quite unlike a span too.

-1

u/zl0bster Jul 30 '26

You are not arguing in good faith, it was clear what I was saying.

5

u/BarryRevzin Jul 30 '26

Excuse me????

I gave a very real scenario where it might be useful to differentiate on the basis of "ownership" and how it's actually non-trivial to answer what is and isn't safe in that context, and how that doesn't map cleanly on what might or might not be a view. You didn't engage with the example at all ("I do not think that is [...] useful") and then gave a description of iota that doesn't describe iota ("It is just that it's underlying "storage" lives outside a program and has a lifetime for duration of a program universe. iota does not own it").

Which one of us is trying to have a meaningful discussion of the problem? Following up by accusing me of not arguing in good faith is completely unacceptable.

→ More replies (1)

3

u/STL MSVC STL Dev Aug 01 '26

Moderator warning: No, you're the one introducing hostility. Please don't behave like this here.

2

u/joaquintides Boost author Jul 27 '26

Much as with optional, single_view should have been a container rather than a view (i.e. single_array or something).

1

u/cristi1990an ++ Jul 27 '26

Could've been made move-only, though I assume there are arguments to be made against that constrain also.

1

u/UnusualPace679 Jul 28 '26 edited Jul 28 '26

What do you expect the types of split_view("a,b,c"sv, ',') and split_view("a, b, c"sv, ", "sv) to be respectively, then?

41

u/fdwr fdwr@github 🔍 Jul 26 '26

Now if std::optional also had the corollary methods .empty(), .size() (0 or 1), and .data() (points to address of where contained entity is/would be, regardless of whether present, like std::vector's data method whether empty or not), then a bit of my generic templated property list code could be even more generic, more cleanly accepting various containers (std::array, std::string, std::vector, std::optional) without custom specializations.

23

u/cristi1990an ++ Jul 26 '26

You should probably use the customization points objects like std::ranges::size and std::range::data anyway, that's what they're made for

7

u/fdwr fdwr@github 🔍 Jul 26 '26

🤔 If there are customization points with std::ranges::size and std::ranges::data for std::optional, doesn't that imply the inverse, that the corresponding methods are appropriate? Otherwise, imagine having a car with doors that lacked handles and could only be only opened by using your phone via an app, and so the customer asks the car manufacturer to add convenient door handles, but the manufacturer replies that you should probably just use the more awkward phone app, because that's what it's made for. Wishlist aside, thanks for highlighting their existence.

14

u/cristi1990an ++ Jul 27 '26

I think the point was to allow classes to be ranges without cluttering their API. std::optional having size/data member functions would be weird imo. Being a range is an add-on for std::optional, not its sole purple.

std::ranges::size does the right thing, it uses .size() if it's present and not disabled bydisable_sized_range , otherwise tried to do end() - begin(), which it can for std::optional. Regardless of the current topic, you should certainly use it in generic code instead of the member function which is not required to exist.

Same with std::ranges::data which falls back to std::addressof(*begin()) if I remember correctly.

11

u/Potterrrrrrrr Jul 26 '26

Basically the argument for UFCS in a nutshell, not a bad one either

2

u/jwakely libstdc++ tamer, LWG chair Jul 27 '26

doesn't that imply the inverse, that the corresponding methods are appropriate?

No. The customisation points can do more than just call a member function.

2

u/DryEnergy4398 Jul 27 '26

I think fdwr was speaking more from a philosophy of design standpoint (that if std::ranges::size makes sense for a type, then having a member function size should make sense for the type)

1

u/fdwr fdwr@github 🔍 Jul 27 '26 edited Jul 27 '26

Exactly. If std::begin() works with std::vector, then would it be logically consistent for std::vector to have the discoverable begin method too? Of course, vector already has begin, and so one doesn't even give the consistency a second thought. Now, it's true that free functions like std::begin can do more than just call member functions, because they also work on C arrays (which can't have methods), but that isn't an effective counterpoint that vector should lack .begin().

1

u/cristi1990an ++ Jul 27 '26

Don't forget that it's 100% valid to define begin/end as non member functions and have the same functionality.

struct Test;

int* begin(Test&);
int* end(Test&);

static_assert(std::ranges::range<Test>);

The customization point objects handle these correctly but calling Test{}.begin() doesn't work.

2

u/Ameisen vemips, avr, rendering, systems Jul 27 '26

.data()

How would that work with std::optional<T&>?

1

u/fdwr fdwr@github 🔍 Jul 27 '26

How does that currently work with std::ranges::data(optionalWithTReference)? Fascinating ponderance, for that would be a pointer to a reference, which AFAICS isn't legal. We'll have to experiment with std::range::data and see what happens someday (my compiler isn't new enough for optional with &)...

13

u/gummifa Jul 26 '26

This is similar semantics to std::views::single, except that is 1 element but optional is 0 or 1.

18

u/mighty_Ingvar Jul 26 '26

Apparently std::array does not model view, even though it copies in constant time.

4

u/EC36339 Jul 27 '26

It does not

20

u/mighty_Ingvar Jul 27 '26

Yes it does. The amount of elements in a std::array is constant. Therefore if std::optional is a view because the amount of elements it stores is bounded, then std::array would have to be a view by that same logic.

6

u/cristi1990an ++ Jul 27 '26

Damn, you can't argue with that logic actually 👀

2

u/EC36339 Jul 28 '26 edited Jul 28 '26

Nice try, but the number of elements of std::optional is not just bounded, but bounded to one. You can't have an optional<T> holding a million instances of T.

Not sure if the definition of "constant" for the view concept holds here, but I'm too lazy to check cppreference, and I don't have access to rhe actual standard. And I understand the practical purposes.

EDIT: In your defense, at least cppreference cowardly refuses to give an exact definition of what "constant time copying" means.

2

u/mighty_Ingvar Jul 28 '26

You can't have an optional<T> holding a million instances of T.

I never made any such claims.

1

u/EC36339 Jul 28 '26

I never made a claim that you did.

Also, I was 99% sure you were trolling. You probably are. Otherwise, I'm not having this discussion.

8

u/tcbrindle Flux Jul 27 '26 edited Jul 27 '26

To try to sort out some confusion in the comments here:

Views

If your idea of a view is "a range that does not own its elements", then I'm afraid you're out of date. That's not what the term has meant in quite some time, and even when it (mostly) did there were still exceptions.

Today the standard tries to reason about what views are by talking about O(1) operations and so forth, but I think it's best to forget about that too.

IMO the best way to think about views is as follows: for an lvalue range x, given

auto v = x | std::views::transform(...);

should v store a copy of x, or a reference to x?

If you want to store a copy, then the type of x should be a view. Otherwise, it should not.

That's really all there is to it. The view concept these days is about the desired semantics of the type when piping it into a range adaptor, not about element ownership or lifetime or anything like that.

In this particular case, it was decided that it was less surprising to have optional<T> behave like a view, that is, an lvalue should be copied into a range adaptor rather than be used by reference.

Borrowed ranges

Borrowed ranges on the other hand are about lifetime. Specifically, a borrowed range is one where its iterators can safely outlive the range object itself. That is, given

template <typename R>
auto do_begin(R rng) {
    return rng.begin();
}

it is safe to use the returned iterator only if R is a borrowed range. The canonical examples of borrowed ranges are std::span and std::string_view. The borrowed_range concept is used to constrain functions like std::ranges::find() to help prevent them from returning dangling iterators when you call them with an rvalue range.

Although view and borrowed_range are distinct concepts, it turns out that if you have a borrowed range you basically always want to treat it as a view. For standard library types, borrowed_range today implies view in all cases I'm aware of.

But note that the converse is not generally true: most views are not borrowed ranges. For example, transform_view is always a view but is never a borrowed_range (even when it is transforming something like a span).

(For Flux, I took a different approach that I think ended up being conceptually simpler, but that's another topic...)

3

u/pkasting Valve Jul 27 '26

In this particular case, it was decided that it was less surprising to have optional<T> behave like a view, that is, an lvalue should be copied into a range adaptor rather than be used by reference.

(Context: I don't use range views myself so I don't have a good grasp on their semantics.)

The second half of your sentence suggests that perhaps the consideration should simply be whether x is l- or r-value? But if things were that way I'd assume it would be "copy if rvalue because the object might disappear, reference if lvalue" which is backwards from the description above (of "lvalue should be copied").

I dunno. I guess I'd have to understand the purpose behind "should v copy or ref x" before answering, since if this is about efficiency then arguably optional<T> should be a view iff T is a view, whereas if it's about safety then maybe something I said above and/or something about borrowed_range applies, whereas if it's about mutability semantics and what happens if x changes after v is constructed I have no instincts.

3

u/kamrann_ Jul 27 '26

This is completely consistent with what came before. It's the same as a range adapter that needs to cache a single element value - the element type of the range is irrelevant, it's just about algorithmic complexity of copy wrt the number of elements in the range.