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

Question

我想为图形创建一个邻接矩阵.由于我读过matrix[x][y]因为不检查范围而使用表单数组是不安全的,所以我决定使用stl的vector模板类.我需要存储在矩阵中的是布尔值.所以我的问题是,如果使用std::vector<std::vector<bool>* >*产生过多的开销或者有一种更简单的矩阵方式以及如何正确初始化它.

编辑:非常感谢您的快速解答.我刚才意识到,那当然我不需要任何指针.矩阵的大小将在开始时初始化,并且在程序结束之前不会更改.这是一个学校项目,所以如果我写"好"代码会很好,虽然技术上性能不是太重要.使用STL很好.使用像boost这样的东西可能不受欢迎.

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版本以及异常的奇怪用法,但您明白了.

Answer 2

标准向量默认不进行范围检查.

即运算符[]不进行范围检查.

()方法与[]类似,但会进行范围检查.
它将超出范围抛出异常.

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

其他说明:为什么矢量<指针>？
你可以很容易地得到一个vector <Object>.现在无需担心内存管理(即泄漏).

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;

Answer 3

最好的办法:

创建自己的矩阵类,这样就可以控制它的每个方面,包括范围检查.

例如.如果您喜欢"[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;

NB.如果你这样编程,那么C++就像所有其他"安全"语言一样安全.

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::arrayvs 的相对性能的评论中进行了一些讨论之后boost::multi_array,我会指出这个代码是g++ -O3 -DNDEBUG在带有1333MHz DDR3内存的Q9450上使用Debian/Lenny amd64 编译的,而boost::multi_array对于0.6s则需要3.3s boost::array.

#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;
}

Answer 5

还要考虑一下您的图形/矩阵有多大，性能很重要吗？图是静态的，还是可以随着时间的推移而增长，例如通过添加新的边？