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

I want to create an adjacency matrix for a graph. Since I read it is not safe to use arrays of the form matrix[x][y] because they don't check for range, I decided to use the vector template class of the stl. All I need to store in the matrix are boolean values. So my question is, if using std::vector<std::vector<bool>* >* produces too much overhead or if there is a more simple way for a matrix and how I can properly initialize it.

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

EDIT: Thanks a lot for the quick answers. I just realized, that of course I don't need any pointers. The size of the matrix will be initialized right in the beginning and won't change until the end of the program. It is for a school project, so it would be good if I write "nice" code, although technically performance isn't too important. Using the STL is fine. Using something like boost, is probably not appreciated.

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

10 个解决方案

#1

Note that also you can use boost.ublas for matrix creation and manipulation and also boost.graph to represent and manipulate graphs in a number of ways, as well as using algorithms on them, etc.

请注意,您也可以使用boost.ublas进行矩阵创建和操作,还可以使用boost.graph以多种方式表示和操作图形,以及在它们上使用算法等。

Edit: Anyway, doing a range-check version of a vector for your purposes is not a hard thing:

编辑:无论如何,为您的目的做一个矢量的范围检查版本并不困难:

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

Note that you would also need to add the const version of the operators, and/or iterators, and the strange use of exceptions, but you get the idea.

请注意,您还需要添加运算符和/或迭代器的const版本以及异常的奇怪用法,但您会明白这一点。

#2

The standard vector does NOT do range checking by default.

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

i.e. The operator[] does not do a range check.

即操作员[]不进行范围检查。

The method at() is similar to [] but does do a range check.
It will throw an exception on out of range.

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

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

Other notes: Why a vector<Pointers> ?
You can quite easily have a vector<Object>. Now there is no need to worry about memory management (i.e. leaks).

其他说明:为什么矢量 <指针> ?你可以很容易地得到一个vector

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

Note: vector<bool> is overloaded and not very efficient (i.e. this structure was optimized for size not speed) (It is something that is now recognized as probably a mistake by the standards committee).

注意:vector 过载并且效率不高(即这个结构针对大小而不是速度进行了优化)(现在标准委员会认为这可能是一个错误)。

If you know the size of the matrix at compile time you could use std::bitset?

如果你在编译时知道矩阵的大小,你可以使用std :: bitset吗?

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

or if it is runtime defined use boost::dynamic_bitset

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

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

All of the above will allow you to do:

以上所有内容都可以让您:

m[6][3] = true;

#3

Best way:

Make your own matrix class, that way you control every last aspect of it, including range checking.

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

eg. If you like the "[x][y]" notation, do this:

例如。如果您喜欢“[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. If you program like this then C++ is just as safe as all those other "safe" languages.

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

#4

If you want 'C' array performance, but with added safety and STL-like semantics (iterators, begin() & end() etc), use boost::array.

如果你想要'C'数组性能,但是增加了安全性和类似STL的语义(迭代器,begin()和end()等),请使用boost :: array。

Basically it's a templated wrapper for 'C'-arrays with some NDEBUG-disable-able range checking asserts (and also some std::range_error exception-throwing accessors).

基本上它是'C'数组的模板包装器,带有一些NDEBUG禁用范围检查断言(以及一些std :: range_error异常抛出访问器)。

I use stuff like

我喜欢这样的东西

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

instead of

float m[4][4];

all the time and it works great (with appropriate typedefs to keep the verbosity down, anyway).

所有的时间它都很有效(使用适当的typedef来保持详细程度,无论如何)。

UPDATE: Following some discussion in the comments here of the relative performance of boost::array vs boost::multi_array, I'd point out that this code, compiled with g++ -O3 -DNDEBUG on Debian/Lenny amd64 on a Q9450 with 1333MHz DDR3 RAM takes 3.3s for boost::multi_array vs 0.6s for boost::array.

更新:在这里关于boost :: array vs boost :: multi_array的相对性能的评论中进行了一些讨论之后,我会指出这个代码,在带有1333MHz的Q9450上用Debian / Lenny amd64上的g ++ -O3 -DNDEBUG编译DDR :: RAM对于boost :: multi_array需要3.3s,对于boost :: array需要0.6s。

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

#5

What I would do is create my own class for dealing with matrices (probably as an array[x*y] because I'm more used to C (and I'd have my own bounds checking), but you could use vectors or any other sub-structure in that class).

我要做的是创建我自己的类处理矩阵(可能作为一个数组[x * y],因为我更习惯于C(我有自己的边界检查),但你可以使用矢量或任何该类中的其他子结构)。

Get your stuff functional first then worry about how fast it runs. If you design the class properly, you can pull out your array[x*y] implementation and replace it with vectors or bitmasks or whatever you want without changing the rest of the code.

首先让你的东西功能,然后担心它的运行速度。如果你正确地设计了类,你可以拉出你的数组[x * y]实现,并用向量或位掩码或任何你想要的替换它而不改变其余的代码。

I'm not totally sure, but I thing that's what classes were meant for, the ability to abstract the implementation well out of sight and provide only the interface :-)

我不完全确定,但我认为类是什么意思,能够很好地抽象实现并只提供接口:-)

#6

In addition to all the answers that have been posted so far, you might do well to check out the C++ FAQ Lite. Questions 13.10 - 13.12 and 16.16 - 16.19 cover several topics related to rolling your own matrix class. You'll see a couple of different ways to store the data and suggestions on how to best write the subscript operators.

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

Also, if your graph is sufficiently sparse, you may not need a matrix at all. You could use std::multimap to map each vertex to those it connects.

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

#7

my favourite way to store a graph is vector<set<int>>; n elements in vector (nodes 0..n-1), >=0 elements in each set (edges). Just do not forget adding a reverse copy of every bi-directional edge.

我最喜欢的存储图形的方法是vector >;向量中的n个元素(节点0..n-1),> =每个集合中的0个元素(边缘)。只是不要忘记添加每个双向边的反向副本。

#8

Consider also how big is your graph/matrix, does performance matter a lot? Is the graph static, or can it grow over time, e.g. by adding new edges?

还要考虑你的图形/矩阵有多大,性能是否重要?图表是静态的,还是可以随着时间的推移而增长,例如通过添加新边缘?

#9

Probably, not relevant as this is an old question, but you can use the Armadillo library, which provides many linear algebra oriented data types and functions.

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

Below is an example for your specific problem:

以下是您的具体问题的示例:

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

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

#10

Mind you std::vector doesn't do range checking either.

记住你std :: vector也不做范围检查。

#1