CODEWITHSUNDEEP
c++stdstd-ranges
Damir Tenishev
Damir Tenishev

Reputation: 3402

How to use std::views::filter result for std::ranges::random_access_range?

The std::views::filter can't model the std::ranges::random_access_range concept (most likely because it can't map random access from temporary filtered range to original range; correct me if I am wrong in reasoning or wording).

I can use std::ranges::to<std::vector>() (see demo below) to convert the temporary range to the vector, but:

  1. It creates a copy of the values in the vector v and I can't change them. Is there a way to solve this?
  2. Is it the best (most efficient from performance and memory reallocation perceptive) approach?
  3. What would be the real impact on performance and memory reallocation? Would the real std::vector be created dynamically in memory?

(Of course, "most efficient" means here "without the context"; for sure in real cases the code of rar function could be changed to process filtering inside, avoiding extra allocations. The question is, can this be done better if rar function is "untouchable"?)

#include <algorithm>
#include <ranges>
#include <vector>
#include <iostream>

constexpr auto rar = []<std::ranges::random_access_range Rng>(Rng & range) {
    std::ranges::for_each(range, [](auto& v) { v = 0.0f;  });
};

int main()
{
    std::vector<float> v = { 0.0f, 1.0f, 0.0f, 2.0f };

    // rar(v);

     auto no_zeros = v | std::views::filter([](const auto& lhs) { return lhs != 0.0f; });
    // This won't compile since std::views::filter can't produce std::ranges::random_access_range for the created range
    // rar(no_zeros);

    // Is this the only possible way and what is the performance/memory allocation impact?
    auto no_zeros_as_vector = v | std::views::filter([](const auto& lhs) { return lhs != 0.0f; }) | std::ranges::to<std::vector>();
    rar(no_zeros_as_vector);

    std::ranges::copy
    (
        v,
        std::ostream_iterator<float>{std::cout, ", "}
    );
    std::cout << std::endl;
}

Upvotes: 0

Views: 62

Answers (1)

Botond Horv&#225;th
Botond Horv&#225;th

Reputation: 1017

You need to put something in a random accessable container, (unless you implement your own random accessable view what needs to iterate threw the filter view whenever it is indexed, this will be slooooow, but will not allocate memory). If the copy of your object is cheap (like float in this case) copying each float is the fastest way.

But if your type is a hard to copy user defined type you can put pointers to the container, if you do something like this. std::views::transform([](auto& x){return &x;}) before putting the data in a vector. This can reduce the size you need to allocate, if your type is larger than 64 bits. And yes vector will have dynamicly allocated memory. If you dont want pointers to be in your view you can transform back v to a view

    auto no_zeros_as_vector = v | std::views::filter([](const auto& lhs) { return lhs != 0.0f; }) 
        | std::views::transform([](auto& x){return &x;})
        | std::ranges::to<std::vector>()
        | std::views::transform([](auto* x)->float& {return *x;});

So to summarize, if you don't want to write your own view with a bad efficiency you need to allocate some memory, std::vector is a good way to manage it. In cases with large type you can save memory and cpu time storing only pointers in the vector.

Note: I assume you need a random_access_range because you will need to index the view in the future. If you will never index it (or only a few times) you can yust keep the view returned by the filter and get the nth elment by iterating it.

Upvotes: 1

Related Questions