30

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

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

4

10 回答 10

25

请注意，您还可以使用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 版本的运算符和/或迭代器，以及异常的奇怪用法，但您明白了。

于 2009-03-06T11:34:48.570 回答
13

最好的办法：

制作你自己的矩阵类，这样你就可以控制它的每一个方面，包括范围检查。

例如。如果您喜欢“[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++ 与所有其他“安全”语言一样安全。

于 2009-03-06T11:55:31.670 回答
10

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

即 operator[] 不做范围检查。

at() 方法与 [] 类似，但会进行范围检查。
它会在超出范围时抛出异常。

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

其他说明：为什么是 vector<Pointers> ？
你可以很容易地拥有一个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;
于 2009-03-06T12:40:53.480 回答
5

如果您想要“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在此处对vs的相对性能的评论中进行了一些讨论后boost::multi_array，我要指出，g++ -O3 -DNDEBUG在 Debian/Lenny amd64 上编译的这段代码，在 1333MHz DDR3 RAM 的 Q9450 上需要 3.3 秒，boost::multi_array而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;
}
于 2009-03-06T13:51:55.293 回答
4

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

先让你的东西发挥作用，然后再担心它的运行速度。如果你正确地设计了这个类，你可以取出你的 array[x*y] 实现并将其替换为向量或位掩码或任何你想要的东西，而无需更改其余代码。

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

于 2009-03-06T11:41:47.413 回答
3

除了到目前为止已发布的所有答案之外，您最好查看C++ FAQ Lite。问题13.10 - 13.12和16.16 - 16.19涵盖了与滚动您自己的矩阵类相关的几个主题。您将看到几种不同的存储数据的方法以及如何最好地编写下标运算符的建议。

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

于 2009-03-06T12:16:52.213 回答
3

我最喜欢的存储图表的方式是vector<set<int>>；向量中的 n 个元素（节点 0..n-1），>=0 每个集合中的元素（边）。只是不要忘记添加每个双向边缘的反向副本。

于 2017-02-15T16:29:56.557 回答
1

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

于 2009-03-06T11:32:39.450 回答
1

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

于 2009-03-06T11:37:47.500 回答
1

可能不相关，因为这是一个老问题，但您可以使用Armadillo库，它提供了许多面向线性代数的数据类型和函数。

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

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

// In C++98
Mat<bool> matrix;
matrix << true << true << endr
       << false << false << endr;
于 2015-11-01T09:47:35.683 回答