`<algorithm>`: Unwrapping output iterators in range algorithms

[CaseyCarter]

std algorithms validate checked/wrapped iterators and unwrap them into unchecked/unwrapped iterators before operating on them. This lets us both help users find bugs in the arguments they pass to algorithms and have algorithms be performant even when given checked iterators. The pertinent machinery is:

• _Adl_verify_range(first, last) tries to validate the range [first, last) by calling a user customization point via argument dependent lookup.
• _Get_unwrapped(x) extracts an unwrapped iterator/sentinel from the wrapped iterator/sentinel x.
• _Get_unwrapped_unverified(x) either returns x or extracts an unwrapped iterator from x (as determined by the author of x's type) whose range we cannot verify because we don't know a priori how many elements will be written.
• _Idl_distance<I>(first, last) returns iter_difference_t<I>(last - first) when last - first is valid, and otherwise returns a value of the tag type _Distance_unknown. (The idea here is that you pass the wrapped iterator type I and unwrapped iterator/sentinel first and last, but I'm not sure we want to tolerate corresponding wrapped and unwrapped iterator types with differing difference types. Someone needs to ask @BillyONeal.)
• _Get_unwrapped_n(x, n) has behavior that depends on the type of n:
  • if the type is _Distance_unkown, _Get_unwrapped_n returns _Get_unwrapped_unverified(x).
  • Otherwise, the type must be iter_difference_t<decltype(x)> and _Get_unwrapped_n both validates that x + [0, n) is a valid counted range and returns an unwrapped iterator extracted from the wrapped iterator x.
• _Seek_wrapped(w, u) injects unwrapped iterator u into the wrapped iterator w, both of which denote elements of the same range. This is used to compute return values.

Currently all of the above work with Ranges move-only iterators and differing iterator/sentinel types except for _Idl_distance. Consequently the unwrapping story for output iterators passed to Ranges algorithms is very poor. We need a ranges::_Idl_distance which handles iterator/sentinel pairs and move-only iterators and knows about sized_sentinel_for. We should also have a range overload of _Idl_distance so we can simply write:

template <input_range _Rng, /* stuff */ _Out>
void some_alg(_Rng _Range, _Out _Result) {
  auto _UResult = _Get_unwrapped_n(_Result, _Idl_distance(_Range));
  // ...

Once _Idl_distance is squared away, we need to audit all range algorithms and add unwrapping/rewrapping support for output iterators. We've already _Get_unwrapped_unverified for some (but not all) appropriate algorithms, the vast majority don't unwrap iterators and should therefore be easily found. It's probably also a good idea to have the operator* implementations in test::iterator (defined in tests/std/tests/range_algorithm_support.hpp) static_assert that the iterator type is unwrapped to both help with the algorithm audit and guard against future regressions.

[StephanTLavavej]

Relabeling as performance since I don't believe this affects correctness - please meow if I've misunderstood.

[StephanTLavavej]

Reviewing #983, I believe that ranges::replace_copy and ranges::replace_copy_if are also candidates. They always write N things to the output (which can variously be input elements or _Newval). Note that this is very different from ranges::copy_if which writes a varying-based-on-predicate number of things.

[StephanTLavavej]

Should we also audit for _Get_unwrapped_unverified usage, in the algorithms that don't know how many elements will be written?

[CaseyCarter]

Yes, I've expanded the problem statement.