在C++中创建矩阵的正确方法

Question

我想为一个图创建邻接矩阵。由于我读到了使用matrix[x][y]这种形式的数组不安全，因为它们不检查范围，所以我决定使用STL的向量模板类。在矩阵中，我需要存储的只是布尔值。因此，我的问题是，如果使用std::vector<std::vector<bool>>会产生太多额外开销，或者是否有更简单的方法来创建一个矩阵，以及如何正确初始化它。

编辑：非常感谢快速回答。我刚意识到，当然不需要任何指针。矩阵的大小将在一开始初始化，并且直到程序结束都不会改变。它是一个学校项目，所以写出“好看”的代码很重要，尽管技术上性能并不太重要。使用STL是可以的。使用类似boost之类的东西可能不被赞赏。

- Lulu

Answer 1

请注意，您还可以使用boost.ublas进行矩阵的创建和操作，以及boost.graph以多种方式表示和操作图形，以及在其上使用算法等。 编辑：无论如何，为您的目的创建一个向量的范围检查版本并不难。

template <typename T>
class BoundsMatrix
{
        std::vector<T> inner_;
        unsigned int dimx_, dimy_;

public:
        BoundsMatrix (unsigned int dimx, unsigned int dimy)
                : dimx_ (dimx), dimy_ (dimy)
        {
                inner_.resize (dimx_*dimy_);
        }

        T& operator()(unsigned int x, unsigned int y)
        {
                if (x >= dimx_ || y>= dimy_)
                        throw std::out_of_range("matrix indices out of range"); // ouch
                return inner_[dimx_*y + x];
        }
};

注意，您还需要添加运算符的const版本和/或迭代器，以及异常的奇怪使用方式，但您已经明白了这个想法。

- Diego Sevilla

---

那真的很好。 - peedurrr

throw 0?! Why not std::out_of_range("matrix indices out of range") - Alexis Wilke

BoundsMatrix<bool>不起作用。无论如何，这根本不是“向量的范围检查版本”。您甚至没有提供迭代器，为此提供范围检查要困难得多。 - D Drmmr

@DDrmmr，这仅仅是一个指示如何实现的提示，并不是完整的实现。你认为将这些特殊情况包含在类型检查或模板特化中会导致更好的答案吗？ - Diego Sevilla

Answer 2

最佳方式：

制作自己的矩阵类，这样您可以控制它的每个细节，包括范围检查。

例如，如果您喜欢“[x] [y]”表示法，请执行以下操作：

class my_matrix {
  std::vector<std::vector<bool> >m;
public:
  my_matrix(unsigned int x, unsigned int y) {
    m.resize(x, std::vector<bool>(y,false));
  }
  class matrix_row {
    std::vector<bool>& row;
  public:
    matrix_row(std::vector<bool>& r) : row(r) {
    }
    bool& operator[](unsigned int y) {
      return row.at(y);
    }
  };
  matrix_row& operator[](unsigned int x) {
    return matrix_row(m.at(x));
  }
};
// Example usage
my_matrix mm(100,100);
mm[10][10] = true;

注意：如果您以这种方式编程，则C++与所有其他“安全”语言一样安全。

- Jimmy J

---

我无法编译这段代码：error: cannot bind non-const lvalue reference of type ‘bool&’ to an rvalue of type ‘bool’，出错位置在 return row.at(y);。 - RoG

@RoG 这是因为 std::vector<bool> 为布尔类型提供了专门的特化，因此它实际上返回一个代理对象。因此，您无法将引用分配给它。请参阅 https://en.cppreference.com/w/cpp/container/vector_bool（它本质上是一个动态位集）。 - Noak Palander

@RoG 还可以作为所讨论的事情的演示 https://godbolt.org/z/G4rfjs6vT - Noak Palander

Answer 3

标准向量默认情况下不进行范围检查。

即，operator[]不进行范围检查。

方法at()类似于[]，但会进行范围检查。
如果超出范围，它将抛出异常。

std::vector::at()
std::vector::operator[]()

其他注意事项： 为什么使用vector<指针>？
您可以很容易地拥有一个vector<对象>。现在无需担心内存管理（即泄漏）。

std::vector<std::vector<bool> >   m;

注意：vector<bool> 被重载了，效率不是很高（即此结构体被优化为大小而非速度）（现在标准委员会已经认识到这可能是个错误）。

如果您在编译时知道矩阵的大小，可以使用 std::bitset？

std::vector<std::bitset<5> >    m;

或者如果它是运行时定义的，则使用boost::dynamic_bitset

std::vector<boost::dynamic_bitset>  m;

以上所有内容将使您能够做到：

m[6][3] = true;

- Martin York

Answer 4

如果您想要具有'C'数组的性能，但又希望增加安全性和类似STL的语义（迭代器、begin()和end()等），请使用boost::array。

基本上，它是'C'-数组的模板包装器，具有一些可通过NDEBUG禁用的范围检查断言（还有一些std::range_error异常抛出的访问器）。

我使用类似以下的东西：

boost::array<boost::array<float,4>,4> m;

替代

float m[4][4];

一直以来，它都表现出色（使用适当的typedef可以减少冗余代码）。

---

更新：在这里的评论中讨论了boost::array和boost::multi_array之间相对性能的问题。我想指出，在Debian/Lenny amd64上使用g++ -O3 -DNDEBUG编译该代码，配备Q9450和1333MHz DDR3 RAM，boost::multi_array需要3.3秒，而boost::array只需要0.6秒。

#include <iostream>
#include <time.h>
#include "boost/array.hpp"
#include "boost/multi_array.hpp"

using namespace boost;

enum {N=1024};

typedef multi_array<char,3> M;
typedef array<array<array<char,N>,N>,N> C;

// Forward declare to avoid being optimised away
static void clear(M& m);
static void clear(C& c);

int main(int,char**)
{
  const clock_t t0=clock();

  {
    M m(extents[N][N][N]);
    clear(m);
  }

  const clock_t t1=clock();

  {
    std::auto_ptr<C> c(new C);
    clear(*c);
  }

  const clock_t t2=clock();

  std::cout 
    << "multi_array: " << (t1-t0)/static_cast<float>(CLOCKS_PER_SEC) << "s\n"
    << "array      : " << (t2-t1)/static_cast<float>(CLOCKS_PER_SEC) << "s\n";

  return 0;
}

void clear(M& m)
{
  for (M::index i=0;i<N;i++)
    for (M::index j=0;j<N;j++)
      for (M::index k=0;k<N;k++)
    m[i][j][k]=1;
}


void clear(C& c)
{
  for (int i=0;i<N;i++)
    for (int j=0;j<N;j++)
      for (int k=0;k<N;k++)
    c[i][j][k]=1;
}

- timday

---

对于多维数组，boost::multiarray (http://www.boost.org/doc/libs/1_38_0/libs/multi_array/doc/index.html) 可能是更好的选择。 - janneb

不行，我以前尝试过，它的性能与C数组相比非常糟糕。而且它的存储总是堆分配，与可以使用堆栈的boost :: array相比较劣。 - timday

感谢提供基准测试数据，我一直在研究为什么结果与我的测试不同。有两个因素导致时间差异较大：1）使用char而不是double；2）将初始化包括在计时中。例如，如果您使用（续...） - janneb

双精度或单精度浮点数，如果不包括初始化，则 multi_array 稍微更快。一些实验让我相信 multi_array 初始化会将数组清零；它占用了一半的时间（使用不同大小的数组进行测试）。然而，对于 char 和 int，数组（继续...） - janneb

在 g++ 4.1.2，boost 1.33 中，multi_array 总是表现不如其他选项。 - janneb

Answer 5

我会创建一个处理矩阵的类（可能是数组[x*y]，因为我更习惯使用C语言（并且我会有自己的边界检查），但您也可以在该类中使用向量或任何其他子结构）。

先让您的东西功能正常，然后再考虑它运行得有多快。如果您正确地设计了该类，则可以将数组[x*y]实现取出并替换为向量、位掩码或任何其他您想要的内容，而不必更改其余代码。

我不完全确定，但我认为这就是类的意义所在，即能够很好地将实现抽象化，并仅提供接口 :-)

- Pax

Answer 6

我最喜欢存储图的方法是使用vector<set<int>>；向量中有n个元素(节点0..n-1)，每个集合中至少有0个元素(边)。只需不要忘记添加每个双向边的反向副本。

- OverInflatedWalrus

Answer 7

除了之前发布的所有答案，你可能需要查看C++ FAQ Lite。问题13.10 - 13.12和16.16 - 16.19涵盖了几个与自己编写矩阵类相关的主题。你将看到几种不同的存储数据的方式，并提出如何最好地编写下标运算符的建议。

此外，如果你的图足够稀疏，你可能根本不需要矩阵。你可以使用std::multimap将每个顶点映射到它连接的顶点。

- Kristo

Answer 8

也许这个问题已经过时了，但是你可以使用Armadillo库，它提供了许多与线性代数有关的数据类型和函数。

以下是针对您特定问题的示例：

// In C++11
Mat<bool> matrix = {  
    { true, true},
    { false, false},
};

// In C++98
Mat<bool> matrix;
matrix << true << true << endr
       << false << false << endr;

- Devesh Khandelwal

Answer 9

考虑一下你的图/矩阵有多大，性能是否非常重要？这个图是静态的，还是可以随着时间增长，例如添加新的边缘？

- siddhadev

Answer 10

请注意，std::vector 也不进行范围检查。

- shoosh

---

除非您使用的是调试版 stdlib，或者您正在调用 vector::at，否则请务必返回仅已翻译的文本。 - Iraimbilanja