从其它std容器中转换std容器的元素

Question

问题

在这个黑客等级问题中，我们被要求以下列方式旋转矩阵的元素：

示例输入输出

第一项和第二项指定矩阵的大小，第三项指定必须旋转多少次。例如，以下输入：

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

将产生以下产出：

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

溶液

我的想法是旋转这些环。

#include <vector>
#include <iostream>
#include <algorithm>

using Matrix = std::vector<std::vector<int>>;

void rotate_mat (Matrix &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<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<int>  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<int*> v_ring_ptr;
        // Top side of the ring
        for(auto j=ring_i; j<=(n-1)-ring_i; ++j) {
            v_ring.push_back(mat[ring_i][j]);
            v_ring_ptr.push_back(&mat[ring_i][j]);
        }
        // Right side of the ring
        for(auto i=ring_i+1; i<=(m-1)-ring_i; ++i) {
            v_ring.push_back(mat[i][(n-1)-ring_i]);
            v_ring_ptr.push_back(&mat[i][(n-1)-ring_i]);
        }
        // Bottom size of the ring
        for(auto j=(n-1)-ring_i-1; j>ring_i; --j) {
            v_ring.push_back(mat[(m-1)-ring_i][j]);
            v_ring_ptr.push_back(&mat[(m-1)-ring_i][j]);
        }
        // Left size of the ring
        for(auto i=(m-1)-ring_i; i>ring_i; --i) {
            v_ring.push_back(mat[i][ring_i]);
            v_ring_ptr.push_back(&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<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<m; ++i) {
        mat.push_back(std::vector<int>{});
        mat[i].reserve(n);
        for(auto j=0; j<n; ++j) {
            int x; std::cin >> x;
            mat[i].push_back(x);
        }
    }
    return mat;
};

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

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

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

    return 0;
}

问题

我的主要问题是，我希望避免拥有v_ring副本和这个部分：

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

是否有一种方法来存储对原始矩阵内容的引用，以便自动反映所构造的环中的转换？我和std::reference_wrapper试过了。它几乎可以工作，我可以修改环中的元素，例如使用++运算符，但是我不能进行辅助，std::rotate也不会对它们产生任何影响。

有什么想法吗？我也对任何其他可能出现在你脑海中的方法感兴趣！我认为这种方式很容易用代码来表达。

Answer 1

有些事情要注意：

• 正如你说的，有std::min(m,n)/2;环。
• 环R(r, p)有2*(r+p-2)元素。
• 环的左上角总是协调(x,x)。这在代码中是可见的:) j = ring_i; v_ring.push_back(mat[ring_i][j]);
• 您的代码使用相对有效的内存量进行就地转换，并在O(m*n)时间内运行，这是最好的方法。
• 性能的改进将是对矩阵中的数据使用单个向量，例如m(x,y) = m.data[x * cols + y]

，我们能换个办法吗?

给定局部坐标系，其中(0，0)是环的左上角

圆环一侧的坐标(i,j), 0<=i<w, 0<=j<h, j == 0 || i == 0，可以使用该函数由一个位置移动。

std::pair<int, int>
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{};
}

现在可以在矩阵坐标中实现。

std::pair<int, int>
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);
}

现在所需要做的就是实现满足可移动赋值的和可移动结构的迭代器。你的环的开始是放置环的元素，环，也是环的末端。

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

   std::vector<std::vector<int>>& matrix;
   int rows;
   int cols;
   int ring;

    class ring_iterator : public std::iterator<std::forward_iterator_tag, int>
    {
    public:

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

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

        RingView* view;
        int x;
        int y;

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

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

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

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

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

        // usually required
        int& operator*() {
            return view->matrix[x][y];
        }
        int* operator->() {
            return &(view->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;
    }
};

现在，您可以使用视图旋转矩阵。为了能够在两个方向旋转(顺时针方向为正方向，负逆时针方向为正方向)，我们使用

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

void rotate_mat (Matrix &mat, int r){
    auto n_rings = std::min(mat.size(),mat[0].size())/2; // Number of rings
    for(auto ring_i=0; ring_i<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());
    }
}

完整代码：https://ideone.com/I3vg5v

Answer 2

我从堆栈溢出中得到了我想要的解决方案(检查它是这里)。现在它不需要额外的副本了。我还以为这不会那么冗长呢。我认为能够在引用向量上使用这些算法是一个有用的特性。

#include <vector>
#include <iostream>
#include <algorithm>

using Matrix = std::vector<std::vector<int>>;

/**
 * Class implementing std::reference_wrapper that
 * cannot be rebound after creation.
 **/
template <class T>
class single_bind_reference_wrapper {

    // pointer to the original element
    T *p_;

public: 

    // typedefs
    using type = T;

    // Construct/Copy/Destroy
    single_bind_reference_wrapper(T& ref) noexcept : p_(std::addressof(ref)) {}
    single_bind_reference_wrapper(T&&) = delete;

    // Enable implicit convertsion from ref<T> to ref<const T>,
    // or ref<Derived> to ref<Base>
    template <class U, std::enable_if_t<std::is_convertible<U*, T*>{}, int> = 0>
    single_bind_reference_wrapper(const single_bind_reference_wrapper<U>& other) noexcept :
        p_(&other.get()) { }

    // Assignment
    template <class U>
    decltype(auto) operator=(U &&u) const 
          noexcept(std::is_nothrow_assignable<T, U>{}) {
        return get() = std::forward<U>(u);
    }

    decltype(auto) operator=(const single_bind_reference_wrapper& other) const
          noexcept(std::is_nothrow_assignable<T, T>{}) {
        return get() = other.get();
    }

    // Access
    operator T& () const noexcept { return *p_; }
    T& get() const noexcept { return *p_; }
};

template <class T>
void swap(single_bind_reference_wrapper<T> &lhs,
          single_bind_reference_wrapper<T> &rhs)
    noexcept(std::is_nothrow_move_constructible<T>::value &&
             std::is_nothrow_move_assignable<T>::value){
    auto tmp = std::move(lhs.get());
    lhs = std::move(rhs.get());
    rhs = std::move(tmp);
}

void rotate_mat (Matrix &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<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<single_bind_reference_wrapper<int>>  v_ring;
        // Top side of the ring
        for(auto j=ring_i; j<=(n-1)-ring_i; ++j) {
            v_ring.push_back(mat[ring_i][j]);
        }
        // Right side of the ring
        for(auto i=ring_i+1; i<=(m-1)-ring_i; ++i) {
            v_ring.push_back(mat[i][(n-1)-ring_i]);
        }
        // Bottom size of the ring
        for(auto j=(n-1)-ring_i-1; j>ring_i; --j) {
            v_ring.push_back(mat[(m-1)-ring_i][j]);
        }
        // Left size of the ring
        for(auto i=(m-1)-ring_i; i>ring_i; --i) {
            v_ring.push_back(mat[i][ring_i]);
        }
        std::rotate(v_ring.begin(),v_ring.begin()+r%v_ring.size(),v_ring.end());
    }
};

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

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

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

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

    return 0;
}

Answer 3

“我认为这种方式很容易用代码来表达”。可悲的是，容易写的东西并不总是容易读懂的。六个循环，六个字母变量，没有注释.坦率地说，我不能跟随(这意味着我不会试图跟随，除非我真的必须这样做)，而且我不确定你是否能够在两周后自己理解它。

您应该尝试通过注释或更好地通过变量和类型名称来更好地记录代码。

另一个更简单的-arguably方法是创建一个函数，修改访问矩阵的索引。例如，如果希望旋转一次的矩阵的元素(0,0)，则需要基础矩阵的元素(0,1)。

以下是我的看法(我没有花太多时间在算法中，但试图使其易于阅读)：

struct Coordinates {int row=0, col=0; }; 
using Matrix_size = Coordinates;

// determine the ring to which those coordinates belongs
int ring_number(Coordinates coord, Matrix_size m_size, int offset=0) {
    if  (  coord.row == 0+offset
        || coord.col == 0+offset
        || coord.row == m_size.row-1-offset
        || coord.col == m_size.col-1-offset
        ) return 0;
    return 1 + ring_number(coord, m_size, offset+1);
}

// return the coordinates of north-west and southwest angles of the ring
std::pair<Coordinates, Coordinates> ring_coordinates(Coordinates coord, Matrix_size m_size) {
    auto rn = ring_number(coord, m_size);
    return { Coordinates{rn, rn}, Coordinates{m_size.row-rn-1, m_size.col-rn-1} };
}

Coordinates rotate_coordinates(Coordinates c, Matrix_size m_size, int step=1) {
    auto [min, max] = ring_coordinates(c, m_size);
    step %= 2*(max.row-min.row+max.col-min.col); // number of elements in the ring;
    for (int i = 0; i < step; ++i) {
        if (c.row == min.row && c.col < max.col) ++c.col;
        else if (c.col == max.col && c.row < max.row) ++c.row;
        else if (c.row == max.row && c.col > min.col) --c.col;
        else --c.row;
    }
    return c;
}

然后，您可以使用它输出旋转矩阵：

#include <iostream>
#include <vector>

int main() {
    std::vector<std::vector<int>> data = { {1,2,3,4}, {5,6,7,8}, {9,10,11,12}, {13,14,15,16} };
    Matrix_size msz = {4, 4};
    for (int row = 0; row < msz.row; ++row) {
        for (int col = 0; col < msz.col; ++col) {
            auto rc = rotate_coordinates(Coordinates{row, col}, msz, 1);
            std::cout << data[rc.row][rc.col] << " ";
        }
        std::cout << '\n';
    }
}