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?

On Dec 23, 10:09 pm, Mark <mnbaya...@gmail.com> 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?

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/lib...c4(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 s.

On Dec 23, 10:09 pm, Mark <mnbaya...@gmail.com> 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?

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

On Dec 23, 7:51 pm, johanatan <johana...@gmail.com> wrote:
> On Dec 23, 10:09 pm, Mark <mnbaya...@gmail.com> 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?
>
> 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/lib...c4(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 s.

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

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

On Dec 23, 7:54 pm, johanatan <johana...@gmail.com> wrote:
> On Dec 23, 10:09 pm, Mark <mnbaya...@gmail.com> 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?
>
> 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

On 24 Dec, 03:09, Mark <mnbaya...@gmail.com> 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).

maybe this will :

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

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

Regards,

Andrew Marlow

On Dec 23 2007, 8:18 pm, "Jim Langston" <tazmas...@rocketmail.com>
wrote:
> 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
> tazmas...@rocketmail.com

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.