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

@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) мы заходим один раз

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

Новые блоги и статьи Все статьи Все блоги /
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Рецензия / Мнение/ Перевод https:/ / **********/ gallery/ thinkpad-x220-tablet-porn-gzoEAjs . . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .

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

Решение

Решение

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

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