2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ thanks a lot! :) that looks great! Why did you use auto for the ints too? \$\endgroup\$ – DiogoNeves Oct 22 '14 at 8:07
  • \$\begingroup\$ @DiogoNeves - Good question. I used auto in the row/col calculations because the resulting value of an iterator diference is not an int but a vector::difference_type, which normally is implemented as ptrdiff_t. That way, you get a more correct code without all the typing. \$\endgroup\$ – glampert Oct 22 '14 at 13:29
  • \$\begingroup\$ thanks!!! :) I'll have to pay more attention to return values next time \$\endgroup\$ – DiogoNeves Oct 22 '14 at 21:18
  • \$\begingroup\$ will the auto on the iterators use the const iterator? How can you do it if not? \$\endgroup\$ – DiogoNeves Oct 23 '14 at 11:46
  • 1
    \$\begingroup\$ Great! thanks! Yah, I guess just adding const makes the iterator itself const, not the reference it holds. \$\endgroup\$ – DiogoNeves Oct 23 '14 at 14:22
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ great answer too! I'm not going to mark it as the 'ultimate' answer just because I wasn't looking for that level of optimisation, but a great tip nonetheless ;) \$\endgroup\$ – DiogoNeves Oct 22 '14 at 21:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.