ТГиК-2019-Лекция-23.09.2019

Материал из Кафедра Прикладной Математики
Перейти к навигации Перейти к поиску

Тема лекции - модель памяти и структуры данных.

Презентация по данной лекции

Содержание

Зачем нужны структуры данных?

В любых задачах, которые решаются программистами, используются структуры данных. Если коротко, структура данных — это контейнер, информация в котором скомпонована характерным образом. Благодаря такой «компоновке», структура данных будет эффективна в одних операциях и неэффективна — в других. Наша цель — разобраться в структурах данных таким образом, чтобы вы могли выбрать из них наиболее подходящую для решения конкретной стоящей перед вами задачи. В нашей лекции мы рассмотрим и реализуем два контейнера, используемые в С++: list и vector.

Некоторые структуры данных

Рис.1. Массив

Что такое массив?

Массив - это структура данных, представленная в виде группы ячеек одного типа, объединенных под одним единым именем.

Массивы используются для обработки большого количества однотипных данных. Отдельная ячейка данных массива называется элементом массива. Элементами массива могут быть данные любого типа. Массивы могут иметь как одно, так и более одного измерений. В зависимости от количества измерений массивы делятся на одномерные массивы, двумерные массивы, трёхмерные массивы и так далее до n-мерного массива. Чаще всего в программировании используются одномерные и двумерные массивы.

Схематично массив изображён на рис.1

Рис.2. Список

Что такое список?

Список – это структура данных, представляющая собой последовательность элементов, в каждом из которых хранится информация: например, данные и указатель на следующий узел в цепочке. Есть головной указатель, соответствующий первому элементу в связном списке, и, если список пуст, то он направлен просто на null. При помощи связных списков реализуются файловые системы, хеш-таблицы и списки смежности. На рис.1 наглядно изображена внутренняя структура связного списка.

Рис.3. Типы списков

Типы списков

Существуют такие типы связных списков:

  • Односвязный список (однонаправленный)
  • Двусвязный список (двунаправленный)

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

Рис.4. Стек

Что такое стек?

Стек (англ. stack — стопка) — абстрактный тип данных, представляющий собой список элементов, организованных по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»). Структура стека представлена на рис.3

Что такое вектор?

Вектор — это структура данных, которая является моделью динамического массива.

Объявление вектора: vector < тип данных > <имя вектора>;

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

Основные методы класса std::vector

Методы и пояснения
a.push_back(val) добавляет к вектору a последний элемент val
a[index] извлекает элемент под номером index
a.capacity() возвращает кол-во элементов, которое может быть помещено в зарезервированную память
a.size() возвращает кол-во элементов

Функции

Чем больше строк кода, тем сложнее понять программу. Для того, чтобы упростить понимание и не писать несколько раз одно и то же, используют функции.

Преимущества функции:

  1. Упрощается текст программы за счет модульности (прочитать и понять несколько вызовов функций легче, чем понять длинную последовательность команд)
  2. Уменьшается дублирование текста
  3. Упрощается отладка и тестирование
  4. Имя функции помогает понять её тело

Функции в С++

Объявление функции в С++ содержит:

  1. Тип возвращаемого значения (если функция не должна возвращать значение, используется тип void)
  2. Имя функции
  3. Параметры функции, которые перечисляются в скобках через запятую
  4. Тело функции реализуется в фигурных скобках. Для возврата значения из функции используется return

Пример

Нужно найти сумму двух чисел m и n и вывести полученное значение

#include <iostream>
using namespace std;

int Sum (int x, int y) {
	return x + y;
}

void PrintSum(int n, int m) {
	int sum = Sum(n,m);
	cout << "Sum of integers: " << n << " and " << m << " is " << sum;
} 

int main() {
	int n, m;
	cin >> n >> m;
	PrintSum(n,m);
	return 0;
}

Параметры функции

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

Передача параметров по значению

В предыдущем примере параметры в функцию передавались по значению. Что это означает? Рассмотрим следующий пример:

#include <iostream>
using namespace std;

void ChangeInteger(int x , int y) {
	x = y;
}

int main() {
	int n, m;
	cin >> n >> m;
	ChangeInteger(n,m);
	cout << n;
	return 0;
}

Запустив данный код, мы увидим, что выводится число n, а не m, но почему? Оказывается, что значение n копируется в переменную x при вызове функции. Затем мы изменяем значение x, не трогая переменную m.

Передача параметров по ссылке

Как тогда изменить значение n? Следует передать значения по ссылке, а именно:

void ChangeInteger(int& x , int& y) {
	x = y;
}

Таким образом, для изменения параметров в функции, нужно их передавать по ссылке. Простейший пример, когда нужно изменить параметры по ссылке - это функция swap, которая меняет местами значения:

void Swap(int& x , int& y) {
	int k = x;
	x = y;
	y = k;
}

Передача параметров по константной ссылке

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

size_t PrintVectorSize(vector<int> nums) {
	return nums.size();
}

Если замерить время выполнения этой функции, оно окажется 144 ms. Это слишком много. Давайте передадим вектор по ссылке. Тогда время выполнения будет 0 ms. На данный момент у нас появилось уязвимое место в программе, а именно: мы можем случайно изменить вектор, который НЕ ДОЛЖЕН изменяться. Для того, чтобы исключить такие случайные изменения, существует модификатор const.То есть для решения нашей проблемы нужно передать вектор по константной ссылке. В этом случае вектор не будет копироваться и будет защищен от изменений.

size_t PrintVectorSize(const vector<int>& nums) {
	return nums.size();
}

Главное значение модификатора const - помочь программисту понять, что данная переменная не должна изменяться. Если попытаться это сделать, компилятор выдаст ошибку.

Что такое ООП?

Объектно-ориентированное программирование - это методика разработки программных средств, основанная на представлении программы в виде совокупности объектов, каждый из которых является экземпляром определенного класса, а классы образуют иерархию наследования. Объект - реально существующий предмет со всеми его индивидуальными характеристиками. Класс – это множество объектов с одинаковыми свойствами и одинаковым поведением.

Структура

Структура (struct) — набор публичных полей. Используется, если не нужно контролировать целостность. Типичный пример структуры:

struct Point {
	double x;
	double y;
	Point(double x_, double y_) : x(x_), y(y_) {} 
};

Класс

Класс (class) скрывает данные и предоставляет определенный интерфейс доступа к ним. Используется, если поля связаны друг с другом и эту связь нужно контролировать.

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

#include <iostream>
using namespace std;

class A {
public:
	A() {
		cout << "constructor\n"; 
	}

	~A() {
		cout << "destructor\n";
	}

	void Print() {
        std::cout << "This is class A\n";
    }
};

int main() {
	A a;
	a.Print();
	return 0;
}

//constructor
//This is class A
//destructor

Шаблоны функций и классов

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

Шаблоны функций - это мощный инструмент в С++, который намного упрощает труд программиста. Например, нам нужно запрограммировать функцию, которая выводила бы на экран элементы массива. Задача не сложная! Но, чтобы написать такую функцию, мы должны знать тип данных массива, который будем выводить на экран. И тут нам говорят — тип данных не один, мы хотим, чтобы функция выводила массивы типа int, double, float и char.

Ниже - шаблон для структуры. Он аналогично пишется для класса.

template <typename T>
struct Point {
	T x;
	T y;
	Point(T x_, T y_)
	: x(x_)
	, y(y_) {} 
};

Перегрузка операторов

Пусть имеется два вектора, которые отличаются только типами хранимых значений. Так как типы различны, нам придётся написать 2 функции для вывода всех элементов векторов так, как показано ниже.

#include <iostream>
    #include <vector>
    
    using namespace std;
    
    void Print(vector<int> v) {
        for (size_t i = 0; i < v.size(); ++i) {
            cout << v[i] << " ";
        }
        return;
    }
    
    void Print(vector<double> v) {
        for (size_t i = 0; i < v.size(); ++i) {
            cout << v[i] << " ";
        }
        return;
    }

Для оптимизации в таких случаях используются шаблоны функций. Создадим шаблон для функции Print

//Шаблон для функции Print
    template<typename T>
    void Print(vector<T> v) {
        for (size_t i = 0; i < v.size(); ++i) {
            cout << v[i] << " ";
        }
        return;
    }

А для более хорошего и красивого решения следует использовать перегрузку оператора

//Перегрузка оператора вывода
    template<typename T>
    ostream& operator << (ostream& stream, vector<T> v) {
        stream << "Print vector: ";
        for (size_t i = 0; i < v.size(); ++i) {
            stream << v[i] << " ";
        }
        return stream;
    }
    
    int main() {
        vector<int> v1 = {1,2,3};
        vector<double> v2 = {1.1, 2.2, 3.3};
        
        Print(v1);
        cout << "\n";
    
        Print(v2);
        
        cout << v1 << "\n" << v2 << "\n";
        
        return 0;
    }

Модель памяти

Наименьшая единица памяти в С++ — байт. Память, доступная программе на С++, состоит из последовательностей байт (ненулевой длины), называемых областями памяти (memory location). У каждого байта памяти есть уникальный адрес в памяти, который принято записывать как шестнадцатеричное число с префиксом «0x».

Среди моделей памяти различают стек и кучу.

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

Время жизни данных

Время жизни объекта (object lifetime) — это период во время выполнения программы, когда данные находятся в памяти. Любые свойства данных справедливы только в этот период. Время жизни простых типов данных начинается с момента, когда для них (компилятором или программистом) выделена область памяти, а заканчивается с освобождением (явным или неявным) этой области.

Минимальное время жизни данных называется временем хранения (storage duration), оно зафиксировано в стандарте С++ и всегда известно.

Статическое время хранения означает, что данные находятся в памяти на протяжении всего времени выполнения программы. Им обладают данные в глобальных переменных (если не используется динамическая память), и в локальных, если они объявлены с ключевым словом static (например, static int i = 0).

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

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

Модель памяти: стек

Автоматическая модель памяти, также известная "стек", работает по принципу LIFO (last in, first out), т.е. последним зашел-первым вышел. Автоматическая память работает именно на основе стека, чтобы вызванная из любой части программы функция не затёрла уже используемую автоматическую память, а добавила свои данные в конец стека, увеличивая его размер. При завершении этой функции её данные будут удалены с конца стека, уменьшая его размер. Длина стека останется той же, что и до вызова функции, а у вызывающей функции указатель на конец стека будет указывать на тот же адрес.

Рассмотрим следующий пример:

#include <iostream>
using namespace std;

void f() {
	int k = 5;
}

void g() {
	int k = 7;
	f();
}

int main() {
	int n = 4;
	f();
	g();
	return 0;
}
Аним2-min.gif

Когда в программе запускается очередная функция, то на стеке резервируется блок памяти, достаточный для хранения локальных переменных. Кроме того, в этом блоке хранится служебная информация, такая как адрес возврата. Такая область памяти называется стековым фреймом функции. Когда функция main запускает функцию f, то на стеке ниже функции main резервируется фрейм для функции f. То же самое происходит, когда main вызывает функцию g, а та в свою очередь вызывает f.

Когда функция завершает свою работу, то вершина стека перемещается на фрейм предыдущей функции. При этом фрейм отработавшей функции просто остаётся на стеке. Выйдем из функции f функцию main, запустим функцию g из main. Стековый фрейм перетирает данные, которые были в стеке от предыдущих вызовов. Выйдем из функции g и выйдем из функции main. Когда выходим из программы, то вершина стека поднимается до самого верха.

Модель памяти: куча

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

Оператор new

Чтобы выделить память типа Т в куче, нужно объявить локальную переменную T*:

T* ptr = new T;

new - специальный оператор, который выделяет место в куче. Сама переменная ptr будет находиться в стеке, но указывать на область памяти в куче.

Указатель – это адрес в памяти. Память в С++ представляется как линейный массив байтов. Указатель – это индекс в этом массиве.

Оператор * (оператор разыменовывания), примененный к указателю, возвращает ссылку на объект в куче.

Пример:

int* a = new int;
*a = 4;
int& reference_to_a = *a;
reference_to_a += 10;
cout << *a; // 14
Рис.6. Оператор delete

Оператор delete

Чтобы освободить память, выделенную оператором new, нужно вызвать оператор delete, иначе будет возникать утечка памяти. Что такое утечка памяти? Допустим, что выделяется память в куче, которая потом не освобождается. В конце концов память будет заполнена полностью и программа упадет.

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

delete a;

Оператор new[]

Оператор new[] используется для создания последовательного блока элементов.

T - тип элементов, size - размер блока, data - указатель на первый элемент в блоке.

T* data = new T[size];
Рис.7. Оператор delete[]

Оператор delete[]

Оператор delete[] используется для удаления последовательного блока элементов.

delete[] data;

Если вместо delete[] написать delete, программа может работать некорректно.

Когда выделяется память в куче с помощью new[], выделяется чуть больше места, чем size, выделяется также место для количества элементов. delete[] указывает на количество элементов, после этого удаляются все size элементов.

Арифметика указателей

Как уже было сказано, data - указатель на первый элемент в выделенном блоке. Чтобы обратиться к другим элементам, достаточно прибавить целое число, например: data + 1 будет указывать на второй элемент.

Константный указатель и указатель на константу

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

Указатель на константу

В этом случае можно изменять указатель, но нельзя изменять сам объект

int x = 7;
const T* ptr = &x;
*ptr = 4; // Ошибка!!!
++ptr;

Константный указатель

Можно изменять объект, но нельзя изменять указатель

T* const ptr = &x;
*ptr = 4; 
++ptr; // Ошибка!!!

Константный указатель на константу

Нельзя изменять указатель и объект

const T* const ptr;

Указатели при работе с собственными структурами и классами

#include <iostream>
using namespace std;

class A {
public:
	A() {
		cout << "constructor\n"; 
	}

	~A() {
		cout << "destructor\n";
	}

	void Print() {
        std::cout << "This is class A\n";
    }
};

int main() {
	A* a = new A;
	(*a).Print();
  a->Print();
	delete a;
	return 0;
}

//constructor
//This is class A
//This is class A
//destructor

Рассмотрим данный пример подробнее: как уже говорилось, если создавать элемент в куче, его нужно ОБЯЗАТЕЛЬНО удалять. Если не вызывать delete или delete[], элемент не удалится из кучи в нашем примере. Если вызвать оператор удаления элемента класса A, вызовется его деструктор.

Чтобы обратиться к элементам или методам, который содержит в себе указатель на класс А, можно написать один из следующих двух способов:

  1. (*a).Print(); // сначала разыменовываем указатель (т.е. получаем ссылку), после через . пишем какое поле класса хотим получить
  2. a→Print(); //делает то же самое, но намного удобнее использовать

Однонаправленный список

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

Требования к методам
Методы Требования
GetHead Возвращает указатель на голову списка, он используется для перебора элементов списка
PushFront Добавляет новый элемент в голову списка
InsertAfter Вставляет новый элемент в список так, чтобы он шёл после узла node. Если node == nullptr, метод эквивалентен PushFront
PopFront Удаляет элемент из головы списка и освобождает выделенную под него память. Если список пуст, метод завершается корректно. Если после выполнения метода список стал пустым, метод GetHead должен возвращать nullptr
RemoveAfter Должен удалять из списка элемент, который следует за узлом node, и освобождать выделенную под него память. Если node == nullptr, метод эквивалентен PopFront. Если node->next == nullptr, то метод должен корректно завершаться

Все методы, перечисленные выше, должны работать за O(1)

Деструктор класса List освобождает всю память, выделенную для хранения элементов списка.

template <typename T>
class List {
public:
  struct Node {
    T value;
    Node* next = nullptr;
  };

  ~List();

  void PushFront(const T& value);
  void InsertAfter(Node* node, const T& value);
  void RemoveAfter(Node* node);
  void PopFront();

  Node* GetHead() { return head; }
  const Node* GetHead() const { return head; }

private:
  Node* head = nullptr;
};

template <typename T>
LinkedList<T>::~LinkedList() {
  while (head) {
    PopFront();
  }
}

template <typename T>
void LinkedList<T>::PushFront(const T& value) {
  auto node = new Node{value};
  node->next = head;
  head = node;
}

template <typename T>
void LinkedList<T>::InsertAfter(Node* node, const T& value) {
  if (node) {
    auto new_node = new Node{value};
    new_node->next = node->next;
    node->next = new_node;
  } else {
    PushFront(value);
  }
}

template <typename T>
void LinkedList<T>::RemoveAfter(Node* node) {
  if (!node) {
    PopFront();
  } else if (node->next) {
    auto removing_node = node->next;
    node->next = removing_node->next;
    delete removing_node;
  }
}

template <typename T>
void LinkedList<T>::PopFront() {
  if (head) {
    Node* new_head = head->next;
    delete head;
    head = new_head;
  }
}

И ещё одна, более простая реализация:

#include <exception>
#include <iostream>

template<typename T>
class List {
public:
    List() // 0.1
    : data(nullptr)
    , size(0) {}
    
    T Front() { //2
        return data->val;
    }
    
    T Back() { //3
        node* cur = data;
        while (cur->next != nullptr) {
            cur = cur->next;
        }
        return cur->val;
    }
    
    bool Empty() { //1.2
        return data == nullptr;
    }
    
    bool Size() { //1.1
        return size;
    }
    
    void Insert(const T val, const size_t pos) {  //5
        if (pos < 0 || pos > size) throw std::out_of_range("Position is uncorrect");
        
        node* element = new node(val);
        if (pos == 0) {
            element->next = data;
            data = element;
        } else {
            node* cur = data;
            size_t cur_pos = 0;
            while (cur != nullptr && cur_pos + 1 < pos) {
	              cur = cur->next;
								++cur_pos;
            }
            element->next = cur->next;
            cur->next = element;
        }
        ++size;
    }
    
    void Write() { //4
        node* cur = data;
        while(cur != nullptr) {
            std::cout << cur->val << " ";
            cur = cur->next;
        }
    }
    
    ~List() { //0.2
        while (data != nullptr) {
            node* head = data->next;
            delete data;
            data = head;
        }
    }
    
private:
    struct node {
        T val;
        node* next;
        
        node(T val_)
        : val(val_)
        , next(nullptr) {};
    };
    
    node* data;
    size_t size;
};

int main() {
    try {
        List<int> myList;
        myList.Insert(5, 0);
        myList.Insert(6, 1);
        myList.Insert(7, 1);

        if (myList.Empty()) {
            std::cout << "My list is empty" << std::endl;
        } else {
            std::cout << "My list is not empty" << std::endl;
            myList.Write();
            std::cout << "\nFront is " << myList.Front() << "\nBack is " << myList.Back();
        }
    } catch(const std::exception& ex) {
        std::cout << ex.what();
    }
    
    return 0;
}

Реализация собственного вектора

Давайте подробнее рассмотрим класс std::vector. Мы увидим, что у него есть член класса iterator.

Итератор - "умный" указатель на элемент контейнера, который учитывает его особенности. Например, у всех контейнеров есть методы begin() и end(). begin() возвращает итератор на первый элемент, end() на элемент, находящийся за последним элементом. Таким образом, в С++ реализована концепция полуинтервалов, т.е. вектор лежит в пределах [begin(), end()).

Во всех алгоритмах из библиотеки algorithm используются итераторы. Например, если вы хотите отсортировать вектор по возрастанию нужно вызвать: sort(a.begin(), a.end()).

Реализуем вектор со следующими требованиями:

  • первый вызов метода PushBack для вновь созданного объекта должен делать ёмкость, равной единице
  • метод PushBack должен иметь амортизированную константную сложность
  • метод PushBack должен иметь амортизированную константную сложность
  • в деструкторе должен освобождаться текущий блок памяти, выделенный вектором
Требования к методам
Метод Требования
Capacity Должен возвращать текущую ёмкость вектора — количество элементов, которое помещается в блок памяти, выделенный вектором в данный момент
Size Должен возвращать количество элементов в векторе
PushBack Добавляет новый элемент в конец вектора; если в текущем выделенном блоке памяти не осталось свободного места (т.е. Size() == Capacity()), вектор должен выделить блок размера 2 * Capacity(), скопировать в него все элементы и удалить старый
#include <algorithm>

using namespace std;

template <typename T>
class SimpleVector {
public:
    SimpleVector() = default;
    
    explicit SimpleVector(size_t size) {
        data_begin = new T[size];
        capacity = size;
        this->size = size;
    }
    
    ~SimpleVector() {
        delete[] data_begin;
    }
    
    T& operator[](size_t index) {
        return data_begin[index];
    }
    
    T* begin() {
        return data_begin;
    }
    
    T* end() {
        return data_begin + size;
    }
    
    size_t Size() const {
        return size;
    }
    
    size_t Capacity() const {
        return capacity;
    }
    
    void PushBack(T value) {
        if (Size() == 0) {
            data_begin = new T[++capacity];
        } else if (Size() == Capacity()) {
            capacity *= 2;
            T* new_data = new T[Capacity()];
            move(begin(), end(), new_data);
            
            delete[] data_begin;
            data_begin = new_data;
        }
        
        data_begin[size++] = move(value);
    }
    
private:
    T* data_begin = nullptr;
    size_t capacity = 0;
    size_t size = 0;
};