Структура данных С++ для поиска соседних значений в многомерном массиве

У меня есть проект, в котором я читаю массив с 1 или более измерениями, и для этого проекта мне нужно иметь возможность быстро определять соседей данного элемента. Я не знаю размерности заранее, и я также не знаю заранее величины измерений. Какой была бы лучшая структура данных С++ для хранения этих данных? Коллега рекомендовал вектор векторов векторов . . ., но это кажется невероятно громоздким.


c++ arrays multidimensional-array data-structures neighbours
person Ingulit    schedule 27.09.2013    source источник
comment
Что вы имеете в виду под соседями?   -  person Rafi Kamal    schedule 27.09.2013
comment
Если бы было одно измерение: Индекс x имеет соседей x-1 и x+1 ;;; Два измерения: индекс (x, y) имеет соседей (x-1, y), (x + 1, y), (x, y-1), (x, y + 1) и т. д.   -  person Ingulit    schedule 27.09.2013
comment
И каков ваш вклад в вашу программу? Я предполагаю размерность массива и элементы массива? (например, 2*3 и 1, 2, 3, 4, 5, 6)?   -  person Rafi Kamal    schedule 27.09.2013
comment
Да, за исключением того, что данные не находятся в массиве C++; он находится в проприетарном классе-оболочке, из которого я должен извлечь данные.   -  person Ingulit    schedule 27.09.2013
comment
Вам нужны только ортогональные соседи? (т. е. во 2-м случае их максимум 4) Или вам нужна полная окрестность, где во 2-м случае у вас будет до 8 соседей?   -  person twalberg    schedule 27.09.2013

Ответы (2)


arrow_upward
1
arrow_downward

Если вы знаете адрес какого элемента, для которого вам нужны соседи, не могли бы вы просто выполнить арифметику указателя, чтобы узнать соседей. Например, если p — это расположение элемента, то p— это левый сосед, а p++ — правый сосед.

person aligardezi    schedule 27.09.2013
comment
Я понимаю, о чем вы говорите, но мне нужно выяснить, в чем хранить данные в первую очередь, чтобы что-то подобное было возможно. - person Ingulit; 27.09.2013
comment
Я только что понял, что забыл кое-что упомянуть, поэтому я скопирую то, что прокомментировал выше: данные не в массиве C++; он находится в проприетарном классе-оболочке, из которого я должен извлечь данные. - person Ingulit; 27.09.2013
comment
поэтому я думаю, что вопрос, который нужно задать, заключается в том, какую информацию вам нужно сохранить из класса Wrapper, прежде чем вы сможете принять решение о структуре. - person aligardezi; 27.09.2013
comment
потому что, если вам нужно найти что-то на основе ключа, карта подойдет вам лучше. - person aligardezi; 27.09.2013

arrow_upward
0
arrow_downward

Думайте о своем многомерном массиве как об одномерном массиве. Пусть размерность массива d1 * d2 * ....* dn

Затем выделите память для массива 1D, скажем, A размером d1 * d2 * ....* dn. Например,

int *A = new int[d1 * d2 * ....* dn];

Если вам нужно хранить данные в [i1][i2]...[in]-м индексе, то сохраните в следующем индексе:

A[i1 * (d2*d3*d4.. *dn) + i2 * (d3*d4*....dn) + ..... + in]

Соседними элементами будут:

A[(i1 + 1) * (d2*d3*d4.. *dn) + i2 * (d3*d4*....dn) + ..... + in] 
A[(i1 - 1) * (d2*d3*d4.. *dn) + i2 * (d3*d4*....dn) + ..... + in] 

A[i1 * (d2*d3*d4.. *dn) + (i2 + 1) * (d3*d4*....dn) + ..... + in] 
A[i1 * (d2*d3*d4.. *dn) + (i2 - 1) * (d3*d4*....dn) + ..... + in] 

.............................
A[i1 * (d2*d3*d4.. *dn) + i2 * (d3*d4*....dn) + ..... + (in + 1)] 
A[i1 * (d2*d3*d4.. *dn) + i2 * (d3*d4*....dn) + ..... + (in - 1)]
person Rafi Kamal    schedule 27.09.2013