C++二维std::vector最佳实践

Question

我正在构建一个需要支持二维数组来保存数据网格的应用程序。我有一个名为Map的类，其中包含一个2d数据网格。我想使用向量而不是数组，想知道使用2d向量的最佳实践是什么。我应该拥有一个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);
        }
    }
}

基本上，用什么方法来做这件事会给我带来最少的麻烦（关于内存管理或其他方面）？

- goatlinks

---

除非你想要不规则的数组，否则我不会使用 vector<vector<...> >。 - cobbal

我将需要不规则数组，但我可以在末尾使用填充来实现这一点。 - goatlinks

你考虑过Boost.MultiArray吗？看看文档说了什么：http://www.boost.org/doc/libs/1_42_0/libs/multi_array/doc/user.html#sec_introduction - Manuel

你是否考虑过[..]？ - Manuel

我有一个二维数组类在这里，可能适合您的需求。 - Richard

Answer 1

当你需要一个正方形或二维网格时，可以采用类似于编译器处理多维数组（真正的数组，而不是指向数组的指针）的方式，存储一个正确索引的单个大数组。

以下是使用下面的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
  }
};

矩阵类的变种很多，有许多方法可以为特定用途进行定制。以下是一个不到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;
};

- Roger Pate

---

拥有typedef T value_type的优势是什么？ - fabrizioM

@Roger Pate：没错，我没有注意到你提供了matrix[a][b]的语法。我已经习惯于使用operator()来访问元素，而不是operator[]。在C++FAQ中有一个很好的讨论，建议使用带有2个参数的operator()，而不是在此处提供双重[]语法：http://www.parashift.com/c++-faq-lite/operator-overloading.html#faq-13.11 - David Rodríguez - dribeas

@David：我不同意那个FAQ条目，但最好在新问题中讨论，而不是在这里评论。然而，几乎没有任何FAQ适用于这个类，因为意图（虽然没有明确提到）是成为std::vector的2D模拟。大部分类已经被剥离了，因为我试图只包含必要的内容，以便实现尽可能易懂。（我确实过度简化了ct​​ors，正如你最初注意到的那样，但很容易使它们比具有所有默认参数的版本更清晰易懂。） - Roger Pate

@goatlinks：我的代码使用了一个vector<MapCell>（间接地，将MapCell作为T传递，然后使用vector<T>）。（在这里，指针容器并不合适。C++中不允许引用容器。）大小受可用连续内存的限制。该向量是Matrix类的数据成员，因此存在于该对象中。当你“添加”它们时，会将其复制到向量中，所以这不是问题。 - Roger Pate

这段代码中有些东西我没搞清楚。如果我想要添加一列或一行，我需要“重新排序”矩阵中的所有元素吗？ - Antonio

Answer 2

如果整个矩阵的宽度和高度大部分都是相同的，您可以使用单个向量，并使用(row * columnCount) + column来访问单元格。这样整个矩阵将存储在单个内存块中，而不是每行都分散在多个碎片化的块中。(当然，您正在正确地将此概念包装在一个新类中 - 我只是谈论背后的实现。)

向量的向量具有不幸的属性，即如果在顶部插入一行，则std::vector将对所有其他行执行复制构造(或赋值)，因为它们向下移动了一个位置。这反过来涉及重新分配每行的存储并逐个复制每行单元格中的项目。(C++0x可能会更好处理这个问题。)

如果您知道您经常会这样做，单个大内存块的优点在于您可以在顶部插入新行，而std::vector只需要将所有单元格向前移动columnCount个位置，因此它将严重减少堆操作(释放/重新分配单个块)的数量。

虽然正如您所建议的那样，指向向量的指针的向量将具有进一步的优势，因为它只需要向前移动许多指针值，并且包含所有行指针的块的大小将小得多，从而进一步减少了堆操作的影响。

当然，确保这些事情对应用程序性能的实际影响是唯一的方法，就是使用各种实现进行计时并进行比较。这就是为什么您正在正确地将这些细节隐藏在一个新类中的原因。

- Daniel Earwicker

Answer 3

使用向量并将2个维度转换为一个维度。例如，如果您的矩阵宽度为W，高度为H，则将x，y映射到向量中的索引只需x * W + y。

如果您的矩阵是稀疏的，则可以使用std :: map，其中键是一对（x和y）。

- Patrick

Answer 4

在我的项目中，我经常使用这个简单的网格类。

- StackedCrooked