Как сгладить трехмерный массив, где трехмерное измерение не является фиксированным размером, в одномерный массив?

Question

Для двумерного массива, в котором каждая ячейка (x, y) содержит вектор строк (для простоты) разного размера.

Какой наиболее эффективный способ сгладить эту структуру данных в одномерный массив, т.е. создать функция, инъективно отображающая каждую строку в {1, ..., n}, где n - общее количество строк в структуре данных.

Answer 1

Вы можете сопоставить индекс i, j, k с линейной позицией p в O (1) и обратно в O (log N), где N - это размер 2D-массива, а не общее количество строк.

Во-первых, давайте рассматривать ваш 2D-массив как 1D, так как это значительно упрощает задачу. Индекс i - это индекс вектора в массиве. Индекс k - это позиция строки в векторе. N - размер массива.

Вы можете создать массив целых чисел (например, size_t), который содержит отсчитываемую от нуля кумулятивную сумму всех длин векторов:

lengths = array[N]
lengths[0] = 0
for(i = 1 to N)
    lengths[i] = lengths[i - 1] + size(array[i - 1])

Если хотите, вы можете вычислить общее количество строк как total = lengths[N - 1] + size(array[N - 1]).

Теперь для данной строки с индексом i, k позиция в расширенном массиве равна

p = lengths[i] + k

Учитывая позицию p, вы сопоставляете ее с i, k с помощью алгоритма деления пополам (двоичный поиск, который возвращает индекс левой границы, если точное совпадение не найдено):

i = bisect(lengths, p)
k = p - lengths[i]

Bisection - это упрощенный двоичный поиск, поэтому O (log N).

Все это работает очень хорошо, пока вы не начнете расширять свои векторы. В этот момент вставка и удаление становятся операциями O (N), поскольку вам нужно увеличивать или уменьшать все совокупные суммы после точки вставки. Для вставки:

array[i][k].push(a_string)
for(z = i + 1 to N)
    lengths[z]++

И для удаления:

array[i][k].pop()
for(z = i + 1 to N)
    lengths[z]--

Кстати, если вы все же хотите использовать индексы x, y для массива, вы можете конвертировать между линейным индексом i из lengths и обратно, используя

i = x + C * y
x = i % C
y = i / C

Здесь C - это количество столбцов в вашем массиве. Вы можете легко обобщить это на любое количество измерений.

Answer 2

Вам не подходит простой прямой путь?

#include <vector>
#include <string>

int main() {
        std::vector<std::string> omg[3][4];
        std::vector<std::string> rv;
        for(auto const &row: omg) {
                for(auto const &cell: row) {
                        for(auto const &str: cell) {
                                rv.push_back(str);
                        }
                }
        }
}