C++ 二维 std::vector 最佳实践
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2286991/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
C++ Two Dimensional std::vector best practices
提问by goatlinks
I am building an app that needs to have support for two dimensional arrays to hold a grid of data. I have a class Mapthat contains a 2d grid of data. I want to use vectors rather than arrays, and I was wondering what the best practices were for using 2d vectors. Should I have a vector of vectors of MapCells? or should it be a vector of vectors of pointers to MapCells? or references to MapCells?
我正在构建一个需要支持二维数组来保存数据网格的应用程序。我有一个Map包含二维数据网格的类。我想使用向量而不是数组，我想知道使用二维向量的最佳实践是什么。我应该有一个 MapCells 向量的向量吗？还是应该是指向 MapCells 的指针向量的向量？或对 MapCells 的引用？
class Map {
private:
vector<vector<MapCell>> cells;
public:
void loadMap() {
cells.clear();
for (int i = 0; i < WIDTH; i++) {
//How should I be allocating these?
vector<MapCell> row(HEIGHT);
for (int j = 0; j < HEIGHT; j++) {
//Should I be dynamically allocating these?
MapCell cell;
row.push_back(cell);
}
cells.push_back(row);
}
}
}
Basically what way of doing this is going to get me in the least amount of trouble (with respect to memory management or anything else)?
基本上，这样做的方式会让我遇到最少的麻烦（关于内存管理或其他任何事情）？
采纳答案by goatlinks
When you want a square or 2d grid, do something similar to what the compiler does for multidimensional arrays (real ones, not an array of pointers to arrays) and store a single large array which you index correctly.
当你想要一个正方形或二维网格时，做一些类似于编译器对多维数组（真实的数组，而不是指向数组的指针的数组）所做的事情，并存储一个你正确索引的大数组。
Example using the Matrix class below:
使用以下 Matrix 类的示例：
struct Map {
private:
Matrix<MapCell> cells;
public:
void loadMap() {
Matrix<MapCell> cells (WIDTH, HEIGHT);
for (int i = 0; i < WIDTH; i++) {
for (int j = 0; j < HEIGHT; j++) {
// modify cells[i][j]
}
}
swap(this->cells, cells);
// if there's any problem loading, don't modify this->cells
// Matrix swap guarantees no-throw (because vector swap does)
// which is a common and important aspect of swaps
}
};
Variants of matrix classes abound, and there are many ways to tailor for specific use. Here's an example in less than 100 lines that gets you 80% or more of what you need:
矩阵类的变体比比皆是，并且有许多方法可以针对特定用途进行裁剪。这是一个不到 100 行的示例，可以为您提供 80% 或更多的所需内容：
#include <algorithm>
#include <memory>
#include <vector>
template<class T, class A=std::allocator<T> >
struct Matrix {
typedef T value_type;
typedef std::vector<value_type, A> Container;
Matrix() : _b(0) {}
Matrix(int a, int b, value_type const& initial=value_type())
: _b(0)
{
resize(a, b, initial);
}
Matrix(Matrix const& other)
: _data(other._data), _b(other._b)
{}
Matrix& operator=(Matrix copy) {
swap(*this, copy);
return *this;
}
bool empty() const { return _data.empty(); }
void clear() { _data.clear(); _b = 0; }
int dim_a() const { return _b ? _data.size() / _b : 0; }
int dim_b() const { return _b; }
value_type* operator[](int a) {
return &_data[a * _b];
}
value_type const* operator[](int a) const {
return &_data[a * _b];
}
void resize(int a, int b, value_type const& initial=value_type()) {
if (a == 0) {
b = 0;
}
_data.resize(a * b, initial);
_b = b;
}
friend void swap(Matrix& a, Matrix& b) {
using std::swap;
swap(a._data, b._data);
swap(a._b, b._b);
}
template<class Stream>
friend Stream& operator<<(Stream& s, Matrix const& value) {
s << "<Matrix at " << &value << " dimensions "
<< value.dim_a() << 'x' << value.dim_b();
if (!value.empty()) {
bool first = true;
typedef typename Container::const_iterator Iter;
Iter i = value._data.begin(), end = value._data.end();
while (i != end) {
s << (first ? " [[" : "], [");
first = false;
s << *i;
++i;
for (int b = value._b - 1; b; --b) {
s << ", " << *i;
++i;
}
}
s << "]]";
}
s << '>';
return s;
}
private:
Container _data;
int _b;
};
回答by Daniel Earwicker
If the whole matrix has a mostly constant width and height, you may as well use a single vector, and address cells with (row * columnCount) + column. That way the whole thing will be stored in a single memory block instead of in several fragmented blocks for each row. (Though of course you are doing the right thing to wrap this concept up in a new class - I'm just talking about the behind-the-scenes implementation.)
如果整个矩阵的宽度和高度几乎恒定，您不妨使用单个vector, 并使用(row * columnCount) + column.地址单元格。这样，整个内容将存储在单个内存块中，而不是每一行的几个碎片块中。（当然，您正在做正确的事情来将这个概念包装到一个新类中 - 我只是在谈论幕后实现。）
A vector of vectors has the unfortunate property that if you insert a row at the top, std::vectorwill perform a copy construction (or assignment, possibly) for all the other rows as it shifts them down by one place. This in turn involves reallocating the storage for every row and individually copying the items in the cells of every row. (C++0x will probably be better at this.)
向量的向量具有一个不幸的特性，即如果在顶部插入一行，std::vector则会对所有其他行执行复制构造（或分配，可能），因为它将它们向下移动一个位置。这反过来又涉及为每一行重新分配存储空间并单独复制每一行单元格中的项目。（C++0x 在这方面可能会更好。）
If you know that you will be doing that kind of thing often, the advantage of a single large memory block is that you can insert a new row at the top and std::vectorwill only have to shift all the cells forward by columnCountplaces, so it will seriously reduce the number of heap operations (freeing/reallocating of individual blocks).
如果你知道你会经常做那种事情，单个大内存块的好处是你可以在顶部插入一个新行，std::vector只需要将所有单元格向前移动一个columnCount位置，所以它会严重减少堆操作的数量（释放/重新分配单个块）。
Although as you suggest, a vector of pointers to vectors would have the further advantage that it would only need to shift forward a lot of pointer values, and the size of the block containing all the row pointers will be much smaller, further lessening the impact of heap operations.
尽管正如您所建议的，指向向量的指针向量将具有进一步的优势，即它只需要向前移动大量指针值，并且包含所有行指针的块的大小将小得多，从而进一步减轻影响堆操作。
Of course, the only way to be sure of the actual impact of these things on the performance of an application is to time it with various implementations and compare them. This is why you're doing exactly the right thing by hiding these details inside a new class.
当然，确定这些事情对应用程序性能的实际影响的唯一方法是将其与各种实现进行计时并进行比较。这就是为什么您通过将这些细节隐藏在新类中来做完全正确的事情的原因。
回答by Patrick
Use a vector and translate the 2 dimensions to one dimension. E.g. if your matrix has a width of W and a height of H, then mapping x,y to the index in the vector is simply x*W+y.
使用向量并将二维转换为一维。例如，如果您的矩阵宽度为 W，高度为 H，那么将 x,y 映射到向量中的索引就是 x*W+y。
If your matrix is sparse you may want to use an std::map where the key is a pair (x and y).
如果您的矩阵是稀疏的，您可能需要使用 std::map ，其中键是一对（x 和 y）。
回答by StackedCrooked
In my projects I often use this simple grid class.
在我的项目中，我经常使用这个简单的网格类。
