Реализация библиотеки s21_containers.h.
- Chapter I
1.1. Introduction - Chapter II
2.1. Information - Chapter III
3.1. Part 1
3.2. Part 2
3.3. Part 3
Планета Земля, США, штат Калифорния, где-то среди массивных контейнеров порта Окленда, 29 октября 1993 года.
- Ты правда думаешь, что Бьёрн согласится добавить это в стандарт?
-- Конечно. Тем более он уже интересовался шаблонами пару лет назад, но тогда не смогли добиться достаточно надежности разрабатываемой библиотеки. - сказал мужчина средних лет в белой рубашке и с бейджиком HP Labs, на котором было подписано имя "А. Степанов".
- Я просмотрел твою презентацию по обобщенному программированию. Идея действительно впечатляет, но новый стандарт хотели выпустить до конца года. Здесь же потребуются значительные доработки..
-- Я думаю, что это именно то, чего им не хватало для полного завершения работы над новым стандартом. Тем более, как ты сказал, идея впечатляет. Однако доработки нужны. Для полной уверенности в успешности презентации, нам нужно представить несколько примеров использования подхода и шаблонов в целом. Ты ведь знаком со структурой односвязных списков?
- Ага, кажется начинаю понимать твою задумку. Ты хочешь реализовать обобщенные списки в качестве примера? Один шаблонный класс на все виды типов?
-- Не только. Представь если любой контейнер достаточно описать один раз, а затем использовать с разными типами и классами данных. Сколько времени, сил и ресурсов это сохранит! Списки, словари, множества! - прогулка по набережной Эмбаркадеро становилась явно интереснее.
- Очереди и стеки.. Черт, это гениально.
-- Именно. Кто же после таких примеров откажется от внесения библиотеки в стандарт своего языка?
- Я в деле. Можно будет даже собрать небольшую команду из заинтересованных ребят. Сколько у нас времени на реализацию этих примеров?
-- Около двух недель до встречи с презентацией в Сан Хосе, затем..
В рамках данного проекта вам будет предложено написать собственную библиотеку, реализующую основные стандартные контейнерные классы языка С++: list (список), map (словарь), queue (очередь), set (множество), stack (стек) и vector (вектор). Реализации должны предоставлять весь набор стандартных методов и атрибутов для работы с элементами, проверкой заполненности контейнера и итерирования. В качестве дополнительного задания предлагается реализовать еще несколько не так часто используемых, но отличающихся деталями реализации контейнерных классов из контейнерной библиотеки C++.
Для большинства людей слово контейнер интуитивно понятно и происходит из англоязычного слова contain - "хранить". Так и в программировании: контейнеры используются для хранения наборов объектов одного типа - элементов. Однако контейнерных классов огромное количество. Это связано с тем, что контейнерные классы различаются организацией хранимых наборов объектов и предоставляемыми методами, для взаимодействия с ними. Так, наприер, списки (list) хранят любые объекты, а множества (set) - только уникальные.
Сама необходимость разделять контейнеры, а не использовать для решения различных задач один и тот же, восходит не только к очевидным функциональным различиям. В некоторых случаях эффективнее оказывается использовать списки, например, когда в ходе решения поставленной задачи необходимо часто вставлять элементы в середину контейнера, а если добавление новых элементов производится только в конец, целесообразно использовать очередь.
Каждый вид контейнеров должен предоставить пользователю следующие методы:
-
стандартные конструкторы (конструктор по умолчанию, конструктор копирования, конструктор перемещения, конструктор со списком инициализации, см. материалы);
-
методы доступа к элементам контейнера (например, осуществление доступа к элементу с индексом i);
-
методы проверки наполненности контейнера (например, количество элементов в контейнере, проверка на пустоту контейнера);
-
методы изменения контейнера (удаление и добавление новых элементов, очистка контейнера);
-
методы для работы с итератором контейнера.
Итераторы обеспечивают доступ к элементам контейнера. Для каждого контейнера конкретный тип итератора будет отличаться. Это связано с различным видом организации наборов объектов в контейнерных классах, а также с фактической реализацией контейнера. Итераторы реализуются в таком виде, чтобы они работали схожим образом с указателем на элемент массива языка Си. Именно такой подход через использование итераторов и позволяет взаимодействовать с любыми контейнерами одинаковым образом. Контейнеры предоставляют через методы begin() и end() итераторы, которые указывают на первый и следующий после последнего элементы контейнера соответственно.
Над итератором iter определены следующие операции:
-
*iter: получение элемента, на который указывает итератор; -
++iter: перемещение итератора вперед для обращения к следующему элементу; -
--iter: перемещение итератора назад для обращения к предыдущему элементу; -
iter1 == iter2: два итератора равны, если они указывают на один и тот же элемент; -
iter1 != iter2: два итератора не равны, если они указывают на разные элементы.
Помимо особой организации объектов и предоставления необходимых методов, реализация контейнерных классов требует шаблонизации объектов.
Шаблонные классы или шаблоны классов используются, когда необходимо создать класс, зависящий от дополнительных внешних параметров, которые могут быть другими классами или типами данных. Например, если необходимо создать класс списка, то есть потребность в избежании переписывания реализации списка для всех возможных типов элементов. Хотелось бы, написав один класс с параметром, получить сразу несколько конкретных классов списка (списки символов, целых чисел, вещественных, пользовательских типов и т. д.). В C++ контейнеры, вместе с итераторами и некоторыми алгоритмами, входят в стандартную библиотеку шаблонов (STL) именно по этой причине.
Контейнеры подразделяются на два основных типа: последовательные и ассоциативные. Для нахождения элемента в последовательных контейнерах (list, vector, array, stack, queue), необходимо последовательно просмотреть весь контейнер, в то время как в ассоциативных (map, set, multiset) достаточно обратиться по ассоциированному с значением ключу.
- Программа должна быть разработана на языке C++ стандарта C++17 с использованием компилятора gcc
- Код программы должен находиться в папке src
- При написании кода необходимо придерживаться Google Style
- Обязательно использовать итераторы
- Классы обязательно должны быть шаблонными
- Классы должны быть реализованы внутри пространства имен
s21 - Подготовить полное покрытие unit-тестами методов контейнерных классов c помощью библиотеки GTest
- Запрещено копирование реализации стандартной библиотеки шаблонов (STL)
- Необходимо соблюсти логику работы стандартной библиотеки шаблонов (STL) (в части проверок, работы с памятью и поведения в нештатных ситуациях)
Необходимо реализовать классы библиотеки s21_containers.h (спецификации указаны в соответствующих разделах материалов, см. пункт "Основные контейнеры").
Список классов: list (список), map (словарь), queue (очередь), set (множество), stack (стек), vector (вектор).
- Оформить решение в виде заголовочного файла
s21_containers.h, который включает в себя другие заголовочные файлы с реализациями необходимых контейнеров (s21_list.h,s21_map.hи т.д.) - Предусмотреть Makefile для тестов написанной библиотеки (с целями clean, test)
- За основу стоит рассматривать классическую реализацию контейнеров, но конечный выбор реализаций остается свободным. За исключением списка - его необходимо реализовывать через структуру списка, а не через массив.
Подсказка: Вы можете выделять в базовые классы одинаковую реализацию методов контейнеров. Например, для очереди и стека или для списка и вектора. В качестве одного из возможных примеров иерархического построения в материалах представлена UML-диаграмма библиотеки STL. Однако ваша реализация не обязана быть строго привязана к этой UML-диаграмме.
Необходимо реализовать функции библиотеки s21_containersplus.h (спецификации указаны в соответствующих разделах материалов, см. пункт "Дополнительные контейнеры").
Список классов, которые нужно реализовать дополнительно: array (массив), multiset (мультимножество).
- Оформить решение в виде заголовочного файла
s21_containersplus.h, который включает в себя другие заголовочные файлы с реализациями необходимых контейнеров (s21_array.h,s21_multiset.h) - Предусмотреть Makefile для тестов написанной библиотеки (с целями clean, test)
- За основу стоит рассматривать классическую реализацию контейнеров, но конечный выбор алгоритма остается свободным
Необходимо дополнить классы соответствующими методами, согласно таблице:
| Modifiers | Definition | Containers |
|---|---|---|
iterator insert_many(const_iterator pos, Args&&... args) |
inserts new elements into the container directly before pos |
List, Vector |
void insert_many_back(Args&&... args) |
appends new elements to the end of the container | List, Vector, Queue |
void insert_many_front(Args&&... args) |
appends new elements to the top of the container | List, Stack |
vector<std::pair<iterator,bool>> insert_many(Args&&... args) |
inserts new elements into the container | Map, Set, Multiset |
Обратите внимание, что в качестве аргументов передаются уже созданные элементы соответствующего контейнера, которые необходимо вставить в этот контейнер.
Подсказка 1: обратите внимание, что каждый из этих методов использует конструкцию Args&&... args - Parameter pack. Эта конструкция позволяет передавать переменное число параметров в функцию или метод. То есть при вызове метода, определенного как iterator insert_many(const_iterator pos, Args&&... args), можно написать как insert_many(pos, arg1, arg2), так и insert_many(pos, arg1, arg2, arg3).
Подсказка 2: не забудьте протестировать методы для различных случаев, включая краевые.
💡 Нажми тут, чтобы поделиться с нами обратной связью на этот проект. Это анонимно и поможет команде Продукта сделать твоё обучение лучше.