Sparse Matrix

[Mark]

I'm trying to figure out the best way to go about doing this.
I have a "map" for a game, which I'd like to store in a matrix. Some
cells will be empty (NULL), and some will hold objects.
I need a matrix so that I can quickly find neighboring cells.
However, when create this map, I don't know what size it is going to
be, so it needs to be expandable. I also don't know which direction
it's going to grow in, so starting at [0][0] and expanding as
necessary won't work either, because I may later need to use [-1][0].
I don't really care if the indices are re-written if I try to access a
negative index. (ie, if I try to insert something into [-1][0], if it
increased all the indices by 1 so it didn't have a negative index,
that would be fine).
I just need something that's simple to implement, and preferably has
little overhead. I was contemplating using something like
std::vector<vector<myClass> > but that wouldn't fill the negative
index requirement, would it? Are there any other suggestions?

 

[johanatan]

I'm trying to figure out the best way to go about doing this.
I have a "map" for a game, which I'd like to store in a matrix. Some
cells will be empty (NULL), and some will hold objects.
I need a matrix so that I can quickly find neighboring cells.
However, when create this map, I don't know what size it is going to
be, so it needs to be expandable. I also don't know which direction
it's going to grow in, so starting at [0][0] and expanding as
necessary won't work either, because I may later need to use [-1][0].
I don't really care if the indices are re-written if I try to access a
negative index. (ie, if I try to insert something into [-1][0], if it
increased all the indices by 1 so it didn't have a negative index,
that would be fine).
I just need something that's simple to implement, and preferably has
little overhead. I was contemplating using something like
std::vector<vector<myClass> > but that wouldn't fill the negative
index requirement, would it? Are there any other suggestions?

You could build your own dynamically sizing array (or derive of vector
and override) and let your base ptr point to the middle of the array
(then you could negative index up to numElementsOf(array)/2.

See:
http://msdn2.microsoft.com/en-us/library/59682zc4(VS.80).aspx

I'm sure if you dig around the net, you can find an automatically
increasing array (dynarray) or you could use CArray in MFC or as
mentioned previously std::vector (with derivation).

Hope that helps.

 

[johanatan]

I'm trying to figure out the best way to go about doing this.
I have a "map" for a game, which I'd like to store in a matrix. Some
cells will be empty (NULL), and some will hold objects.
I need a matrix so that I can quickly find neighboring cells.
However, when create this map, I don't know what size it is going to
be, so it needs to be expandable. I also don't know which direction
it's going to grow in, so starting at [0][0] and expanding as
necessary won't work either, because I may later need to use [-1][0].
I don't really care if the indices are re-written if I try to access a
negative index. (ie, if I try to insert something into [-1][0], if it
increased all the indices by 1 so it didn't have a negative index,
that would be fine).
I just need something that's simple to implement, and preferably has
little overhead. I was contemplating using something like
std::vector<vector<myClass> > but that wouldn't fill the negative
index requirement, would it? Are there any other suggestions?

Another option would be an std::map with the indices you choose
(including negative):

std::map< int, std::map< int, yourClass >>

it should perform fairly well as it is an highly optimized balanced
tree of some sort (red/black maybe??).

 

[Mark]

I'm trying to figure out the best way to go about doing this.
I have a "map" for a game, which I'd like to store in a matrix. Some
cells will be empty (NULL), and some will hold objects.
I need a matrix so that I can quickly find neighboring cells.
However, when create this map, I don't know what size it is going to
be, so it needs to be expandable. I also don't know which direction
it's going to grow in, so starting at [0][0] and expanding as
necessary won't work either, because I may later need to use [-1][0].
I don't really care if the indices are re-written if I try to access a
negative index. (ie, if I try to insert something into [-1][0], if it
increased all the indices by 1 so it didn't have a negative index,
that would be fine).
I just need something that's simple to implement, and preferably has
little overhead. I was contemplating using something like
std::vector<vector<myClass> > but that wouldn't fill the negative
index requirement, would it? Are there any other suggestions?

You could build your own dynamically sizing array (or derive of vector
and override) and let your base ptr point to the middle of the array
(then you could negative index up to numElementsOf(array)/2.

See:http://msdn2.microsoft.com/en-us/library/59682zc4(VS.80).aspx

I'm sure if you dig around the net, you can find an automatically
increasing array (dynarray) or you could use CArray in MFC or as
mentioned previously std::vector (with derivation).

Hope that helps.

That link you pointed me to.. it's interesting. Never thought about
doing something like that before. Maybe I'll try it out, thanks!

 

[Jim Langston]

I'm trying to figure out the best way to go about doing this.
I have a "map" for a game, which I'd like to store in a matrix. Some
cells will be empty (NULL), and some will hold objects.
I need a matrix so that I can quickly find neighboring cells.
However, when create this map, I don't know what size it is going to
be, so it needs to be expandable. I also don't know which direction
it's going to grow in, so starting at [0][0] and expanding as
necessary won't work either, because I may later need to use [-1][0].
I don't really care if the indices are re-written if I try to access a
negative index. (ie, if I try to insert something into [-1][0], if it
increased all the indices by 1 so it didn't have a negative index,
that would be fine).
I just need something that's simple to implement, and preferably has
little overhead. I was contemplating using something like
std::vector<vector<myClass> > but that wouldn't fill the negative
index requirement, would it? Are there any other suggestions?

std::vector<std::vector<cMyClass> > would work as long as you consider that
0,0 could actually be 1,2 or such. In which case I'd probably wrap the
std::vector in a class.

Something like this although I just threw this together and you should
probably check for the size in operator() and add if you want etc...

#include <string>
#include <iostream>
#include <vector>

class Cell
{
public:
int SomeData;
};

class GameMapClass
{
public:
typedef std::vector< std::vector< Cell > > MapDataType;
GameMapClass( int MinCol, int MinRow, int MaxCol, int MaxRow ):
MinCol_( MinCol ), MaxCol_( MaxCol ),
MinRow_( MinRow ),
MaxRow_( MaxRow )
{
std::vector<Cell> Row( MaxCol_ - MinCol_ + 1 );
for ( int i = MinRow; i < MaxRow + 1; ++i )
{
Data_.push_back( Row );
}
}

Cell& operator()( int Col, int Row )
{
return Data_[Row - MinRow_][Col - MinCol_];
}

void Dump()
{
for ( std::vector< std::vector<Cell> >::iterator Rit =
Data_.begin(); Rit != Data_.end(); ++Rit )
{
for ( std::vector<Cell>::iterator Cit = Rit->begin(); Cit !=
Rit->end(); ++Cit )
{
std::cout << Cit->SomeData << " ";
}
std::cout << "\n";
}
}
private:
MapDataType Data_;
int MinRow_;
int MaxRow_;
int MinCol_;
int MaxCol_;
};

int main()
{
int MapMinRow = -2;
int MapMinCol = -4;
int MapMaxRow = 10;
int MapMaxCol = 12;

GameMapClass GameMap( MapMinCol, MapMinRow, MapMaxCol, MapMaxRow );
for ( int Row = MapMinRow; Row <= MapMaxRow; ++Row )
for ( int Col = MapMinCol; Col <= MapMaxCol; ++Col )
{
GameMap( Col, Row ).SomeData = Col;
}
GameMap.Dump();
std::cout << "\n";
GameMap(0, 0).SomeData = 999;
GameMap.Dump();

}

 

[Mark]

I'm trying to figure out the best way to go about doing this.
I have a "map" for a game, which I'd like to store in a matrix. Some
cells will be empty (NULL), and some will hold objects.
I need a matrix so that I can quickly find neighboring cells.
However, when create this map, I don't know what size it is going to
be, so it needs to be expandable. I also don't know which direction
it's going to grow in, so starting at [0][0] and expanding as
necessary won't work either, because I may later need to use [-1][0].
I don't really care if the indices are re-written if I try to access a
negative index. (ie, if I try to insert something into [-1][0], if it
increased all the indices by 1 so it didn't have a negative index,
that would be fine).
I just need something that's simple to implement, and preferably has
little overhead. I was contemplating using something like
std::vector<vector<myClass> > but that wouldn't fill the negative
index requirement, would it? Are there any other suggestions?

Another option would be an std::map with the indices you choose
(including negative):

std::map< int, std::map< int, yourClass >>

it should perform fairly well as it is an highly optimized balanced
tree of some sort (red/black maybe??).

Thanks for the suggestion

 

[apm35]

I'm trying to figure out the best way to go about doing this.
I have a "map" for a game, which I'd like to store in a matrix. Some
cells will be empty (NULL), and some will hold objects.
I need a matrix so that I can quickly find neighboring cells.
However, when create this map, I don't know what size it is going to
be, so it needs to be expandable. I also don't know which direction
it's going to grow in, so starting at [0][0] and expanding as
necessary won't work either, because I may later need to use [-1][0].
I don't really care if the indices are re-written if I try to access a
negative index. (ie, if I try to insert something into [-1][0], if it
increased all the indices by 1 so it didn't have a negative index,
that would be fine).

maybe this will help:

http://math.nist.gov/sparselib++/

It is for compute-intensive jobs but hopefully it will be of use.

Regards,

Andrew Marlow

 

[Mark]

I'm trying to figure out the best way to go about doing this.
I have a "map" for a game, which I'd like to store in a matrix. Some
cells will be empty (NULL), and some will hold objects.
I need a matrix so that I can quickly find neighboring cells.
However, when create this map, I don't know what size it is going to
be, so it needs to be expandable. I also don't know which direction
it's going to grow in, so starting at [0][0] and expanding as
necessary won't work either, because I may later need to use [-1][0].
I don't really care if the indices are re-written if I try to access a
negative index. (ie, if I try to insert something into [-1][0], if it
increased all the indices by 1 so it didn't have a negative index,
that would be fine).
I just need something that's simple to implement, and preferably has
little overhead. I was contemplating using something like
std::vector<vector<myClass> > but that wouldn't fill the negative
index requirement, would it? Are there any other suggestions?

std::vector<std::vector<cMyClass> > would work as long as you consider that
0,0 could actually be 1,2 or such. In which case I'd probably wrap the
std::vector in a class.

Something like this although I just threw this together and you should
probably check for the size in operator() and add if you want etc...

#include <string>
#include <iostream>
#include <vector>

class Cell
{
public:
int SomeData;

};

class GameMapClass
{
public:
typedef std::vector< std::vector< Cell > > MapDataType;
GameMapClass( int MinCol, int MinRow, int MaxCol, int MaxRow ):
MinCol_( MinCol ), MaxCol_( MaxCol ),
MinRow_( MinRow ),
MaxRow_( MaxRow )
{
std::vector<Cell> Row( MaxCol_ - MinCol_ + 1 );
for ( int i = MinRow; i < MaxRow + 1; ++i )
{
Data_.push_back( Row );
}
}

Cell& operator()( int Col, int Row )
{
return Data_[Row - MinRow_][Col - MinCol_];
}

void Dump()
{
for ( std::vector< std::vector<Cell> >::iterator Rit =
Data_.begin(); Rit != Data_.end(); ++Rit )
{
for ( std::vector<Cell>::iterator Cit = Rit->begin(); Cit !=
Rit->end(); ++Cit )
{
std::cout << Cit->SomeData << " ";
}
std::cout << "\n";
}
}
private:
MapDataType Data_;
int MinRow_;
int MaxRow_;
int MinCol_;
int MaxCol_;

};

int main()
{
int MapMinRow = -2;
int MapMinCol = -4;
int MapMaxRow = 10;
int MapMaxCol = 12;

GameMapClass GameMap( MapMinCol, MapMinRow, MapMaxCol, MapMaxRow );
for ( int Row = MapMinRow; Row <= MapMaxRow; ++Row )
for ( int Col = MapMinCol; Col <= MapMaxCol; ++Col )
{
GameMap( Col, Row ).SomeData = Col;
}
GameMap.Dump();
std::cout << "\n";
GameMap(0, 0).SomeData = 999;
GameMap.Dump();

}

Thank you for going through the trouble of writing all that out! I
think something like this would probably be the best approach for me.