Двумерная сетка объектов, которая может расширяться в любом направлении C ++

Question

Каков наилучший метод для создания двумерной сетки объектов, которая может динамически расширяться в любом направлении, не выделяя память в пустых частях вогнутых фигур?

Я думал о том, чтобы класс содержал элементы данных, указывающие на смежные объекты (один для Севера, Востока, Юга и Запада), но это не похоже на лучший метод, и в нем также отсутствует способность ссылаться на определенный квадрат с абсолютным значением (т. е. (6, -5)).
Если вопрос кажется запутанным, задайте вопрос, и я постараюсь объяснить проблему лучше.

Answer 1

Просто выдвиньте идею здесь:

Возьмите контейнер ключ / значение, скажем std::map, или самобалансирующееся дерево бинарного поиска или подобное.

Используйте 64 битцелое число в качестве ключа.Используйте старшие 32 бита в качестве координаты X, младшие 32 бита в качестве координаты Y.Таким образом, чтобы найти точку (x, y), вы смотрите вверх (((uint64_t)x) << 32) | y.

Answer 2

Я бы порекомендовал

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.

Это допускает бесконечное расширение во всех измерениях (включая отрицательные, что трудно сделать с массивами) и пробелы. В зависимости от того, что вы делаете, вы обычно хотите прикоснуться к нескольким точкам в области одновременно, и если у вас есть карта точек, это много лишних затрат памяти и времени. Если вы делаете карту небольших регионов, она использует меньше памяти и времени.

Answer 3

Возможно хранить std :: deque из std :: deque's, где каждому внутреннему запросу соответствует строка в сетке. Затем вы можете сохранить первую x-координату, которая используется для каждой отдельной строки. Deques может эффективно расти спереди или сзади.

Обратите внимание, что он не будет хорошо обрабатывать пробелы / отверстия.

Пример поиска:

Если вы хотите, чтобы элемент в (4, 2), вы посмотрели бы на начальную y-координату. Предположим, что это -3. Тогда строки [0] соответствуют y = -3, а строки [5] соответствуют y = 2.

Предположим, что строки [5] имеют начальную x-координату 2. Тогда строки [5] .cols [0] будут представлять все, что находится в (2, 2). Мы бы хотели строки [5] .cols [2] для объекта в (4, 2).

Answer 4

Как насчет двухуровневой структуры: матрицы с указателями на другие матрицы, вы выделяете меньшие матрицы, когда они вам нужны. Вот пример для плитки размером 1000x1000, каждая размером 100x100. Матрицы линеаризуются для упрощения выделения памяти. Вы можете сделать это матрицей матриц матриц, если хотите иметь еще лучшую гранулярность.

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

Делая значения N, M 2^k, вы можете избежать дорогостоящих операций деления и модуляции, заменив их сдвигом битов: x/128 равно x>>7, x*128 равно x<<7 и x%128 x&0x7F (не уверен, что компилятор оптимизирует x/128 с x>>7 внутри)