Создание n-мерного динамического массива

@Валерий_ · Регистрация: 28.10.2014

Студворк — интернет-сервис помощи студентам

Ломаю голову над реализацией функции, которая создаёт n-мерный динамический массив. Возможно ли это вообще?
Для меня проблема в количестве звёздочек, то есть сколько звёздочек у первого указателя, такая и размерность массива, но эти звёзочки просто так не поставишь.
Заранее спасибо за Ваши идеи и советы.

@QuakerRUS · 24.11.2017, 13:12

Pechkin80, я так понимаю, пока не закончатся звездочки.

C++
1
{ typedef typename NDimensionalArray<T, N - 1>::type * type; };

@Pechkin80 · 24.11.2017, 13:14

QuakerRUS, К этой рекурсии вопросов нет, но она никак не связана с функцией выделения памяти.

C++
1
2
3
4
5
6
7
template<typename T>
void initializeNDimensionalArray(T *& arr, size_t N)
{
    arr = new T[N];
    for (size_t it = 0; it < N; ++it)
        initializeNDimensionalArray(arr[it], N);
}

которая тоже рекурсивна.

@QuakerRUS · 24.11.2017, 13:17

Pechkin80, почему не связана? а как же

C++
1
arr = new T[N];

@Pechkin80 · 24.11.2017, 13:19

QuakerRUS, Здесь у N другой смысл. Если в шаблонной рекурсии это размерность, то тут это размер. А размерность задаётся самой рекурсией функции, которая не имеет условия окончания рекурсии.
Получается выделение памяти для массива конечного размера и бесконечной размерности.

@QuakerRUS · 24.11.2017, 13:21

Pechkin80, пока есть звездочки выполняется это

C++
1
2
3
4
5
6
7
template<typename T>
void initializeNDimensionalArray(T *& arr, size_t N)
{
    arr = new T[N];
    for (size_t it = 0; it < N; ++it)
        initializeNDimensionalArray(arr[it], N);
}

Когда звездочки заканчиваются, это (конец рекурсии)

C++
1
2
3
template<typename T>
void initializeNDimensionalArray(T &, size_t)
{}

@Pechkin80 · 24.11.2017, 13:29

QuakerRUS, Звёздочки заканчиваются в шаблонной рекурсии, а тут рекурсия функции.

@QuakerRUS · 24.11.2017, 13:31

Pechkin80, каждый рекурсивный вызов передает на одну звездочку меньше.

Вот тут на одну звездочку больше (смотрим первый аргумент)

C++
1
void initializeNDimensionalArray(T *& arr, size_t N)

В рекурсивном вызове на одну звездочку меньше, так как нет звездочки как в аргументе выше.

C++
1
initializeNDimensionalArray(arr[it], N);

@Pechkin80 · 24.11.2017, 13:34

QuakerRUS, массив всегда неявно преобразовывается в указатель на тип при передачи в качестве аргумента, а для тела функции количество звёздочек неизвестно. Оно его не в состоянии определить.

@QuakerRUS · 24.11.2017, 13:53

Pechkin80, давай на примере.

C++
1
2
3
typedef NDimensionalArray<int, 3>::type ThreeDimensionalArray;
static_assert(std::is_same<ThreeDimensionalArray, int***>::value, "three");
EighteenDimensionalArray arr;

Это аналогично int ***arr, не будем подробно рассматривать.

Далее создаются следующие экземпляры шаблонов

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void initializeNDimensionalArray(int *** arr, size_t N)
{
    arr = new int **[N];
    assert(arr != nullptr);
 
    for (size_t it = 0; it < N; ++it)
        initializeNDimensionalArray(arr[it], N);
}
 
void initializeNDimensionalArray(int ** arr, size_t N)
{
    arr = new int *[N];
    assert(arr != nullptr);
 
    for (size_t it = 0; it < N; ++it)
        initializeNDimensionalArray(arr[it], N);
}
 
void initializeNDimensionalArray(int * arr, size_t N)
{
    arr = new int [N];
    assert(arr != nullptr);
 
    for (size_t it = 0; it < N; ++it)
        initializeNDimensionalArray(arr[it], N);
}

Добавлено через 10 минут
Каждый рекурсивный вызов имеет на одну звездочку меньше. Когда звездочки кончаются, вызывается следующий экземпляр шаблона, который заканчивает рекурсию.

C++
1
2
void initializeNDimensionalArray(int &, size_t)
{}

@COKPOWEHEU · 24.11.2017, 13:58

Сообщение от QuakerRUS

Выложу и пример работы алгоритма от COKPOWEHEU

Да, только именам переменной и макроса лучше бы все-таки различаться.
И, между прочим, обращение к вложенному массиву выглядит не лучше

C
1
arr[i][i][i][i][i][i][i][i][i][i][i][i][i][i][i][i][i][i]=i;

Но это уже, конечно, не недостатки того или иного способа, а сама идея создания 18-мерного массива.
.
Кстати, еще одно преимущество линейного способа - заполнение какими-то числами (bzero / memset), копирование (memcpy) и т.п.
Ну и накладные расходы на создание-удаление вложенного массива значительно больше: для P-мерного массива по N элементов это S = (1-N^P)/(1-N) вызовов new / delete. Для примера Байта, N=2, P=18, тогда S = 262143 вызова. По 8 байт на каждый указатель это 2 мегабайта памяти только накладных расходов, не говоря уж о данных, которых будет sizeof(data)*N^P, то есть 262144*sizeof(data). Так что даже для double (8 байт) это те же 2 мегабайта, столько же сколько занимает служебная информация об указателях на указатели.

Сообщение от Байт

Основная идея изложена уважаемым COKPOWEHEU, в посте 2 - представить вашу чудовищную матрицу в виде линейного массива.

Примерно так. Просто мне не нравится сама идея использовать массивы массивов вместо простой интерпретации линейного, как для статических. В принципе, после расчета выше, когда служебная информация занимает столько же места как и данные, я только утвердился в своем мнении. Хотя произвольный доступ к линейному массиву и может оказаться медленнее.

@TRam_ · 24.11.2017, 14:00

Правда n-мерность динамически задавать для такого массива не получится. Правда тогда и обращение к элементу массива придётся переделывать, так что может менять мерность и вовсе бессмысленно

@QuakerRUS · 24.11.2017, 14:48

Pechkin80, и вообще это не совсем рекурсия. Каждая функция имеет свой экземпляр, так как типы первого аргумента в каждом экземпляре шаблона различаются.

Добавлено через 17 минут

массив всегда неявно преобразовывается в указатель на тип при передачи в качестве аргумента

Pechkin80, и, да, передается не массив, а элемент массива. Например у массива int *** элемент будет иметь тип int **, а у массива int ** элемент будет иметь тип int *

@COKPOWEHEU · 24.11.2017, 14:50

QuakerRUS, можно и в виде рекурсии сделать, тогда передавать размерность явным образом. Это немного уменьшит объем бинарника, возможно повысит читаемость, но кардинально ничего не изменит.

@QuakerRUS · 24.11.2017, 15:02

COKPOWEHEU, думаю, что можно, если, например, передавать в нее информацию о вложенности.

@COKPOWEHEU · 24.11.2017, 15:29

C
1
2
3
4
5
6
void next_level(void **data, int size, int pwr){
  int i;
  if(pwr <=0)return;
  *data = malloc(size);
  for(i=0; i<size; i++) next_level(&data[i], size, pwr-1);
}

Псевдокод. Над выделением памяти под тип данных или над синтаксисом не думал. Но, надеюсь, суть понятна.

@QuakerRUS · 24.11.2017, 15:55

COKPOWEHEU, да, я так примерно себе и представлял. Используем указатели void * (и void **) и передаем информацию о вложенности (pwr-1).

@COKPOWEHEU · 24.11.2017, 16:07

Только это не отменяет двух фактов:
1. массив 18-й степени вложенности это извращение
2. создание такого извращения методом вложенных массивов крайне расточительно
Мне даже любопытно узнать для чего такое может пригодиться.

@TRam_ · 24.11.2017, 16:15

Сообщение от COKPOWEHEU

для чего такое может пригодиться

ну например если в каждом бите "адреса" заложен индекс в очередном измерении...

Добавлено через 1 минуту
Этакое статическое бинарное дерево.

@COKPOWEHEU · 24.11.2017, 16:36

но это ведь не учитывает узлы - только листья. Насколько я знаю, статические бинарные деревья кодируют немного по-другому
(a)(aa)(ab)(aaa)(aab)(aba)(abb)(aaaa)(aa ab)(aaba)(aabb)(abaa)(abab)(abba)(abbb)
в виде линейного массива, кекеке.
то есть для i-го узла дочерними будут [2i+1] и [2i+2]

@TRam_ · 24.11.2017, 16:42

Сообщение от COKPOWEHEU

но это ведь не учитывает узлы - только листья

Если массив с расчётом индекса - да. Если шаблонный класс - его экземпляры очередного уровня и будут узлами.

И да, если "длина массива" не два, то получится не бинарное, а size-нарное дерево. Фиксированной глубины, определяемой размерностью.

Новые блоги и статьи Все статьи Все блоги /
Вступаем в новую фазу генерации favicons, векторную. russiannick 02.11.2026 Теперь нет нужды скрывать что используется простой svg. Исходный код изображения помещаем в поле и жмем кнопку. Исходник преобразуется в вид корректный для помещения в favicon или в url(). Нажатие. . .	Генератор паролей (вариант №4) Maks 01.11.2026 После публикации 3-го варианта генератора паролей, разослал его своим коллегам (с целью оценки), в итоге были получены следующие рекомендации: 1. Вернуть возможность использования знаков \| 1 l I;. . .	Генератор паролей (вариант №3) Maks 30.10.2026 Финальная версия генератора паролей 1С. Доработка решения в этот раз коснулась только визуальной части, а именно, добавлен реквизит ДопПараметры (тип Булево), который скрывает/ отображает реквизиты:. . .	Магическое мышление и магия, современная наука не отличима от магии (говорит ИИ Джемени) zorxor 30.10.2026 Джемени, расскажи, пожалуйста, что такое магическое мышление, что такое магия, почему современная наука чем-то напоминает магию? Фраза «Любая достаточно развитая технология неотличима от магии». . .
За какое время ИИ может подобрать пароль по хешу (рассказывает Джемени ИИ) zorxor 30.10.2026 Расскажи, Джемени, если известен хэш МД5, например, за сколько ИИ сможет подобрать соответствующий пароль? Искусственный интеллект (ИИ) может подобрать простой или средний по сложности пароль по. . .	Кто убил Suno? Почему наше солнышко погасло? (диалог с ИИ Джемени) zorxor 30.10.2026 Как убивали Suno. Хронология. «Убийство» музыкальной нейросети Suno — это затяжной процесс, в котором технологический хайп стартапа разбился о жесткую реальность судебных исков от гигантов. . .	Генератор паролей (вариант №2) Maks 30.10.2026 Обновленная версия ранее созданной обработки. Добавлены следующие реквизиты типа Булево: - Буквы; - Цифры; - Символы. Изменена логика команды "Сгенерировать" и процедуры "ПриОткрытии":. . .	Генератор паролей (вариант №1) Maks 29.10.2026 Реализация из решения ниже выполнена исключительно по моей инициативе, дабы облегчить себе работу в создании паролей для администрируемых мною сервисов и пользователей. Самым главным критерием для. . .

@Валерий_ 2 / 1 / 1 Регистрация: 28.10.2014 Сообщений: 129

	Создание n-мерного динамического массива 21.11.2017, 21:40. Показов 10019. Ответов 55 Метки нет (Все метки) Ломаю голову над реализацией функции, которая создаёт n-мерный динамический массив. Возможно ли это вообще? Для меня проблема в количестве звёздочек, то есть сколько звёздочек у первого указателя, такая и размерность массива, но эти звёзочки просто так не поставишь. Заранее спасибо за Ваши идеи и советы. 0

@Pechkin80 21 / 19 / 7 Регистрация: 14.03.2014 Сообщений: 249
	24.11.2017, 13:19
	QuakerRUS, Здесь у N другой смысл. Если в шаблонной рекурсии это размерность, то тут это размер. А размерность задаётся самой рекурсией функции, которая не имеет условия окончания рекурсии. Получается выделение памяти для массива конечного размера и бесконечной размерности. 0

@Pechkin80 21 / 19 / 7 Регистрация: 14.03.2014 Сообщений: 249
	24.11.2017, 13:29
	QuakerRUS, Звёздочки заканчиваются в шаблонной рекурсии, а тут рекурсия функции. 0

@Pechkin80 21 / 19 / 7 Регистрация: 14.03.2014 Сообщений: 249
	24.11.2017, 13:34
	QuakerRUS, массив всегда неявно преобразовывается в указатель на тип при передачи в качестве аргумента, а для тела функции количество звёздочек неизвестно. Оно его не в состоянии определить. 0

@TRam_ зомбяк 1585 / 1219 / 345 Регистрация: 14.05.2017 Сообщений: 3,940
	24.11.2017, 14:00
	Правда n-мерность динамически задавать для такого массива не получится. Правда тогда и обращение к элементу массива придётся переделывать, так что может менять мерность и вовсе бессмысленно 0

@COKPOWEHEU 4150 / 2728 / 433 Регистрация: 09.09.2017 Сообщений: 12,099
	24.11.2017, 14:50
	QuakerRUS, можно и в виде рекурсии сделать, тогда передавать размерность явным образом. Это немного уменьшит объем бинарника, возможно повысит читаемость, но кардинально ничего не изменит. 0

@QuakerRUS 1469 / 1010 / 456 Регистрация: 30.10.2017 Сообщений: 2,799
	24.11.2017, 15:02
	COKPOWEHEU, думаю, что можно, если, например, передавать в нее информацию о вложенности. 0

@QuakerRUS 1469 / 1010 / 456 Регистрация: 30.10.2017 Сообщений: 2,799
	24.11.2017, 15:55
	COKPOWEHEU, да, я так примерно себе и представлял. Используем указатели void * (и void **) и передаем информацию о вложенности (pwr-1). 0

@COKPOWEHEU 4150 / 2728 / 433 Регистрация: 09.09.2017 Сообщений: 12,099
	24.11.2017, 16:07
	Только это не отменяет двух фактов: 1. массив 18-й степени вложенности это извращение 2. создание такого извращения методом вложенных массивов крайне расточительно Мне даже любопытно узнать для чего такое может пригодиться. 0

@COKPOWEHEU 4150 / 2728 / 433 Регистрация: 09.09.2017 Сообщений: 12,099
	24.11.2017, 16:36
	но это ведь не учитывает узлы - только листья. Насколько я знаю, статические бинарные деревья кодируют немного по-другому (a)(aa)(ab)(aaa)(aab)(aba)(abb)(aaaa)(aa ab)(aaba)(aabb)(abaa)(abab)(abba)(abbb) в виде линейного массива, кекеке. то есть для i-го узла дочерними будут [2i+1] и [2i+2] 0