Цель работы:
- познакомиться с классами
- повысить навыки написания обобщенного кода
- усвоить "внутренности" STL библиотеки
- узнать об инженерной составляющей, которая позволяет повысить эффективность кода за счет различных приемов (в частности об амортизированной сложности)
- получить навыки написания итераторов для пользовательского контейнера
Объектно-ориентированное программирование - парадигма программирования, где упрощение программного кода происходит за счёт дробления кодовой базы на независимые, изолированные части. Куски логической структуры программы и связанные с ними данные разбиваются на классы. Классы инстанцируются в различные наборы данных - объекты. Конечное взаимодействие "пользователя" класса заключается в инстанцировании этого класса в объект и изолированном взаимодействии с этим объектом через методы.
Изначально ООП был задуман как способ хранения данных в куче, и это в полном объёме представлено библиотекой контейнеров STL C++. В этой лабораторной работе вам предстоит познакомиться с внутренней реализацией контейнера vector.
Классы - основополагающая сущность в ООП. В C++ классы практически не отличаются от структур, с которыми вам уже приходилось сталкиваться в первом семестре курса. Фактически единственное отличие классов от структур в C++ - это спецификатор доступа по-умолчанию: в struct это public, а в class - это private. В рамках ООП принято использовать class.
В ООП принято считать, что с объектами стоит взаимодействовать через методы. Методы - это функции, которые тесно взаимодействуют с полями класса. Из того, с чем вы уже наверняка успели подружиться, есть методы std::vector: push_back(), begin(), end(). В идеале ООП подразумевает полную изоляцию внутренних полей - это называется инкапсуляция. Для создания метода, нужно создать функцию внутри класса:
class MyClass {
int my_field;
public:
int get_my_field() {
return my_field;
}
};В данном случае метод get_my_field() - типичный пример геттера (метод, возвращающий значение поля).
Ранее упомянутая цель хранить данные в куче привносит некоторые проблемы: память, выделенную на куче в C++ необходимо собственноручно освободить. В C++ используется концепт RAII: Resource Aquisition Is Initialization
Основные правила RAII:
- Инициализация структуры (даже если она не связана с созданием объекта) приводит к выделению памяти
- Дополнительные выделения памяти должны быть локализованы в методах
- Если есть случай, когда объект существует с невыделенной памятью, нужно убедиться, что везде этот случай успешно обрабатывается
- Прекращение существования объекта (например, выход его из области видимости) приводит к освобождению памяти
Шабло́ны (англ. template) - средство языка программирования, предназначенное для разработки обобщённых алгоритмов, без привязки к некоторым параметрам, зачастую без привязки к типам данных.
Шаблоны позволяют определить универсальные конструкции (функции и/или классы), которые не зависят от определенного типа.
Чтобы без шаблонов реализовать функцию определения минимального элемента из двух аргументов необходимо реализовать эту функцию для каждого типа
float min(float a, float b) { return a < b ? a : b; }
int min(int a, int b) { return a < b ? a : b; }
double min(double a, double b) { return a < b ? a : b; }
/// ...Используя шаблоны, можно реализовать функцию один раз:
template <class T>
T min(T a, T b) {
return (a < b) ? a : b;
}Ключевое слово template означает, что далее идет шаблон функии (или класса, если указывается перед определением класса).
В треугольных скобках <> указываются аргументы шаблона. Так в примере выше указывается, что аргуметом шаблона фукнции будет некий тип T. У шаблонов может быть несколько аргументов, которые перечисляются через запятую template <class T, class U, class V>.
Кроме ключевого слова class можно использовать ключевое слово typename. В большинстве случаев нет никакой разницы в использовании этих двух ключевых слов. Кроме единственного случая. Об этом можно почитать по ссылке.
Шаблоны классов и функций рекомендуется определять в заголовочных файлах, а не делить на заголовчный файл и файл с реализацией.
Инстанцирование шаблона – это генерация кода функции или класса по шаблону для конкретных параметров.
Различают неявное инстанцирование, которое происходит при вызове функции или создании объекта класса, и явное инстанцирование с помощью резервированного слова template. Инстанцирование можно делать только в точке программы, где доступна реализация шаблона функции или методов шаблонного класса.
template double min(double, double);int main() {
int a = 0;
int b = 0;
std::cin >> a >> b;
std::cout << min(a, b);
}Во время компиляции исходного кода компилятор встречает вызов функции min. Он определяет тип для которого необходима эта фукнция, в примере этот тип int. И компилятор генерирует код функции по шаблону для конкретного типа int. Этот процесс можно представить так, что компилятор написал новый заголовочный файл в который перенес шаблонную функцию, только везде вместо типа T подставил тип int.
Представим следующий код
int main() {
int a = 0;
float b = 0;
std::cin >> a >> b;
std::cout << min(a, b);
}В шаблонную функции передаются два разных типа int и float. Но в шаблоне аргументы объявлены как одинаковые типы:
T min(T a, T b);Для какого именно типа должен инстанцировать функцию компилятор: для int или для float? Компилятор не может однозначно ответить на этот вопрос, поэтому он делает единственно правильную вещь. Компилятор прерывает процесс компиляции и сообщает об ошибке времени компиляции разработчику. Это спасает от множества ошибок.
В подобных случаях у разработчика есть два варианта:
- переписать код таким образом, что неоднозначности не будет
- явно указать компилятору какой тип использовать
int main() {
int a = 0;
float b = 0;
std::cin >> a >> b;
std::cout << min<float>(a, b); // Явно указываем, использовать float
std::cout << min<int>(a, b); // Явно указываем, использовать int
std::cout << min<double>(a, b); // Явно указываем, использовать double
}Иногда есть необходимость использовать код для некоторого шаблонного аргумента, который не совпадает с основным кодом шаблона.
Например, мы хотим реализовать функцию поиска минимума из двух Си-строк.
Если использовать обычный код шаблона, то будут сравниваться значения указателей, а не значения строк:
const char* min(const char* a, const char* b) {
return (a < b) ? a : b;
}Выше представлен некорректный код, который получит компилятор испоьзуя реализованный шаблон фукнции min.
Эту проблему призвана решать специализация шаблонов. С помощью нее можно определить реализацию шаблона функции для одного типа данных, которая будет отличаться от реализации шаблона функции для другого типа данных.
Ниже специализация шаблона для Си-строк.
template <>
const char* min(const char* a, const char* b) {
return (strcmp(a, b) < 0) ? a : b;
}Специализация бывает полной и частичной. Подробнее можно прочитать в статье.
Уже раньше упоминалось, что std::vector - это класс. Прозорливый глаз мог заметить, что std::vector может хранить абсолютно любой тип данных, и при этом программисту не приходится каждый раз переписывать половину всего что есть в этой библиотеке
Этого позволяют достигнуть шаблоны. Поле класса может содержать какой-то заранее неизвестный тип T, или указатель T*:
#include <iostream>
template<class T>
class MyClass {
T my_field;
public:
T get_my_field() { return my_field; }
};
int main() {
MyClass<std::string> my_object;
std::cout << my_object.get_my_field() << std::endl;
}Контейнеры - это классы, которые инкапсулируют некую внутреннюю структуру, будь то массив, список или дерево. И снова примером станет std::vector - контейнер, инкапсулирующий динамический массив. Из интересных методов std::vector можно заметить resize(), reserve(), push_back(), insert(). Все они увеличивают количество хранимых данных, но операционная система не может постоянно добавлять память к уже выделенной. По итогу, вне поля зрения конечного пользователя контейнера происходят относительно сложные операции: выделение памяти, копирование старых данных в новый участок памяти, модификация внутренних полей контейнера.
Контейнеры задуманы как структура, из которой потом возможно достать хранимые элементы. Порой неудобно задумываться над внутренним устройством контейнера. Абстракция над этими соображениями представлена в C++ с помощью итераторов. На итераторы можно смотреть как на курсор в текстовом документе
Итератор – это объект, который позволяет перебирать элементы контейнера, переходя от одного элемента к другому. Контейнеры поддерживают определенный тип итератора, который наделен своим собственным набором доступных операций. Библиотека итераторов в STL помогает соединить контейнеры STL вместе с алгоритмами STL. При этом и контейнеры и алгоритмы не завязаны друг на друга, связь осуществляется только через итераторы. На итераторы можно смотреть как на курсор, указывающий на текущий элемент. Этот курсор можно двигать относительно его текущей позиции, в зависимости от типа итератора, на различные смещения. Итератор в себе хранит ту информацию, которая ему необходима для доступа к элементу и выполнению сдвига. Для списка это может быть указатель на вершину, а для массива - это указатель на конкретный элемент.
Эти наборы отличаются и зависят от различных категорий итераторов:
- input_iterator (Входной)
- output_iterator (Выходной)
- forward_iterator (Однонаправленный)
- bidirectional_iterator (Двунаправленный)
- random_access_iterator (Произвольного доступа)
- contiguous_iterator (Данные расположены последовательно в памяти)
Подробнее - https://en.cppreference.com/w/cpp/iterator
Различные типы итераторов "вложены" друг в друга, например bidirectional_iterator полностью имплементирует forward_iterator, random_access_iterator полностью имплементирует forward_iterator.
Чтобы реализовать собственный класс итератора, необходимо в нём задать псевдонимы типов:
class Iterator {
using iterator_concept [[maybe_unused]] = std::contiguous_iterator_tag;
// ...
};Здесь мы указываем, что наш итератор является итератором контейнера, элементы которого расположены последовательно в одном участке памяти (как в массиве) - https://en.cppreference.com/w/cpp/iterator/contiguous_iterator
Также необходимо реализовать сам итератор:
xxclass Iterator {
// тут будет псевдоним типа
Iterator(/* данные для инициализации итератора */) {}
~Iterator() {}
T& operator*() {} // "разыменование" итератора
const T& operator*() const {}
Iterator& operator=(const Iterator&) {}
// для forward_iterator
bool operator==(const Iterator&) {}
Iterator& operator++() {}
// для bidirectional_iterator
Iterator& operator--() {}
// для random_access_iterator
Iterator& operator+=(size_t) {}
Iterator& operator-=(size_t) {}
Iterator operator+(size_t) {}
Iterator operator-(size_t) {}
Iterator& operator[](size_t) {}
bool operator<(const Iterator&) const {}
bool operator>(const Iterator&) const {}
bool operator<=(const Iterator&) const {}
bool operator>=(const Iterator&) const {}
// есть мегахак в C++20:
// Возвращает -1, если меньше
// Возвращает 0, если равно
// Возвращает 1, если больше
// bool operator<=>(const Iterator&) const {}
//
// Реализовав этот оператор, все операторы сравнения
// будут реализованы автоматически
// Меньше кода, меньше хлопот!
//
// Довольно часто можно даже
// bool operator<=>(const Iterator&) const = default;
};Реализация методов и внутренней работы итераторов лежит на разработчике и сильно зависит от того, для какого контейнера реализовывается данный итератор.
Например, реализация итератора для класса vector будет очень похожа на работу с обычными указателями (объект итератора будет содержать указатель на элемент). Реализация же итератора для map будет более сложной и будет сильно зависеть от реализации структуры данных контейнера.
Чтобы правильно реализовать класс vector, необходимо узнать об амортизированной сложности метода push_back. Нет смысла пересказывать то, что уже хорошо описано. Поэтому предлагается самостоятельно ознакомиться с этим понятием по ссылкам:
Вкратце: push_back выделяет памяти больше, чем действительно нужно для одного элемента, и не выделяет память, если это не необходимо. Поэтому в классе vector помимо поля size есть поле capacity
- Реализуйте аналог
std::vector. - Обеспечьте амортизированную сложность O(1) добавления элемента в конец вектора.
- Проверьте код на наличие утечек памяти.
- Использовать
std::vectorзапрещается. - По желанию Проверьте, что ваша реализация правильно работает со стандартными алгоритмами STL (
std::sort,std::copy_if,std::find_if).
template <class T>
class vector {
public:
vector(); // конструктор по умолчанию
vector(const vector<T>&); // конструктор копирования
vector(size_t, const T&); // конструктор, заполняющий массив элементами с заданным значением
~vector(); // деструктор
operator=(const vector<T>&); // оператор присваивания (копирования)
constexpr T& operator[size_t]; // оператор индексации
// необязательно, если хотите познакомиться с исключениями
constexpr T& at(size_t); // безопасный оператор индексации (проверяет на выход за границы массива)
constexpr T& front(); // первый элемент (безопасно)
constexpr T& back(); // последний элемент (безопасно)
constexpr T* data(); // низлежащий указатель на элемент
constexpr vector::iterator begin(); // возвращает итератор на начало массива
constexpr vector::iterator end(); // возвращает итератор на конец массива (элемент "после последнего")
constexpr bool empty(); // возвращает true, если контейнер пуст
constexpr size_t size(); // возвращает количество хранимых элементов
constexpr void reserve(size_t); // выделяет память для хранения элементов (предварительно)
сonstexpr size_t capacity(); // возвращает количество элементов, которые массив может в себя вместить без реаллокаций
constexpr void clear(); // очищает массив, освобождает память
// необязательно, если хотите поиграться с памятью
constexpr vector::iterator insert(const vector::iterator, const T&); // вставка элемента после поданного итератора
constexpr void push_back(const T&); // вставка элемента в конец
constexpr void pop_back(); // удаление элемента из конца массива
constexpr void swap(vector<T>&); // обмен значений массивов
class Iterator {
// ...
};
};Замечание: constexpr в данном случае даёт компилятору знать, что функцию можно inline'ить. Так как при работе с контейнерами вызов функций довольно част, inline может сильно ускорить работу. В общем случае constexpr означает что выражение можно посчитать на этапе компиляции, для работы программы это кодовое слово не несёт значения