C++ Logo


Advanced search

[std-proposals] views::drop_last: the Implementation of begin()/end() in worse case?

From: Hewill Kang <hewillk_at_[hidden]>
Date: Sat, 13 Apr 2024 19:04:36 +0800
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)
  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++() {
      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_*)); //
    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

(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?


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:

Received on 2024-04-13 11:04:49