c++ - C ++使用分割向量的向量
问题描述
假设您有一个如下定义的二维向量:
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)
对于两个方向,这可以通过迭代外部向量并分割内部向量(按顺序或反向)非常简单地完成。但是对于其他方向,我不知道如何去做。
有没有办法使用std::stable_partition
. 是否有另一种数据结构(支持像向量这样的索引)可以让我更轻松地做到这一点?
如果我让我从头开始实施,是否有标准或推荐的方法来做到这一点?
解决方案
您不需要编写自己的算法实现。当您想将现有算法用于自定义数据结构时,迭代器是自定义点。不幸的是,编写自己的迭代器需要相当多的样板文件。我认为 boost 可以提供帮助,但是如果您想继续使用标准库提供的功能,据我所知,您无法自己编写它。
以下内容要带一粒盐。我假设所有内部向量的大小相同。我不考虑const_iterators
,因为你不需要它们来使用std::stable_partition
。我省略了一些您必须自己添加的成员函数。该算法要求迭代器遵守两个命名概念,即LegacyBidirectionalIterator
和ValueSwappable
。话虽如此,这里是如何实现一个迭代器,使您能够迭代二维向量的列:
#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
效率并不是一个真正的大问题,矩阵会相对较小。我只想找到最简单、最清晰的方法。最好不必从头开始编写 stable_partition 实现。
如果矩阵真的很小(比如说~20x20 元素)并且效率真的不是问题,那么最简单的可能是std::stable_partition
只在内部向量上使用。您可以转置矩阵,在循环中为所有内部向量调用算法,再次转置。完毕。那基本上是~10行代码。你的选择 ;)
推荐阅读
- java - Java:Sqlexception:位置不支持的 SQL92 令牌:178
- java - 尝试使用 Media Player 在 Android java 应用程序中播放 mp3 时出错
- maven - 即使詹金斯构建成功,频道停止错误
- bluetooth - 如何禁用 BlueZ 缓存?
- sql - 带有分组的标量子查询需要优化
- javascript - 如何在函数外部使用函数的声明变量但将它们的值保留在 javascript 中?
- reactjs - React-select-async-paginate 选项异步函数使通用
- amazon-web-services - 通过 Cloudformation 创建 SQS 队列及其访问策略时出错
- discord - Discord.py on_member_join 没有响应
- github - 在触发 AWS codebuil 时指定 file_path