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");
    }
}

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';
    }
}