CODEWITHSUNDEEP
c++iteratorc++20c++-conceptsstd-ranges
Tom Huntington
Tom Huntington

Reputation: 3415

Why doesn't ranges provide a type erased view for non-contiguous ranges?

I would like to have a function that will take any range/view of a fixed value type.

int main()
{
    std::array<std::pair<int, int>, 2> a{...};
    std::array<std::pair<int, int>, 3> b{...};
    generic_fun(a);
    generic_fun(b);

};

Of course I could do

template <std::ranges::range R>
    requires std::same_as<std::ranges::range_value_t<R>,std::pair<int,int>>
auto generic_fun(R range)
{
    for(const auto& element : range)
        return element.first;
}

but then the visual studio ide doesn't know the type of element.

I was expecting the ranges library to have some type like

template <typename T>
struct view
{
    template <std::ranges::range R>
        requires std::same_as<std::ranges::range_value_t<R>, T>
    view(R);
    T* begin() const;
    T* end() const;
};

Which would give me ide support for

auto generic_fun(view<std::pair<int,int>> a)
{
    for (const auto& b : a)
        return b.first;
}

Why doesn't such a type exist in the ranges library? Is it technically infeasible to define a type that abstracts away all but the value type of ranges/iterators? Or does no-one care about doing this because the only reason is ide support?

I though it would be natural to have a type (templated on a given value type) that wraps a given iterator concept, but std doesn't define any. (If there's something to read on the internet about types that wrap concepts, could you point me there please?)

Upvotes: 9

Views: 1337

Answers (1)

Barry
Barry

Reputation: 302748

range-v3 has this under the name any_view<Ref, Cat>, where Ref is the range's reference (not value_type) and Cat is the iteration category (which defaults to input). That would let you write a function like:

int sum(any_view<int const&> v) { // <== not a function template
    int s = 0;
    for (int i : v) {
        s += i;
    }
    return s;
}

std::list<int> l = {1, 2, 3};
assert(sum(l) == 3);

The problem is, this range adapter is extremely expensive. Think about the way that iteration works. We have a loop like:

for (; it != end; ++it) {
    use(*it);
}

Even for input iterators, that means you have to type erase:

  • operator!=
  • operator++
  • operator*

And that's three indirect calls per element (either virtual function calls, or through a function pointer, depending on implementation). That's a lot of overhead, and it's very rarely something that you would actually want to use anyway. As a result, it was very low priority as far as range adaptors to add into C++20 and isn't even on our plan for adding range adaptors in the future.

Now, for contiguous ranges the story is a bit different, since you can always store just (T*, size_t) and it doesn't matter what the original range was. It's still type erasure, but it's free - there's no added overhead. So span<T> is great in that regard.

Or does no-one care about doing this because the only reason is ide support?

There are situations where type erasure actually is important. Maybe you're storing a bunch of ranges of different types. Maybe you're hiding this across an ABI boundary. But IDE support seems like a very weak motivator for using type erasure - especially in a context like this where there is fairly significant performance overhead to doing this.

[...] but then the visual studio ide doesn't know the type of element.

You could also fix that by not using auto.

Upvotes: 11

Related Questions