C++ 使用 <algorithm> 对 vector 的 vector 进行划分

Question

假设您有一个 2D vector 定义如下:

std::vector<vector<int>> v

代表一个矩阵:

1 1 0 1 3
0 4 6 0 1
5 0 0 3 0
6 3 0 2 5

我想对该矩阵进行稳定分区(例如使用谓词 el != 0)，但在各个方向上。这意味着我希望能够获得:

1 1 6 1 3     0 0 0 0 0      1 1 1 3 0     0 1 1 1 3
5 4 0 3 1     1 1 0 1 3      4 6 1 0 0     0 0 4 6 1
6 3 0 2 5     5 4 0 3 1      5 3 0 0 0     0 0 0 5 3
0 0 0 0 0     6 3 6 2 5      6 3 2 5 0     0 6 3 2 5
 (down)         (up)          (right)       (left)

对于两个方向，这可以通过迭代外部 vector 并划分内部 vector (按顺序或相反)来非常简单地完成。然而，对于其他方向，我不知道如何去做同样的事情。

有没有办法使用std::stable_partition来实现这一点。是否有另一种数据结构(支持像 vector 一样的索引)可以让我更轻松地做到这一点？
如果我从头开始实现这一点，是否有标准或推荐的方法来做到这一点？

Answer 1

您不需要编写自己的算法实现。当您想要将现有算法用于自定义数据结构时，迭代器是自定义点。不幸的是，编写自己的迭代器需要相当多的样板文件。我认为 boost 可以提供帮助，但如果您想继续使用标准库提供的功能，据我所知，没有办法自己编写它。

以下内容需持保留态度。我假设所有内部 vector 的大小相同。我没有考虑 const_iterators，因为您不需要它们来使用 std::stable_partition 。我省略了一些您必须自己添加的成员函数。该算法要求迭代器遵守两个命名概念，即 LegacyBidirectionalIterator和 ValueSwappable 。话虽这么说，以下是如何实现一个迭代器，使您能够迭代 2d vector 的列:

#include <iostream>
#include <vector>

struct vector2d_col_iterator {
    using container_t = std::vector<std::vector<int>>;
    container_t& container;
    size_t row;
    size_t col;
    vector2d_col_iterator& operator++(){
        ++row;
        return *this;
    }
    bool operator==(const vector2d_col_iterator& other) const {
        return col == other.col && row == other.row;
    }
    bool operator !=(const vector2d_col_iterator& other) const {
        return !(*this == other);
    }
    int& operator*() { return container[row][col]; }
    static vector2d_col_iterator begin(container_t& container,int col) {
        return {container,0,col};
    }
    static vector2d_col_iterator end(container_t& container,int col) {
        return {container,container.size(),col};
    }
};

int main() {
    std::vector<std::vector<int>> v{ {1,2,3},{4,5,6}};
    auto begin = vector2d_col_iterator::begin(v,1);
    auto end = vector2d_col_iterator::end(v,1);
    for ( ; begin != end; ++begin) std::cout << *begin << " ";
}

输出:

2 5

Live example

Efficiency is not a really big issue, the matrices will be relatively small. I just want to find the simplest, clearest way of doing this. Preferably without having to write a stable_partition implementation from scratch.

如果矩阵真的很小(比如说 ~20x20 元素)并且效率确实不是问题，那么最简单的方法可能是仅在内部 vector 上使用 std::stable_partition 。您可以转置矩阵，在循环中为所有内部 vector 调用算法，然后再次转置。完毕。基本上就是 10 行代码。你的选择;)