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. 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).

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?SO: What is the best way to drop last element using c++20 ranges

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