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

Однонаправленный с писок - экземпляр контейнерного класса forward_list<>. Данный контейнер введен в стандарте C++ 11. forward_list в отличие от list не поддерживает двунаправленные итераторы (только однонаправленные). Список не допускает произвольного доступа к элементам, поскольку это структура данных последовательного доступа. В нём не определены ни оператор индексирования [ ], ни метод at(). В связи с этим forward_list (как и list) не поддерживает работу с некоторыми алгоритмами. В частности, со списком не может быть реализован алгоритм сортировки, однако список имеет собственные методы сортировки. Каждый элемент списка содержит некоторое значение (информационное поле типа Т) и ссылку (указатель) на последующий элемент списка. Такая организация позволяет вставлять и удалять данные в произвольное место в списке с одной и той же скоростью.

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

Для использования однонаправленного списка необходимо включить заголовочный файл <forward_list>.

#include <forward_list>

В этом файле однонаправленный список определен как шаблонный класс в пространстве имен std.

namespace std {

template <typename T,

typename Allocator= allocator<T> >

class forward_list;

}

Элементы последовательного списка могут иметь любой тип Т. Необязательный второй шаблонный параметр определяет модель памяти. По умолчанию используется модель allocator, предусмотренная стандартной библиотекой C++.

Операции с однонаправленным списком приведены по группам в табл. 26.8 – 26.14.

Таблица 26.8