`bel::filter_view` is not a model of `std::ranges::range`

[JohelEGP]

Although a specialization of bel::filter_view can satisfy std::ranges::range, it can't model it. That's because it fails to meet https://eel.is/c++draft/range.range#2.2:

(2.2) both ranges​::​begin(t) and ranges​::​end(t) are amortized constant time and non-modifying, and

A problem that also applies to std::ranges::filter_view is that its iterator's increment can't meet https://eel.is/c++draft/iterator.requirements.general#13:

13 # All the categories of iterators require only those functions that are realizable for a given category in constant time (amortized). Therefore, requirement tables and concept definitions for the iterators do not specify complexity.

See also https://github.com/ericniebler/stl2/issues/585#issuecomment-575747082.

[JohelEGP]

FYI, the issue is that bel::filter_view::begin always computes the return value from the begin of the underlying range.

Places that don't have complexity requirements are a view's default and non-copy/move constructors (https://eel.is/c++draft/range.view#2) and the CPO for a view (https://eel.is/c++draft/range.adaptors and https://eel.is/c++draft/customization.point.object have no complexity requirements).

Those could compute the filter view's begin without failing to model a view concept.

bel::views::filter(r); // OK
bel::filter_view{r}; // OK

Now, that changes Belleviews status quo. Currently, modifying the underlying range's elements doesn't invalidate the filter view over that underlying range. But my suggestion to use the filter view's constructor or CPO fixes its begin to whichever underlying iterator satisfied the filter's predicate, so iterating the filter view again starts from a subrange of the underlying range.

[correaa]

I have a question to understand the situation.

Is it clear what the categories of std::ranges::filter_view and bel::views::filter and the categories of the corresponding underlying iterators need to be? (even as a function of the category of the underlying range).

For sure, it is InputRange/Iterator or more. And for sure, it has to be less than RandomAccess. It may well be a new kind of category, no?

To be concrete, does it make sense to write a table like this?

Underlying range	Immutable Filter view	Mutable Filter view
RandomAccess	Bidirectional	InputRange (?)
Bidirectional	Bidirectional	InputRange (?)
InputRange	InputRange	--

[JohelEGP]

It may well be a new kind of category, no?

If you can make it fit between two existing C++ Standard library iterator categories. Otherwise it's something else I don't know about.

To be concrete, does it make sense to write a table like this?

Looks OK. IIUC from watching https://www.youtube.com/watch?v=qv29fo9sUjY and the README, Belleviews is OK with the mutable being the same category as the immutable.

I have a question to understand the situation.

Were my answer actually helpful? The category and failure to meet complexity requirements seems like an orthogonal issue to me.

[correaa]

If you can make it fit between two existing C++ Standard library iterator categories. Otherwise it's something else I don't know about.

yes, exactly, I think this is a new category of ranges. (And of iterators... it may well be that iterators and ranges do not need to have the same categories. It might also be that ranges and iterators are invalidated differently! ranges should be more fragile to invalidation. Also, the invalidation can automatically redefine still-valid subranges)

IIUC from watching https://www.youtube.com/watch?v=qv29fo9sUjY and the README, Belleviews is OK with the mutable being the same category as the immutable.

I see. (see my comment in the video)

Were my answer actually helpful?

Yes, but I have a lot to figure out yet.

The category and failure to meet complexity requirements seems like an orthogonal issue to me.

Not in general, in IMO. Complexity is one of the things that can make Bidirectional different from RandomAccess.

[JohelEGP]

I see.

The std::ranges library doesn't have "range categories" like the <iterator> library has "iterator categories". Instead, it uses concepts for ranges (e.g., forward_range at https://eel.is/c++draft/range.refinements), and are defined in terms of the iterator concept (which use the iterator category as a part of their specification).

Not in general, in IMO. Complexity is one of the things that can make Bidirectional different from RandomAccess.

That's actually all there is to it. As quoted in the opening comment, iterators provide only constant (amortized) operations.

[correaa]

The std::ranges library doesn't have "range categories" like the <iterator> library has "iterator categories". Instead, it uses concepts for ranges (e.g., forward_range at https://eel.is/c++draft/range.refinements), and are defined in terms of the iterator concept (which use the iterator category as a part of their specification).

Yes, this is I think where thing becomes problematic because there might be no exact matching between range categories (or range concept) and iterator categories. And also invalidation can be different.

That's actually all there is to it. As quoted in the opening comment, iterators provide only constant (amortized) operations.

I would completely ignore the words "constant amortized" in the current design. It means nothing at best because it implies either an incorrect behavior (e.g. threads as in the talk) or an unbounded cost for its correct utilization (synchronization).

[correaa]

Maybe I am saying something obvious, but after mutation of the element referenced by a filter-iterator, the filter-iterator is, in general, invalidated for dereference. (because dereference will not give something that fulfills the predicate of the filter-iterator). The only thing you can do with it is to increment it (or decrement it).

In that sense, the mutable-filter-iterator is like an InputIterator but is also Bidirectional, not just Forward. That is the reason I think the normal categories don't apply. Since access-features and input-output characteristics are really orthogonal. Perhaps we need a new concept, InputBidirectional.

What I am not sure about is the range itself. If .begin() is cached, the whole range is invalidated for sure, but is it also invalidated in bel::views?

I have the impression that mutable filter views are in one of the "lowest" categories of iterators and one of the weakest ranges conceptually. I think it is futile to try to view it as something that InputIterator in practice.