Контейнер последовательностей list

Контейнерный класс list реализуется как двусвязный список, что позволяет ему поддерживать двунаправленные итераторы для прохождения контейнера как в прямом, так и в обратном направлениях. Для контейнера list может быть использован любой алгоритм, использующий однонаправленные и двунаправленные итераторы. Контейнер последовательностей list эффективно реализует операции вставки и удаления в любое место контейнера.

Шаблон класса list предоставляет еще восемь функций-членов: splice, push_front, pop_front, remove, unique, merge, reverse и sort. Многие функции класса vector поддерживаются также и в классе list. Для работы с объектом (его компонентами) необходимо включать заголовочный файл <list>.

#include <iostream>

using std::cout;

using std::endl;

#include <list>

template<class T>

void PrintList(const std::list<T> &lst);

main()

{ std::list<int> ls,ll;

std::list<int>::iterator itr;

int ms[]={2,5,3};

int mm[]={2,15,23,1};

ls.push_back(2);

ls.push_front(5);

ls.push_front(7);

ls.push_back(9);

PrintList(ls);

ll.insert(ll.begin(),ms,ms+sizeof(ms)/sizeof(int));// добавление

PrintList(ll);

ll.push_front(6);

ls.splice(ls.end(),ll);

PrintList(ls);

PrintList(ll);

ls.sort(); // сортировка ls

PrintList(ls);

ll.insert(ll.begin(),mm,mm+sizeof(mm)/sizeof(int));

PrintList(ll);

ll.sort(); // сортировка ll

ls.merge(ll); // перенос элементов ll в ls

PrintList(ls);

ls.pop_front(); // удаление первого элемента списка

ls.pop_back(); // удаление последнего элемента списка

ls.reverse(); // реверсивный переворот списка ls

PrintList(ls);

ls.unique(); // удаление из списка ls одинаковых эл-тов

PrintList(ls);

ls.swap(ll); // обмен содержимым списков ls и ll

PrintList(ls);

PrintList(ll);

ls.push_front(2);

ls.assign(ll.begin(),ll.end());// замена ls содержимым ll

PrintList(ls);

PrintList(ll);

ls.remove(2); // удаление из ls всех 2

PrintList(ls);

itr=ls.begin();

itr++;

ls.erase(itr,ls.end());// удаление из ls элементов с itr до ls.end

PrintList(ls);

return 0;

}

template<class T>

void PrintList(const std::list<T> &lst)

{ std::list<T>::const_iterator pt;

if (lst.empty())

{ cout << endl << "List is empty." << endl;

return;

}

cout<<" LIST размер = "<<lst.size()<<" содержимое = ";

for(pt=lst.begin();pt!=lst.end();pt++)

cout<<*pt<<' ';

cout<<endl;

}

Результат работы программы:

LIST размер = 4 содержимое = 7 5 2 9

LIST размер = 3 содержимое = 2 5 3

LIST размер = 8 содержимое = 7 5 2 9 6 2 5 3

List is empty.

LIST размер = 8 содержимое = 2 2 3 5 5 6 7 9

LIST размер = 4 содержимое = 2 15 23 1

LIST размер = 12 содержимое = 1 2 2 2 3 5 5 6 7 9 15 23

LIST размер = 10 содержимое = 15 9 7 6 5 5 3 2 2 2

LIST размер = 7 содержимое = 15 9 7 6 5 3 2

List is empty.

LIST размер = 7 содержимое = 15 9 7 6 5 3 2

LIST размер = 6 содержимое = 15 9 7 6 5 3

LIST размер = 1 содержимое = 15

Рассмотрим некоторые конструкции, использованные в программе.

Используя функцию push_back (общую для всех контейнеров последовательностей) вставки чисел в конец ls и push_front (определенную для классов list и deque) добавления значений в начало ls, создаем последовательность целых чисел. В инструкции

ll.insert(ll.begin(),ms,ms+sizeof(ms)/sizeof(int));

используется функция insert класса list, вставляющая в начало последовательности ll элементы массива ms.

Далее в строке

ls.splice(ls.end(),ll);

используется компонента-функция splice класса list, выполняющая удаление элементов списка ll с одновременным переносом их в список ls до позиции итератора ls.end() – первый аргумент функции. В классе list имеются две другие версии этой функции:

void splice(iterator it, list& x, iterator first);

void splice(iterator it, list& x, iterator first, iterator last);

Функция с тремя аргументами позволяет удалить один элемент из контейнера, определенного в качестве второго элемента, начиная с позиции, определенной третьим аргументом. В функции с четырьмя элементами последние два параметра определяют диапазон удаляемых из контейнера (второй параметр) значений. Как и первая функция, два других удаляемых значения помещают в позицию, отмеченную итератором (первый аргумент).

Выполнение инструкции

ls.sort();

вызывает функцию sort() класса list, производящую упорядочивание элементов list по возрастанию.

После сортировки списков ls и ll выполняется функция

ls.merge(ll);

удаляющая все объекты контейнера ll и вставки их в отсортированном виде в контейнер ls (оба списка должны быть отсортированы в одном порядке).

Далее следуют функции pop_front – удаления элемента из начала последовательности и доступная во всех контейнерах последовательности функция pop_back – удаление из конца последовательности.

В строке

ls.unique();

используется функция класса list, выполняющая удаление элементов-дубликатов. При этом список должен быть отсортирован.

Использование далее функции

ls.swap(ll);

доступной во всех контейнерах, приводит к обмену содержимым контейнеров ls и ll.

В строке программы

ls.assign(ll.begin(),ll.end());

использована функция для замены содержимого объекта ls содержимым объекта ll в диапазоне, определяемом двумя аргументами итераторами.

Строка

ls.remove(2);

содержит вызов функции remove, удаляющей из ls все копии значения 2.