Map square coordinates in matrix to flat array indices without hurting performance I'm more like playing and the problem I'm going to demonstrate is a learning task, so to speak, not something I really need to solve. 

Imagine having a matrix of data. You chose square in it and would like to access each point on square perimeter by 1D index, like this:



This image represents instance of some Matrix class, such as:

Matrix m = ...;
std::cout&lt;&lt;m.data[0][1]; // "foo", first row, second column


Now I would like to create wrapping class Subsquare which, if represents the yellow square on the image works like this:

// Params: x, y, size, parent matrix
Subsquare sqr(1, 1, 6, m); // create from matrix

std::cout&lt;&lt;sqr[4]; //"4", as per image


I did try to make the class, but I got lost when trying to invent the algorithm to perform the mapping. I'd also like the algorithm to be optimal.

This is my attempt:

/**
 * @brief The Subsquare class allows you to iterate over square section of matrix
 */
class Subsquare {
public:
    /**
     * @brief Subsquare
     * @param x coordinate, 0-indexed
     * @param y coordinate, 0-indexed
     * @param length size of the square, it will span length items with it's side
     * @param parent matrix that contains the data
     */
    Subsquare(const int x, const int y, const int length, const Matrix&amp; parent)
        : x(x)
        , y(y)
        , length(length)
        // the trick is that we only can count square corners once
        , items(length*4-4)
        , m(parent)
    {}
    /**
     * @brief The Side enum is helper enum for determining from which side are we picking index
     *
     */
    enum Side:byte {
        TOP,
        RIGHT,
        BOTTOM,
        LEFT
    };
    /**
     * @brief operator [] provides access to nth item in square, starting
     *                    at top left corner and going clockwise
     * @param index the index, 0-indexed
     * @return
     */
    int operator[] (int index) const {
        const byte side = index/(length-1);
        const int position = index%(length-1);
        //std::cerr&lt;&lt;"Pos: "&lt;&lt;index&lt;&lt;" side: "&lt;&lt;(int)side&lt;&lt;" subpos: "&lt;&lt;position&lt;&lt;'\n';
        switch (side) {
        case TOP:
            return m.data[y][x+position];
            break;
        case RIGHT:
            return m.data[y+position][x+length-1];
            break;
        case BOTTOM:
            return m.data[y+length-1][x+length-1-position];
            break;
        case LEFT:
            return m.data[y+length-1-position][x];
            break;
        }
    }
    /**
     * @brief Allows iterating over the square using for(int val: square) {}
     */
    class iterator {
    public:
        iterator(const int pos, const Subsquare&amp; sq) :
            pos(pos), parent(sq)
        {}
        int pos;
        const Subsquare&amp; parent;
        int operator*() {
            return parent[pos];
        }
        bool operator!=(const iterator&amp; other) {
            return other.pos!=pos;
        }
        void operator++() {
            ++pos;
        }
    };
    /// Iterator helper methods
    iterator begin() const {
        return iterator(0, *this);
    }
    iterator end() const {
        return iterator(items, *this);
    }

    const Matrix&amp; m;
    const int x;
    const int y;
    const int length;
    const int items;
};


Now this works correctly, it seems:

1 2 3
4 5 6
7 8 9
1, 2, 3, 6, 9, 8, 7, 4,


However I'm quite concerned about performance. Is there a way to make the algorithm faster while keeping it comfortable to use? The task I'm working on involves searching squares in very big matrix and the algorithm must be fast.
I see nothing wrong with the concept.
Code looks reasonable to me.

Iterator

You implementation of iterator does not meet the requirements for a standard iterator so you may have issues using it with some of the standard algorithms.

See: http://en.cppreference.com/w/cpp/iterator/iterator

You are missing some standard types in the iterator:

Member type Definition
iterator_category   Category
value_type  T
difference_type Distance
pointer Pointer
reference   Reference


Currently your iterator can only be considered an Input Iterator but given its simplicity it really should be Random Access Iterator.

http://en.cppreference.com/w/cpp/iterator/iterator_tags

Which means it needs to support the following:

http://en.cppreference.com/w/cpp/concept/RandomAccessIterator

Accesses

Currently you only have const accesses:

int operator[] (int index) const {


Normally you would expect to see non const access as well

int&amp; operator[] (int index) {


And maybe a version that validates its parameters.

int  at(int index) const {
int&amp; at(int index) {


Also since you currently don't allow write access through operator[] your iterator is actually const_iterator. There are several version of iterator that you can implement.

iterator       begin();
const_iterator begin() const;
const_iterator cbegin() const;


Might also be worth adding the reverse versions of the iterator but that might also be overkill.