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