Собственная реализация контейнера односвязный список. По другому линейный однонаправленный список. Был разработан аналог библиотечной реализации <forward_list>
- SingleLinkedList
. Может хранить данные произвольного типа.
- конструктор по умолчанию, который создаёт пустой список;
- метод
GetSize
, который возвращает количество элементов в списке; - метод
IsEmpty
, который возвращаетtrue
, если список пустой, иfalse
в противном случае. - метод
PushFront
, который делает вставки элемента в начало односвязного списка. Предоставляет строгую гарантию безопасности исключений: если в процессе работы метода будет выброшено исключение, состояние списка остается таким же, как до вызова метода. - Метод
Clear
очищает список и не выбрасывает исключений
Для поддержки перебора элементов контейнера SingleLinkedList были разработаны:
- Шаблонный класс
BasicIterator
, на основе которого объявлены константный и неконстантный итераторы списка - Константные и неконстантные версии методов
begin
иend
, которые возвращают итераторы на первый элемент контейнера и позицию, следующую за последним элементом. - Методы
cbegin
иcend
позволяют удобно получать константные итераторы
Кроме того, был реализованы следующий функционал:
- Операции сравнения
==
,!=
,<
,>
,<=
,>=
; - Конструирование односвязного списка на основе
initializer_list
. - Конструктор копирования и операция присваивания
- Метод
PopFront
. Удаляет первый элемента непустого списка за время O(1). Не выбрасывает исключений. - Метод
InsertAfter
. За время O(1) вставляет в список новое значение следом за элементом, на который ссылается переданный вInsertAfter
итератор. Метод обеспечивает строгую гарантию безопасности исключений. - Метод
EraseAfter
. За время O(1) удаляет из списка элемент, следующий за элементом, на который ссылается переданный в InsertAfter итератор. Не выбрасывает исключений. - Методы
before_begin
иcbefore_begin
. Возвращают итераторы, ссылающиеся на фиктивную позицию перед первым элементом списка. Такой итератор используется как параметр для методовInsertAfter
иEraseAfter
, когда нужно вставить или удалить элемент в начале списка. Разыменовывать этот итератор нельзя.
Для проекта используется система сборки CMake. Рекомендуется осуществлять сборку проекта в отдельной директории, чтобы не испортить директорию с исходным кодом, так в процессе сборки создаются вспомогательные файлы CMake, промежуточные файлы компиляции. Возможная структура каталога для сборки:
cpp-single-linked-list
├── single-linked-list/ # папка с исходным кодом
│ ├── CMakeLists.txt
│ ├── main.cpp
│ └── single-linked-list.h
└── single-linked-list-build / # папка для сборки
└── # тут будут файлы сборки
Команды для сборки:
cd single-linked-list-build/
cmake ../single-linked-list/ -G "MinGW Makefiles"
cmake --build .
Флаг -G "MinGW Makefiles"
используется под Windows, так как используется генератор "MinGW Makefiles"
Для запуска программы используется следующая команда:
./single-linked-list.exe
- C++17
- GCC (MinGW-w64) 11.2.2
- CMake 3.22.0