#Implementation of std::views

58 messages · Page 1 of 1 (latest)

last anchor
#

I want to know how std::views is implemented (in most compilers or standard implementation) and how to create custom class that support it. Any help is appreciated.

golden lotusBOT
#

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question use !howto ask.

normal field
#

I'm not sure if you realize how vague that question is, or if you do realize but still want any bit of information/starting point you can

#

if all you're interested in is to have your custom range/view be compatible with all the pipeline stuff, you don't quite need to understand how the stuff in std::views work/is implemented

#

if you want to implement your own range adaptor, then yeah you'll probably want to have a look there

#

so depending which you want, it's going to be a very different answer/direction to push you towards

#

or maybe you want to look at both

#

I kinda have to go, so I'll just mention a couple of things about making your own range/view, since I have a very easy link to provide for that

#

for the other bit, making your own range adaptor, it's gonna require a much longer discussion

#

which I can't have now

#

so I'll leave it to whoever swings by

last anchor
normal field
#

I mean

#

that doesn't clarify which bit you want to know more about

#

range adaptors are a completely different beast to explain compared to just making your own range

#

it's also much simpler to explain the idea behind the whole customization point object, than it is to walk you through the implementation of one (for the range adaptor case) without just going "just read it"

last anchor
normal field
#

what part

#

customization point objects?

#

range adaptors?

#

or even just a range

#

cause I still don't know which one you wanted to know about, or if you actually wanted to look at all of them

last anchor
normal field
#

I'll have more time later, but for now I'll just comment that that's mostly correct
In the strictest sense, the concept doesn't require that there is an underlying range, e.g. the iota view has no underlying range
The lightweight thing is required however

last anchor
normal field
# last anchor But I wonder how they achieve that lightweight...

that actually sounds backward to me

the message you replied to, was a message where I clarified the "definition" of what a view is, as per the requirements/constraints of the concept std::ranges::view found in the standard
as any definition, there's no "how do you achieve that definition", it's just a definition, either you satisfy the definition, or you don't
if you were asking about a specific implementation of a specific view, it would be more on point

to give you an analogy, it's as if I just said that "an even number is a number you can divide by 2" and then you asked "how can even number be divided by 2"

#

a view, as per the requirements to legally satisfy/model the concept std::ranges::view, must be "lightweight", by some definition of lightweight

if the type you're looking at isn't "lightweight", then it cannot (legally) satisfy the view concept

#

then if your question was "how can I write a custom view that respects the lightweight constraint", there extremely little that can be said in general aside from "just understand how lightweight is defined and try your best to be lightweight"

#

if you have an actual implementation/implementation attempt then we can look through it and figure out the complexity of some operations, then figure out if the implementation matches the constraint or not

#

and now that I've mentioned those implementations, the standard library provides dozens of view type templates in the std::ranges namespace, and those view type templates are accompanied by their matching range adaptor objects in the std::views namespace

#

asking about how std::views is "implemented" is partly awkward because of that, there are dozens of things in there

#

and even just talking about the parts they have in common isn't a simple task

normal field
# last anchor But I wonder how they achieve that lightweight...

and talking specifically about "how can the views produced from the range adaptor objects found in namespace std::views" is a non-trivial question, in that either we go through every single one of them, or I just throw some generalities about some techniques you can apply, which technically rely more on your understanding of the model object of C++ and less about views in particular

#

making something "lightweight" isn't a problem specific to views, it's about understanding how much it can "cost" you to copy/move a range in general

#

e.g. containers in general aren't "lightweight", because copying a container requires copying every single one of the element they contain
copying a span however is "lightweight" because a span is essentially just a pointer + size, and that doesn't depend whatsoever on the size of the span

#

the simple way of achieving "lightweightness" is that you just reference some underlying range, and require that that underlying range outlives you (the view)

#

it's not the only way

last anchor
#

I understand the concept of views, but I just cannot know this is possible. I spent some times to read and try something about it, but what I have done is trying to mimic a ranges and use standard views to view it.
Example: std::views::filter would return a view which sastify a predicate. Did they achieve it by storing the function inside the view? Or they have some special containers containing iterators to underlying ranges?
Same for std::views::transform, it didn't change the containers at all but when I observe the views, it shows that the containers were modified. If it just copy and modify, it's not a view anymore. If they store the function, the function must be stored in polymorphic container types (to accept all function objects), which add overhead.
And most importantly: how views can be chained with each other and how they get the job done by just viewing underlying range without any copy from the ranges itself or until the view is invoked.

normal field
# last anchor I understand the concept of views, but I just cannot know this is possible. I sp...

I understand the concept of views, but I just cannot know this is possible. I spent some times to read and try something about it, but what I have done is trying to mimic a ranges and use standard views to view it.
unclear

Example: std::views::filter would return a view which sastify a predicate.
std::views::filter helps produce views with an "underlying range", where only the elements of that underlying range that satisfy the predicate are "kept"

Did they achieve it by storing the function inside the view?
yes the predicate/function is stored inside the resulting view, that's explicitly written on cppref when they mention the pred_ data member; note that this is an "exposition-only" data member to explain the behaviour and what to expect when using filter_view, in particular any copy/move/whatnot that needs to happen on the predicate/function
if you go through that you'll also notice that I'm not being fully thorough and accurate in my description here but the point was to show you where that piece of information was

Or they have some special containers containing iterators to underlying ranges?
unclear
they could have special iterators if they wished to but I don't see how that relates to the function/predicate

Same for std::views::transform, it didn't change the containers at all but when I observe the views, it shows that the containers were modified.
that's incorrect, std::views::transform doesn't "modify" the original container, it produces a view of transformed elements, there is a gigantic difference

If it just copy and modify, it's not a view anymore.
incorrect

If they store the function, the function must be stored in polymorphic container types (to accept all function objects),
incorrect, but a bit off-topic

which add overhead.
"lightweight" does not mean no-cost/zero overhead so that's partially off topic (for lightweightness concerns and implementation concerns of views)

normal field
# last anchor I understand the concept of views, but I just cannot know this is possible. I sp...

And most importantly: how views can be chained with each other
because a view is still a range, and that an actual view typically can always be used to build more views on top of it, cause it's literally a range with some added guarantees

and how they get the job done by just viewing underlying range without any copy from the ranges itself
that just isn't a requirement to be a view, although you still typically avoid copies if you don't need to copy, whether that can be avoided or not wholly depend on what specific view we're looking at and what parameters you used.
for example if the predicate you gave to std::views::filter always perform a copy internally then there will always be copy
alternatively if the predicate doesn't accept the right type as input, then a conversion will potentially occur

or until the view is invoked.
well it would be typical that views are implemented to perform lazy evaluation, it's easy to do that by deferring any and all kind of "evaluation" at the point where the iterator is dereferenced, so you only "work" at the exact moment someone attempts to fetch an element

#

to expand a bit on

Same for std::views::transform, it didn't change the containers at all but when I observe the views, it shows that the containers were modified.
that's incorrect, std::views::transform doesn't "modify" the original container, it produces a view of transformed elements, there is a gigantic difference

If it just copy and modify, it's not a view anymore.
incorrect
see this for example

#

;compile -std=c++20

#include <iostream>
#include <ranges>

int main()
{
    int const original_data[] { 1, 2, 3, 4, 5 };

    std::cout << "before view_transform:\n\t";
    for (int i : original_data)
        std::cout << i << ' ';
    
    std::cout << "\nview_transform:\n\t";
    for (int i : original_data | std::views::transform([] (int i) { return i * i; }))
        std::cout << i << ' ';
    
    std::cout << "\nafter view_transform:\n\t";
    for (int i : original_data)
        std::cout << i << ' ';
}
shut snowBOT
#
Program Output
before view_transform:
1 2 3 4 5 
view_transform:
1 4 9 16 25 
after view_transform:
1 2 3 4 5
slybach#0000 | 73ms | c++ | x86-64 gcc 13.2 | godbolt.org
normal field
#

the view concept has a specific definition for what it means with "lightweight", it might be worthwhile to double check it
the very short (and inaccurate) tl;dr is that a view must have constant time move construction

#

https://en.cppreference.com/w/cpp/ranges/view#Semantic_requirements

T models view only if:

  • move construction of T has constant time complexity, and
  • if N copies and/or moves are made from a T object holding M elements, then these N objects have O(N+M) destruction (which implies that a moved-from view object has O(1) destruction), and
  • either std::copy_constructible<T> is false, or copy construction of T has constant time complexity, and
  • either std::copyable<T> is false, or copy assignment of T has no more time complexity than destruction followed by copy construction.
last anchor
#

Oh ok, I understand about the view concept. Now about their implementation...
I just know the views are derived from a class known as std::ranges::view_interface, but in cppreference they didn't include possible implementation...
One thing I notice is that the assignment of different views didn't work for some reasons...

normal field
# last anchor Oh ok, I understand about the view concept. Now about their implementation... I ...

I just know the views are derived from a class known as std::ranges::view_interface
that's inaccurate, there are no requirement that a view must derive from view_interface in order to qualify as a view
as stated in cppreference view_interface is just a helper, it's there to allow you to avoid some of the boilerplate that you would typically have to write yourself
I briefly mentioned that in the other thread I linked to you earlier

the standard library makes use of that helper itself for its own implementation of views

in cppreference they didn't include possible implementation
you'd mostly check the properties of the iterator and do the right thing based on those properties, including making the function/overload not available
e.g. for data you'd use something like to_address on the first element, because the required properties guarantee that that's enough, and for those that don't satisfy the required properties then data wouldn't make sense so you disable it
at that point it's more about you understanding the various iterator concepts, and if you really want to be able to implement something similar to view_interface yourself then you need to be comfortable with templates and type traits and tags and whatnot
if you aren't looking to reimplement view_interface yourself, then view_interface is provided by the standard library precisely to avoid you having to implement it yourself and have a ton of boilerplate on your hands

One thing I notice is that the assignment of different views didn't work for some reasons...
unclear

last anchor
#

I will have a look on the attempt of reimplement std::ranges::view_interface later, as I should have some decent knowledge on how to use it.
But I don't know why I cannot assign two different views of same underlying range with each other (modifying a view to view the underlying range or adding more constraint in it, or even assign it with a similiar view). The implementation use auto to deduce type so I don't have any idea about the type they return...

normal field
#

If you aren't dealing with the exact same view type that's just not going to work in general

#

About every single view produced by the range adaptor object (that are in std::views) will have distinct types, it doesn't matter that you're using the same underlying range to produce those views, every single different adaptor will potentially produce a different view type, which is why your question was just so abstract

#

Because you were literally asking about how to implement dozens of different types

#

To give a bad parallel, it was a bit as if you were asking how to implement all the standard containers in one question

last anchor
#

Oh, I understand why my question is too abstract.
For now I don't need to know how to reimplement all of them, just some general underlying work they do to know why pipeline is possible...
My final goal is to be able to define a custom working view that sastify the requirement and understand how views work.

normal field
# last anchor Oh, I understand why my question is too abstract. For now I don't need to know h...

[...] just some general underlying work they do to know why pipeline is possible...
My final goal is to be able to define a custom working view that sastify the requirement and understand how views work.
just to be clear, a view in and of itself has little to do with the "pipeline" thing

a view is just a special kind of range, and if you want to implement a simple one just make a span, and that custom span will just work with pipelines if you tell the standard library that your custom span is indeed a valid view (and yes you can very easily lie about it, though you shouldn't)

if you want to make your own thingy that works with the pipeline syntax, then those are range adaptors/range adaptor objects/range adaptor closure objects
the tl;dr of range adaptors is that they take a (viewable) range (and maybe some additional parameters) as input, and produce a view

conceptually there's nothing special about pipelines, because again a view IS a range, and specifically a view is a viewable range, so chaining/piping just works the same way that 1 + 2 + 3 works, it just so happens that there are a tons of gotchas to be mindful of, and dealing with them properly is why ranges/views make heavy use of concepts, because implementing them without concepts and constraints would be incredibly more complex and annoying

#

if you want to try your hand at making a range adaptor, just start with something like all or take I guess