Reputation: 3361
I have the following code for a 2D-grid iterator.
#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;
}
It works fine when using the standard iterator functions from algorithm
using Grid2D::begin()
and Grid2D::end()
.
However, my code does not work when I directly pass a Grid2D
instance to the functions from std::ranges
. The error message I get is very cryptic due to template spewing, but here it goes:
$ 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);
| ~~~~~~~~~~~^~~~~
What do I have to implement / change to make my Grid2D
template be usable with the std::ranges::
functions?
Solution as per the accepted answer
#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;
}
Upvotes: 0
Views: 556
Reputation: 76628
First, the iterator needs to be move-assignable which your iterator is not due to the reference member. Instead of a reference use a pointer or std::reference_wrapper
and this issue will disappear.
Then your iterator is missing a post-increment operator.
Also, operator*
should be marked const
.
I think this should fix all the explicit syntactic requirements of the concepts. I haven't checked whether the semantic requirements are fulfilled. If they are not, the program has undefined behavior.
Also, std::iterator
is deprecated. If you compile with -Werror
this is likely to make it fail. Instead add the few members it implicitly declares explicitly.
Upvotes: 2