Rotating contents of a matrix (vector<string>) to the left or right

Question

Each vector element is a row and each character is a column.

Assume the matrix is square (N*N) and N is < 10.

I have some code to do it but it doesn't look great and would love some feedback on how to make it better. You can use any function of the C++ standard library. The only constraint is it can't be in-place. I'm looking to improve it in style and any optimisations needed.

enum DIRECTION
{
    DIR_RIGHT = 0,
    DIR_LEFT = 1
};
    
vector<string> rotate(const vector<string>& original, DIRECTION direction)
{
    vector<string> rotated(original);
    for (vector<string>::const_iterator irow = original.begin(); irow != original.end(); ++irow) {
        int new_col = direction == DIR_RIGHT ? (original.size() - 1) - (irow - original.begin())
                                             : (irow - original.begin());
        for (string::const_iterator icol = (*irow).begin(); icol != (*irow).end(); ++icol) {
            int new_row = direction == DIR_RIGHT ? (icol - (*irow).begin())
                                                 : ((*irow).size() - 1) - (icol - (*irow).begin());
            rotated[new_row][new_col] = *icol;
        }
    }
    return rotated;
}

Example input:

"###"
"oho"
"ooo"

Rotating right should output:

"oo#"
"oh#"
"oo#"

P.s. For convenience I've included using namespace std;, the final code uses the namespace explicitly E.g. std::vector.

Answer 1

I didn't look very closely at the algorithm, so I'll trust that it is correct ;)

Some stylistic changes you could do are:

• Use auto to clean up those long iterator names.

• Break long lines. Shorter lines are usually easier to digest.

• DIRECTION is a bit unusual for the name of an enum type. That notation is normally used for the enum constants, the type usually goes with the same notation used for classes and structs (CamelCase, in most projects).

• Use const as much as possible. Making the integer indexes const in this case won't change much, but making things that are not supposed to change const is a good habit, so you should aways try to do it, even for small sections of code. You never know when that tiny function might grow.

Following is a snippet of code with the above changes applied:

enum Direction
{
    DIR_RIGHT = 0,
    DIR_LEFT  = 1
};

std::vector<std::string> rotate(const std::vector<std::string>& original, Direction direction)
{
    std::vector<std::string> rotated(original);

    for (auto irow = original.cbegin(); irow != original.cend(); ++irow) {

        const auto new_col = (direction == DIR_RIGHT) ?
            (original.size() - 1) - (irow - original.cbegin()) :
            (irow - original.cbegin());

        for (auto icol = (*irow).cbegin(); icol != (*irow).cend(); ++icol) {

            const auto new_row = (direction == DIR_RIGHT) ?
                (icol - (*irow).cbegin()) :
                ((*irow).size() - 1) - (icol - (*irow).cbegin());

            rotated[new_row][new_col] = *icol;
        }
    }

    return rotated;
}

Side note: You might also want to check out std::distance() to replace the iterator diferences you are computing with operator -.

Also, by using cbegin()/cend(), you can ensure the returned iterators are of type const_iterator and thus pointing to immutable data.

Answer 2

Use @glampert's changes as a good starting point as it is now more obvious what the program does.

Unfortunately I can't see any useful library calls that would make it easier, a reason is that we need the coordinates. Thinking this was just me I looked through the first pages of a google search to see if any of those solutions used anything, but none did.

If your worried about speed then you can try out this template

template<Direction direction>
std::vector<std::string> rotate(const std::vector<std::string>& original) {
    // loop invariant, you compiler really should do this for your
    const auto osize = (original.size() - 1); 
    // assume all string are equal length, compiler can't guess this.
    const auto isize = original[0].size() - 1);
    ... glampert's code with the above osize/isize
}

std::vector<std::string> rotate(const std::vector<std::string>& original, Direction direction) {
    if (direction == DIR_LEFT) 
       return rotate<DIR_LEFT)(original);
    if (direction == DIR_RIGHT) 
       return rotate<DIR_RIGHT)(original);

    // paranoia check in case you add more directions
    assert(direction == DIR_RIGHT || direction == DIR_LEFT); 
}

If your lucky your compiler will do this for your already by inlining the code. But if not then the result of this should be that all uses of direction will be done at compile time resulting in some dead code elimination and const folding making the chosen direction faster at the cost of extra code for the other direction in the program.

There is no reason to start on these if your matrix is small, else you can measure if this really is faster.

If your data is large look at some blocking code and modify your code to do the same, see this example not the accepted answer but the one by user2088790, adapting your code to the SSE version will take a big more thought.