Решение конкретной части вопроса:
Если у кого-то есть советы или рекомендации по вращению векторного массива M * N 2d
C ++ хорош в отделении алгоритмов от данных.
Пожалуйста, обратите внимание, что ответ является немного длинным и был написан с целью учебника.
Давайте начнем !!
Мы хотим, чтобы в нашем алгоритме rotate_2d_matrix_clockwise было 3 функции:
- Он должен работать со всеми типами данных, то есть
int, char, double или любым пользовательским типом.
- Должен работать с различными типами контейнеров, такими как
std::array и std::vector
- Он должен быть в цепочке, то есть пользователь должен иметь возможность вызвать
rotate_2d_matrix_clockwise для результата, возвращенного rotate_2d_matrix_clockwise, чтобы добиться 2-кратного поворота.
Как только мы разобрались с нашими требованиями, мы можем составить некоторые варианты использования нашего алгоритма.
std::vector<std::vector<char>> data = { {'a', 'b', 'c', 'd'},
{'e', 'f', 'g', 'h'},
{'i', 'j', 'k', 'l'} };
rotate_2d_matrix_clockwise(data); // rotating 2d-matrix of vector<char>
std::array<std::array<int, 4>, 3> data2 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
// rotating 2d-matrix of array<int>, twice
rotate_2d_matrix_clockwise(rotate_2d_matrix_clockwise(data2)));
Итак, давайте использовать некоторые шаблоны для создания общей функции 2d-поворота по часовой стрелке.
Наши rotate_2d_matrix_clockwise будут:
- возьмите
original_matrix и верните новый rotated_matrix.
- автоматически выводит размеры , т.е. M x N контейнера, переданного ему.
- создайте
rotated_matrix и передайте его вспомогательной функции rotate_2d_matrix_clockwise_impl, где будет выполняться фактическая работа.
Так как же будет выглядеть реализация rotate_2d_matrix_clockwise для std::array?
template<typename T, size_t M, size_t N>
auto rotate_2d_matrix_clockwise(std::array<std::array<T, M>, N> const & original_matrix)
-> std::array<std::array<T, N>, M>
{
std::array<std::array<T, N>, M> rotated_matrix;
rotate_2d_matrix_clockwise_impl(original_matrix, rotated_matrix, M, N); // rotate
return rotated_matrix;
}
Аккуратный и точный.
Однако реализация rotate_2d_matrix_clockwise для std::vector немного запутанная.
template<typename Matrix2D>
auto rotate_2d_matrix_clockwise(Matrix2D const & original_matrix) -> Matrix2D
{
int const M = original_matrix[0].size(); // deduce M and N
int const N = original_matrix.size();
Matrix2D rotated_matrix; // vector has no form, hence we have to resize it for `N x M`
rotated_matrix.resize(M);
for (auto x = 0; x < M; ++x) {
rotated_matrix[x].resize(N);
}
rotate_2d_matrix_clockwise_impl(original_matrix, rotated_matrix, M, N); // rotate
return rotated_matrix;
}
Теперь давайте посмотрим, как будет выглядеть фактический алгоритм вращения rotate_2d_matrix_clockwise_impl.
Следует отметить, что алгоритм не зависит от контейнера и / или содержащихся в нем данных. Он просто фокусируется на вращении.
template<typename OriginalMatrix2D, typename RotatedMatrix2D>
void rotate_2d_matrix_clockwise_impl(OriginalMatrix2D const & original_matrix,
RotatedMatrix2D & rotated_matrix,
int const M,
int const N)
{
for (auto x = 0; x < N; ++x) {
for (auto y = 0; y < M; ++y) {
// Source : /3736570/2d-evklidovy-vektornye-vrascheniya
rotated_matrix[y][-x -1 +N] = original_matrix[x][y];
}
}
}
Вот полный рабочий пример, скомпилированный в C ++ 11.
#include <iostream>
#include <vector>
#include <array>
template<typename Matrix2D>
void print_matrix(Matrix2D const & vec)
{
std::cout << "size of matrix is [" << vec[0].size() << " x " << vec.size() << "]\n";
for (auto const & inner_vec : vec) {
for (auto const & item : inner_vec) {
std::cout << item << ", ";
}
std::cout << std::endl;
}
}
template<typename OriginalMatrix2D, typename RotatedMatrix2D>
void rotate_2d_matrix_clockwise_impl(OriginalMatrix2D const & matrix,
RotatedMatrix2D & rotated_matrix,
int const M,
int const N)
{
for (auto x = 0; x < N; ++x) {
for (auto y = 0; y < M; ++y) {
// Source : /3736570/2d-evklidovy-vektornye-vrascheniya
rotated_matrix[y][-x -1 +N] = matrix[x][y];
}
}
}
template<typename T, size_t M, size_t N>
auto rotate_2d_matrix_clockwise(std::array<std::array<T, M>, N> const & original_matrix)
-> std::array<std::array<T, N>, M>
{
std::array<std::array<T, N>, M> rotated_matrix;
rotate_2d_matrix_clockwise_impl(original_matrix, rotated_matrix, M, N);
return rotated_matrix;
}
template<typename Matrix2D>
auto rotate_2d_matrix_clockwise(Matrix2D const & original_matrix) -> Matrix2D
{
int const M = original_matrix[0].size();
int const N = original_matrix.size();
Matrix2D rotated_matrix;
rotated_matrix.resize(M);
for (auto x = 0; x < M; ++x) {
rotated_matrix[x].resize(N);
}
rotate_2d_matrix_clockwise_impl(original_matrix, rotated_matrix, M, N);
return rotated_matrix;
}
int main()
{
std::array<std::array<int, 4>, 3> data = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
std::cout << "\nBefore Rotation :\n";
print_matrix(data);
std::cout << "\nAfter 2nd Clockwise Rotation :\n";
print_matrix(rotate_2d_matrix_clockwise(rotate_2d_matrix_clockwise(data)));
std::vector<std::vector<char>> data2 = { {'a', 'b', 'c', 'd'}, {'e', 'f', 'g', 'h'}, {'i', 'j', 'k', 'l'}};
std::cout << "Before Rotation :\n";
print_matrix(data2);
std::cout << "\nAfter Clockwise Rotation :\n";
print_matrix(rotate_2d_matrix_clockwise(data2));
return 0;
}