Hi folks,

I recently plan to write proposals for views::drop_last(n) (and
views::take_last(n)), which are labeled Tier 1 on P2760
<https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/p2760r1.html#tier-1>.
The trickiest part is implementing drop_last_view::end() when dealing with
only-forward-non-sized ranges.

In such a case, we need to calculate the end position. range/v3 uses two
iterators to probe the end, similar to this:

template<forward_range R>auto probe_last(R& r, range_difference_t<V> n) {
  auto it = ranges::begin(r);
  auto probe = ranges::next(it, n, ranges::end(r));
  for (; probe != ranges::end(r); ++probe)
    ++it;
  return it;
}

We probe the end by advancing both iterators simultaneously. If the latter
iterator reaches the end of the original range, the previous one is the end
position of drop_last_view.

Therefore, the drop_last_view::begin()/end() can be implemented as
follows (*let's
ignore other more optimized cases*):

template<view V>struct drop_last {
  V *base_*;
  range_difference_t<V> *count_*;

  auto begin() { return ranges::begin(*base_*); }

  auto end() {
    return probe_last(*base_*, *count_*); // O(*N*)
  }
};

However, this makes the first call to end() take O(*N*), where *N* is the
size of the original range (because the probe iterator must reach the end).
The advantage is that we can reuse this probe_last() help function when
implementing take_last_view::begin().

Another way to implement drop_last_view::begin()/end() in the worst-case is
to wrap the current iterator as well as the probe iterator with a custom
iterator, then specialize its operator==:

template<view V>
struct drop_last {
  V *base_*;
  range_difference_t<V> *count_*;

  struct iterator {
    iterator_t<V> *current_*, *probe_*;

    // lots of iterator operations...
    iterator& operatpr++() {
      ++*current_*;
      ++*probe_*;
      return *this;
    }

    bool operatpr==(sentinel_t<V> end) const {
      return *probe_* == end*;*
    }
  };

  auto begin() {
    auto it = ranges::begin(*base_*);
    auto probe = ranges::next(it, *count_*, ranges::end(*base_*)); //
O(*count_*)
    return iterator{it, probe};
  }

  auto end() { return ranges::end(*base_*); }
};

This way seems to be more efficient than the previous one because the
begin() call only takes O(*count_*) instead of O(*N*). The downside is that
we basically introduce an iterator that behaves exactly the same as the
original iterator, except for the operator== operator. This brings lots of
repetition.

(Range/v3 adopts the second method, but thanks to its internal helper
classes such as adapter_base, which can easily create such iterators with
such custom behavior. However, there is no such thing in the standard
currently, the closest one is P2727 std::iterator_interface
<https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/p2727r3.html>).

I'm not sure if there is a better solution for this. I would like to know
which method you think is more likely to be accepted by the standard?

Reference:

SO: What's the best way to `take_last(n)` a non-sized range?
<https://stackoverflow.com/questions/74866888/whats-the-best-way-to-take-lastn-a-non-sized-range>
SO: What is the best way to drop last element using c++20 ranges
<https://stackoverflow.com/questions/71689137/what-is-the-best-way-to-drop-last-element-using-c20-ranges>

range/v3 drop_last_view:
https://github.com/ericniebler/range-v3/blob/master/include/range/v3/view/drop_last.hpp