C++ за 21 день седьмое издание

Классы двухсвязного

0. 
   односвязного
   

списков библиотеки STL
Стандартная библиотека шаблонов (STL) предоставляет програм­ мистам двухсвязный список (doubly linked list) в форме шаблона клас­ са s t d : : l i s t . Основное преимущество связанного списка в быстрой зставке и извлечении элементов за постоянное время. Начиная с вер­ сии С++11 вы можете также использовать односвязный список (singly inked list) в форме шаблона класса s t d : : f o r w a r d _ lis t, который мож­ но пройти только в одном направлении.

На сегодняшнем занятии.

■ Как создать экземпляр классов l i s t и f o rw a r d _ lis t .

■ Использование классов списков библиотеки STL, включая вставку и извлечение.

■ Как обратить и отсортировать элементы.

424 ЗАНЯТИЕ 18. Классы двухсвязного иодносвязного списков библиотеки ST.


Характеристики класса std: :lis t


Связанный список (linked list) — это коллекция узлов (node), каждый из которых, кроме

представляющего интерес значения или объекта, содержит также указатель на следующие

узел, т.е. каждый узел связан со следующим и с предыдущим, как показано на рис. 18.1.

Связь с	Данные	Связь со	Связь с	Данные Связь со
предыдущим		следующим	предыдущим	следующим
	Узел N			Узел N + 1

Р И С -18-1. Визуальное представление двухсвязного списка

Реализация класса l i s t библиотеки STL обеспечивает постоянную продолжитель­ ность вставки в начало, в конец и в середину списка.