Списки (list)

Список не надає довільного доступу до своїх елементів, зате вставка і видалення виконуються за постійний час. Клас list реалізований в STL у вигляді двохзв’язного списку, кожен вузол якого містить посилання на подальший і попередній елементи. Тому операції інкремента і декремента для ітераторів списку виконуються за постійний час, а пересування на n вузлів вимагає часу, пропорційного n. Після виконання операцій вставки та видалення значення всіх ітераторів і посилань залишаються дійсними. Список підтримує конструктори, операцію привласнення, функцію копіювання, операції порівняння та ітератори, аналогічні векторам і чергам.

Доступ до елементів списків обмежується наступними методами:

reference front();

const_reference front() const;

reference back();

const_reference back() const;

Для занесення в початок і кінець списку визначені методи, аналогічні відповідним методам черги:

void push_front(const Т& value);

void pop_front();

void push_back(const T& value);

void pop_back();

Крім того, діє решта всіх методів для зміни об'єктів list, аналогічні векторам і чергам:

iterator insert(iterator position, const Т& value);

void insert(iterator position,size_type n,const T&value);

template <class InputIter>

void insert(iterator position, Inputlter first,

InputIter last);

iterator erase(iterator position);

iterator erase(iterator first , iterator last);

void swap();

void clear();

Для списку не визначена функція capacity, оскільки пам'ять під елементи відводиться в міру необхідності. Можна змінити розмір списку, видаливши або додавши елементи в кінець списку (аналогічно двосторонній черзі):

void resize(size_type sz, Т с = Т());

Окрім перерахованих, для списків визначено декілька специфічних методів. Зчеплення списків (splice) призначене для переміщення елементів з одного списку в іншій без перерозподілу пам'яті, тільки за рахунок зміни вказівок:

void splice(iterator position, list<T>& x):

void splice(iterator position, list<T>& x, iterator i );

void splice(iterator position, list<T>& x,

iterator first , iterator last);

Обидва списки повинні містити елементи одного типу. Перша форма функції вставляє в список перед елементом, позиція якого вказана першим параметром, всі елементи списку, вказаного другим параметром, наприклад:

list <int> L1, L2;

...

// Формування списків

L1.splice(L1.begin() + 4, L2);

Другий список залишається порожнім. Не можна вставити список в самого себе. Друга форма функції переносить елемент, позицію якого визначає третій параметр, із списку х в список, який викликає функцію. Допускається переносити елемент в межах одного списку. Третя форма функції аналогічним чином переносить із списку в список декілька елементів. Їх діапазон задається третім і четвертим параметрами функції. Якщо для одного і того ж списку перший параметр знаходиться в діапазоні між третім і четвертим, результат не визначений. Приклад:

#include <iostream>

#include <list>

using namespace std;