P2406R4
Add `lazy_counted_iterator`

1. Revision History

r4: Integrate SG9 feedback (Issaquah)

• Fix missing change from input_or_output_iterator to input_iterator in the synopsis

• Simplify the definition of when two iterators refer to the same sequence

• Simplify the definition of void operator++(int)

• Add opens section for additional design suggestions/questions raised

• Add implementation experience section

r3: Itegreating LEWG feedback:

• Define iterator_concept and iterator_category like other iterator adaptors do, unlike counted_iterator which is special

• Require input_iterator as operator++(int) definition doens’t match output_iterator requirements

• General cleanup

r2: Integrating SG9 feedback:

• Removing references to p2578, after SG9 vote against it

• Fix design suggested

• Add design alternatives

r1: Improving many parts, following feedback from Inbal Levi and from Reddit users

r0: initial revision

2. Problem description

2.1. Range with the exact number of items

Look at this example code [CE-FILTER]:

#include <ranges>
#include <iostream>
 
namespace rv = std::views;
 
int main() {
    for (auto i  : rv::iota(0)
            | rv::filter([](auto i) { return i < 11; })
            | rv::take(11))
        std::cout << i << '\n';
}

Compiler explorer gets a timeout when trying to run this simple example, instead of printing the numbers from 0 to 10. Running the same code locally, it runs for very long time. Tracking the roots of the issue, the problem is that take uses counted_iterator when the range isn’t random_access and counted_iterator increments the internal iterator even if the counter has reached the requested count. In this case, the filter never returns when trying to increment it once again (at least not until iota reaches the UB case of signed overflow).

The example above is just for illustration, but we can think about cases where it isn’t clear for the user how many items the filter is expected to return, so limiting the output count with take becomes dangerous and results in unexpected behavior.

It means take isn’t usable on ranges if we don’t know in advance that there is an extra element in the range.

2.2. input_iterator case

Even more common problem is when using input ranges, e.g. basic_istream_view. In most of these cases, advancing the internal iterator when reaching the count means eating an additional input that can’t be retrieved again later, or hanging forever if no additional input exists and the stream isn’t closed. For example [CE-ISTREAM]:

#include <ranges>
#include <iostream>
#include <sstream>
#include <cassert>
 
namespace rn = std::ranges;
namespace rv = rn::views;
 
int main()
{
    auto iss = std::istringstream("0 1 2");
    for (auto i : rn::istream_view<int>(iss)
                  | rv::take(1))
        std::cout << i << '\n';
    auto i = 0;
    iss >> i;
    std::cout << i << std::endl; // flush it in case the assert fails
    assert(i == 1); // FAILS, i == 2
}

It makes it harder to use ranges for things like parsing input, if the rest of the stream is still to be used or we aren’t sure there is any additional element in the stream.

Seems like this was discussed in [range-v3-issue57], and there was no decision what is the right solution.

3. Current behavior is what the standard mandates

Under 23.5.6.5 [counted.iter.nav], the standard defines the behavior of operator++ for counted_iterator as:

Effects: Equivalent to:
++current;
--length;
return *this;

It means that even when length becomes 0, the internal iterator is incremented, thus consuming an additional item from the range, and causing the effects mentioned above for input iterator case or when ++ on the internal iterator is costly (or never returns).

4. Desired behavior

As long as counted_iterator is valid (not equal to default_sentinel), it must never try to access more than n items (when n is the given count). If the range doesn’t have n items, the behavior is kept as is, i.e. it isn’t defined (operator++ might hang forever or access things that shouldn’t be accessed etc.).

5. High-level design of the proposed solution

We propose adding a new iterator type, lazy_counted_iterator. This type behaves similarly to counted_iterator, with changes to its operator definition around 0 count so it doesn’t increment the internal iterator when reaching 0 count.

Additionally, this requires adding lazy_take and views::lazy_counted that uses the new iterator instead of counted_iterator.

6. Design points for discussion

6.1. Consructing with 0 count

Similarly to counted_iterator, lazy_counted_iterator must allow constructing with 0 count. In most design alternatives, this puts the iterator in an inconsistent internal state, as the underlying iterator is expected to be "one step back".

Please note that base() and decrementing are the only operations involving the state of the internal iterator and still legal for counted_iterator constructed with n==0.

The solution accepted in SG9 is to:

1. Cap lazy_counted_iterator to forward_iterator, so decrementing is never supported.

2. Don’t provide base() method, so there is no way to observe the inconsistency and get unexpected behavior in some cases.

This also simplifies the implementation, as there is no requirement to to differentiate between these two states of the underlying iterator. (Implementations might still decide to track it for providing additional diagnostics for violations of the precondition of iterator comparison.)

6.2. Return type of operator++(int)

For non-forward iterators, today counted_iterator::operator++(int) is defined with return current++; and decltype(auto), as such an iterator might return a different type or not return anything at all (e.g. if it’s move only iterator). input_or_output_iterator is weakly_incrementable, not incrementable. As we don’t always increment the iterator, there is no consistent type to return. As a result, for non-forward iterators, we define operator++(int) as returning void. This also prevents us from supporting output_iterator, as one of its requirements is to support *it++.

6.3. Why lazy_take instead of fixing take?

We could have change take to use lazy_counted_iterator when constructed with input (non lazy) range. Besides ABI considerations, we find it wrong if take used to return one type (counted_iterator) and now will start returning a different one, lazy_counted_iterator, as this is source-breaking change. Additionally, as demonstrated above, there are cases where the user wants using lazy_counted_iterator on forward iterators too, but this is something that only the user know and we can’t automatically detect and decide on behalf of them. We can’t change all cases of take to use lazy_counted_iterator, due to the differences in behavior both for lazy input iterators and forward iterators (that are not random access), as described below.

We aren’t happy with the additional burden on teachability, but we believe in most cases users can just use lazy_take and it does The Right Thing. The only point where users must be aware of it is when they use base() method, which we expect to be quite advance usage in general. Users who care about absolute performance, can choose using take when they know it works correctly for their case.

7. Wording

7.1. Wording for lazy_counted_iterator

Under Header <iterator> synopsis [iterator.syn] add the new type:

// [iterators.counted], counted iterators
 template<input_or_output_iterator I> class counted_iterator;             // freestanding

 template<input_iterator I>
   requires see below
   struct iterator_traits<counted_iterator<I>>;            // freestanding

// [iterators.lazy.counted], lazy counted iterators
 template<input_iterator I> class lazy_counted_iterator;             // freestanding

In Iterator adaptors [predef.iterators], after 25.5.7 Counted iterators [iterators.counted] add new section:

Under this section add:

7.1.1. x.1 Class template lazy_counted_iterator [lazy.counted.iterator]

Class template lazy_counted_iterator is an iterator adaptor with the same behavior as the underlying iterator except that it keeps track of the distance to the end of its range. It can be used together with default_sentinel in calls to generic algorithms to operate on a range of N elements starting at a given position without needing to know the end position a priori.

[Example 1:

list<string> s;
// populate the list s with at least 10 strings
vector<string> v;
// copies 10 strings into v:
ranges::copy(lazy_counted_iterator(s.begin(), 10), default_sentinel, back_inserter(v));

Two values i1 and i2 of types lazy_counted_iterator<I1> and lazy_counted_iterator<I2> refer to elements of the same sequence if and only if there exists some integer n such that next(i1.current, i1.count() + n) and next(i2.current, i2.count() + n) refer to the same (possibly past-the-end) element.

namespace std {
  template<input_iterator I>
  class lazy_counted_iterator {
  public:
    using iterator_type = I;
    using value_type = iter_value_t<I>;
    using difference_type = iter_difference_t<I>;
    using iterator_concept  = see below;
    using iterator_category = see below;                      // not always present
    constexpr lazy_counted_iterator() requires default_initializable<I> = default;
    constexpr lazy_counted_iterator(I x, iter_difference_t<I> n);
    template<class I2>
      requires convertible_to<const I2&, I>
        constexpr lazy_counted_iterator(const lazy_counted_iterator<I2>& x);

    template<class I2>
      requires assignable_from<I&, const I2&>
        constexpr lazy_counted_iterator& operator=(const lazy_counted_iterator<I2>& x);

    constexpr iter_difference_t<I> count() const noexcept;
    constexpr decltype(auto) operator*();
    constexpr decltype(auto) operator*() const
      requires dereferenceable<const I>;

    constexpr lazy_counted_iterator& operator++();
    constexpr void operator++(int);
    constexpr lazy_counted_iterator operator++(int)
      requires forward_iterator<I>;

    template<common_with<I> I2>
      friend constexpr iter_difference_t<I2> operator-(
        const lazy_counted_iterator& x, const lazy_counted_iterator<I2>& y);
    friend constexpr iter_difference_t<I> operator-(
      const lazy_counted_iterator& x, default_sentinel_t);
    friend constexpr iter_difference_t<I> operator-(
      default_sentinel_t, const lazy_counted_iterator& y);

    template<common_with<I> I2>
      friend constexpr bool operator==(
        const lazy_counted_iterator& x, const lazy_counted_iterator<I2>& y);
    friend constexpr bool operator==(
      const lazy_counted_iterator& x, default_sentinel_t);

    template<common_with<I> I2>
      friend constexpr strong_ordering operator<=>(
        const lazy_counted_iterator& x, const lazy_counted_iterator<I2>& y);

    friend constexpr iter_rvalue_reference_t<I> iter_move(const lazy_counted_iterator& i)
      noexcept(noexcept(ranges::iter_move(i.current)));
    template<indirectly_swappable<I> I2>
      friend constexpr void iter_swap(const lazy_counted_iterator& x, const lazy_counted_iterator<I2>& y)
        noexcept(noexcept(ranges::iter_swap(x.current, y.current)));

  private:
    I current = I();                    // exposition only
    iter_difference_t<I> length = 0;    // exposition only
  };
}

The member typedef-name iterator_concept denotes

• forward_iterator_tag if Iterator models forward_iterator, and

• input_iterator_tag otherwise.

The member typedef-name iterator_category is defined if and only if the qualified-id iterator_traits<Iterator>::iterator_category is valid and denotes a type. In that case, iterator_category denotes

• forward_iterator_tag if the type iterator_traits<Iterator>::iterator_category models derived_from<forward_iterator_tag>, and

• iterator_traits<Iterator>::iterator_category otherwise.

7.1.2. x.2 Constructors and conversions [lazy.counted.iter.const]

constexpr lazy_counted_iterator(I i, iter_difference_t<I> n);

Preconditions: n >= 0.

Effects: Initializes current with std::move(i) and length with n.

template<class I2>
  requires convertible_to<const I2&, I>
    constexpr lazy_counted_iterator(const lazy_counted_iterator<I2>& x);

Effects: Initializes current with x.current and length with x.length.

template<class I2>
  requires assignable_from<I&, const I2&>
    constexpr lazy_counted_iterator& operator=(const lazy_counted_iterator<I2>& x);

Effects: Assigns x.current to current and x.length to length.

Returns: *this.

7.1.3. x.3 Accessors [lazy.counted.iter.access]

constexpr iter_difference_t<I> count() const noexcept;

Effects: Equivalent to: return length;

7.1.4. x.4 Element access [lazy.counted.iter.elem]

constexpr decltype(auto) operator*();
constexpr decltype(auto) operator*() const
  requires dereferenceable<const I>;

Preconditions: length > 0 is true.

Effects: Equivalent to: return *current;

7.1.5. x.5 Navigation [lazy.counted.iter.nav]

constexpr lazy_counted_iterator& operator++();

Preconditions: length > 0.

Effects: Equivalent to:

if (length > 1) ++current;
--length;
return *this;

constexpr void operator++(int);

Preconditions: length > 0.

Effects: Equivalent to:

++*this;

constexpr lazy_counted_iterator operator++(int)
  requires forward_iterator<I>;

lazy_counted_iterator tmp = *this;
++*this;
return tmp;

template<common_with<I> I2>
  friend constexpr iter_difference_t<I2> operator-(
    const lazy_counted_iterator& x, const lazy_counted_iterator<I2>& y);

Effects: Equivalent to: return y.length - x.length;

friend constexpr iter_difference_t<I> operator-(
  const lazy_counted_iterator& x, default_sentinel_t);

friend constexpr iter_difference_t<I> operator-(
  default_sentinel_t, const lazy_counted_iterator& y);

7.1.6. x.6 Comparisons [lazy.counted.iter.cmp]

template<common_with<I> I2>
  friend constexpr bool operator==(
    const lazy_counted_iterator& x, const lazy_counted_iterator<I2>& y);

Effects: Equivalent to: return x.length == y.length;

friend constexpr bool operator==(
  const lazy_counted_iterator& x, default_sentinel_t);

template<common_with<I> I2>
  friend constexpr strong_ordering operator<=>(
    const lazy_counted_iterator& x, const lazy_counted_iterator<I2>& y);

Effects: Equivalent to: return y.length <=> x.length;

[Note 1: The argument order in the Effects: element is reversed because length counts down, not up. — end note]

7.1.7. x.7 Customizations [lazy.counted.iter.cust]

friend constexpr iter_rvalue_reference_t<I>
  iter_move(const lazy_counted_iterator& i)
    noexcept(noexcept(ranges::iter_move(i.current)));

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

template<indirectly_swappable<I> I2>
  friend constexpr void
    iter_swap(const lazy_counted_iterator& x, const lazy_counted_iterator<I2>& y)
      noexcept(noexcept(ranges::iter_swap(x.current, y.current)));

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

7.2. Wording for views::lazy_counted and lazy_take_view

Under Header <ranges> synopsis [ranges.syn] add the new types:

// [range.counted], counted view
namespace views { inline constexpr unspecified counted = unspecified; }     // freestanding

// [range.lazy.counted], lazy counted view
namespace views { inline constexpr unspecified lazy_counted = unspecified; }     // freestanding

 // [range.take], take view
template<view> class take_view;        // freestanding

template<class T>
  constexpr bool enable_borrowed_range<take_view<T>> =      // freestanding
    enable_borrowed_range<T>;

namespace views { inline constexpr unspecified take = unspecified; }        // freestanding

 // [range.lazy.take], lazy take view
template<view> class lazy_take_view;        // freestanding

template<class T>
  constexpr bool enable_borrowed_range<lazy_take_view<T>> =      // freestanding
    enable_borrowed_range<T>;

namespace views { inline constexpr unspecified lazy_take = unspecified; }        // freestanding

7.3. Wording for views::lazy_counted

In Range adaptors [range.adaptors], after 26.7.18 Counted view [range.counted] add new section:

7.3.1. 26.7.x Lazy counted view [range.lazy.counted]

A lazy counted view presents a view of the elements of the counted range ([iterator.requirements.general]) i + [0, n) for an iterator i and non-negative integer n.

The name views::lazy_counted denotes a customization point object ([customization.point.object]). Let E and F be expressions, let T be decay_t<decltype((E))>, and let D be iter_difference_t<T>. If decltype((F)) does not model convertible_to<D>, views::lazy_counted(E, F) is ill-formed.

[Note 1: This case can result in substitution failure when views::lazy_counted(E, F) appears in the immediate context of a template instantiation. — end note]

Otherwise, views::lazy_counted(E, F) is expression-equivalent to:

• If T models contiguous_iterator, then span(to_address(E), static_cast<size_t>(static_-cast<D>(F))).

• Otherwise, if T models random_access_iterator, then subrange(E, E + static_cast<D>(F)), except that E is evaluated only once.

• Otherwise, subrange(lazy_counted_iterator(E, F), default_sentinel).

7.4. Wording for lazy_take_view

After 26.7.10 Take view [range.take] add new section:

Under this section add:

7.4.1. x.1 Overview [range.lazy.take.overview]

lazy_take_view produces a view of the first N elements from another view, or all the elements if the adapted view contains fewer than N.

The name views::lazy_take 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::lazy_take(E, F) is ill-formed. Otherwise, the expression views::lazy_take(E, F) is expression-equivalent to:

• If T is a specialization of ranges::empty_view ([range.empty.view]), then ((void)F, decay-copy(E)), except that the evaluations of E and F are indeterminately sequenced.

• Otherwise, if T models random_access_range and sized_range and is a specialization of span ([views.span]), basic_string_view ([string.view]), or ranges::subrange ([range.subrange]), then U(ranges::begin(E), ranges::begin(E) + std::min<D>(ranges::distance(E), F)), except that E is evaluated only once, where U is a type determined as follows:

  • if T is a specialization of span, then U is span<typename T::element_type>;

  • otherwise, if T is a specialization of basic_string_view, then U is T;

  • otherwise, T is a specialization of ranges::subrange, and U is ranges::subrange<iterator_t<T>>;

  • otherwise, if T is a specialization of ranges::iota_view ([range.iota.view]) that models random_access_range and sized_range, then ranges::iota_view(*ranges::begin(E), *(ranges::begin(E) + std::min<D>(ranges::distance(E), F))), except that E is evaluated only once.

• Otherwise, if T is a specialization of ranges::repeat_view ([range.repeat.view]):

  • if T models sized_range, then views::repeat(*E.value_, std::min<D>(ranges::distance(E), F)) except that E is evaluated only once;

  • otherwise, views::repeat(*E.value_, static_cast<D>(F)).

• Otherwise, ranges::lazy_take_view(E, F).

[Example 1:

vector<int> is{0,1,2,3,4,5,6,7,8,9};
for (int i : is | views::lazy_take(5))
  cout << i << ' '; // prints 0 1 2 3 4

7.4.2. x.2 Class template lazy_take_view [range.lazy.take.view]

namespace std::ranges {
  template<view V>
  class lazy_take_view : public view_interface<lazy_take_view<V>> {
  private:
    V base_ = V();                                      // exposition only
    range_difference_t<V> count_ = 0;                   // exposition only

    // [range.lazy.take.sentinel], class template lazy_take_view::sentinel
    template<bool> class sentinel;                      // exposition only

  public:
    lazy_take_view() requires default_initializable<V> = default;
    constexpr lazy_take_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() requires (!simple-view<V>) {
      if constexpr (sized_range<V>) {
        if constexpr (random_access_range<V>) {
          return ranges::begin(base_);
        } else {
          auto sz = range_difference_t<V>(size());
          return lazy_counted_iterator(ranges::begin(base_), sz);
        }
      } else if constexpr (sized_sentinel_for<sentinel_t<V>, iterator_t<V>>) {
        auto it = ranges::begin(base_);
        auto sz = std::min(count_, ranges::end(base_) - it);
        return lazy_counted_iterator(std::move(it), sz);
      } else {
        return lazy_counted_iterator(ranges::begin(base_), count_);
      }
    }

    constexpr auto begin() const requires range<const V> {
      if constexpr (sized_range<const V>) {
        if constexpr (random_access_range<const V>) {
          return ranges::begin(base_);
        } else {
          auto sz = range_difference_t<const V>(size());
          return lazy_counted_iterator(ranges::begin(base_), sz);
        }
      } else if constexpr (sized_sentinel_for<sentinel_t<const V>, iterator_t<const V>>) {
        auto it = ranges::begin(base_);
        auto sz = std::min(count_, ranges::end(base_) - it);
        return lazy_counted_iterator(std::move(it), sz);
      } else {
        return lazy_counted_iterator(ranges::begin(base_), count_);
      }
    }

    constexpr auto end() requires (!simple-view<V>) {
      if constexpr (sized_range<V>) {
        if constexpr (random_access_range<V>)
          return ranges::begin(base_) + range_difference_t<V>(size());
        else
          return default_sentinel;
      } else if constexpr (sized_sentinel_for<sentinel_t<V>, iterator_t<V>>) {
        return default_sentinel;
      } else {
        return sentinel<false>{ranges::end(base_)};
      }
    }

    constexpr auto end() const requires range<const V> {
      if constexpr (sized_range<const V>) {
        if constexpr (random_access_range<const V>)
          return ranges::begin(base_) + range_difference_t<const V>(size());
        else
          return default_sentinel;
      } else if constexpr (sized_sentinel_for<sentinel_t<const V>, iterator_t<const V>>) {
        return default_sentinel;
      } else {
        return sentinel<true>{ranges::end(base_)};
      }
    }

    constexpr auto size() requires sized_range<V> {
      auto n = ranges::size(base_);
      return ranges::min(n, static_cast<decltype(n)>(count_));
    }

    constexpr auto size() const requires sized_range<const V> {
      auto n = ranges::size(base_);
      return ranges::min(n, static_cast<decltype(n)>(count_));
    }
  };

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

constexpr lazy_take_view(V base, range_difference_t<V> count);

Preconditions: count >= 0 is true.

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

7.4.3. x.3 Class template lazy_take_view::sentinel [range.lazy.take.sentinel]

namespace std::ranges {
  template<view V>
  template<bool Const>
  class lazy_take_view<V>::sentinel {
  private:
    using Base = maybe-const<Const, V>;                                     // exposition only
    template<bool OtherConst>
      using CI = lazy_counted_iterator<iterator_t<maybe-const<OtherConst, V>>>;  // exposition only
    sentinel_t<Base> end_ = sentinel_t<Base>();                             // exposition only

  public:
    sentinel() = default;
    constexpr explicit sentinel(sentinel_t<Base> end);
    constexpr sentinel(sentinel<!Const> s)
      requires Const && convertible_to<sentinel_t<V>, sentinel_t<Base>>;

    constexpr sentinel_t<Base> base() const;

    friend constexpr bool operator==(const CI<Const>& y, const sentinel& x);

    template<bool OtherConst = !Const>
      requires sentinel_for<sentinel_t<Base>, iterator_t<maybe-const<OtherConst, V>>>
    friend constexpr bool operator==(const CI<OtherConst>& y, const sentinel& x);
  };
}

constexpr explicit sentinel(sentinel_t<Base> end);

Effects: Initializes end_ with end.

constexpr sentinel(sentinel<!Const> s)
  requires Const && convertible_to<sentinel_t<V>, sentinel_t<Base>>;

Effects: Initializes end_ with std::move(s.end_).

constexpr sentinel_t<Base> base() const;

Effects: Equivalent to: return end_;

friend constexpr bool operator==(const CI<Const>& y, const sentinel& x);

template<bool OtherConst = !Const>
  requires sentinel_for<sentinel_t<Base>, iterator_t<maybe-const<OtherConst, V>>>
friend constexpr bool operator==(const CI<OtherConst>& y, const sentinel& x);

Effects: Equivalent to: return y.count() == 0 || y.base() == x.end_;

8. Opens

• basic_const_iterator defines iterator_category only if the underlying iterator models forward_iterator. move_iterator defines it even for input_iterator case. We followed move_iterator example in the wording above, but maybe basic_const_iterator behvaior is what should be used here?

• views::lazy_counted and lazy_take effectively increment the underlying iterator when reaching count for cases like random_access_iterator, as they use tools other than lazy_counted_iterator in such cases (span, returning the iterator directly etc.). We kept it this way as:

  1. These types don’t promise to never increment the underlying iterator for such cases, they only promise it implicitly for the cases that use lazy_counted_iterator.

  2. We don’t think that difference is directly observable (especially as lazy_counted_iterator doesn’t provide base()).

  3. We could’ve define these types to always use lazy_counted_iterator internally, but this limits their usability and means we can’t recommend people to just use lazy_take by default.

• There was a suggestion to combine operator* definitions into a single const overload, but we aren’t sure about this and would like to hear more about it.

9. Implementation experience

The current wording has been implemented over Microsoft STL [MSFT-STL].

There is also a partial implementation, that is based as much as possible directly on the wording of this paper [YB-IMPL].

10. Note about optimization

It’s interesting to note that with any level of optimization enabled (including -Og!), gcc is able to "fix the issue" [CE-OPT] for the filter+take case (but not for input_iterator, of course). It’s maybe even more interesting to see the mentioned optimization is not an optimizer bug, and when the filter will never return another number, it doesn’t change the behavior [CE-OPT2].

11. Acknowledgements

Many thanks to the Israeli NB members for their feedback and support, in particular Inbal Levi, Dvir Yitzchaki, Dan Raviv and Andrei Zissu. Thanks r/cpp Reddit users for their feedback on P2406R0 [reddit-cpp]. Thanks SG9 members for their feedback and guidance.