views::take_last and views::drop_last

Contents

1  Abstract

This paper proposes two new range adaptors, views::take_last and views::drop_last, that respectively produce the last N elements of a range and all-but-the-last N elements of a range. They mirror the shape of the existing views::take / views::drop adaptors and fill an obvious gap in the standard range adaptor set.

2  Revision History

R0

R1

3  Motivation

C++20 introduced views::take and views::drop to select or discard a prefix of a range. There is currently no direct adaptor that operates on the suffix of a range. Users have to fall back to composition:

r | views::reverse | views::take(n) | views::reverse   // take last n elements
r | views::reverse | views::drop(n) | views::reverse   // drop last n elements

which:

1. Requires bidirectional_range.
2. Is verbose and obscures intent.

While users can achieve the same effect for sized_range case via views::drop(size - n) or views::take(size - n), it's actually quite difficult to do this on the fly in the pipeline. We must first store the input range in a temp variable and then calculate size manually:

auto temp_r = r      | ... | ... | ... ;
auto take_n = temp_r | views::drop(ranges::distance(tmp_r) - n);      // take last n elements
auto drop_n = temp_r | views::take(ranges::distance(tmp_r) - n);      // drop last n elements

Introducing take_last or drop_last greatly improves readability and expressiveness and can generally handle any range that can be theoretically extracted or dropped from the end, for example, any forward range and non-forward-but-sized ranges:

r | views::take_last(n)   // last n elements
r | views::drop_last(n)   // drop last n

4  Prior Art

5  Design

5.1  Concept requirements

For input range that is already sized_range, we can essentially use views::drop/views::take to make hypothetical take_last_view and drop_last_view. There's no need to rewrite the same logic.

The non-sized cases are what we're truly interested in; and the views class would require:

template<view V>
  requires forward_range<V> && (!sized_range<V>)
[take|drop]_last_view;

Rationale:

• If V is sized_range we know the size up front and can jump to the correct offset (take_last) or compute the correct end (drop_last) directly. views::drop and views::take can already do this perfectly for us.
• If V is only forward_range we can make it work with a two-iterator "probe" technique that traverses the range once, provided we are allowed to re-visit elements (i.e. forward_iterator).
• An input-only, non-sized range provides neither, and cannot support the operation without buffering — we explicitly do not want that.

5.2  take_last: what begin() and end() return

take_last_view never introduces a new iterator type; it always yields the underlying iterator. The interesting question is how begin() is computed. Two cases are handled:

Case 2 uses the classical "runner" trick:

auto it    = ranges::begin(base_);
auto probe = ranges::next(it, count_, ranges::end(base_));
while (probe != ranges::end(base_)) {
  ++it;
  ++probe;
}
return it;

5.3  drop_last: what begin() and end() return

Unlike take_last, drop_last genuinely needs a new iterator type, because the "logical end" of the range is count steps before the physical end and we may not be able to represent that with the underlying sentinel. Two cases:

Case 2 requires a bespoke iterator; see the next section.

5.4  Iterator design for drop_last_view::iterator (case 2)

The iterator carries two copies of iterator_t<V>:

iterator_t<V> current_;    // logical position
iterator_t<V> probe_;      // current_ advanced by count_ (clamped to end)

Both advance together on every operation. When probe_ reaches the underlying sentinel, iteration is complete:

friend constexpr bool
operator==(const iterator& x, const sentinel_t<V>& y)  { return x.probe_ == y; }

The bespoke iterator intentionally does not provide subtraction with sentinel_t<V>. This iterator is only used in the fallback case where V is forward but not sized, and where the logical end cannot be represented directly by an iterator into the underlying range. If sentinel_t<V> and iterator_t<V> were sized sentinels for each other, then the underlying forward range would already be a sized_range, and the adaptor would use the sized-range case instead of this iterator.

When the underlying iterator supports stronger iterator concepts, the wrapper preserves those operations by applying the same movement to both current_ and probe_. This maintains the invariant that probe_ denotes the position corresponding to current_ advanced by count_, and allows the fallback iterator to preserve bidirectional, random-access, and contiguous capabilities of the underlying iterator where available.

5.5  Caching for amortized O(1) begin()

Per [range.range], ranges::begin(r) must be amortized O(1). This matters for all the above cases where the naive begin() or end() is not O(1).

The specification uses the standard "cache the value on the first call and return it unchanged on subsequent calls" formulation.

5.6  Why end() does not reuse begin()'s work

An attractive optimisation for take_last case 2 is to observe that at the end of the two-iterator loop, probe_ equals ranges::end(base_) already, and could conceivably be returned by end() to avoid recomputing it.

The author intentionally avoids this design because end() may be called before begin(). Returning an iterator instead of a sentinel from end() would force the O(N) traversal to run prematurely, simply returning ranges::end(base_) which is O(1) seems better choice.

5.7  Precondition on count

Following take_view / drop_view, both constructors add:

Preconditions: count >= 0 is true.

5.8  reserve_hint()

take_last_view always provides reserve_hint(), because its cardinality is bounded above by count_. drop_last_view provides reserve_hint() only when the base range is approximately-sized. This lets ranges::to<C> allocate the right capacity even when the exact size cannot be obtained in O(1). The rules are the following:

• take_last_view::reserve_hint() returns min(ranges::reserve_hint(base_), count_) when the underlying range is approximately-sized, and count_ otherwise.
• drop_last_view::reserve_hint() returns max(ranges::reserve_hint(base_) - count_, 0).

5.9  Borrowed-range propagation

Both views are borrowed iff the underlying range V models enable_borrowed_range, which is consistent with drop_view/take_view.

5.10  Unbounded ranges

These adaptors are suffix operations and therefore are meaningful for ranges with a reachable end. The constraints cannot, in general, express finiteness. For a non-sized forward range, take_last_view::begin() must reach the physical end of the base range, and therefore might not terminate for an unbounded range. Similarly, drop_last_view on an unbounded range has no mathematical “last N elements” to remove.

Since the current standard does not have the concept of infinite ranges, this may require another paper for rejecting unbounded ranges at compile time.

6  Proposed Wording

This wording is relative to N5046.

6.1  Change to 24.2 [ranges.syn]

namespace std::ranges {
  […]
  namespace views { inline constexpr unspecified drop_while = unspecified; }

  // [range.take.last], take last view
  template<view V>
    requires forward_range<V> && (!sized_range<V>)
  class take_last_view;

  template<class T>
    constexpr bool enable_borrowed_range<take_last_view<T>> =
      enable_borrowed_range<T>;

  namespace views { inline constexpr unspecified take_last = unspecified; }

  // [range.drop.last], drop last view
  template<view V>
    requires forward_range<V> && (!sized_range<V>)
  class drop_last_view;

  template<class T>
    constexpr bool enable_borrowed_range<drop_last_view<T>> =
      enable_borrowed_range<T>;

  namespace views { inline constexpr unspecified drop_last = unspecified; }
  […]
}

6.2  Add 25.7.? Take last view [range.take.last] after 25.7.13 [range.drop.while] as indicated:

6.2.1  Overview [range.take.last.overview]

take_last_view produces a view of the last N elements of another view.

The name views::take_last denotes a range adaptor object ([range.adaptor.object]). Let E and F be expressions, let T be remove_cvref_t<decltype((E))>, and let D be range_difference_t<decltype((E))>. If decltype((F)) does not model convertible_to<D>, views::take_last(E, F) is ill-formed. Otherwise, the expression views::take_last(E, F) is expression-equivalent to:

• Preconditions: static_cast<D>(F) >= 0 is true.

Drafting note: This is to reject negative count; otherwise, r | views::drop(dist - std::min(dist, -42)) would produce r | views::drop(dist + 42).

• If T models sized_range, then E | views::drop(ranges::distance(E) - std::min(ranges::distance(E), static_cast<D>(F))), except that E is evaluated only once.
• Otherwise, take_last_view(E, F).

[Example:

for (int i : views::iota(0, 10) | views::take_last(3))
  print("{} ", i);        // prints 7 8 9

— end example]

6.2.2  Class template take_last_view [range.take.last.view]

namespace std::ranges {
  template<view V>
    requires forward_range<V> && (!sized_range<V>)
  class take_last_view : public view_interface<take_last_view<V>> {
    V base_ = V();                     // exposition only
    range_difference_t<V> count_ = 0;  // exposition only

  public:
    take_last_view() requires default_initializable<V> = default;
    constexpr explicit take_last_view(V base, range_difference_t<V> count);

    constexpr V base() const & requires copy_constructible<V> { return base_; }
    constexpr V base() && { return std::move(base_); }

    constexpr auto begin();
    constexpr auto end() { return ranges::end(base_); }

    constexpr auto reserve_hint() {
      if constexpr (approximately_sized_range<V>) {
        auto sz = static_cast<range_difference_t<V>>(ranges::reserve_hint(base_));
        return to-unsigned-like(std::min(sz, count_));
      }
      return to-unsigned-like(count_);
    }

    constexpr auto reserve_hint() const {
      if constexpr (approximately_sized_range<const V>) {
        auto sz = static_cast<range_difference_t<const V>>(ranges::reserve_hint(base_));
        return to-unsigned-like(std::min(sz, count_));
      }
      return to-unsigned-like(count_);
    }
  };

  template<class R>
  take_last_view(R&&, range_difference_t<R>) -> take_last_view<views::all_t<R>>;
}

constexpr explicit take_last_view(V base, range_difference_t<V> count);

Preconditions: count >= 0 is true.

Effects: Initializes base_ with std::move(base) and count_ with count.

constexpr auto begin();

Returns:

• If V models bidirectional_range and common_range, ranges::prev(ranges::end(base_), count_, ranges::begin(base_)).
• Otherwise, the first iterator i reachable from ranges::begin(base_) such that bool(ranges::next(i, count_, ranges::end(base_)) == ranges::end(base_)) is true.

Remarks: In order to provide the amortized constant-time complexity required by the range concept when take_last_view models forward_range, this function caches the result within the take_last_view for use on subsequent calls.

6.3  Add 25.7.? Drop last view [range.drop.last] after [range.take.last] as indicated:

6.3.1  Overview [range.drop.last.overview]

drop_last_view produces a view of a range with its last N elements removed.

The name views::drop_last denotes a range adaptor object ([range.adaptor.object]). Let E and F be expressions, let T be remove_cvref_t<decltype((E))>, and let D be range_difference_t<decltype((E))>. If decltype((F)) does not model convertible_to<D>, views::drop_last(E, F) is ill-formed. Otherwise, the expression views::drop_last(E, F) is expression-equivalent to:

• Preconditions: static_cast<D>(F) >= 0 is true.
• If T models sized_range, then E | views::take(std::max(ranges::distance(E) - static_cast<D>(F), D(0))), except that E is evaluated only once.
• Otherwise, drop_last_view(E, F).

[Example:

for (int i : views::iota(0, 10) | views::drop_last(3))
  print("{} ", i);        // prints 0 1 2 3 4 5 6

— end example]

6.3.2  Class template drop_last_view [range.drop.last.view]

namespace std::ranges {
  template<view V>
    requires forward_range<V> && (!sized_range<V>)
  class drop_last_view : public view_interface<drop_last_view<V>> {
    V base_ = V();                     // exposition only
    range_difference_t<V> count_ = 0;  // exposition only

    // 24.7.?.3, class drop_last_view::iterator
    class iterator;                    // exposition only

  public:
    drop_last_view() requires default_initializable<V> = default;
    constexpr explicit drop_last_view(V base, range_difference_t<V> count);

    constexpr V base() const & requires copy_constructible<V> { return base_; }
    constexpr V base() && { return std::move(base_); }

    constexpr auto begin();
    constexpr auto end();

    constexpr auto reserve_hint() requires approximately_sized_range<V> {
      const auto s = static_cast<range_difference_t<V>>(ranges::reserve_hint(base_));
      return to-unsigned-like(s < count_ ? 0 : s - count_);
    }

    constexpr auto reserve_hint() const requires approximately_sized_range<const V> {
      const auto s = static_cast<range_difference_t<const V>>(ranges::reserve_hint(base_));
      return to-unsigned-like(s < count_ ? 0 : s - count_);
    }
  };

  template<class R>
  drop_last_view(R&&, range_difference_t<R>) -> drop_last_view<views::all_t<R>>;
}

constexpr explicit drop_last_view(V base, range_difference_t<V> count);

Preconditions: count >= 0 is true.

Effects: Initializes base_ with std::move(base) and count_ with count.

constexpr auto begin();

Returns:

• If V models bidirectional_range and common_range, ranges::begin(base_).
• Otherwise, iterator(ranges::begin(base_), ranges::next(ranges::begin(base_), count_, ranges::end(base_))).

Remarks: In order to provide the amortized constant-time complexity required by the range concept when drop_last_view models forward_range, this function caches the result within the drop_last_view for use on subsequent calls.

constexpr auto end();

Returns:

• If V models bidirectional_range and common_range, ranges::prev(ranges::end(base_), count_, ranges::begin(base_)).
• Otherwise, ranges::end(base_).

Remarks: In order to provide the amortized constant-time complexity required by the range concept when drop_last_view models forward_range, this function caches the result within the drop_last_view for use on subsequent calls.

6.3.3  Class drop_last_view::iterator [range.drop.last.iterator]

namespace std::ranges {
  template<view V>
    requires forward_range<V> && (!sized_range<V>)
  class drop_last_view<V>::iterator {
    iterator_t<V> current_ = iterator_t<V>();                       // exposition only
    iterator_t<V> probe_   = iterator_t<V>();                       // exposition only

    constexpr iterator(iterator_t<V> current, iterator_t<V> probe);   // exposition only
  public:
    using iterator_concept  = see below;
    using iterator_category = see below;
    using value_type        = range_value_t<V>;
    using difference_type   = range_difference_t<V>;

    iterator() = default;
    constexpr iterator_t<V> base() const;

    constexpr range_reference_t<V> operator*() const;
    constexpr auto operator->() const noexcept requires contiguous_range<V>;

    constexpr iterator& operator++();
    constexpr iterator operator++(int) = default;

    constexpr iterator& operator--() requires bidirectional_range<V>;
    constexpr iterator operator--(int) requires bidirectional_range<V> = default;

    constexpr iterator& operator+=(difference_type n) requires random_access_range<V>;
    constexpr iterator& operator-=(difference_type n) requires random_access_range<V>;

    constexpr range_reference_t<V> operator[](difference_type n) const
      requires random_access_range<V>;

    friend constexpr bool operator==(const iterator& x, const iterator& y);
    friend constexpr bool operator==(const iterator& x, const sentinel_t<V>& y);

    friend constexpr bool operator<(const iterator& x, const iterator& y)
      requires random_access_range<V>;
    friend constexpr bool operator>(const iterator& x, const iterator& y)
      requires random_access_range<V>;
    friend constexpr bool operator<=(const iterator& x, const iterator& y)
      requires random_access_range<V>;
    friend constexpr bool operator>=(const iterator& x, const iterator& y)
      requires random_access_range<V>;
    friend constexpr auto operator<=>(const iterator& x, const iterator& y)
      requires random_access_range<V> && three_way_comparable<iterator_t<V>>;

    friend constexpr iterator operator+(const iterator& x, difference_type n)
      requires random_access_range<V>;
    friend constexpr iterator operator+(difference_type n, const iterator& x)
      requires random_access_range<V>;
    friend constexpr iterator operator-(const iterator& x, difference_type n)
      requires random_access_range<V>;
    friend constexpr difference_type operator-(const iterator& x, const iterator& y)
      requires sized_sentinel_for<iterator_t<V>, iterator_t<V>>;

    friend constexpr decltype(auto) iter_move(const iterator& i)
      noexcept(noexcept(ranges::iter_move(i.current_)));

    friend constexpr void iter_swap(const iterator& x, const iterator& y)
      noexcept(noexcept(ranges::iter_swap(x.current_, y.current_)))
      requires indirectly_swappable<iterator_t<V>>;
  };
}

The member typedef-name iterator_concept is defined as follows:

• If V models contiguous_range, then iterator_concept denotes contiguous_iterator_tag.
• Otherwise if V models random_access_range, then iterator_concept denotes random_access_iterator_tag.
• Otherwise, if V models bidirectional_range, then iterator_concept denotes bidirectional_iterator_tag.
• Otherwise, iterator_concept denotes forward_iterator_tag.

The member typedef-name iterator_category is defined as follows:

• Let C be iterator_traits<iterator_t<V>>::iterator_category.
• If C models derived_from<random_access_iterator_tag>, then iterator_category denotes random_access_iterator_tag.
• Otherwise, if C models derived_from<bidirectional_iterator_tag>, then iterator_category denotes bidirectional_iterator_tag.
• Otherwise, iterator_category denotes C.

constexpr iterator(iterator_t<V> current, iterator_t<V> probe);

Effects: Initializes current_ with current and probe_ with probe.

constexpr iterator_t<V> base() const;

Effects: Equivalent to: return current_;

constexpr range_reference_t<V> operator*() const;

Effects: Equivalent to: return *current_;

constexpr auto operator->() const noexcept requires contiguous_range<V>;

Effects: Equivalent to: return to_address(current_);

constexpr iterator& operator++();

Effects: Equivalent to:

++current_;
++probe_;
return *this;

constexpr iterator& operator--() requires bidirectional_range<V>;

Effects: Equivalent to:

--current_;
--probe_;
return *this;

constexpr iterator& operator+=(difference_type n) requires random_access_range<V>;

Effects: Equivalent to:

current_ += n;
probe_   += n;
return *this;

constexpr iterator& operator-=(difference_type n) requires random_access_range<V>;

Effects: Equivalent to:

current_ -= n;
probe_   -= n;
return *this;

constexpr range_reference_t<V> operator[](difference_type n) const
  requires random_access_range<V>;

Effects: Equivalent to: return current_[n];

friend constexpr bool operator==(const iterator& x, const iterator& y);

Returns: x.current_ == y.current_.

friend constexpr bool operator==(const iterator& x, const sentinel_t<V>& y);

Returns: x.probe_ == y.

friend constexpr bool operator<(const iterator& x, const iterator& y)
  requires random_access_range<V>;
friend constexpr bool operator>(const iterator& x, const iterator& y)
  requires random_access_range<V>;
friend constexpr bool operator<=(const iterator& x, const iterator& y)
  requires random_access_range<V>;
friend constexpr bool operator>=(const iterator& x, const iterator& y)
  requires random_access_range<V>;
friend constexpr auto operator<=>(const iterator& x, const iterator& y)
  requires random_access_range<V> && three_way_comparable<iterator_t<V>>;

Let op be the operator.

Effects: Equivalent to: return x.current_ op y.current_;

friend constexpr iterator operator+(const iterator& x, difference_type n)
  requires random_access_range<V>;
friend constexpr iterator operator+(difference_type n, const iterator& x)
  requires random_access_range<V>;

Effects: Equivalent to:

auto tmp = x;
tmp += n;
return tmp;

friend constexpr iterator operator-(const iterator& x, difference_type n)
  requires random_access_range<V>;

Effects: Equivalent to:

auto tmp = x;
tmp -= n;
return tmp;

friend constexpr difference_type operator-(const iterator& x, const iterator& y)
  requires sized_sentinel_for<iterator_t<V>, iterator_t<V>>;

Returns: x.current_ - y.current_.

friend constexpr decltype(auto) iter_move(const iterator& i)
  noexcept(noexcept(ranges::iter_move(i.current_)));

Effects: Equivalent to: return ranges::iter_move(i.current_);

friend constexpr void iter_swap(const iterator& x, const iterator& y)
  noexcept(noexcept(ranges::iter_swap(x.current_, y.current_)))
  requires indirectly_swappable<iterator_t<V>>;

Effects: Equivalent to ranges::iter_swap(x.current_, y.current_).

7  Implementation experience

The author implemented views::take_last and views::drop_last based on libstdc++, see here.

8  Feature-test macro

Add to [version.syn]:

#define __cpp_lib_ranges_take_last 20XXXXL  // freestanding, also in <ranges>
#define __cpp_lib_ranges_drop_last 20XXXXL  // freestanding, also in <ranges>

9  References

• [ A Plan for C++26 Ranges] Barry Revzin, https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/p2760r1.html
• [range-v3] Eric Niebler, range-v3, https://github.com/ericniebler/range-v3.