Динамическая память (выделение и освобождение памяти под переменные, одномерные массивы, двумерные массивы).

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

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

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

В С++ существуют два оператора для ДВП: new (выделяет память и возвращает указатель на ее начало) и delete (освобождает память, предварительно выведенную посредством оператора new).

Синтаксис.

x=new тип;

delete x;

Выделение и удаление памяти под одномерные массивы.

x=new тип-массива [размер];

delete []x;

При выделении памяти под массивы им нельзя присвоить начальное значение.

Выделение и удаление памяти под двумерные массивы.

// объявление двумерного динамического массива на 10 элементов:
float **ptrarray = new float* [2]; // две строки в массиве
for (int count = 0; count < 2; count++)
ptrarray[count] = new float [5]; // и пять столбцов
// где ptrarray – массив указателей на выделенный участок памяти под массив вещественных чисел типа float

// высвобождение памяти отводимой под двумерный динамический массив:

for (int count = 0; count < 2; count++)

delete [] ptrarray[count];

// где 2 – количество строк в массиве

Динамическое выделение памяти необходимо для эффективного использования памяти компьютера. Например, мы написали какую-то программку, которая обрабатывает массив. При написании данной программы необходимо было объявить массив, то есть задать ему фиксированный размер (к примеру, от 0 до 100 элементов). Тогда данная программа будет не универсальной, ведь может обрабатывать массив размером не более 100 элементов. А если нам понадобятся всего 20 элементов, но в памяти выделится место под 100 элементов, ведь объявление массива было статическим, а такое использование памяти крайне не эффективно.

В С++ есть свой механизм выделения и освобождения памяти — это функции new и delete.

Пример использования new:

int * p = new int[1000000]; // выделение памяти под 1000000 int`ов

Т.е. при использовании функции new не нужно приводить указатель и не нужно использовать sizeof().

Освобождение выделенной при помощи new памяти осуществляется посредством следующего вызова:

delete [] p;

Если требуется выделить память под один элемент, то можно использовать

int * q = new int;

или

int * q = new int(10); // выделенный int проинциализируется значением 10

в этом случае удаление будет выглядеть следующим образом:

delete q;

Существует также специальная операция взятия адреса, обозначаемая символом &. Ее результатом является адрес объекта. Следующий оператор присваивает указателю pint адрес переменной ival:

int *pint;

pint = &ival; // pint получает значение адреса ival

Мы можем обратиться к тому объекту, адрес которого содержит pint (ival в нашем случае), используя операцию разыменования, называемую также косвенной адресацией. Эта операция обозначается символом *. Вот как можно косвенно прибавить единицу к ival, используя ее адрес:

*pint = *pint + 1; // неявно увеличивает ival

Это выражение производит в точности те же действия, что и

ival = ival + 1; // явно увеличивает ival

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

Основные отличия между статическим и динамическим выделением памяти таковы:

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

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

Оператор new имеет две формы. Первая форма выделяет память под единичный объект определенного типа:

int *pint = new int(1024);

Здесь оператор new выделяет память под безымянный объект типа int, инициализирует его значением 1024 и возвращает адрес созданного объекта. Этот адрес используется для инициализации указателя pint. Все действия над таким безымянным объектом производятся путем разыменовывания данного указателя, т.к. явно манипулировать динамическим объектом невозможно.

Вторая форма оператора new выделяет память под массив заданного размера, состоящий из элементов определенного типа:

int *pia = new int[4];

В этом примере память выделяется под массив из четырех элементов типа int. К сожалению, данная форма оператора new не позволяет инициализировать элементы массива.

Некоторую путаницу вносит то, что обе формы оператора new возвращают одинаковый указатель, в нашем примере это указатель на целое. И pint, и pia объявлены совершенно одинаково, однако pint указывает на единственный объект типа int, а pia – на первый элемент массива из четырех объектов типа int.

Когда динамический объект больше не нужен, мы должны явным образом освободить отведенную под него память. Это делается с помощью оператора delete, имеющего, как и new, две формы – для единичного объекта и для массива:

// освобождение единичного объекта

delete pint;

// освобождение массива

delete[] pia;

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

Наш сжатый обзор динамического выделения памяти и использования указателей, наверное, больше породил вопросов, чем дал ответов. В разделе 8.4 затронутые проблемы будут освещены во всех подробностях. Однако мы не могли обойтись без этого отступления, так как класс Array, который мы собираемся спроектировать в последующих разделах, основан на использовании динамически выделяемой памяти.

77. Тип данных «Массив массивов»

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

// объявление двумерного динамического массива на 10 элементов:

float **ptrarray = new float* [2]; // две строки в массиве

for (int count = 0; count < 2; count++)

ptrarray[count] = new float [5]; // и пять столбцов

// где ptrarray – массив указателей на выделенный участок памяти под массив вещественных чисел типа float

Сначала объявляется указатель второго порядка float **ptrarray, который ссылается на массив указателей float* [2], где размер массива равен двум. После чего в цикле for каждой строке массива объявленного в строке 2 выделяется память под пять элементов. В результате получается двумерный динамический массив ptrarray[2][5]. Рассмотрим пример высвобождения памяти отводимой под двумерный динамический массив.

// высвобождение памяти отводимой под двумерный динамический массив:

for (int count = 0; count < 2; count++)

delete [] ptrarray[count];

// где 2 – количество строк в массиве

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

// new_delete_array2.cpp: определяет точку входа для консольного приложения.

#include "stdafx.h"

#include <iostream>

#include <ctime>

#include <iomanip>

using namespace std;

int main(int argc, char* argv[])

{

srand(time(0)); // генерация случайных чисел

// динамическое создание двумерного массива вещественных чисел на десять элементов

float **ptrarray = new float* [2]; // две строки в массиве

for (int count = 0; count < 2; count++)

ptrarray[count] = new float [5]; // и пять столбцов

// заполнение массива

for (int count_row = 0; count_row < 2; count_row++)

for (int count_column = 0; count_column < 5; count_column++)

ptrarray[count_row][count_column] = (rand() % 10 + 1) / float((rand() % 10 + 1)); //заполнение массива случайными числами с масштабированием от 1 до 10

// вывод массива

for (int count_row = 0; count_row < 2; count_row++)

{

for (int count_column = 0; count_column < 5; count_column++)

cout << setw(4) <<setprecision(2) << ptrarray[count_row][count_column] << " ";

cout << endl;

}

// удаление двумерного динамического массива

for (int count = 0; count < 2; count++)

delete []ptrarray[count];

system("pause");

return 0;

}

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

78. Представление строк в языках программирования. Достоинства и недостатки различных представлений (отличие ‘A’ от “A”).

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

Реализация в языках программирования

• В первых языках программирования вообще не было строкового типа; программист должен был сам строить функции для работы со строками того или другого типа.

• В Си используются нуль-терминированные строки с полным ручным контролем со стороны программиста.

• В стандартном Паскале строка выглядит как массив из 256 байтов; первый байт хранил длину строки, в остальных хранится её тело. Таким образом, длина строки не может превышать 255 символов. В Borland Pascal 7.0 также появились строки «а-ля Си» — очевидно, из-за того, что в число поддерживаемых платформ вошла Windows.

• В Object Pascal и STL строка является «чёрным ящиком», в котором выделение/высвобождение памяти происходит автоматически — без участия программиста. При создании строки память выделяется автоматически; как только на строку не останется ни одной ссылки, память возвращается системе. Преимущество этого метода в том, что программист не задумывается над работой строк. С другой стороны, программист имеет недостаточный контроль над работой программы в критичных к скорости участках; также трудно реализуется передача таких строк в качестве параметра в DLL. Также Object Pascal автоматически следит, чтобы в конце строки был символ с кодом 0. Поэтому если функция требует на входе нуль-терминированную строку, для конвертации надо просто написать PAnsiChar(строковая_переменная) или PWideChar(строковая_переменная) (для Pascal), переменная.c_str() (для Builder/STL).

• В C# и других языках со сборкой мусора строка является неизменяемым объектом; если строку нужно модифицировать, создаётся другой объект. Этот метод медленный и расходует немало временной памяти, но хорошо сочетается с концепцией сборки мусора. Преимущество этого метода в том, что присваивание происходит быстро и без дублирования строк. Также имеется некоторый ручной контроль над конструированием строк (в Java, например, через класс StringBuffer) — это позволяет уменьшить количество выделений и высвобождений памяти и, соответственно, увеличить скорость.

Представление массивом символов

В этом подходе строки представляются массивом символов; при этом размер массива хранится в отдельной (служебной) области. От названия языка Pascal, где этот метод был впервые реализован, данный метод получил название Pascal strings.

Слегка оптимизированным вариантом этого метода является т. н. формат c-addr u (от англ. character-aligned address + unsigned number), применяемый в Форте. В отличие от Pascal strings, здесь размер массива хранится не совместно со строковыми данными, а является частью указателя на строку.

Преимущества

• программа в каждый момент времени «знает» о размере строки, и операции добавления символов в конец, копирования и получения размера строки выполняются достаточно быстро;

• строка может содержать любые данные;

• возможно на программном уровне следить за выходом за границы строки при её обработке;

• возможно быстрое выполнение операции вида «взятие N-ого символа с конца строки».

Недостатки

• проблемы с хранением и обработкой символов произвольной длины;

• увеличение затрат на хранение строк — значение «длина строки» также занимает место и в случае большого количества строк маленького размера может существенно увеличить требования алгоритма к оперативной памяти;

• ограничение максимального размера строки. В современных языках программирования это ограничение скорее теоретическое, так как обычно размер строки хранится в 32-битовом поле, что даёт максимальный размер строки в 4 294 967 295 байт (4 гигабайта).

Метод «завершающего байта»

Основная статья: Нуль-терминированная строка

Второй метод заключается в использовании «завершающего байта». Одно из возможных значений символов алфавита (как правило, это символ с кодом 0) выбирается в качестве признака конца строки, и строка хранится как последовательность байтов от начала до конца. Есть системы, в которых в качестве признака конца строки используется не символ 0, а байт 0xFF (255) или код символа «$».

Метод имеет три названия — ASCIIZ (символы в кодировке ASCII с нулевым завершающим байтом), C-strings (наибольшее распространение метод получил именно в языке Си) и метод нуль-терминированных строк.

Преимущества

• отсутствие дополнительной служебной информации о строке (кроме завершающего байта);

• возможность представления строки без создания отдельного типа данных;

• отсутствие ограничения на максимальный размер строки;

• экономное использование памяти;

• простота получения суффикса строки;

• простота передачи строк в функции (передаётся указатель на первый символ);

• возможность использовать алфавит с переменным размером символа (например, UTF-8).

Недостатки

• долгое выполнение операций получения длины и конкатенации строк;

• отсутствие средств контроля за выходом за пределы строки, в случае повреждения завершающего байта возможность повреждения больших областей памяти, что может привести к непредсказуемым последствиям — потере данных, краху программы и даже всей системы;

• невозможность использовать символ завершающего байта в качестве элемента строки.

79. Основные алгоритмы обработки строк.
Символьная информация в алгоритмах описывается данными двух типов: символьным и строковым. Они отличаются друг от друга тем, что значением символьной переменной является один символ, а строковой – строка символов.

При построении алгоритмов обработки строк полезно знать и использовать следующие возможности: стандартные процедуры и функции для строк (символов); упорядоченность множества символов; механизм динамических строк и их внутреннее представление; основные способы обработки строковых переменных. Основные алгоритмы обработки строк: включение и исключение символов или последовательности символов; поиск в строке (алгоритмы Кнута, Мориса и Пратта, Боуера и Мура и др.); прямой поиск и т.д. Алгоритмы преобразования строк применимы сейчас к широкому кругу задач: редактирование текстов; перевод текста с одного естественного языка в другой; криптология; информационно-поисковые системы; структурный подход к задаче распознавания образов и др.

80. Основные функции стандартной библиотеки <cctype>

Заголовочный файл cctype содержит функции обработки символов. Эта библиотека объявляет набор функций для выполнения различных классификаций и некоторых операций преобразования отдельных символов.

Все функции, определённые в заголовочном файле cctype принимают в качестве аргумента значение типа int (эквивалент одного символа) и возвращают целое число, которое является эквивалентом символа, либо значением, которое представляет логическое значение: целочисленное значение 0 — ложь, и целочисленное значение, отличное от 0 — истина. В этом файле определены два набора функций:

· функции классификации символов;

· функции преобразования символов.

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

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

81. Основные функции стандартной библиотеки <cstring>

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

Не нашли, что искали? Воспользуйтесь поиском: