Vector initialisation using ranges vs lambda inline initialisation

Question

I would like to initialise a vector by transforming the other one. I made a test with two ways of inline initialisation a transformed std::vector.

One using lambda inline initialisation (with std::transform):

   std::vector<int> foo(100,42);
   const auto fooTimesTwo = [&]{
            std::vector<int> tmp(foo.size());
            std::transform(foo.begin(), foo.end(), tmp.begin(), convert);
            return tmp;
    }();

And the other one - using std::ranges::views::transform:

   std::vector<int> foo(100,42);
   auto transform_range = (foo | std::ranges::views::transform(convert));
   std::vector<int> fooTimesTwo {
           transform_range.begin(),
           transform_range.end()
   };

I expected that both way of vector initialisation should have similar performance, but from some reason the benchmark of solution with traditional std::transform is much faster that the second one (9.7 times faster -> https://quick-bench.com/q/3PSDRO9UbMNunUpdWGNShF49WlQ ).

My questions are:

• Do I use std::ranges::views::transform incorrectly?
• Why does it work so much slower?

Side note - it can be done using boost::make_transform_iterator, but I couldn't check it on quick-bench as they don't support boost. So I'm not sure about efficiency of such solution.

Answer 1

Why does it work so much slower?

The problem you're running into is one of the differences between the C++98/C++17 iterator model and the C++20 iterator model. One of the old requirements for X to be a forward iterator was:

if X is a mutable iterator, reference is a reference to T; if X is a constant iterator, reference is a reference to const T,

That is, the iterator's reference type had to be a true reference. It could not be a proxy reference or a prvalue. Any iterator whose reference is a prvalue is automatically an input iterator only.

There is no such requirement in C++20.

So if you look at foo | std::ranges::views::transform(convert), this is a range of prvalue int. In the C++20 iterator model, this is a random access range. But in the C++17, because we're dealing with prvalues, this is an input range only.

vector's iterator-pair constructor is not based on the C++20 iterator model, it is based on the C++98/C++17 iterator model. It's using the old understanding of iterator category, not the new understanding. And the C++20 range adaptors work very hard to ensure that they do the "right thing" with respect to the old iterator model. Our adapted range does correctly advertise itself as random access when checked as C++20 and input when checked as C++17:

void f(std::vector<int> v) {
    auto r = v | std::views::transform(convert);
    using R = decltype(r);
    static_assert(std::ranges::random_access_range<R>);
    static_assert(std::same_as<std::input_iterator_tag,
        std::iterator_traits<std::ranges::iterator_t<R>>::iterator_category>);
}

So what happens when you pass two input iterators into vector's iterator pair constructor? Well, it can't allocate a huge chunk up front (we can't do last - first here because it's an input iterator, the notion that having a "sized sentinel" might be independent from the traversal category is also a new thing in the C++20 iterator model)... instead it basically does this:

for (; first != last; ++first) {
    push_back(*first);
}

Can't do any better than that for an input iterator. But that's super inefficient, because we end up doing like eight allocations instead of one.

---

In range-v3, you can do this:

auto result = foo | ranges::views::transform(convert)
                  | ranges::to<std::vector>();

The to algorithm understands the C++20 iterator model and does the right thing by reserving in advance here. However, to is very limited in the fact that it's an external library and we can't just modify standard library types to opt into it. We hope to have a std::ranges::to in C++23 that will come with improvements to the standard library containers to do this even better. At that point, this solution will be better than your original solution since std::vector<int> foo(tmp.size()) is itself wasteful by having to zero-initialize a chunk of memory, only to immediately overwrite it.

---

In the meantime, I do wonder both about the general value of preserving this reference-must-be-reference requirement (that few people even know about and probably even fewer rely on: the biggest value is probably just knowing that operator->() can return &operator*()?).

std::vector<bool> already lies about this and advertises itself as being a random access C++17 range, for instance.

Standard library implementations though should be able to handle this case better. They should be able to safely check for the C++20 iterator concepts and do something intelligent as a result. In this case, we have C++20 random access iterators, so vector should be able to construct itself efficiently in this context. Submitted 100070.