使迭代器与 std::ranges 函数一起工作

Question

我有以下二维网格迭代器代码。

#include <algorithm>
using std::ranges::count_if;
using std::ranges::for_each;

#include <iostream>
using std::endl;
using std::cout;

#include <iterator>
using std::iterator;
using std::forward_iterator_tag;

#include <memory>
using std::make_shared;
using std::shared_ptr;

#include <stdexcept>
using std::invalid_argument;

#include <vector>
using std::vector;


template <typename T>
class Grid2D;
    
template <typename T>
class Grid2DIterator : public iterator<forward_iterator_tag, T> {
private:
    Grid2D<T> & grid;
    size_t index;

    size_t getX() const
    {
        return index % grid.sizeX();
    }

    size_t getY() const
    {
        return index / grid.sizeX();
    }
public:
    using iterator = Grid2DIterator<T>;

    Grid2DIterator(Grid2D<T> * grid, size_t index)
        : grid(*grid), index(index)
    {}

    Grid2DIterator()
        : Grid2DIterator(nullptr, 0)
    {}

    T & operator*() {
        return grid(getX(), getY());
    }
    
    Grid2DIterator & operator++() {
        ++index;
        return *this;
    }
    
    bool operator==(Grid2DIterator const & other) const {
        return other.grid == grid && index == other.index;
    }
    
    bool operator!=(Grid2DIterator const & other) const {
        return !(*this == other);
    }
};


template <typename T>
class Grid2D {
private:
    vector<vector<T>> grid;
public:
    Grid2D(size_t x, size_t y, T const & init);
    Grid2D(vector<vector<T>> const & grid);
    
    T const & operator()(size_t x, size_t y) const;
    T & operator()(size_t x, size_t y);
    bool operator==(Grid2D<T> const & other) const;
    
    size_t sizeX() const;
    size_t sizeY() const;
    size_t size() const;
    
    Grid2DIterator<T> begin();
    Grid2DIterator<T> end();
};


template <typename T>
Grid2D<T>::Grid2D(size_t x, size_t y, T const & init)
    : grid(y, vector<T>(x, init))
{
    if (x < 1)
        throw invalid_argument("x must be >= 1");
        
    if (y < 1)
        throw invalid_argument("y must be >= 1");
}

template <typename T>
Grid2D<T>::Grid2D(vector<vector<T>> const & grid)
    : grid(grid)
{}

template <typename T>
T const & Grid2D<T>::operator()(size_t x, size_t y) const
{
    return grid.at(y).at(x);
}

template <typename T>
T & Grid2D<T>::operator()(size_t x, size_t y)
{
    return grid.at(y).at(x);
}

template <typename T>
bool Grid2D<T>::operator==(Grid2D<T> const & other) const
{
    return sizeX() == other.sizeX() && sizeY() == other.sizeY();
}

template <typename T>
size_t Grid2D<T>::sizeX() const
{
    return grid[0].size();
}

template <typename T>
size_t Grid2D<T>::sizeY() const
{
    return grid.size();
}

template <typename T>
size_t Grid2D<T>::size() const
{
    return sizeX() * sizeY();
}

template <typename T>
Grid2DIterator<T> Grid2D<T>::begin()
{
    return Grid2DIterator(this, 0);
}

template <typename T>
Grid2DIterator<T> Grid2D<T>::end()
{
    return Grid2DIterator(this, sizeX() * sizeY());
}

int main()
{
    vector<vector<int>> vec = {
        {1, 2, 3, 4, 5},
        {6, 7, 8, 9, 10},
        {11, 12, 13, 14, 15},
        {16, 17, 18, 19, 20},
        {21, 22, 23, 24, 25}
    };
    Grid2D<int> grid(vec);
    for_each(grid, [] (auto const & item) { cout << item << endl; });
    auto cnt = count_if(grid, [] (auto const & i) { return i > 7; });
    cout << "Count: " << cnt << endl;
}

使用 Grid2D::begin() 和 Grid2D::end() 使用 algorithm 中的标准迭代器函数时，它工作正常。但是，当我直接将 Grid2D 实例传递给 std::ranges 中的函数时，我的代码不起作用。由于模板涌出，我收到的错误消息非常神秘，但它是这样的：

$ LANG=C g++ --std=c++20 grid.cpp -o grid
grid.cpp: In function 'int main()':
grid.cpp:167:13: error: no match for call to '(const std::ranges::__for_each_fn) (Grid2D<int>&, main()::<lambda(const auto:19&)>)'
  167 |     for_each(grid, [] (auto const & item) { cout << item << endl; });
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11.1.0/algorithm:64,
                 from grid.cpp:1:
/usr/include/c++/11.1.0/bits/ranges_algo.h:184:7: note: candidate: 'template<class _Iter, class _Sent, class _Proj, class _Fun>  requires (input_iterator<_Iter>) && (sentinel_for<_Sent, _Iter>) && (indirectly_unary_invocable<_Fun, std::projected<_Iter, _Proj> >) constexpr std::ranges::for_each_result<_Iter, _Fun> std::ranges::__for_each_fn::operator()(_Iter, _Sent, _Fun, _Proj) const'
  184 |       operator()(_Iter __first, _Sent __last, _Fun __f, _Proj __proj = {}) const
      |       ^~~~~~~~
/usr/include/c++/11.1.0/bits/ranges_algo.h:184:7: note:   template argument deduction/substitution failed:
grid.cpp:167:13: note:   candidate expects 4 arguments, 2 provided
  167 |     for_each(grid, [] (auto const & item) { cout << item << endl; });
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11.1.0/algorithm:64,
                 from grid.cpp:1:
/usr/include/c++/11.1.0/bits/ranges_algo.h:195:7: note: candidate: 'template<class _Range, class _Proj, class _Fun>  requires (input_range<_Range>) && (indirectly_unary_invocable<_Fun, std::projected<decltype(std::__detail::__ranges_begin((declval<_Container&>)())), _Proj> >) constexpr std::ranges::for_each_result<std::ranges::borrowed_iterator_t<_Range>, _Fun> std::ranges::__for_each_fn::operator()(_Range&&, _Fun, _Proj) const'
  195 |       operator()(_Range&& __r, _Fun __f, _Proj __proj = {}) const
      |       ^~~~~~~~
/usr/include/c++/11.1.0/bits/ranges_algo.h:195:7: note:   template argument deduction/substitution failed:
/usr/include/c++/11.1.0/bits/ranges_algo.h:195:7: note: constraints not satisfied
In file included from /usr/include/c++/11.1.0/string_view:44,
                 from /usr/include/c++/11.1.0/bits/basic_string.h:48,
                 from /usr/include/c++/11.1.0/string:55,
                 from /usr/include/c++/11.1.0/bits/locale_classes.h:40,
                 from /usr/include/c++/11.1.0/bits/ios_base.h:41,
                 from /usr/include/c++/11.1.0/streambuf:41,
                 from /usr/include/c++/11.1.0/bits/streambuf_iterator.h:35,
                 from /usr/include/c++/11.1.0/iterator:66,
                 from /usr/include/c++/11.1.0/bits/ranges_algobase.h:36,
                 from /usr/include/c++/11.1.0/bits/ranges_algo.h:35,
                 from /usr/include/c++/11.1.0/algorithm:64,
                 from grid.cpp:1:
/usr/include/c++/11.1.0/bits/ranges_base.h: In substitution of 'template<class _Range, class _Proj, class _Fun>  requires (input_range<_Range>) && (indirectly_unary_invocable<_Fun, std::projected<decltype(std::__detail::__ranges_begin((declval<_Container&>)())), _Proj> >) constexpr std::ranges::for_each_result<std::ranges::borrowed_iterator_t<_Range>, _Fun> std::ranges::__for_each_fn::operator()(_Range&&, _Fun, _Proj) const [with _Range = Grid2D<int>&; _Proj = std::identity; _Fun = main()::<lambda(const auto:19&)>]':
grid.cpp:167:13:   required from here
/usr/include/c++/11.1.0/bits/ranges_base.h:579:13:   required for the satisfaction of 'range<_Tp>' [with _Tp = Grid2D<int>&]
/usr/include/c++/11.1.0/bits/ranges_base.h:639:13:   required for the satisfaction of 'input_range<_Range>' [with _Range = Grid2D<int>&]
/usr/include/c++/11.1.0/bits/ranges_base.h:579:21:   in requirements with '_Tp& __t' [with _Tp = Grid2D<int>&]
/usr/include/c++/11.1.0/bits/ranges_base.h:581:22: note: the required expression 'std::ranges::__cust::begin(__t)' is invalid
  581 |         ranges::begin(__t);
      |         ~~~~~~~~~~~~~^~~~~
/usr/include/c++/11.1.0/bits/ranges_base.h:582:20: note: the required expression 'std::ranges::__cust::end(__t)' is invalid
  582 |         ranges::end(__t);
      |         ~~~~~~~~~~~^~~~~
cc1plus: note: set '-fconcepts-diagnostics-depth=' to at least 2 for more detail
grid.cpp:168:24: error: no match for call to '(const std::ranges::__count_if_fn) (Grid2D<int>&, main()::<lambda(const auto:20&)>)'
  168 |     auto cnt = count_if(grid, [] (auto const & i) { return i > 7; });
      |                ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11.1.0/algorithm:64,
                 from grid.cpp:1:
/usr/include/c++/11.1.0/bits/ranges_algo.h:400:7: note: candidate: 'template<class _Iter, class _Sent, class _Proj, class _Pred>  requires (input_iterator<_Iter>) && (sentinel_for<_Sent, _Iter>) && (indirect_unary_predicate<_Pred, std::projected<_Iter, _Proj> >) constexpr std::iter_difference_t<_Iter> std::ranges::__count_if_fn::operator()(_Iter, _Sent, _Pred, _Proj) const'
  400 |       operator()(_Iter __first, _Sent __last,
      |       ^~~~~~~~
/usr/include/c++/11.1.0/bits/ranges_algo.h:400:7: note:   template argument deduction/substitution failed:
grid.cpp:168:24: note:   candidate expects 4 arguments, 2 provided
  168 |     auto cnt = count_if(grid, [] (auto const & i) { return i > 7; });
      |                ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11.1.0/algorithm:64,
                 from grid.cpp:1:
/usr/include/c++/11.1.0/bits/ranges_algo.h:415:7: note: candidate: 'template<class _Range, class _Proj, class _Pred>  requires (input_range<_Range>) && (indirect_unary_predicate<_Pred, std::projected<decltype(std::__detail::__ranges_begin((declval<_Container&>)())), _Proj> >) constexpr std::ranges::range_difference_t<_Range> std::ranges::__count_if_fn::operator()(_Range&&, _Pred, _Proj) const'
  415 |       operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
      |       ^~~~~~~~
/usr/include/c++/11.1.0/bits/ranges_algo.h:415:7: note:   template argument deduction/substitution failed:
/usr/include/c++/11.1.0/bits/ranges_algo.h:415:7: note: constraints not satisfied
In file included from /usr/include/c++/11.1.0/string_view:44,
                 from /usr/include/c++/11.1.0/bits/basic_string.h:48,
                 from /usr/include/c++/11.1.0/string:55,
                 from /usr/include/c++/11.1.0/bits/locale_classes.h:40,
                 from /usr/include/c++/11.1.0/bits/ios_base.h:41,
                 from /usr/include/c++/11.1.0/streambuf:41,
                 from /usr/include/c++/11.1.0/bits/streambuf_iterator.h:35,
                 from /usr/include/c++/11.1.0/iterator:66,
                 from /usr/include/c++/11.1.0/bits/ranges_algobase.h:36,
                 from /usr/include/c++/11.1.0/bits/ranges_algo.h:35,
                 from /usr/include/c++/11.1.0/algorithm:64,
                 from grid.cpp:1:
/usr/include/c++/11.1.0/bits/ranges_base.h: In substitution of 'template<class _Range, class _Proj, class _Pred>  requires (input_range<_Range>) && (indirect_unary_predicate<_Pred, std::projected<decltype(std::__detail::__ranges_begin((declval<_Container&>)())), _Proj> >) constexpr std::ranges::range_difference_t<_Range> std::ranges::__count_if_fn::operator()(_Range&&, _Pred, _Proj) const [with _Range = Grid2D<int>&; _Proj = std::identity; _Pred = main()::<lambda(const auto:20&)>]':
grid.cpp:168:24:   required from here
/usr/include/c++/11.1.0/bits/ranges_base.h:579:13:   required for the satisfaction of 'range<_Tp>' [with _Tp = Grid2D<int>&]
/usr/include/c++/11.1.0/bits/ranges_base.h:639:13:   required for the satisfaction of 'input_range<_Range>' [with _Range = Grid2D<int>&]
/usr/include/c++/11.1.0/bits/ranges_base.h:579:21:   in requirements with '_Tp& __t' [with _Tp = Grid2D<int>&]
/usr/include/c++/11.1.0/bits/ranges_base.h:581:22: note: the required expression 'std::ranges::__cust::begin(__t)' is invalid
  581 |         ranges::begin(__t);
      |         ~~~~~~~~~~~~~^~~~~
/usr/include/c++/11.1.0/bits/ranges_base.h:582:20: note: the required expression 'std::ranges::__cust::end(__t)' is invalid
  582 |         ranges::end(__t);
      |         ~~~~~~~~~~~^~~~~

我必须实施/更改什么才能使我的 Grid2D 模板可用于 std::ranges:: 函数？

根据接受的答案解决

#include <algorithm>
using std::ranges::count_if;
using std::ranges::for_each;

#include <iostream>
using std::endl;
using std::cout;

#include <iterator>
using std::forward_iterator_tag;

#include <memory>
using std::make_shared;
using std::shared_ptr;

#include <stdexcept>
using std::invalid_argument;

#include <vector>
using std::vector;


template <typename T>
class Grid2D;
    
template <typename T>
class Grid2DIterator {
private:
    Grid2D<T> * grid;
    size_t index;

    size_t getX() const
    {
        return index % grid->sizeX();
    }

    size_t getY() const
    {
        return index / grid->sizeX();
    }
public:
    using iterator_category = std::forward_iterator_tag;
    using value_type = T;
    using difference_type = T;
    using pointer = T*;
    using reference = T&;

    Grid2DIterator(Grid2D<T> * grid, size_t index)
        : grid(grid), index(index)
    {}

    Grid2DIterator()
        : Grid2DIterator(nullptr, 0)
    {}

    T & operator*() const {
        return (*grid)(getX(), getY());
    }
    
    Grid2DIterator & operator++() {
        ++index;
        return *this;
    }

    Grid2DIterator operator++(int) {
        auto copy(*this);
        operator++();
        return copy;
    }
    
    bool operator==(Grid2DIterator const & other) const {
        return other.grid == grid && index == other.index;
    }
    
    bool operator!=(Grid2DIterator const & other) const {
        return !(*this == other);
    }
};


template <typename T>
class Grid2D {
private:
    vector<vector<T>> grid;
public:
    Grid2D(size_t x, size_t y, T const & init);
    Grid2D(vector<vector<T>> const & grid);
    
    T const & operator()(size_t x, size_t y) const;
    T & operator()(size_t x, size_t y);
    bool operator==(Grid2D<T> const & other) const;
    
    size_t sizeX() const;
    size_t sizeY() const;
    size_t size() const;
    
    Grid2DIterator<T> begin();
    Grid2DIterator<T> end();
};


template <typename T>
Grid2D<T>::Grid2D(size_t x, size_t y, T const & init)
    : grid(y, vector<T>(x, init))
{
    if (x < 1)
        throw invalid_argument("x must be >= 1");
        
    if (y < 1)
        throw invalid_argument("y must be >= 1");
}

template <typename T>
Grid2D<T>::Grid2D(vector<vector<T>> const & grid)
    : grid(grid)
{}

template <typename T>
T const & Grid2D<T>::operator()(size_t x, size_t y) const
{
    return grid.at(y).at(x);
}

template <typename T>
T & Grid2D<T>::operator()(size_t x, size_t y)
{
    return grid.at(y).at(x);
}

template <typename T>
bool Grid2D<T>::operator==(Grid2D<T> const & other) const
{
    return sizeX() == other.sizeX() && sizeY() == other.sizeY();
}

template <typename T>
size_t Grid2D<T>::sizeX() const
{
    return grid[0].size();
}

template <typename T>
size_t Grid2D<T>::sizeY() const
{
    return grid.size();
}

template <typename T>
size_t Grid2D<T>::size() const
{
    return sizeX() * sizeY();
}

template <typename T>
Grid2DIterator<T> Grid2D<T>::begin()
{
    return Grid2DIterator(this, 0);
}

template <typename T>
Grid2DIterator<T> Grid2D<T>::end()
{
    return Grid2DIterator(this, size());
}

int main()
{
    vector<vector<int>> vec = {
        {1, 2, 3, 4, 5},
        {6, 7, 8, 9, 10},
        {11, 12, 13, 14, 15},
        {16, 17, 18, 19, 20},
        {21, 22, 23, 24, 25}
    };
    Grid2D<int> grid(vec);
    for_each(grid, [] (auto const & item) { cout << item << endl; });
    auto cnt = count_if(grid, [] (auto const & i) { return i > 7; });
    cout << "Count: " << cnt << endl;
}

Answer 1

首先，迭代器需要是 move-assignable 而您的迭代器不是引用成员。使用指针或 std::reference_wrapper 而不是引用，此问题将消失。

那么你的迭代器缺少一个 post-increment 运算符。

此外，operator* 应标记为 const。

我认为这应该解决概念的所有明确句法要求。我还没有检查是否满足 semantic 要求。如果不是，则程序具有未定义的行为。

此外，std::iterator 已弃用。如果您使用 -Werror 进行编译，这很可能会使其失败。而是添加它隐式显式声明的几个成员。

使迭代器与 std::ranges 函数一起工作

Make iterator work with std::ranges functions

c++

iterator

c++20

std-ranges