Converting a get-by-index function into an iterator for use with STL algorithms

Question

This is a solution to Advent of Code 2016, Day 8. The tricky part of this problem is that you have to be able to rotate both the rows and columns of a two-dimensional array. Rotating a row is easy using std::rotate, but rotating a column seems much harder.

My basic approach was to write a "getter function" such that get(i) returns the ith element of the (row/column) currently being rotated; and then I wrote a very straightforward "rotate by 1 in a loop" function in terms of get(i). That implementation is marked // DUMB below. (Although, given this particular problem's range of input, "it's not dumb if it works.")

But I'd really like to use std::rotate if possible, both for speed ("rotate by 1 in a loop" is O(byxn), when it should be just O(n)) and for elegance. So I wrote a wrapper that takes the "getter" function and turns it into an iterator. This is marked // CLEVER below.

• Does the STL or Boost already provide some way to turn an indexed "getter" function into a random-access iterator?
• I turn my array into a "getter" function and then turn the getter function into an iterator; seems a bit roundabout. Does the STL or Boost already provide a straightforward way to construct a "strided" iterator on an array?
• I see that std::iterator is deprecated in C++17. In C++17, would my code Just Work if I stopped inheriting from std::iterator? or what's the best practice for writing iterators these days?

---

#include <assert.h>
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <iterator>
#include <regex>
#include <string>
const int HEIGHT = 6;
const int WIDTH = 50;
bool grid[HEIGHT][WIDTH];
#if 1
template<typename Getter>
auto make_iterator(const Getter& get, int i) // CLEVER
{
 using T = std::remove_reference_t<decltype(get(i))>;
 struct It : std::iterator<std::forward_iterator_tag, T> {
 const Getter *get_;
 int i_;
 It(const Getter& g, int i) : get_(&g), i_(i) {}
 It& operator++() { ++i_; return *this; }
 It operator++(int) { It temp = *this; ++i_; return temp; }
 decltype(auto) operator*() const { return (*get_)(i_); }
 bool operator==(const It& rhs) const { return i_ == rhs.i_; }
 bool operator!=(const It& rhs) const { return i_ != rhs.i_; }
 };
 return It(get, i);
}
template<typename Getter>
void rotate_right(int by, int n, const Getter& get)
{
 std::rotate(make_iterator(get, 0), make_iterator(get, (n - by) % n), make_iterator(get, n));
}
#else
template<typename Getter>
void rotate_right(int by, int n, const Getter& get)
{
 while (by != 0) { // DUMB
 bool temp = get(n-1);
 for (int i = n-1; i >= 0; --i) {
 get(i+1) = get(i);
 }
 get(0) = temp;
 --by;
 }
}
#endif
void process_input(std::string line)
{
 std::smatch m;
 if (std::regex_match(line, m, std::regex("rect (.*)x(.*)"))) {
 int a_wide = std::stoi(m.str(1));
 int b_tall = std::stoi(m.str(2));
 for (int i=0; i < a_wide; ++i) {
 for (int j=0; j < b_tall; ++j) {
 grid[j][i] = true;
 }
 }
 } else if (std::regex_match(line, m, std::regex("rotate row y=(.*) by (.*)"))) {
 int row = std::stoi(m.str(1));
 int by = std::stoi(m.str(2)) % WIDTH;
 rotate_right(by, WIDTH, [&](int i) -> decltype(auto) { return grid[row][i]; });
 } else if (std::regex_match(line, m, std::regex("rotate column x=(.*) by (.*)"))) {
 int column = std::stoi(m.str(1));
 int by = std::stoi(m.str(2)) % HEIGHT;
 rotate_right(by, HEIGHT, [&](int i) -> decltype(auto) { return grid[i][column]; });
 } else {
 assert(false);
 }
}
int main()
{
 std::string buf;
 while (std::getline(std::cin, buf)) {
 process_input(buf);
 }
 for (int i=0; i < HEIGHT; ++i) {
 for (int j=0; j < WIDTH; ++j) {
 printf("%c", grid[i][j] ? '#' : '.');
 }
 printf("\n");
 }
}

• Incomputable: Is the input to create iterator only matrix? If yes, then you could make (non portable) assumption that they are laid out in memory row wise and always jump at constant distance.
• Quuxplusone: @Incomputable: Yes, that assumption would be reasonable in my case; that's what I was getting at with the phrase "strided iterator". But does such a thing exist? and/or can it be implemented in less code than what I've got here?
• Incomputable: I couldn't find anything in the boost. I believe it will have the same code size, but it is certainly possible to remove that getter step.
• user33306: Wouldn't it make more sense to use a vector<bool> or the c++11 array class? Then you've got iterators and indexes that you can use
• Quuxplusone: @tinstaafl: As of C++14, the core language provides built-in arrays that are about as full-featured as the library ones. ;) E.g. std::begin(a) and std::size(a) work for core language arrays T[N] just the same as they do for std::array<T,N>. Anyway, I'm not sure what specific change you're proposing: is it just to change the one line bool grid[HEIGHT][WIDTH]; to std::array<std::array<bool, WIDTH>, HEIGHT> grid; and leave the rest untouched?

Answer 1

Code Review

It's unfortunate that this needs to support C++17, for in C++20 we have standard Range views that permit this kind of transformation much more easily. Or we could use the Range algorithms that accept a projection argument.

The macros WIDTH and HEIGHT and the global variable grid aren't needed for the iterator class or the rotate_right() function - prefer to declare those after the more general utility that you might later want to extract to a header file.

Instead of including <stdio.h> and referencing printf, prefer <cstdio> and std::printf - or, better, just stick to <iostream> only.

We could be more cautious with our regexes, so that we only ever apply std::stoi to digit sequences. In any case, we should verify that the resulting numbers are within the valid range for our grid.

You're right that inheriting from std::iterator<> is no longer recommended. Just define the member types used by std::iterator_traits<> directly in your iterator class:

 struct It
 {
 using iterator_category = std::forward_iterator_tag;
 using value_type = T;
 using pointer = T*;
 using difference_type = std::ptrdiff_t;
 using reference = T&;

I extracted these functions so I could test without an input file:

static void make_rect(int a_wide, int b_tall)
{
 for (int i=0; i < a_wide; ++i) {
 for (int j=0; j < b_tall; ++j) {
 grid[j][i] = true;
 }
 }
}
static void shift_column(int column, int by)
{
 rotate_right(by, HEIGHT, [&](int i) -> auto& { return grid[i][column]; });
}
static void shift_row(int row, int by)
{
 rotate_right(by, WIDTH, [&](int i) -> auto& { return grid[row][i]; });
}

---

I found I was able to break the program using

 make_rect(10, 4);
 shift_column(2, 9);
 shift_row(2, -20);

The shift_column by more than the height of the grid causes the computation (n - by) % n to yield a negative result, which the code doesn't seem to expect. I wrote a small helper to avoid that:

static int positive_modulo(int dividend, int divisor)
{
 auto remainder = dividend % divisor;
 return remainder > 0 ? remainder : remainder + divisor;
}

---

Using Ranges

If I were writing this code today, I would be looking to lean on standard Ranges views and algorithms. Then we can use a single rotate_right() function for both rows and columns, but passing a row-view or a column-view rather than a function:

#include <algorithm>
#include <iterator>
#include <ranges>
#include <utility>
template<std::ranges::forward_range R>
 requires std::permutable<std::ranges::iterator_t<R>>
auto rotate_right(R&& r, std::size_t by)
{
 auto const len = std::ranges::distance(r);
 auto new_mid = std::ranges::begin(r);
 by %= len;
 if (by != 0) {
 std::advance(new_mid, len - by);
 }
 return std::ranges::rotate(std::forward<R>(r), new_mid);
}
static void shift_column(std::size_t column, std::size_t by)
{
 auto select_element = [column](auto& row) -> auto& { return row[column]; };
 rotate_right(grid | std::views::transform(select_element), by);
}
static void shift_row(std::size_t row, std::size_t by)
{
 rotate_right(grid[row], by);
}

The Ranges version of the function to fill a rectangle is also simplified, with no arithmetic necessary:

static void fill_rect(int a_wide, int b_tall)
{
 auto rows = grid | std::views::take(b_tall);
 for (auto& r: rows) {
 std::ranges::fill(r | std::views::take(a_wide), true);
 }
}

And the Ranges demo function:

#include <iostream>
int main()
{
 fill_rect(10, 4);
 shift_column(2, 9);
 shift_row(2, 70);
 shift_column(27, 2);
 for (auto& row: grid) {
 *std::ranges::copy(row | std::views::transform([](bool b){ return ".#"[b]; }),
 std::ostream_iterator<char>{std::cout}).out = '\n';
 }
}