What am I missing in my custom std::ranges iterator?

Question

I'd like to provide a view for a customer data structure, with it's own iterator. I wrote a small program to test it out, shown below. It I uncomment begin(), then it works. But if I use DummyIter, then I get a compile error.

In my full program, I've implemented a full iterator but for simplicity, I narrowed it down to the necessary functions here.

#include <iostream>
#include <ranges>
#include <vector>

template<class T>
struct DummyIter
{
  using iterator_category = std::random_access_iterator_tag;
  using value_type = T;
  using difference_type = std::ptrdiff_t;

  DummyIter() = default;

  auto operator*() const { T t; return t; }

  auto& operator++() { return *this; }

  auto operator++(int val) { DummyIter tmp = *this; ++*this; return tmp; }

  auto operator==(const DummyIter& iter) const { return true; }
};

template<class V>
struct DummyView : std::ranges::view_interface<DummyView<V>>
{
  //auto begin() const { return std::ranges::begin(v); }
  auto begin() const { return DummyIter<int>(); }

  auto end() const { return std::ranges::end(v); }

  V v;
};

int main() {
  auto view = DummyView<std::vector<int>>();
  view | std::views::filter([](auto i) { return i > 0; });
}

I'm using GCC 11.1.0. What am I missing in my iterator for it to be ranges compliant?

error: no match for 'operator|' (operand types are 'DummyView<std::vector<int> >' and 'std::ranges::views::__adaptor::_Partial<std::ranges::views::_Filter, main()::<lambda(auto:15)> >')
   37 |   view | std::views::filter([](auto i) { return i > 0; });
      |   ~~~~ ^ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
      |   |                        |
      |   |                        std::ranges::views::__adaptor::_Partial<std::ranges::views::_Filter, main()::<lambda(auto:15)> >
      |   DummyView<std::vector<int> >

Thanks for providing a [mre] and using features of C++20 that my Visual Studio doesn't even understand. — Thomas Weller, Mar 18 '22 at 09:25
You certainly aren't fulfilling all the requirements of `random_access_iterator_tag` — Alan Birtles, Mar 18 '22 at 09:46
Compilers support for C++20 is still quite poor, so please specify compiler you are using. — Marek R, Mar 18 '22 at 10:21
@Bob__: Probably not, since there's nothing to "add". In fact, @dromodel - why not use `auto operator++(int val) { return *this; }`, like with the other incrementation operator? — einpoklum, Mar 18 '22 at 11:30

score 17 · Accepted Answer · answered Mar 18 '22 at 15:31

The way to check this kind of thing for ranges is:

Verify that your iterator is an input_iterator.
Verify that your sentinel is a sentinel_for your iterator.

Those are the checks that will tell you what functionality you're missing.

In this case, that's:

using I = DummyIter<int>;
using S = std::vector<int>::const_iterator;

static_assert(std::input_iterator<I>);   // ok
static_assert(std::sentinel_for<S, I>);  // error

And the issue there is that S isn't a sentinel_for<I> because it's not equality comparable. You need to know when the iteration stops, and you don't have that operator - your DummyIter<T> is comparable to another DummyIter<T>, but not to what you're returning from end().

So you either need to add another operator== to DummyIter<T>, or have DummyView<V>::end() return some kind of DummySentinel<V> that is comparable to DummyIter<T>. It depends on the real problem which is the better approach, there are examples of both in the standard library.

康桓瑋 · Answer 2 · 2022-03-18T11:30:34.133

Because your DummyView does not meet the concept of range, to be precise, the return type of view.end() cannot be used as a sentinel for view.begin(), because there is no suitable operator==() for DummyIter to compare with std::vector<int>::const_iterator, which means that there is no way to know if the iterator has reached the end of the range.

The workaround is just to add bool operator==(std::vector<int>::const_iterator) const to your DummyIter

template<class T>
struct DummyIter {
  // ...
  bool operator==(std::vector<T>::const_iterator) const;
};

Demo

Marek R · Answer 3 · 2022-03-18T11:01:52.353

3

This can't work since return types of your begin and end do not match. So basically those iterators can't be compared to each other.

Prove:

here is your code with extra static assert
here is dummy fix which compiles since now same return type is used for begin and end

Minimum requirement is that result of begin() and end() are comparable. Different types for begin() and end() are useful when size of range is not known. Here is nice explanation of sentinel (mentioned in comment).

edited Mar 18 '22 at 11:01

answered Mar 18 '22 at 10:39

Marek R

32,568
6
55
140

2

Doesn't C++20 support ranges having sentinels with types different from the one returned by `begin` (once a proper comparator has been provided)? – Bob__ Mar 18 '22 at 10:43
1

@Bob__ yes, they do, but you do need to provide ability to compare iterator with sentinel, which OP code failed to do. – Revolver_Ocelot Mar 18 '22 at 10:44
@Bob__ actually, it's c++17. – Passer By Mar 18 '22 at 10:52
If he planed to implemented sentinel then he completely lost track how to do it. – Marek R Mar 18 '22 at 10:59
There is no requirement that the return types of `begin` and `end` match. – Barry Mar 18 '22 at 15:32
bu they have to be comparable (equal or not equal), what did I mentioned in last edit. – Marek R Mar 18 '22 at 15:41
3

@MarekR The first half of your answer is still wrong. – Barry Mar 18 '22 at 16:00

What am I missing in my custom std::ranges iterator?

3 Answers3

Linked