Transforming elements of std containers from other std containers Problem

In this HackerRank problem we are asked to rotate the elements of a matrix in the following way:


Example Input and Output

First and second entry specify the size of the matrix and third entry how many times it has to be rotated. As an example, the following input:

4 4 2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16


would produce the following output:

3 4 8 12
2 11 10 16
1 7 6 15
5 9 13 14


Solution

My idea was to rotate these rings. 

#include &lt;vector&gt;
#include &lt;iostream&gt;
#include &lt;algorithm&gt;

using Matrix = std::vector&lt;std::vector&lt;int&gt;&gt;;

void rotate_mat (Matrix &amp;mat, int r){
    auto m = mat.size(); // Number of rows
    auto n = mat[0].size(); // Number of columns
    auto n_rings = std::min(m,n)/2; // Number of rings
    for(auto ring_i=0; ring_i&lt;n_rings; ++ring_i){
        // The elements of the ring are stored sequentially 
        // in v_ring so it can be rotated with std::rotate 
        std::vector&lt;int&gt;  v_ring;
        // v_ring_ptr points to the original places in the matrix,
        // so the rotation of v_ring can be assigned back to the matrix
        std::vector&lt;int*&gt; v_ring_ptr;
        // Top side of the ring
        for(auto j=ring_i; j&lt;=(n-1)-ring_i; ++j) {
            v_ring.push_back(mat[ring_i][j]);
            v_ring_ptr.push_back(&amp;mat[ring_i][j]);
        }
        // Right side of the ring
        for(auto i=ring_i+1; i&lt;=(m-1)-ring_i; ++i) {
            v_ring.push_back(mat[i][(n-1)-ring_i]);
            v_ring_ptr.push_back(&amp;mat[i][(n-1)-ring_i]);
        }
        // Bottom size of the ring
        for(auto j=(n-1)-ring_i-1; j&gt;ring_i; --j) {
            v_ring.push_back(mat[(m-1)-ring_i][j]);
            v_ring_ptr.push_back(&amp;mat[(m-1)-ring_i][j]);
        }
        // Left size of the ring
        for(auto i=(m-1)-ring_i; i&gt;ring_i; --i) {
            v_ring.push_back(mat[i][ring_i]);
            v_ring_ptr.push_back(&amp;mat[i][ring_i]);
        }

        std::rotate(v_ring.begin(),v_ring.begin()+r%v_ring.size(),v_ring.end());
        // Update the rotated values in the original matrix
        for (auto i=0; i&lt;v_ring.size(); ++i){
            *v_ring_ptr[i] = v_ring[i];
        }
    }
};

Matrix read_matrix(int m, int n) {
    Matrix mat;
    mat.reserve(m);
    for(auto i=0; i&lt;m; ++i) {
        mat.push_back(std::vector&lt;int&gt;{});
        mat[i].reserve(n);
        for(auto j=0; j&lt;n; ++j) {
            int x; std::cin &gt;&gt; x;
            mat[i].push_back(x);
        }
    }
    return mat;
};

void print_matrix(Matrix &amp;mat){
    for (auto&amp; i : mat){
        for (auto&amp; j : i) {
            std::cout &lt;&lt; j &lt;&lt; " ";
        }
        std::cout &lt;&lt; "\n";
    }
};

int main() {
    int m,n; std::cin &gt;&gt; m &gt;&gt; n;
    int r; std::cin &gt;&gt; r;

    auto mat = read_matrix(m,n);
    rotate_mat(mat,r);
    print_matrix(mat);

    return 0;
}


Questions

My main problem is that I would like to avoid having the v_ring copy and this part:

for (auto i=0; i&lt;v_ring.size(); ++i){
    *v_ring_ptr[i] = v_ring[i];
}


Is there a way to store references to the content of the original matrix so the transformation in the constructed rings would automatically be reflected? I tried with std::reference_wrapper. It almost works with that, I can modify the elements in the ring for example with ++ operator, but I cannot make assigments, nor std::rotate has any effect on them.

Any ideas? I'm also interested in any other approach that could come to your mind! I thought this way was easy to express in code
Some things to note :


As you said there are std::min(m,n)/2; rings. 
the ring R(r, p) has 2*(r+p-2) elements.
the top left of the ring has always coordinates (x,x). This is visible in your code :) j = ring_i; v_ring.push_back(mat[ring_i][j]);
Your code is using a relatively efficient amount of memory for the in-place transformation, and running in O(m*n) time, which is the best possible.
A performance improvement will be to use a single vector for the data in the matrix such that m(x,y) = m.data[x * cols + y] 


Can we do it differently ?

Given the local coordinates system where (0, 0) is the top left of the ring



A coordinate (i,j), 0&lt;=i&lt;w, 0&lt;=j&lt;h, j == 0 || i == 0 on a side of a ring, can be moved by one position using the function

std::pair&lt;int, int&gt;
rotated_local_next(int i, int j, int w, int h)
{
   if(j == 0) //top , special case top-right
   {
        return i == w-1 ? std::make_pair(i, ++j) : std::make_pair(++i, j);
   }
   if(i == w-1) //right, special case bottom-right
   {
        return j == h-1 ? std::make_pair(--i, j) : std::make_pair(i, ++j);
   }
   if(j == h-1) //bottom, special case bottom-left
   {
        return i == 0 ? std::make_pair(i, --j) : std::make_pair(--i, j);
   }
   if(i == 0) //left, special case top-left
   {
        return j == 0 ? std::make_pair(++i, j): std::make_pair(i, --j);
   }

   // cannot happen
   throw std::exception{};
}


You can now implement in matrix coordinates

std::pair&lt;int, int&gt;
rotated_matrix_next(int x, int y, int ring_i, int height, int width )
{
     auto local_point = rotated_local_next(x-ring_i, y-ring_i, width-2*(ring_i), height-2*(ring_i));
     return std::make_pair(local_point.first + ring_i, local_point.second + ring_i);
}


All you need to do now is to implement iterators satisfying MoveAssignable and MoveConstructible. The beginning of your ring is the element at positing ring, ring, which is also the end of the ring.

struct RingView
{
    //ring start at 0
   RingView(std::vector&lt;std::vector&lt;int&gt;&gt;&amp; mat, int ringnumber)
   : matrix(mat)
   , rows(mat.size())
   , cols(mat[0].size())
   , ring(ringnumber)
   {}

   std::vector&lt;std::vector&lt;int&gt;&gt;&amp; matrix;
   int rows;
   int cols;
   int ring;

    class ring_iterator : public std::iterator&lt;std::forward_iterator_tag, int&gt;
    {
    public:

        ring_iterator(RingView* v = nullptr, int xpos = 0, int ypos = 0)
        : view(v)
        , x(xpos)
        , y(ypos)
        {}

        ring_iterator(const ring_iterator&amp; other) = default;
        ring_iterator(ring_iterator&amp;&amp; other) = default;
        ring_iterator&amp; operator =(ring_iterator const&amp;) = default;
        ring_iterator&amp; operator=(ring_iterator&amp;&amp;) = default;
        virtual ~ring_iterator() = default;

        RingView* view;
        int x;
        int y;

        // Forward
        ring_iterator&amp; operator++() {
            auto posnext = rotated_matrix_next(x, y, view-&gt;ring, view-&gt;cols, view-&gt;rows);

            x = posnext.first;
            y = posnext.second;
            return *this;
        }

        ring_iterator operator++(int) {
            auto posnext = rotated_matrix_next(x, y, view-&gt;ring, view-&gt;cols, view-&gt;rows);
            ring_iterator next_iter = *this;
            next_iter.x = posnext.first;
            next_iter.y = posnext.second;
            return next_iter;
        }

        bool operator==(const ring_iterator&amp; other) const {
            if(view == nullptr ){
                return other.view == nullptr;
            }
            return view-&gt;ring == other.view-&gt;ring &amp;&amp; x == other.x &amp;&amp; y == other.y;
        }

        bool operator!=(const ring_iterator&amp; other) const {
            return !(*this == other);
        }

        // usually required
        int&amp; operator*() {
            return view-&gt;matrix[x][y];
        }
        int* operator-&gt;() {
            return &amp;(view-&gt;matrix[x][y]);
        }
    };

    ring_iterator begin()
    {
        return ring_iterator(this, ring, ring);
    }

    ring_iterator end()
    {
        return begin();
    }

    int size() const
    {
        return 2*(rows+cols -2) - 4 * ring;
    }
};


Now you can rotate the matrix using the view. To be able to rotate in both directions (positive for clockwise, negative counter-clockwise) we use

r' = (r % view.size() + view.size()) % view.size();

void rotate_mat (Matrix &amp;mat, int r){
    auto n_rings = std::min(mat.size(),mat[0].size())/2; // Number of rings
    for(auto ring_i=0; ring_i&lt;n_rings; ++ring_i){
        RingView view(mat,ring_i);
        int r_modulo = (r % view.size() + view.size()) % view.size();
        auto next_location = view.begin();
        std::advance(next_location, r_modulo);
        std::rotate(view.begin(),next_location,view.end());
    }
}


Full code : https://ideone.com/I3vg5v