Wishlist for range-v3 version 1.0

[ericniebler]

• [x] Redesigned range access (begin, end, etc.) customization points and safe_iterator_t.
• [x] Optionally use C++20 concepts when available (see new-concepts-syntax branch for initial work).
• [x] Use SFINAE-in-return-type instead of SFINAE-in-template-argument-list to avoid LLVM#36158
• [ ] Better diagnostics for failed requirements checks.
• [x] Views conforming to P0789.
  • [x] Handle const/non-const view iteration like in P0789 (see simple-view<Rng>):
  • [x] view::split works with Input ranges if the pattern is a "tiny" range.
  • [x] Replace iterator_range with subrange.
• [x] Algorithms return subrange<> or dangling<subrange<>> where appropriate.
• [ ] Class template argument deduction where appropriate.
• [x] Add ref_view / ~remove~ deprecate hack-ish begin/end support for reference_wrapper.
• [x] Comparison function objects (less, etc.) conform to the Ranges TS.
• [ ] Rethink view::reverse and view::stride as described in #805
• [x] Header reorganization.
• [ ] ~Range size can be (and usually is) signed.~
• [ ] Drop with_braced_init_args support and see who complains.
• [x] Require C++14(?)
• [ ] Include a .clang-format file, and CI coverage to ensure contributions meet the format.
• [ ] Restrict the view_interface::operator[] slicing overloads to those that are O(1).
• [ ] more?

Generally, make a pass through the Ranges TS and the proposals in-flight, find differences between them and range-v3, and squash them!

@CaseyCarter Can you think of more interface-breaking changes we should lump into a major new range-v3 release?

[CaseyCarter]

That's a reasonable set of features. We should try to coordinate with clang folk on 36158: we don't want to invest in a workaround if the bug is on someone's plate to investigate in the next few months.

I think we should be violently militant and make range_size_type_t an alias for range_difference_type_t. range-v3 can "fix" broken ranges by giving them a properly signed size ;)

I'd like to pull optional into the detail namespace - that's interface-breaking. In a perfect world, we would stop using optional<T&>/variant<T&> so we can use the standard components when they're available instead of our implementations.

[ericniebler]

In a perfect world, we would stop using optional<T&>/variant<T&> so we can use the standard components instead of our implementations when they're available.

We'll have more problems moving away from my home-rolled variant: the visit_i interface is used in places and not supported by std::variant. EDIT: but I agree in principle.

[CaseyCarter]

visit_i (and visit for that matter) can be implemented non-intrusively, albeit with some fancy footwork to get around the lack of a get variant with UB when valueless. I believe I can achieve zero overhead at least for Clang & GCC.

[h-2]

While interfaces are on the table: you previously closed #722, but I also didn't see any of the metafunctions in the first TS if I recall correctly. I think they are kind of important and cleaning that up would help a lot. You said @CaseyCarter had tried and then reverted the changes. Do you feel like this is worth investigating again and would you accept a PR on this if I make it work without creating other wild problems?

[ericniebler]

would you accept a PR on this if I make it work without creating other wild problems?

Specifically to make the traits (value_type and friends) work with ranges as well as iterators? I'm pretty sure @CaseyCarter and I decided it was impossible in the general case, but I don't remember the specific reason. You're welcome to try.

[CaseyCarter]

I'm pretty sure @CaseyCarter and I decided it was impossible in the general case

I vaguely recall that ambiguity was an issue. Something along the lines of "When Range::difference_type is a valid type, does difference_type_t<Range> return Range::difference_type or difference_type_t<iterator_t<Range>>?" I think the killer was that iterators can be ranges - I'm looking at you directory_iterator! - in which case there's no way to resolve the ambiguity if the associated types differ.

[h-2]

"When Range::difference_type is a valid type, does difference_type_t return Range::difference_type or difference_type_t<iterator_t>?"

What does it do now? Does difference_type_t<> always do difference_type_t<iterator_t<Range>>? That's more convoluted than I thought :thinking: The most intuitive solution IMHO would be if difference_type_t<> always operated on exactly the type you are giving it. If you specifically want it return the member type definition of a member type definition (::iterator::difference_type) instead of just a member type definition (::difference_type), than you should actually call difference_type_t<iterator_t<Range>> or a specifically defined iterator_difference_type_t<Range> (although the former is much clearer from my POV). This still leaves:

I think the killer was that iterators can be ranges - I'm looking at you directory_iterator! - in which case there's no way to resolve the ambiguity if the associated types differ.

I think that was a poor design decision, but that's irrelevant at this point. Is this the only example? At least it is clear that here the associated types are the same. And I have a difficult time imagining a well-designed example where they aren't – member types would also be ambiguous, in general it would just be confusing.

Based on my current information I would argue strongly against supporting this and state that "If a type satisfies InputRange and statisfies InputIterator the associated types [...] for both concepts are required to be identical."

If OTOH you want to support this kind of setup, there is no way to resolve the ambiguity, and I would argue to make one set of metafunctions only resolve on ranges, and the other one only resolve on iterators. Ideally, I would then also call them range_difference_t<>, and iterator_difference_t<> or iter_difference_t<> and not have a difference_t<> at all to reduce confusion. This would also be a change from now, where difference_t<> is apparently only required to work on iterators, but also works on some ranges (STL containers) – which is just awkward.

[h-2]

What does it do now? Does difference_type_t<> always do difference_type_t<iterator_t<Range>>? That's more convoluted than I thought :thinking:

I just stumbled over this again today, range_difference_t<> always does difference_type_t<iterator_t<Range>>, too, and never returns the member type of the range:

struct myv : std::vector<int>
{
    using base = std::vector<int>;
    using base::base;

    using difference_type = int32_t;

    using typename base::value_type;
    using typename base::reference;
    using typename base::const_reference;
    using typename base::pointer;
    using typename base::iterator;
    using typename base::const_iterator;
};

static_assert(std::is_same_v<ranges::difference_type_t<typename myv::iterator>, int64_t>); // passes
static_assert(std::is_same_v<ranges::difference_type_t<myv>, int64_t>);                    // fails
static_assert(std::is_same_v<ranges::range_difference_type_t<myv>, int64_t>);              // passes

1. The first assertion is expected to pass, all good.
2. The second assertion is expected to not be defined iff ranges::difference_type_t is the wrong metafunction to use on ranges; but it is defined and fails which would be expected, iff it were the right thing to use on ranges.
3. The third metafunction is expected to be the correct one to use on ranges, but this passes, because it completely ignores the member type. I see that you don't want to force ranges to define this, and that it might make sense to have range_difference_type_t<Range> fallback to difference_type_t<iterator_t<Range>> if there is no member definition or specialisation of the associated type, but always doing this? :cold_sweat:

I know why these things happen from reading the code, now, but I find it very hard to see the logic in it; I would like to re-iterate that it would really clear things up if we had

1. a single interface (with the limitation that a type that is both iterator and range must have same associated types); or
2. two distinct interfaces for iterators and ranges respectively where the range_ and iterator_ versions are not defined on the other type (but range_FOO_t<Rng> might fallback to iterator_FOO_t<iterator_t<Rng>>).

[ericniebler]

I know why these things happen from reading the code, now, but I find it very hard to see the logic in it

The range_[xxx]_t<R> aliases are intended to be a shorthand for [xxx]_t<iterator_t<R>> aliases, no more and no less. If they are confusing, the proper thing, IMO, is to simply drop them. Having them sometimes pick up an associated type from the range makes it useless in a generic context. Generic code needs to know how to use the associated types. If range_difference_type_t<Rng> cannot be used to accurately represent the difference of two of Rng's iterators, then what is it for?

I'll note that I left these aliases out of the Ranges TS for precisely this reason, and I'm becoming increasingly convinced from this conversation that they should be dropped for range-v3 also.

[h-2]

The range_[xxx]_t aliases are intended to be a shorthand for [xxx]_t<iterator_t> aliases, no more and no less. If they are confusing, the proper thing, IMO, is to simply drop them.

Ok, I wouldn't mind that, actually.

Having them sometimes pick up an associated type from the range makes it useless in a generic context. Generic code needs to know how to use the associated types.

Well, I think the assumption here is that the member types that a range defines are always identical to the member types of its iterator (are there contradicting examples?). Then again, it is bad to have the same thing defined in two places which is probably why you never included these kind of requirements on ranges, instead relying fully on the iterators? That makes sense, but also contradicts current expectations from people who are used to dealing with containers as the most prominent example of ranges. This got me another time, as well, when I expected that a random access range would always provide operator[] – which it doesn't necessarily, because only its iterator is required to provide this.¹

I am not sure how to resolve this properly, as containers are not going to go away, and people will definitely refer to the value_type of std::vector<int>, and not "the value_type of std::vector<int>'s iterator" for the foreseeable future (less so for difference_type maybe). So people could expect the value_type_t<> metafunction to work on containers. Which it currently does. Which then leads people to also expect it from other ranges – which it doesn't.

So removing range_[xxx]_t<> is only the first step. IMHO you would also need to make [xxx]_t stop working on containers and engage in the mission of educating people to only depend on the iterator's associated types; or make [xxx]_tmirror the previous behaviour of range_[xxx]_t<> where it also works on all ranges, via their iterator (and hope that there are no conflicting definitions between a range's associated types and its iterator's associated types). In the end this also resolves to always relying on the iterator so I am slightly in favour of the first solution.

_{¹ I am aware that requiring it only on the range would not be sufficient, as there are examples where the range provides it, but the iterator doesn't (cases where operator[] is not in O(1) and the range in fact is not random acces, e.g.std::unordered_map`).}

[tonyelewis]

Not sure if these are appropriate entries for this issue but... Some things I've been thinking would be nice:

• Algorithms equivalent to the find algorithms (find_index()) that return the (optional-wrapped?) index of the found element (like first_index in Perl). For me, getting the index is a pretty common use-case for find algorithms. For random-access ranges this cleans up the caller's syntax; for forward ranges, it makes the caller able to do get the index more efficiently; for input ranges, it means the caller doesn't have to write their own loop.
• (As discussed the other day) support for a simple way to convert arbitrarily nested ranges into a string by variadically specifying the joining strings.
• (As discussed the other day) possibly: lazy, owning range algorithms.

Are any of these interest you? I might be able to make a vaguely competent job of a PR for the index thing.

As always, thanks very much. My thanks are sincere, even if the mugs are a bit naff. :)

[KindDragon]

* _more?_

Most voted feature request "enumerated range" #785?

[JohelEGP]

• [ ] Include a .clang-format file, and CI coverage to ensure contributions meet the format.

With all the macro usage in the deep-integration branch, this seems unfeasible. You'd either have to splash // disable clang-format and // enable clang-format in a lot of places because clang will reformat the macros into ugly messes, or manually select the changes and applying clang-format. I prefer auto format on file save, so I refrain from the latter.