CODEWITHSUNDEEP
c++data-structuresstlgraphmatrix
Lucas
Lucas

Reputation: 14129

A proper way to create a matrix in 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.

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.

Upvotes: 35

Views: 108256

Answers (10)

Diego Sevilla
Diego Sevilla

Reputation: 29001

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.

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.

Upvotes: 25

shoosh
shoosh

Reputation: 78914

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

Upvotes: 1

OverInflatedWalrus
OverInflatedWalrus

Reputation: 189

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.

Upvotes: 3

Devesh Khandelwal
Devesh Khandelwal

Reputation: 398

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.

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;

Upvotes: 1

Loki Astari
Loki Astari

Reputation: 264331

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).

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).

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

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

or if it is runtime defined use boost::dynamic_bitset

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

All of the above will allow you to do:

m[6][3] = true;

Upvotes: 11

timday
timday

Reputation: 24902

If you want 'C' array performance, but with added safety and STL-like semantics (iterators, begin() & end() etc), use 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).

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).

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.

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

Upvotes: 5

Jimmy J
Jimmy J

Reputation: 1985

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:

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.

Upvotes: 15

Michael Kristofik
Michael Kristofik

Reputation: 35178

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.

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.

Upvotes: 3

paxdiablo
paxdiablo

Reputation: 881103

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).

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.

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 :-)

Upvotes: 4

siddhadev
siddhadev

Reputation: 16621

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?

Upvotes: 1

Related Questions