Map square coordinates in matrix to flat array indices without hurting performance

Question

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:

enter image description here

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

Matrix m = ...;
std::cout<<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<<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& 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<<"Pos: "<<index<<" side: "<<(int)side<<" subpos: "<<position<<'\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& sq) :
 pos(pos), parent(sq)
 {}
 int pos;
 const Subsquare& parent;
 int operator*() {
 return parent[pos];
 }
 bool operator!=(const iterator& 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& 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.

• Incomputable: When you'll start going down wide matrices you'll get cache misses. How many times will you traverse like that? Is transposing and saving a copy worth it? Does the platform store matrices in row major order?
• Tomáš Zato: The matrix is just nested std::vector. Every square is only traversed once. At worst case, all possible squares in matrix are traversed. I'm not sure how to answer the rest of the questions.
• Incomputable: Transpose is when you swap columns and rows. So seems like no, since you will traverse only once. The last one is just precaution, may be you wanted to deploy it on some architecture where array are allocated in different order. It looks good already, if I got everything right. Also storing matrices as vector of vectors is not a good idea, if they are not resized.
• Loki Astari: @TomášZato Incomputable is trying to describe another form of optimization. He wants to double the memory you use to try and reduce accesses speed.
• Loki Astari: @TomášZato: What makes you think there is a performance issue.

Answer 1

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& operator[] (int index) {

And maybe a version that validates its parameters.

int at(int index) const {
int& 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.