Лекция 9

Освобождение памяти занимаемой списком

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

template <typename T>
void delete_list(node<T>* p)
{
    while(p)
    {
        auto p1 = p;
        p = p -> next;
        delete p1;
    }
}

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

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

Векторы и строки (С++)

К моменту создания C++, внезапно оказалось, что C-строки, представимые в виде массива символов, ровно как и нерасширяемые массивы, морально устарели. Поэтому Бьярн Страуструп ввёл супер удобные классы string и vector<T>, которые несколько повышают уровень абстракции и работают столь же эффективно.

Работа со строками

Операции	Описание
`s[i]`	i-ый символ
`s.size()`	Размер строки
`s.c_str()`	Константный указатель на c-строку
`string s1 = s`	Новая копия строки

`s.erase(1, 3)`	Удаление 3 символов
`s.substr(1, 3)`	Подстрока из 3 символов
`s.insert(1, s1)`	Вставка s1 перед 1 символом
`s.find_first_of(s1)`	Поиск любого символа из s1
`s.find(s1)`	Поиск подстроки в строке

`string::npos`	-1, ~ нет совпадений

string::npos — это специальная константа, которая была введена в язык для обозначения несуществующего индекса в массиве. Значение этой константы, строго говоря, зависит от реализации стандартной библиотеки, однако, как правило, ее значение равно -1.

Векторы

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

#include <vector>
using namespace std;

vector<int> v(10);   // Вектор из 10 нулей
v[0] = 5;

v.size();
v.push_back(777);  // Вставить новый элемент в конец
p.pop_back();      // Удаление последнего элемента

Контроль выхода за границы реализован не был т.к. это привело бы к снижению производительности.

Что происходит, когда векторы присваиваются

При выполнении операции v1 = v происходят следующие действия:

Память занимаемая v1 уничтожается.
Для v1 выделяется память размера v.
Содержимое v копируется в v1.

Процесс копирования вектора

Как вектор управляет памятью

Вектор выделяет чуть больше памяти чем ему требуется для хранения элементов. Поэтому различают логическую длину (size) и фактическую длину (capacity).

v.capacity();  // Получить фактическую длину

Как только size пытается превысить capacity, capacity увеличивается и происходит выделение дополнительной памяти.

v.resize(n);    // Изменить размер (обрезать / дополнить нулями)
v.reserve(n);   // Увеличить вектор, чтобы можно было хранить n элементов

При добавлении элемента, если выполняется условие size > cap тогда capacity увеличивается в 2 раза: v.reserve(size * 2).

Если в процессе работы программы становится ясно, что в дальнейшем размер вектора увеличиваться не будет, тогда можно урезать capacity вектора до его size.

v.shrink_to_fit();      // C++11
vector<int>(v).swap(v); // C++98

Классы и перегрузка операций

В языке С++ есть встроенные типы. Например

int i;
double d;

При этом мы можем производить с ними привычные действия.

d = 5.0; i = 3;
d = i * d;

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

Отличие класса от структуры, лишь в том, что в классе поля по-умолчанию приватные, а в структуре публичные.

Описание класса

Рассмотрим процесс создания класса на примере класса Date. Описание самого класса необходимо помещать в *.h файл.

/* date.h */

class Date
{
    private: // это слово писать не обязательно
        int y, m, d;

    public:
        // Конструктор класса
        Date(int d, int m, int y)
        {
          this->d = d;
          this->m = m;
          this->y = y;
        }

        void add_days(int n);
};

Все функции размещенные внутри класса автоматически помечаются модификатором inline.

Определение внешних функций класса осуществляется в *.cpp файлах.

/* date.cpp */

#include "date.h"

// Определение некоторой функции вне интерфейса класса
void Date::add_days(int n)
{
  ...
}

При надлежащей реализации класса Data, в C++ будут возможный действия следующего рода:

Data d(17, 10, 14), d1 = d;
cin >> d1;
Date d2(31, 12, 14);

d += 7;
d1 = d1 - 7;
int n = d2 - d;
if (d == d1)...
d++; ++d; d1--; --d1;
d2++;
cout << d << ' ' << d1

Как видим это код выглядит так, будто Data это встроенный тип.

Перегрузка бинарной операции

Перегрузка операции это описание операции с тем же именем, но работающей с другими типами.

@ - обозначение бинарной операции в рамках курса

Существует 2 способа

1.Как функцию-член

a.operator@(b)

2.Как внешнюю функцию

~operator@(a, b)

Реализовывать необходимо одно из двух. При попытке реализовать оба варианта компилятор выдаст ошибку.

class Date
{

    ...

    void operator+=(int n)
    {
        add_days(n); // inline
    }
}

т.е. d += 7; ~ d.operator+=(7); ~ d.add_days(7);

Передача объектов в функцию

Напомним, что в C++ передача параметров в функцию осуществляется по значению, то есть в функцию передается копия передаваемой переменной. Этот факт справедлив и для очень больших объектов таких как string или vector. Чтобы не происходило полного копирования объектов, нужно передавать их по ссылке:

void f(vector<int> &v);

void f(const string &s);   // Изменить строку не получится