Поэлементное выделение памяти

@Timurs · Регистрация: 23.02.2016

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

Добрый вечер!
Многократно возникает следующая ситуация: допустим у нас есть цикл, в котором прописаны некоторые условия, попадая в которые мы получаем нужные нам числа, и перед нами стоит задача создать массив из этих чисел, чтобы дальше продолжить работу. Размер массива мы не знаем, так как не знаем сколько раз попадём в условия -- всё на рандоме, а потому нам приходится дублировать код. Как через оператор new выделять память на один элемент массива, писать туда элемент, при повторном прохождении добавлять памяти на следующий элемент и т.д. пока цикл не кончится?
Мне представляется как-то так это всё дело int size = 1; int* array = new int[size], а потом в нужных местах писать что-то вроде new array[size++] для выделения памяти, но так память по моей логике не выделится...
Векторами пользоваться нельзя.
Типичный пример ситуации (часть кода после комментария /*Количество неповторяющихся элементов*/ приходится дублировать)

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream> 
#include <iomanip> 
#include <cstdlib> 
#include <ctime> 
 
#define SIZE 100 
 
int main() {
    int sort[SIZE];
    setlocale(LC_ALL, "Russian");
    /*Создание массива случайных чисел*/
    std::cout << "Массив \n";
    srand(time(NULL));
    for (int i = 0; i < SIZE; i++) {
        sort[i] = rand() % 100;
        std::cout << std::setw(3) << sort[i];
        if (((i + 1) % 10) == 0) std::cout << "\n";
    }
    std::cout << "\n \n";
    /*Сортировка массива*/
    std::cout << "Сортировка массива \n";
    int temp;
    for (int i = 0; i < SIZE - 1; i++) {
        int j_temp = i;
        for (int j = SIZE - 1; j > i; j--) {
            if (sort[j] < sort[j_temp]) {
                j_temp = j;
            }
        }
        temp = sort[i];
        sort[i] = sort[j_temp];
        sort[j_temp] = temp;
    }
    for (int i = 0; i < SIZE; i++) {
        std::cout << std::setw(3) << sort[i];
        if (((i + 1) % 10) == 0) std::cout << "\n";
    }
    std::cout << "\n \n";
    /*Количество неповторяющихся элементов*/
    std::cout << "Количество неповторяющихся элементов \n";
    int delsize = 0;
    for (int i = 0; i < SIZE; i++) {
        if (i == 0) {
            if (sort[i] != sort[i + 1]) delsize++;
        }
        else if (i == SIZE - 1) {
            if (sort[i - 1] != sort[i]) delsize++;
        }
        else {
            if (sort[i - 1] == sort[i] || sort[i] == sort[i + 1]) continue;
            else delsize++;
        }
    }
    std::cout << std::setw(3) << delsize << "\n \n";
    /*Неповторяющийся массив*/

@Renji · 30.07.2018, 20:37

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

Векторами пользоваться нельзя.

1) malloc/realloc/free. Но Си.
2) Variable-length array массивы размер которых задается на стадии исполнения (но потом не меняется). Но его в стандарте C++ вообще нету (а компилятор скорее всего поддерживает).
3) Фиксированный массив размера "чтоб точно хватило". Но не экономно.

@Mournful Max · 30.07.2018, 21:10

Можно объединить 1 и 3 варианты, предложенные мистером Renji:
• создать некий буффер ( массив фиксированного размера ), в который будут вноситься вводимые числа ;
• создать указатель, который будет указывать на область памяти, где будут храниться все числа ( динамический массив ).
В процессе ввода чисел, после того, как буффер заполняется ( кончается место в массиве ), мы берем и перевыделяем память в основном массиве ( область памяти, на которую ссылается тот самый указатель ) под такое кол-во элементов, чтобы скопировать прежние данные с основного массива + данные из буффера. Потом очищаем буффер, повторяем действия.
Я известем своей отчетливостью ( нет ), потому если что-то не ясно — спрашивайте. Если все ясно — попытайтесь это реализовать сами. Если ничего не получится, тогда кину пример. Удачи.

@Yetty · 30.07.2018, 21:46

Timurs, количество различных элементов можно находить проще, например так:

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
27
28
29
30
31
#include <iostream>
#include <ctime>
using namespace std;
 
int main()
{
    srand((int)time(0));
    int n, k=0, count=0;
    cout <<"n="; cin >>n;
 
    int*a = new int[n];
 
    for (int i = 0; i < n; i++)
      {
      a[i]=rand()%9 + 1;
      cout <<a[i]<<" ";
      }    
    
    for(int i = 0; i < n; i++)
    {
    k=0;
    for(int j = 0; j < n; j++) 
        if(i!=j&&a[i]==a[j]) k++;        
      if (k==0) count++;
    }
          
    cout <<"\ncount="<<count<<"\n";      
    delete[]a;
system("pause");
return 0;
}

не совсем понятно что именно Вам нужно. сформулируйте задачу

Verevkin · 30.07.2018, 21:58

А чо если для сохранения всех новых элементов использовать однонаправленный список, а после формирования - выделять память (1 раз) под массив для их хранения/обработки/сортировки и переносить данные из списка в этот массив с последующим освобождением памяти из-под элементов списка? Каждый элемент списка - это указатель на структуру, память под которую выделяется при добавлении указателя в конец списка, поэтому перераспределения и фрагментации не будет. Красота, ёмаё!

@Timurs · 31.07.2018, 01:32 **[ТС]**

Renji, Captain Maxee, я Вас понял, но мне как раз и интересно как сэкономить память и не повторять проверки, то есть заведомо выделить память, чтоб точно на все элементы хватило ну вообще не вариант, неинтересно так. Просто мой мозг отказывается понимать почему куски памяти нельзя добавлять, такое чувство что можно, но что-то не так пишу.

Yetty, знаю, просто тут грубо говоря каждый элемент проверяется с каждым и мне показалось это совсем кривым вариантом, n^2 проверок, а через sort n*(n-1)/2 - 1 + этот for, в нём вроде бы 3n -- итого 0.5n^2+2.5n-1.
не совсем понятно что именно Вам нужно. сформулируйте задачу
Да всё просто, есть массив например 1, 2, 3, 4, 4 и я хочу 1, 2, 3 сразу писать в свежий массив походу дела, не выделяя заведомо память на три элемента. Но пишется только один элемент.
А если раскомментить строки, то всё падает.

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
int size = 0, one = 1;
    int* delrepeat = new int[one];
    std::cout << "Неповторяющийся массив \n";
    for (int i = 0; i < SIZE; i++) {
        if (i == 0) {
            if (sort[i] != sort[i + 1]) {
                delrepeat[size++] = sort[i];
                //delrepeat = new int[one];
            }
        }
        else if (i == SIZE - 1) {
            if (sort[i - 1] != sort[i]) {
                delrepeat[size++] = sort[i];
                //delrepeat = new int[one];
            }
        }
        else {
            if (sort[i - 1] == sort[i] || sort[i] == sort[i + 1]) continue;
            else {
                delrepeat[size++] = sort[i];
                //delrepeat = new int[one];
            }
        }
    }

Какого лешего он не хочет ещё кусочка памяти добавить, ему жалко что ли?

Не понимаю... На векторе ж легко пушбэком в конец кидать, более того, я всегда и думал, что это именно так и реализовано.

Verevkin, вот это походу то, что надо! Правда проблема есть одна -- не знаю что такое однонаправленный список и структура. Можете продемонстрировать как это прокрутить можно на примере кода что выше?

Добавлено через 28 минут
Точнее через сортировку вышло 0.5n*(n-1) + 2*(n-2) + 2 = 0.5n^2 + 2.5n + 2 проверки.

Verevkin · 31.07.2018, 08:25

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

Правда проблема есть одна -- не знаю что такое однонаправленный список и структура.

В интернетах полно примеров. В том числе, и на этом форуме. Поиск рулит.
Вкратце: элементы списка представляют собой такую структуру:

C++
1
2
3
4
5
6
typedef struct TListItem
{
  DWORD data; // поле данных
  // ... куча других полей данных ...
  TListItem* Next; // указатель на след. элемент
} *PListItem;

Такие элементы создаются только динамически по мере необходимости.Их размер всегда известен заранее - sizeof(TListItem), так что можно юзать даже malloc() вместо new.

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

Можете продемонстрировать как это прокрутить можно на примере кода что выше?

Конечно нет. Кто из нас тут программист: ты или я?
Мне работать надо, некогда мне. На форуме народу много и все шарят.

@Mournful Max · 31.07.2018, 09:01

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

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

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

ему жалко что ли?

Нет, ему не жалко. Сейчас объясню. Вот, например, у нас есть память :

Code
1
|*|*|*| | |*|*|

Где | | — ячейка памяти ; * — какие-то данные.
Вот, например, у тебя первые три звездочки ( * ) — массив int[ 3 ]. Дальше — две пустые ячейки памяти ( | | | ), а потом ( две звездочки ) — это какие-то другие данные... возможно, даже не относящиеся к твоей программе. Имеется в виду оперативная память, конечно же. А она, как известно, используется всеми запущенными приложениями, а не только тем, активное окно которого сейчас. И ты вот, вроде, сможешь добавить по 1 дополнительной ячейке два раза ( занять те две свободные ячейки памяти ( | | | ) ), а дальше что ? Дальше — занято. Придется перевыделить память в другом месте, где есть больше свободных ячеек. Потому вот и нельзя так просто.
Теперь к делу...

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

На векторе ж легко пушбэком в конец кидать, более того, я всегда и думал, что это именно так и реализовано.

Если имеется в виду std::vector, то он в большинстве случаев, грубо говоря, реализован так, как я выше описал : если есть возможность занять несколько свободных ячеек «спереди», то он это и делает. Если нет — переносит массив в другое место, где есть больше ячеек для хранения информации. Естественно, вся эта реализация скрыта за методом push_back(), который, в свою очередь, скорее всего, внутри себя, вызывает другие методы. Но ты этого не видишь — в этом и вся прелесть ООП ( и функционального программирования в частности ).
Чуть позже скину пример того, как можно решить твою задачу стандартными средствами.

Байт · 31.07.2018, 10:06

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

Какого лешего он не хочет ещё кусочка памяти добавить, ему жалко что ли?

Ему-то не жалко, но ты ее не просил.

Вот в Си есть такая функция - realloc. Ее можно использовать и в плюсах, так как Си в обще-то подмножество С++.
Но можно реализовать нужный тебе механизм и на new-delete. Суть в том, что выделяется новая область памяти, туда переписываются данные из старой, а старая уничтожается.

C++
1
2
3
4
5
6
7
8
size = 1;
int *d = new int[size];
int *dn;
// Когда нужен новый элемент
dn = new int[++size];
for(int i=0; i<size-1; i++) dn[i] = d[i];
delete d[];
d = dn;

Добавлено через 3 минуты
Но очень прошу тебя - никогда так не делай!
Дело в том, что выделение памяти + копирование - все это достаточно дорого. И для каждой единицы все это проделывать - глупо.
Поэтому умные люди выделяют память кусками. Собственно, приблизительно так и устроен vector.

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

Не по теме:

Вот, навеяло...
Душа просит поэзии

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

Не по теме:

Точнее
Душа просит поэзии

Добавлено через 1 минуту
Там был переход через страницу и такой маленький глючок...

@Yetty · 31.07.2018, 10:26

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

знаю, просто тут грубо говоря каждый элемент проверяется с каждым и мне показалось это совсем кривым вариантом, n^2 проверок, а через sort n*(n-1)/2 - 1 + этот for, в нём вроде бы 3n -- итого 0.5n^2+2.5n-1.
не совсем понятно что именно Вам нужно. сформулируйте задачу
Да всё просто, есть массив например 1, 2, 3, 4, 4 и я хочу 1, 2, 3 сразу писать в свежий массив походу дела, не выделяя заведомо память на три элемента. Но пишется только один элемент.

Timurs, у Вас для сортировки применён метод пузырька, его сложность n^2, так что если нужно записывать в новый массив, по быстродействию такой вариант должен не уступать (+ не меняется порядок элементов):

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <ctime>
using namespace std;
 
int main()
{
    srand((int)time(0));
    int n, k=0, m=0, count=0;
    cout <<"n="; cin >>n;
 
    int*a = new int[n];
 
    for (int i = 0; i < n; i++)
      {
      a[i]=rand()%9 + 1;
      cout <<a[i]<<" ";
      }    
    cout <<"\n";
    
    for(int i = 0; i < n; i++)
    {
    k=0;
    for(int j = 0; j < n; j++) 
        if(i!=j&&a[i]==a[j]) k++;        
      if (k==0) count++;
    }
    
    int*b = new int[count];
    
    for(int i = 0; i < n; i++)
    {
    k=0;
    for(int j = 0; j < n; j++) 
        if(i!=j&&a[i]==a[j]) k++;        
      if (k==0) b[m++]=a[i];
    }  
    
    for (int i = 0; i < count; i++)      
      cout <<b[i]<<" ";      
    
    cout <<"\ncount="<<count<<"\n";      
    delete[]a;
    delete[]b;
system("pause");
return 0;
}

@SuperKir · 31.07.2018, 14:47

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

Правда проблема есть одна -- не знаю что такое однонаправленный список и структура

На скорую руку накидал для примера)

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <iostream>
#include <ctime>
#include <iomanip>
 
#define SIZE 100
 
using namespace std;
 
struct Node
{
    int data;
    Node *next;
};
 
void add(Node *&head, int value)
{
    if (head)
    {
        Node *temp = new Node;
        temp->data = value;
        temp->next = head;
        head = temp;
    }
    else
    {
        head = new Node;
        head->data = value;
        head->next = NULL;
    }
}
 
int pop(Node *&head)
{
    if (!head)
        return -1;
    else
    {
        int val = head->data;
        Node *temp = head;
        head = head->next;
        delete temp;
        return val;
    }
}
 
void print(Node *head)
{
    if (!head)
        cout << "Empty list" << endl;
    else
    {
        Node *temp = head;
        while (temp)
        {
            cout << temp->data << " ";
            temp = temp->next;
        }
    }
}
 
int length(Node *head)
{
    if (!head)
        return -1;
    else
    {
        Node *temp = head;
        int count = 0;
        while (temp)
        {
            count++;
            temp = temp->next;
        }
        return count;
    }
}
 
void del(Node *&head)
{
    if (!head)
        return;
    else
    {
        while (head->next)
        {
            Node *temp = head;
            head = head->next;
            delete temp;
        }
        delete head;
        head = nullptr;
    }
}
 
int main()
{
    Node *head = nullptr;
    int sort[SIZE];
    cout << "Array \n";
    srand(time(NULL));
    for (int i = 0; i < SIZE; i++)
    {
        sort[i] = rand() % 100;
        cout << setw(3) << sort[i];
        if (((i + 1) % 10) == 0) cout << "\n";
    }
 
    for (int i = 0; i < SIZE - 1; i++)
    {
        bool isExist = false;
        for (int j = i + 1; j < SIZE; j++)
            if (sort[i] == sort[j])
            {
                isExist = true;
                break;
            }
        if (!isExist)
            add(head, sort[i]);
    }
 
    int new_size = length(head);
    cout << endl << "Count = " << new_size << endl;
 
    cout << "New array" << endl;
    int *new_sort = new int[new_size];
 
    for (int i = new_size - 1; i >= 0; i--)
        new_sort[i] = pop(head);
    for (int i = 0; i < new_size; i++)
    {
        cout << setw(3) << new_sort[i];
        if (((i + 1) % 10) == 0) cout << endl;
    }
    cout << endl;
 
    
    delete[]new_sort;
    return 0;
}

@Timurs · 04.08.2018, 18:42 **[ТС]**

Байт, спасибо! Именно эта штука мне и интересна. Понял, так делать не буду, но для понимания как это работает разок-то надо сделать) Проблема в том, что всё равно не получается, хотя Ваш комментарий понял.

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
int size = 0, one = 1;
    int* delrepeat = new int[one];
    std::cout << "Неповторяющийся массив \n";
    for (int i = 0; i < SIZE; i++) {
        if (i == 0) {
            if (sort[i] != sort[i + 1]) {
                delrepeat[size++] = sort[i];
            }
        }
        else if (i == SIZE - 1) {
            if (sort[i - 1] != sort[i]) {
                delrepeat[size++] = sort[i];
                //delrepeat = new int[one];
            }
        }
        else {
            if (sort[i - 1] == sort[i] || sort[i] == sort[i + 1]) continue;
            else {
                int* delrepeat_n = new int[++one];
                for (int i = 0; i < one - 1; i++) delrepeat_n[i] = delrepeat[i];
                delete delrepeat[];
                delrepeat = delrepeat_n;
                delrepeat_n[size++] = sort[i];
            }
        }
    }

Компилятор ругается на delete delrepeat[]; -- синтаксическая ошибка говорит. И ещё два момента: как добавить памяти, перекопировать и добавить новый элемент в третьем условии else if (i == SIZE - 1) и, самое главное, надо же сделать, чтобы это всё автоматически делалось в цикле, эта сугубо частная же ситуация, то есть в первое условие else if (i == 0) мы заходим один раз, обычно такого не бывает, то есть при любой итерации цикла мы можем провалиться в любое условие. Как это всё учесть и прописать?

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

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

эта сугубо частная же ситуация, то есть в первое условие else if (i == 0) мы заходим один раз

а если эти элементы совпадают, то этот код накроется...

Новые блоги и статьи Все статьи Все блоги /
Символьное дифференцирование igorrr37 13.02.2026 / * Логарифм записывается как: (x-2)log(x^2+2) - означает логарифм (x^2+2) по основанию (x-2). Унарный минус обозначается как ! */ #include <iostream> #include <stack> #include <cctype>. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .

Поэлементное выделение памяти

Решение

Решение

@Mournful Max Велосипедист... 353 / 220 / 73 Регистрация: 15.12.2015 Сообщений: 785
	30.07.2018, 21:10
	Можно объединить 1 и 3 варианты, предложенные мистером Renji: • создать некий буффер ( массив фиксированного размера ), в который будут вноситься вводимые числа ; • создать указатель, который будет указывать на область памяти, где будут храниться все числа ( динамический массив ). В процессе ввода чисел, после того, как буффер заполняется ( кончается место в массиве ), мы берем и перевыделяем память в основном массиве ( область памяти, на которую ссылается тот самый указатель ) под такое кол-во элементов, чтобы скопировать прежние данные с основного массива + данные из буффера. Потом очищаем буффер, повторяем действия. Я известем своей отчетливостью ( нет ), потому если что-то не ясно — спрашивайте. Если все ясно — попытайтесь это реализовать сами. Если ничего не получится, тогда кину пример. Удачи. 2

Verevkin Злостный нарушитель 10311 / 5733 / 1269 Регистрация: 12.03.2015 Сообщений: 26,568
	30.07.2018, 21:58
	А чо если для сохранения всех новых элементов использовать однонаправленный список, а после формирования - выделять память (1 раз) под массив для их хранения/обработки/сортировки и переносить данные из списка в этот массив с последующим освобождением памяти из-под элементов списка? Каждый элемент списка - это указатель на структуру, память под которую выделяется при добавлении указателя в конец списка, поэтому перераспределения и фрагментации не будет. Красота, ёмаё! 3