Unable to use std::ranges::is_sorted with view's each - not a forward iterator

[iK4tsu]

It is possible to use storage and a simple view with std::ranges::is_sorted. However, view::each does not satisfy the forward iterator requirements.

See an example here

With multi component views it would be nice if the extended iterator satisfied the requirements as it would make it easier not only to verify if a storage is sorted by another storage, or with any other range that requires forward iterators.

registry.sort<A,B>();
std::ranges::is_sorted(registry.view<A,B>().each(), cmp, []( auto each ){ return std::get<1>(each); });

Well I can

registry.sort<A,B>();
std::ranges::is_sorted(registry.view<A>().each(), cmp, [&registry]( auto entt ){ return registry.get<B>(entt); });

but now I have to capture the registry and do a get call for every entity.

Also, this is assuming that every entity that owns A also owns B, which is true for my use-case, but not everyone.

[skypjack]

Unfortunately, the iterable object returned by each cannot offer forward iterators. It's funny because this happens due to an idiosyncrasy of the C++ language. 😅

Long story short, among the other things, the reference type of a forward iterator must be an actual reference. On the other hand, the view returns a tuple containing the entity and a bunch of component references 🤷‍♂️ that's it. The multi-pass and all other requirements would still apply, but we can't say it's a forward iterator anyway. A long-standing flaw in the standard that has been long discussed and never truly resolved.

There is nothing I can do here I guess but I'm open to suggestions if you want to discuss it further. 👍

[iK4tsu]

Probably a similar approach to ranges' zip implementation. It offers forward iterators if all views are forward iterators. The same for bidirectional and random access. Paper So, if a storage is by itself a forward iterator, and this iteration is kind of like a zip | filter - or the other way around, it could be possible, if I'm seeing this straight.

Edit: with this I'm referring to the idea behind zip, I know this cannot be implemented with a zip, or the iteration is the same as a zip because it isn't, but since we have access to the underlying storages it could work I think

[skypjack]

Technically speaking, this iterator is literally a zip iterator already. It also models a forward iterator for most of the requirements. However, its reference type cannot be a reference and this puts it in the input iterator category. An algorithm that checks the category and requires a forward iterator tag will reject it. It doesn't matter if it provides a multi-pass guarantee, if it's default constructible or if it fits all other requirements of a forward iterator. That is why I mentioned a well-known and documented idiosyncrasy of the C++ language. Fortunately, the forward iterator concept fixed it with C++20. It doesn't require an actual reference anymore when dereferencing for example. However, I cannot change the iterator category since the requirement is still there.

[iK4tsu]

But can't we add using iterator_concept = std::forward_iterator_tag to work with c++20 ranges?

[skypjack]

Well, technically speaking this is still a C++17 library (mainly because C++20 isn't a thing yet in many envs). I guess it's possible though. However, I'm not 100% sure that iterator_traits reads this type member from iterators. The standard talks about explicit specializations of the traits. Am I missing something?

[iK4tsu]

Well, reading through this paper and the iterator tag says it does, if I'm understanding it correctly. C++17 will use the category and C++20 will prioritize the concept, making it compatible with both legacy and current iterator implementations. Since this specific iterator is an input_iterator in the legacy system and a forward_iterator in the newer system, it also is a valid candidate to specify the different iterator tags, if I'm understanding this correctly.

[skypjack]

Actually, there are a few iterators in EnTT that model a different concept. For example, the ones for meta containers too. I'll review them all soon. 👍

[iK4tsu]

Thank you! Looking forward to this :)