Why chained range views sometimes increase in size?

Question

I have been playing around with std::ranges::views and have noticed that every chained view gets bigger. For view iterators this pattern is simple, each is always 8 byte bigger than the one before. But for views themselves, the transform does not increase size at all, while filter increases it by an amount I cannot make sense of. On MSVC this pattern is slightly different, but still unpredictable to me.

Test code:

#include <iostream>
#include <ranges>
#include <string>

int main() {
    static constexpr auto printed = [](auto&& v) {
        std::cout << "sizeof(v): " << sizeof(v) << ", ";
        std::cout << "sizeof(it): " << sizeof(v.begin()) << ", ";
        std::cout << "values: { ";
        for (auto&& x : v) {
            std::cout << x << ", ";
        }
        std::cout << "}\n";
        return v;
    };

    using namespace std::ranges::views;
    auto hundred = printed(iota(0ull, 100ull));
    auto small = printed(hundred | filter([](auto i) { return i < 50; }));
    auto times_seven = printed(small | transform([](auto i) { return i * 7; }));
    auto even = printed(times_seven | filter([](auto i) { return i % 2 == 0; }));
    auto as_string = printed(even | transform([](auto i) { return std::to_string(i); }));
    auto no_twos = printed(as_string | filter([](auto s) { return s.find('2') == s.npos; }));
}

Run it on GodBolt

Results:

view	sizeof(it)	delta	sizeof(view), GCC/Clang	delta	sizeof(view), MSVC	delta
iota	8		16		16
filter	16	8	32	16	48	32
transform	24	8	32	0	64	16
filter	32	8	64	32	112	48
transform	40	8	64	0	128	16
filter	48	8	112	48	192	64

My code does not really care about the size of the views since they are never stored anywhere, I am just wondering why they cannot be constant, only dependent on size of the lambda (here always empty). I tried looking into source code, but I find it very hard to read with all the layers of base classes, template specialization and concept constraints.

康桓瑋 · Accepted Answer · 2025-04-11 09:44:37Z

But for views themselves, the transform does not increase size at all, while filter increases it by an amount I cannot make sense of.

In order to maintain the amortized constant time of ranges::begin guaranteed by the range concept, filter_view needs to cache the first iterator of the underlying view that matches the predicate, so that each call to its begin() can return the cached iterator without repeated seeks.

This is why filter_view's begin() is not const-qualified, because the first iterator needs to be cached and stored in the filter_view itself when begin() is called for the first time.

This means that, unlike transform_view, when filter_view acting on other views, in addition to saving copies of the underlying view and predicates, it also needs to save its iterator.

The increased amount is the size of the internal cache that saves the iterator of the underlying view.

For view iterators this pattern is simple, each is always 8 byte bigger than the one before.

The function object is stored in filter_view and transform_view itself, so their iterators need to save not only the underlying iterator, but also an extra pointer (8 bytes) to the view class to facilitate access to the function object.

This is why these two are never borrowed_range, because when they are destroyed, their iterators will access dangling pointers.

Collectives™ on Stack Overflow

Why chained range views sometimes increase in size?

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related