Using std::ranges algorithms with custom containers and iterators

Question

I have the following simplified code representing a range of integers that I want to use with various std algorithms. I am trying to update my code to use C++20's ranges versions of the algorithms so I can delete all of the begin() and end() calls. In the below code, std::any_of works with my container and iterator, but std::ranges::any_of does not.

#include <iostream>
#include <algorithm>

class Number_Iterator {
    public:
        using iterator_category = std::input_iterator_tag;
        using value_type = int;
        using difference_type = int;
        using pointer = int*;
        using reference = int&;

        Number_Iterator(int start) noexcept : value(start) {}
        Number_Iterator& operator++() noexcept { ++value; return *this; }
        bool operator==(const Number_Iterator& other) const noexcept = default;
        int operator*() const noexcept { return value; }

    private:
        int value;
};

class Numbers {
    public:
        Numbers(int begin, int end) noexcept : begin_value(begin), end_value(end) {}
        Number_Iterator begin() const noexcept { return {begin_value}; }
        Number_Iterator end() const noexcept { return {end_value}; }

    private:
        int begin_value;
        int end_value;
};

int main() {
    const auto set = Numbers(1, 10);
    const auto multiple_of_three = [](const auto n) { return n % 3 == 0; };

    // Compiles and runs correctly
    if(std::any_of(set.begin(), set.end(), multiple_of_three)) {
        std::cout << "Contains multiple of three.\n";
    }

    // Does not compile
    if(std::ranges::any_of(set, multiple_of_three)) {
        std::cout << "Contains multiple of three.\n";
    }

    return 0;
}

When I try to compile the above code, I get the following error messages from Visual Studio 2019 (16.11.15) with the flag /std:c++20:

Source.cpp(42,21): error C2672: 'operator __surrogate_func': no matching overloaded function found
Source.cpp(42,7): error C7602: 'std::ranges::_Any_of_fn::operator ()': the associated constraints are not satisfied
1>C:\Program Files (x86)\Microsoft Visual Studio\2019\Community\VC\Tools\MSVC\14.29.30133\include\algorithm(1191): message : see declaration of 'std::ranges::_Any_of_fn::operator ()'

I have tried looking at the std::ranges::_Any_of_fn::operator() declaration, but I find myself more confused by that.

What am I missing to get the std::ranges algorithms to work with my container?

For the curious, what I'm actually iterating over are squares on a chess board, but those are represented by integers, so the difference from the above code isn't so great.

Ted Lyngmo · Accepted Answer · 2022-06-12 09:25:36Z

5

To use your range with any_of it must satisfy the input_range concept:

template< class T >
  concept input_range =
    ranges::range<T> && std::input_iterator<ranges::iterator_t<T>>;

Then via the input_iterator concept:

template<class I>
  concept input_iterator =
    std::input_or_output_iterator<I> &&
    std::indirectly_readable<I> &&
    requires { typename /*ITER_CONCEPT*/<I>; } &&
    std::derived_from</*ITER_CONCEPT*/<I>, std::input_iterator_tag>;

and via the input_or_output_iterator concept

template <class I>
concept input_or_output_iterator =
  requires(I i) {
    { *i } -> /*can-reference*/;
  } &&
  std::weakly_incrementable<I>;

you land in the weakly_incrementable concept:

template<class I>
  concept weakly_incrementable =
    std::movable<I> &&
    requires(I i) {
      typename std::iter_difference_t<I>;
      requires /*is-signed-integer-like*/<std::iter_difference_t<I>>;
      { ++i } -> std::same_as<I&>;   // pre-increment
      i++;                           // post-increment
    };

in which you see that the iterator must have both the pre-increment and post-increment versions of operator++.

The iterator must also be default constructible because std::ranges::end creates a sentinel:

template< class T >
    requires /* ... */
constexpr std::sentinel_for<ranges::iterator_t<T>> auto end( T&& t );

And sentinel_for

template<class S, class I>
  concept sentinel_for =
    std::semiregular<S> &&
    std::input_or_output_iterator<I> &&
    __WeaklyEqualityComparableWith<S, I>;

requires it to satisfy semiregular:

template <class T>
concept semiregular = std::copyable<T> && std::default_initializable<T>;

But without being default constructible, this substitution will fail:

template < class T >
concept default_initializable = std::constructible_from<T> && requires { T{}; } && ...

edited Jun 12, 2022 at 9:25

answered Jun 12, 2022 at 8:15

Ted Lyngmo

124k7 gold badges93 silver badges155 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

Mark H Over a year ago

Thanks for diving through the iterator concepts. Where does the requirement for a default constructor come from?

Ted Lyngmo Over a year ago

@MarkH Good question. :-) I had to dig a lot to find it. Updated the answer.

Mark H Over a year ago

Interesting. Thanks for digging. Now I'm wondering why a sentinel iterator should be default constructible when I would think all end() iterators should be associated with some container, and thus require a unique value. But that's beyond the scope of the question.

Ted Lyngmo Over a year ago

@MarkH I wondered the same thing. It's jungle of requirements and it's easy to stray when digging around. :)

Ted Lyngmo Over a year ago

@康桓瑋 Indeed. I wonder how it could be used in this case though. If one does auto e = std::ranges::end(the_set_in_the_question); and then default construct a sentinel: decltype(e) ed;, then e == ed will not be true.

|

Mark H · Accepted Answer · 2022-06-12 08:07:34Z

2

Apparently, the std::ranges algorithms require two more methods in the iterator: a default constructor and a post-increment operator (return value optional). Adding these methods allows the code to compile and run correctly:

Number_Iterator() noexcept : value(-1) {}
void operator++(int) noexcept { ++value; }

answered Jun 12, 2022 at 8:07

Mark H

6174 silver badges13 bronze badges

Collectives™ on Stack Overflow

Using std::ranges algorithms with custom containers and iterators

2 Answers 2

7 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

7 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related