Как реализовать алгоритм на С++?

Question

[HabrArkady]

Дан массив a0.
В цикле последовательно вычисляются
bi = F(ai), ai+1 = G(bi),
F, G – некоторые алгоритмы, 0 при a, i и (i+1) - индексы.
Причем размерность каждого следующего массива больше размерности предыдущего массива.
Во сколько раз больше становится известно только непосредственно перед вычислением каждого массива.
Можно завести максимально возможный размер каждого массива статически, при компиляции - так написал, все работает. При таком подходе, памяти может использоваться в десятки раз больше реально необходимого. Очень хочу минимизировать объем памяти.
В лоб, используя new и delete и только два имени a и b, - не получается, не позволяет синтаксис. Можно реализовать данный алгоритм, используя new и delete, правда, при этом, на каждой итерации придется заводит новое имя. Совсем не хочется играться с именами. Использовать умные указатели также не получается.
Вопрос: “Как реализовать такой алгоритм, используя динамическую память на С++ и только два имени”?

Comments

[maaGames]

зачем заводить новое имя (новый указатель)? удалил через delete и в этот же указатель присваивай новый, созданный через new.

[HabrArkady]

Не получается. В том то и вопрос, что он удалить не дает. Оператор delete будет стоять перед new. И никакие ухищрения не помогают.

[res2001]

HabrArkady,

Оператор delete будет стоять перед new.

Все правильно. Какие там ухищрения? Если ошибка/сегфол или еще что - пишите сюда. Проблема не ясна. Она явно не в повторном использовании имен. Приведите код и ошибку.

[HabrArkady]

Да Visual Studio не дает ставить оператор delete перед оператором new. Проблема как раз в этом. Выдается ошибка на этапе компиляции. А ухищрения в том, что пытаюсь показать, что это повторный проход и что объект уже создан.

[Александр Ананьев]

HabrArkady, какая ошибка компиляции? Показывайте код и ошибку к нему. Очевидно, вы что-то не так делаете.

[res2001]

HabrArkady, Значит вы что-то пишете синтаксически не правильно вот и все.
Давайте код и текст ошибки.

[HabrArkady]

Код я приводить не буду. Он достаточно сложен, чтобы сходу так разобраться. Даже сама идея алгоритма очень трудна для понимания. А уж по поводу реализации то и подавно. А в чем проблема попытаюсь объяснить.
new a0;
new ptr_a;
цикл (по условию)
{
new b; b = F(ptr_a);
new a; a = G(b);
ptr_a = a;
delete b;
if (условие выполняется) => delete a;
}
delete a0;
delete ptr_a;
Надеюсь схему привел достаточно понятно и наглядно. В чем проблема?
Если убрать цикл (т.е. при однократном проходе), то все работает идеально, вообще никаких проблем.
Проблема возникает при повторном проходе, при второй, третьей итерации и т.д.
Условие не выполняется, следовательно запускается повторно. Мы имеем реальный, нормальный массив а, массива b нет. Заходим в цикл - первая строчка цикла выполняется без проблем. Создаем массив b, находим значения массива b, массив а нам уже не нужен. Его необходимо удалить, чтобы создать заново с новой размерностью.
Например по условию - if (проход !=1) => delete a;
И все приехали. Хотя массив а существует, реальный, нормальный, а удалить его нельзя.
Более того, то, что оператор < delete a > находится строчкой выше оператора < new a > воспринимается как синтаксическая ошибка.
Если вкратце, то так.

Answer 1

[rPman]

у тебя два пути, вместо массивов использовать списки (если нужен не последовательный доступ то придется с индексами, это +log(n) требований памяти) на основе std:list и индекса std:map (сильно фрагментирует память, что плохо в общем случае но просто для разработки) или расширять размер памяти под массив (с копированием содержимого из старого в новый), обычно увеличивают в два раза по мере роста массива - std:vector.

Так же есть готовая реализация, хранит массив крупными кусками std:deque (это если нужно итеративно по списку идти)

Comments

[mayton2019]

Автор вообще не говорит про проблему нехватки памяти. Он - просто не знает как реализовать.

В данный момент мне кажется - безразлично как. Пускай с std::map. Это будет хороший старт.

А оптимизации потом когда будет ясно где надо улучшать.

[HabrArkady]

Я знаю как реализовать, я написал программу, она работает прекрасно. Меня как раз интересует вопрос: “Как реализовать такой алгоритм, используя динамическую память на С++ и только два имени”? Именно для уменьшения объема используемой памяти. Не нравится, когда используется только 10-я или 100-я часть из зарезервированного объема. На бумаге алгоритм работает прекрасно. Вопрос: "Как реализовать программно"?

[rPman]

HabrArkady, ты пробовал реализовать простейший алгоритм - у тебя есть блок памяти T* mas=new T[MAX_SIZE] (ну или malloc) и рядом переменная real_size, как только real_size превышает MAX_SIZE, ты сохраняешь старую в mas_old=mas затем инициализируешь новый массив большего размера MAX_SIZE*=2 и mas=new T[MAX_SIZE] копируешь старый в новый и освобождаешь старый delete old_mas

[HabrArkady]

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

[rPman]

причем тут новое имя, у тебя должна быть переменная T* mas; в которой должен лежать текущий массив, ты его по мере расширения (или уменьшения) должен пересоздавать, т.е. он будет каждый раз указывать на новое место но работать будет mas[i]

этот подход самый простой, не создает фрагментацию памяти, но у него проблема - требования к памяти 2x на время расширения размера

Answer 2

[Wataru]

Используйте std::vector. Их можно присваивать как переменные. При этом там под капотом не будет никакого копирования, а просто изменение указателей в данном случае (так как правая часть - временное значение).

std::vector<int> a, b;
a = a0;
b = F(a);
for (int i = 1; i <= n; ++i) {
  a = G(b);
  b = F(a);
}

Если вас напрягает, что функции G и F выделяют память внутри, то можно сделать, чтобы они получали vector, в который надо вернуть значения:

void F(const vector<int> &a, vector<int>& res);
void G(const vector<int> &b, vector<int>& res);

std::vector<int> a, b;
a = a0;
b = F(a);
for (int i = 1; i <= n; ++i) {
  G(b, a);
  F(a, b);
}