C выделение памяти под вектора (5 видео) | Курс школьной геометрии

std::vector при нехватке памяти

Содержание

01.03.2019
2 комментариев к “std::vector при нехватке памяти”
Динамическое выделение памяти в Си
Стандартные функции динамического выделения памяти
Динамическое выделение памяти для одномерных массивов
Динамическое выделение памяти для двумерных массивов
Перераспределение памяти
Комментариев к записи: 94
Как выделить память для std :: vector & lt; std :: vector & lt; int & gt; & GT; тип данных?
Решение
Другие решения
🔥 Видео

Видео:vector | Библиотека стандартных шаблонов (stl) | Уроки | C++ | #1Скачать

01.03.2019

Контейнер std::vector представляет собой динамический массив, автоматически увеличивающийся в размере по мере надобности. Он описан в любом приличном руководстве по С++. Там же описываются его методы, достоинства и недостатки по сравнению с другими контейнерами.

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

Дополнительная память выделяется во время работы трёх методов: resize, reserve и push_back. Вначале посмотрим, что по поводу них пишет стандарт (здесь и далее черновик С++11 №3337).

Стандарт

Метод reserve описан в пункте 23.3.6.3. Он ничего не возвращает. При слишком большом новом размере должен запускать исключение std::length_error. Однако здесь же есть сноска, говорящая о том, что данный метод вызывает Allocator::allocate, который может запустить иное исключение.

Метод resize описан в том же пункте. Так же ничего не возвращает. Про исключения не говорится ни слова. Но сказано, что метод присоединяет (appends) новые элементы. Правда не уточняется, использует ли он для этого метод push_back или обходится без него.

push_back описан в пункте 23.3.6.5. Ничего не возвращает. Про исключения запускаемые методом ничего не говорится.

Вот что мы имеем: reserve должен запускать std::length_error, но это на усмотрение распределителя памяти. resize и push_back остаются на совести разработчиков библиотеки.

Тестовая программа

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

Здесь есть три места, в которых она должна «упасть». В методы resize и reserve подаются заведомо слишком большие значения. А в цикле вектор наполняется до тех пор, пока метод push_back не вызовет ошибку.

Наша задача — изменить этот код так, чтобы программа не «упала» до последней строчки.

GCC Linux

Компилятор GCC (реально g++, но это формальность) на системе Linux для методов resize и reserve запустил std::length_error, а последний push_back запустил std::bad_alloc. Таким образом доработанный вариант программы выглядит следующим образом:

Данная программа выводит три строки с наименованиями пойманных исключений:

Обратите внимание: функция printf вызывается после очистки вектора. Дело в том, что ей тоже нужна память, которую полностью «поглотил» наш вектор. Без нее она не может нормально вывести строку.

GCC Windows

GCC портированный на Windows для методов resize и reserve также запустил исключение std::length_error. А вот цикл наполнения вектора методом push_back привел к… полному зависанию операционной системы.

Тест проводился дважды. Программа компилировалась и запускалась на исполнение. После вывода строк

программа, а вслед за ней и вся система (Windows 10), «уходила в себя». После 15 минут ожидания, она так и не «очнулась». Не помогала даже комбинация Ctrl+Alt+Del. В итоге приходилось жать кнопку Reset на системном блоке.

C++ Builder 6

Данная IDE потребовала дополнительных исследований. Для нашего примера метод resize запустил исключение EAccessViolation, метод reserve не запустил никакого исключения, наполнение вектора также запустило EAccessViolation.

Согласно документации, исключение EAccessViolation возникает при попытке обращения к неверному адресу памяти. Получается, C++ Builder 6 запускает его и при нехватке памяти? Но почему тогда метод reserve не запустил никакого исключения?

Если наш пример написать так:

То в этом случае метод push_back запустит std::bad_alloc, а не EAccessViolation. Почему такое разное поведение?

Ответ кроется в методе reserve. Обратите внимание: в исходном примере мы передавали туда отрицательное число -1, а в новом примере нормальное число 20. При этом в первом случае он не запустил никакого исключения. Как так? Неужели он смог зарезервировать память под -1 элемент вектора? В поисках ответа на этот вопрос мне пришлось покопаться в исходном коде класса std::vector.

Ни для кого не секрет, что современные компиляторы фирмы Borland (ныне принадлежат Embarcadero) используют свой распределитель памяти. А работает он, как оказывается, очень «интересным» образом. В частности, он позволяет «выделять» память под отрицательное количество байт. Как такое возможно, я не знаю. По всей видимости — ошибка в реализации. Но, факт остается фактом. Приведенный ниже код, несмотря на свою явную ошибочность нормально компилируется и не вызывает никаких вопросов ни со стороны компилятора, ни со стороны распределителя памяти.

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

Именно это и происходит в наших примерах. Вернемся к первому из них.

Метод resize вначале выделяет память под нужное кол-во элементов. Разумеется ему это «удается». Далее он начинает ее заполнять. Со временем реально выделенная память кончается и тогда происходит EAccessViolation.

Метод reserve также выделяет память. Ему это «удается». Но так как никакого обращения к ней не происходит, ошибка остается незамеченной. То есть vec вроде бы как владеет достаточным количеством памяти, но это не так.

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

Теперь разберем второй пример (с исключением std::bad_alloc).

Метод reserve резервирует память под 20 элементов. Всё хорошо.

Далее вектор начинает наполняться. Со временем размера массива начинает не хватать, и запрашивается дополнительная память. Здесь по всей видимости используется другой распределитель памяти, лишенный недостатка своего коллеги. Поэтому мы и получаем std::bad_alloc.

Embarcadero RAD Studio 10 и Microsoft Visual Studio 2017

К счастью для нас разработчики C++ Builder 6 не сидели сложа руки и исправили описанную выше странность (правда не могу сказать в какой конкретно версии своего продукта). Так, в Embarcadero RAD Studio 10 Seatle строка

во время компиляции вызывает предупреждение: «array size is negative», а во время исполнения запускает исключение std::bad_alloc.

Вообще компиляторы, входящие в состав Emabarcadero RAD Studio 10 и Microsoft Visual Studio 2017 ведут себя схожим образом: для методов resize и reserve они запускают std::length_error, а для push_back — std::bad_alloc. В этом они повторяют поведение GCC в Linux.

Выводы

Все рассмотренные современные компиляторы при нехватке памяти для методов resize и reserve запускают std::length_error, а для метода push_back — std::bad_alloc. Хотя такое поведение и не регламентируется стандартом.

Одновременно с этим нужно помнить, что некоторые компиляторы (и не только давно устаревшие) могут приводить к девиантному поведению.

Видео:Выделение и освобождение динамической памяти в СиСкачать

2 комментариев к “std::vector при нехватке памяти”

Память также выделяется при insert/emplace и emplace_back.
Стандарт гарантирует что clear или resize не освобождает память, надо использовать shrink_to_fit (C++11)
bad_alloc выбрасывает второй шаблонный аргумент вектора — std::allocator

VS2019 — во всех трех случаях: resize(), reserve() и push_back() — кидает bad_alloc.

Видео:#51. Функции malloc(), free(), calloc(), realloc(), memcpy() и memmove() | Язык C для начинающихСкачать

Динамическое выделение памяти в Си

Очень часто возникают задачи обработки массивов данных, размерность которых заранее неизвестна. В этом случае возможно использование одного из двух подходов:

выделение памяти под статический массив, содержащий максимально возможное число элементов, однако в этом случае память расходуется не рационально;
динамическое выделение памяти для хранение массива данных.

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

Начальный адрес статического массива определяется компилятором в момент его объявления и не может быть изменен.

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

Видео:Динамический массив с++ пример. Создание, заполнение, удаление, размер динамического массива. #55Скачать

Стандартные функции динамического выделения памяти

Функции динамического выделения памяти находят в оперативной памяти непрерывный участок требуемой длины и возвращают начальный адрес этого участка.

Функции динамического распределения памяти:

Для использования функций динамического распределения памяти необходимо подключение библиотеки :

Поскольку обе представленные функции в качестве возвращаемого значения имеют указатель на пустой тип void , требуется явное приведение типа возвращаемого значения.

Для определения размера массива в байтах, используемого в качестве аргумента функции malloc() требуется количество элементов умножить на размер одного элемента. Поскольку элементами массива могут быть как данные простых типов, так и составных типов (например, структуры), для точного определения размера элемента в общем случае рекомендуется использование функции

Память, динамически выделенная с использованием функций calloc(), malloc() , может быть освобождена с использованием функции

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

Видео:Язык Си с нуля - Урок 24 - Динамическое распределение памяти, void*, утечки памяти.Скачать

Динамическое выделение памяти для одномерных массивов

Форма обращения к элементам массива с помощью указателей имеет следующий вид:

Пример на Си : Организация динамического одномерного массива и ввод его элементов.

Результат выполнения программы:

Видео:[C++] STL: VectorСкачать

Динамическое выделение памяти для двумерных массивов

Пусть требуется разместить в динамической памяти матрицу, содержащую n строк и m столбцов. Двумерная матрица будет располагаться в оперативной памяти в форме ленты, состоящей из элементов строк. При этом индекс любого элемента двумерной матрицы можно получить по формуле

index = i*m+j;

где i — номер текущей строки; j — номер текущего столбца.

Рассмотрим матрицу 3×4 (см. рис.)

Индекс выделенного элемента определится как

index = 1*4+2=6

Объем памяти, требуемый для размещения двумерного массива, определится как

n·m·(размер элемента)

Однако поскольку при таком объявлении компилятору явно не указывается количество элементов в строке и столбце двумерного массива, традиционное обращение к элементу путем указания индекса строки и индекса столбца является некорректным:

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

p — указатель на массив,
m — количество столбцов,
i — индекс строки,
j — индекс столбца.

Пример на Си Ввод и вывод значений динамического двумерного массива

Результат выполнения

Возможен также другой способ динамического выделения памяти под двумерный массив — с использованием массива указателей. Для этого необходимо:

выделить блок оперативной памяти под массив указателей;
выделить блоки оперативной памяти под одномерные массивы, представляющие собой строки искомой матрицы;
записать адреса строк в массив указателей.

Графически такой способ выделения памяти можно представить следующим образом.

При таком способе выделения памяти компилятору явно указано количество строк и количество столбцов в массиве.
Пример на Си

Результат выполнения программы аналогичен предыдущему случаю.

С помощью динамического выделения памяти под указатели строк можно размещать свободные массивы. Свободным называется двухмерный массив (матрица), размер строк которого может быть различным. Преимущество использования свободного массива заключается в том, что не требуется отводить память компьютера с запасом для размещения строки максимально возможной длины. Фактически свободный массив представляет собой одномерный массив указателей на одномерные массивы данных.

Для размещения в оперативной памяти матрицы со строками разной длины необходимо ввести дополнительный массив m , в котором будут храниться размеры строк.

Пример на Си : Свободный массив

Результат выполнения

Видео:new c++ что это. new c++ пример. c++ new delete. delete c++ что это. delete c++ пример. Урок #53Скачать

Перераспределение памяти

Если размер выделяемой памяти нельзя задать заранее, например при вводе последовательности значений до определенной команды, то для увеличения размера массива при вводе следующего значения необходимо выполнить следующие действия:

Выделить блок памяти размерности n+1 (на 1 больше текущего размера массива)
Скопировать все значения, хранящиеся в массиве во вновь выделенную область памяти
Освободить память, выделенную ранее для хранения массива
Переместить указатель начала массива на начало вновь выделенной области памяти
Дополнить массив последним введенным значением

Все перечисленные выше действия (кроме последнего) выполняет функция

ptr — указатель на блок ранее выделенной памяти функциями malloc() , calloc() или realloc() для перемещения в новое место. Если этот параметр равен NULL , то выделяется новый блок, и функция возвращает на него указатель.
size — новый размер, в байтах, выделяемого блока памяти. Если size = 0 , ранее выделенная память освобождается и функция возвращает нулевой указатель, ptr устанавливается в NULL .

Размер блока памяти, на который ссылается параметр ptr изменяется на size байтов. Блок памяти может уменьшаться или увеличиваться в размере. Содержимое блока памяти сохраняется даже если новый блок имеет меньший размер, чем старый. Но отбрасываются те данные, которые выходят за рамки нового блока. Если новый блок памяти больше старого, то содержимое вновь выделенной памяти будет неопределенным.

Пример на Си Выделить память для ввода массива целых чисел. После ввода каждого значения задавать вопрос о вводе следующего значения.

Результат выполнения

Видео:Что такое динамическая память. Утечка памяти. Стек и куча. Статическая память. Обзорный урок #45Скачать

Комментариев к записи: 94

#include
#include
#include
int main()
<
int **a; // указатель на указатель на строку элементов
int i, j, n, m;
system( «chcp 1251» );
system( «cls» );
printf( «Введите количество строк: » );
scanf( «%d» , &n);
printf( «Введите количество столбцов: » );
scanf( «%d» , &m);

// Выделение памяти под указатели на строки
a = ( int **)malloc(n * sizeof ( int *));
if (a== NULL )

// Ввод элементов массива
for (i = 0; i // цикл по строкам
<
// Выделение памяти под хранение строк
a[i] = ( int *)malloc(m * sizeof ( int ));
if (a[i]== NULL )
for (j = 0; j // цикл по столбцам
<
printf( «a[%d][%d] = » , i, j);
scanf( «%d» , &a[i][j]);
>
>
// Вывод элементов массива
for (i = 0; i // цикл по строкам
<
for (j = 0; j // цикл по столбцам
<
printf( «%5d » , a[i][j]); // 5 знакомест под элемент массива
>
printf( «n» );
>

// Очистка
ALARM:
for ( int ii = 0; ii // цикл по строкам
free(a[ii]); // освобождение памяти под строку
free(a);
getchar(); getchar();
return 0;
>

#include
#include
#include
#include
#include
#include
#define S 5

using namespace std;

void two_dim_input( int ** a)
<
srand(time(0));
for ( int i = 0; i for ( int u = 0; u int *)a + i * S + u) = rand() % 99;
>
>

int ** mas = ( int **)calloc(S, sizeof (*mas));
for ( int i = 0; i int *)calloc(S, sizeof (mas));
two_dim_input(mas);
two_dim_output(mas);

two_dim_sum(mas);
printf( «nn» );
two_dim_output(mas);
for ( int i = 0; i // цикл по строкам
free(mas[i]); // освобождение памяти под строку
free(mas);
>

cout «_asm code started working» endl;

_asm <
pushf // помещаем регистр флагов в стек
pop var // извлекаем операнд из стека (шта?)
>

cout «_asm code finished working» endl;

// Вывод var
cout var endl;

short *var;
var = new short[1];
cout «_asm code started working» endl;

_asm <
pushf // помещаем регистр флагов в стек
pop *var[0] // извлекаем операнд из стека (шта?)
>

cout «_asm code finished working» endl;

// Вывод var
cout *var[0] endl;

#include
#include
#include
#include

int main()
<
system( «chcp 1251»); system(«cls» );
srand(time( NULL ));
int * b, n, m;
printf( «кол-во строк: «); scanf_s(«%d» , &n);
printf( «кол-во столбцов: «); scanf_s(«%d» , &m);
b = ( int *)malloc(n * m * sizeof ( int ));
for ( int i = 0; i for ( int j = 0; j for ( int i = 0; i for ( int j = 0; j «%4d» , *(b + i * m + j));
>
printf( «n» );
>
int max, maxi = 0, maxj = 0;
max = *b;
for ( int i = 0; i for ( int j = 0; j if (*(b + i * m + j) == max) <
continue;
>
else if (*(b + i * m + j) > max) <
max = *(b + i * m + j);
maxi = i;
maxj = j;
>
>
printf( «nMax = %d» , max);
printf( «nmaxi = %d» , maxi);
printf( «nmaxj = %d» , maxj);

for ( int i = maxi; i for ( int j = 0; j «nматрица после удаления строкиnn» );
for ( int i = 0; i for ( int j = 0; j «%4d» , *(b + i * m + j));
>
printf( «n» );
>
m++;
for ( int i = 0; i for ( int j = m — 1; j > maxj — 1; j—) <
*(b + i * m + j) = *(b + i * m + (j — 1)); //зміщуємо стовбчики вправо
>
>
for ( int i = 0; i for ( int j = 0; j «nматрица после добавления столбцаnn» );
for ( int i = 0; i for ( int j = 0; j «%4d» , *(b + i * m + j));
>
printf( «n» );
>
return 0;
>
else return 0;
>

#include
#include
#include
#include

int main()
<
system( «chcp 1251»); system(«cls» );
srand(time( NULL ));
int * b, n, m;
printf( «кол-во строк «); scanf_s(«%d» , &n);
printf( «кол-во столбцов: «); scanf_s(«%d» , &m);
b = ( int *)malloc(n * m * sizeof ( int ));
for ( int i = 0; i for ( int j = 0; j for ( int i = 0; i for ( int j = 0; j «%4d» , *(b + i * m + j));
>
int max, maxi = 0, maxj = 0;
max = *b;
for ( int i = 0; i for ( int j = 0; j if (*(b + i * m + j) == max) <
continue;
>
else if (*(b + i * m + j) > max) <
max = *(b + i * m + j);
maxi = i;
maxj = j;
>
>
printf( «nMax = %d» , max);
printf( «nmaxi = %d» , maxi);
printf( «nmaxj = %d» , maxj);
>

#define _CRT_SECURE_NO_WARNINGS
#include «stdlib.h»
#include «stdio.h»
#include «conio.h»
#include «math.h»
#include
#include «locale.h»
#include «string.h»
#include «windows.h»
#include «time.h»

int main()
<
int ** a; // указатель на указатель на строку элементов
int ** b; // указатель на указатель на строку элементов
int i, j, n, m;
int counter = 0;
system( «chcp 1251» );
system( «cls» );
printf( «Введите количество строк: » );
scanf( «%d» , &n);
printf( «Введите количество столбцов: » );
scanf( «%d» , &m);
// Выделение памяти под указатели на строки
a = ( int **)malloc(n * sizeof ( int *));
// Ввод элементов массива
for (i = 0; i // цикл по строкам
<
// Выделение памяти под хранение строк
a[i] = ( int *)malloc(m * sizeof ( int ));
for (j = 0; j // цикл по столбцам
<
printf( «a[%d][%d] = » , i, j);
scanf( «%d» , &a[i][j]);
>
>

// Вывод элементов массива
for (i = 0; i // цикл по строкам
<
for (j = 0; j // цикл по столбцам
<
printf( «%5d » , a[i][j]); // 5 знакомест под элемент массива
>
printf( «n» );
>

b = ( int **)malloc(n * sizeof ( int *));
// Ввод элементов массива
for (i = 0; i // цикл по строкам
<
// Выделение памяти под хранение строк
b[i] = ( int *)malloc(m * sizeof ( int ));
for (j = 0; j // цикл по столбцам
<
printf( «a[%d][%d] = » , i, j);
scanf( «%d» , &b[i][j]);
>
>

for (i = 0; i // цикл по строкам
<
for (j = 0; j // цикл по столбцам
<
printf( «%5d » , b[i][j]); // 5 знакомест под элемент массива
>
printf( «n» );
>

a = ( int **)realloc(a, (2*n*m) * sizeof ( int ));

for (i = n; i // цикл по строкам
<
for (j = 0; j // цикл по столбцам
<
a[i][j] = b[counter][j];
counter++;
>
printf( «n» );
>

for (i = 0; i // цикл по строкам
<
for (j = 0; j // цикл по столбцам
<
printf( «%5d » , a[i][j]); // 5 знакомест под элемент массива
>
printf( «n» );
>

// Очистка памяти
for (i = 0; i // цикл по строкам
free(a[i]); // освобождение памяти под строку
free(a);

for (i = 0; i // цикл по строкам
free(b[i]); // освобождение памяти под строку
free(b);

Видео:Язык Си с нуля - Урок 25 - Динамические массивы, адресация памяти.Скачать

Как выделить память для std :: vector & lt; std :: vector & lt; int & gt; & GT; тип данных?

Предположим, следующая структура данных typedef std::vector > MYARRAY определено. Тогда для переменной MYARRAY var Как я могу выделить память для этой переменной, прежде чем помещать в нее данные. Например,

Если мы не выделяем память для var , тогда он будет выделять память автоматически. Итак, как я могу выделить память для этой переменной, прежде чем помещать данные в нее? Если это std::vector var2 Я могу просто использовать var2.reserve(n) выделить память перед ее использованием.

РЕДАКТИРОВАТЬ:
Два предложения были сделаны, но ни один не может работать:

Решение 1: выделить память для каждого элемента

var.reserve (3);
для (int i = 0; i var определяется в исполняемой программе как пустая переменная, а ее содержимое задается функцией, определенной в динамической библиотеке. Если оба используют динамическую библиотеку времени выполнения, это не будет проблемой. Но в моем случае оба связаны со статической библиотекой времени выполнения, что означает, что каждый модуль отвечает за выделение памяти. поскольку var определяется в исполняемой программе, она также должна позаботиться о распределении памяти.

Видео:Двумерный динамический массив c++ пример. Создание, заполнение, удаление. Динамические массивы. #56Скачать

Решение

То, как вы резервируете память для вектора, не зависит от того, какой тип содержит вектор. Если вы хотите зарезервировать место для n элементы в MYARRAY , вызов MYARRAY.reserve(n); ,

Его содержимое уже там. Следовательно, если вы поместите данные в эту переменную, она снова выделит память.

Правильно. Хотите зарезервировать память или нет? Если вы хотите зарезервировать память, вам придется использовать память, которую вы зарезервировали. Для того, чтобы вы «проталкивали данные в эту переменную», вам нужно было бы где-то хранить данные, а не память, которую вы зарезервировали. Если вы зарезервируете память и будете использовать эту память, вам никогда не нужно будет что-либо выдвигать, потому что это будет означать, что у вас есть что-то, кроме зарезервированной памяти, которое вам нужно добавить к вектору, которого у вас просто не могло быть ,

У вас есть три варианта:

1) Не резервируйте память. Соберите объекты, где вы хотите, а затем вставьте их в вектор. vec.push_back(myVector);

2) Резервная память. Соберите объекты на месте в векторе. vec[n].push_back(myInt);

3) Резервная память. Соберите объекты, где вы хотите, а затем назначьте их в память, которую вы зарезервировали. vec[n]=myIntVector

Обратите внимание, что ни в одном из этих случаев вы не резервируете память, а затем перемещаетесь в вектор.

Видео:array и vector в языке программирования с++Скачать

Другие решения

Как вы уже отметили, std::vector имеет reserve метод, который зарезервирует место для большего количества элементов данных. Если бы вы должны были сделать p1.reserve(3) vector будет пытаться выделить место для 3 целых чисел. Если вы бежите var.reserve(3) , var будет пытаться выделить место для 3 std::vector Это то, что звучит так, как будто ты хочешь сделать.

Выделить на std::vector «s внутри из var Вы могли бы сделать:

Если вы хотите выделить место до вставив векторы, вы можете объявить var как:

Вы не можете зарезервировать пространство для векторных данных, пока вектор не существует. Я полагаю, вы ищете это: