Two-dimentional grid of objects that can extend in any direction C++

What is the best method to create a two-dimensional grid of objects that can extend dynamically in any direction, without allocating memory in the empty parts of conca开发者_开发知识库ve shapes?

I was thinking of having the class contain data members that pointed toward the adjacent objects (one for North, East, South, and West), but this doesn't seem like it would be the best method, and it also lacks the ability to refer to a certain square with an absolute value (i.e. (6,-5)).

If the question seems confusing ask and I'll try to explain the problem better.

---

Just throwing an idea out here:

Take a key/value container, say std::map, or a self-balancing binary-search tree or similar.

Use a 64 bit integer as the key. Use the high 32 bits as an X coordinate, the low 32 bits as a Y coordinate. Thus to find point (x, y) you look up (((uint64_t)x) << 32) | y.

---

Perhaps store a std::deque of std::deque's, where each interior deqeue corresponds to a row in the grid. You can then store the first x-coordinate that's used for each individual row. Deques can efficiently grow from the front or the back.

Note that it wouldn't handle gaps/holes very well.

Example of lookup:

If you want the element at (4, 2), you would look at the beginning y-coordinate. Suppose it's -3. Then, rows[0] would correspond to y = -3, and rows[5] would correspond to y = 2.

Suppose rows[5] has beginning x-coordinate 2. Then rows[5].cols[0] would represent whatever's at (2, 2). We would want rows[5].cols[2] for the object at (4, 2).

---

I would recommend

const int region_size = 16; //powers of two only!  4, 8, 16, 32, 64, etc
const int region_minor = region_size-1;
const int region_major = ~region_minor;
typedef std::array<region_size, std::array<region_size, point> > region; //a 16 by 16 region
std::map<std::pair<int, int>, region> world;

point& getPoint(int x, int y) {
    std::pair<int,int> major_coords(x&region_major, y&region_major);
    region &r = world[major_coords]; //get region
    return r[x&region_minor,y&region_minor]; //return the point in this region
}
//This creates points/regions as they're needed as well.

This allows infinite expansion in all dimensions (including negative, that's hard to do with arrays), and gaps. Depending on what you're doing, you usually want to touch several points in an area at once, and if you have a map of points, that's a lot of extra overhead in both memory and time. If you make a map of small regions, it uses less memory and time.

---

How about a two level structure: a matrix with pointers to other matrices, you allocate the smaller matrices when you need them. Here's an example for 1000x1000 tiles, each of size 100x100. The matrices are linearized to simplify the memory allocation. You could make this a matrix of matrices of matrices if you want to have even better granularity.

#define N 100
#define M 1000
using namespace std;
int *mat[M*M];

void set(int x,int y,int value)
{ int hx=x/N;
  int hy=y/N;
  int lx=x%N;
  int ly=y%N;

  if(mat[hx+hy*N]==NULL)
  { mat[hx+hy*N]=new int[N*N];
  }
  mat[hx+hy*N][lx+ly*N]=value; 
}

int get(int x,int y)
{ int hx=x/N;
  int hy=y/N;
  int lx=x%N;
  int ly=y%N;
  if(mat[hx+hy*N]==NULL)
  { return -1;
  }
  return mat[hx+hy*N][lx+ly*N]; 
}

Making the N, M values 2^k you can avoid costly division and modulo operations by replacing them with bit shifting: x/128 is x>>7, x*128 is x<<7 and x%128 is x&0x7F. (not sure if the compiler will optimise x/128 with x>>7 internally)