Re: Sparse Matrix
Mark wrote:
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();
}
--
Jim Langston
tazmaster@rocketmail.com