C++ Программирование в среде С++ Builder 5

         

Списки


Списки — двусвязные линейные структуры данных, т. е. каждый элемент имеет два указателя для ссылки на два других элемента. Списки занимают ровно столько памяти, сколько необходимо для хранения наличных элементов. Вставка и удаление из списка очень эффективны. Слабым местом списка является доступ к элементам. Прямой доступ, как в векторах, невозможен. Для поиска нужного элемента приходится двигаться по списку, начиная с самого начала.

Создание списков

Существуют различные способы конструирования списков.

#include <list>

list<int>ilist;

list<double>dlist(20, 1.0);

list<MyType>mtlist(10) ;

Эти объявления имеют тот же смысл, что и соответствующие объявления для векторов. Так же как и вектор, список можно конструировать, инициализировав содержимым другого контейнера:

int iarr[5] = {1, 2, 3, 4, 5};

list<int> linti(iarr, iarr + 5);

В списке можно хранить любой тип данных, при условии, что он поддерживает те функции-элементы (конструкторы и проч.), о которых говорилось выше при обсуждении векторов.

Действия над списками



Поскольку список занимает ровно столько памяти, сколько необходимо, для него не имеет смысла понятие вместимости. Поэтому у списков нет функций capacity () и reserve (). Невозможно и обращение к элементам по индексу.

В остальном над списками можно производить все те операции, что описывались в предыдущем параграфе о векторах. Но следует упомянуть о некоторых дополнительных возможностях списков.

Помимо известных вам уже методов push back() и pop back (), имеются функции push_front () и pop_front () для добавления или удаления элемента в начале списка.

Функция remove () удаляет из списка все элементы с указанным значением.

Функция unique () удаляет все повторяющиеся элементы (стоящие;

подряд, поэтому функцию имеет смысл применять только на сортированных списках), оставляя только первое вхождение элемента с данным значением.

Функция reverse () обращает порядок элементов в списке.

Функция sort () (без аргумента) производит сортировку списка в соответствии с операцией “меньше”, т. е. в восходящем порядке. Можно задать в качестве аргумента функциональный объект, реализующий отношение, в соответствии с которым нужно сортировать список:


#intlude <functional> linti.sort(greater_equal<int>());



Функция sort() сохраняет относительный порядок следования повторяющихся элементов. Такого рода сортировку называют стабильной.

Функция merge () выполняет слияние сортированного списка с другим сортированным списком. Элементы второго списка удаляются. Как и в случае sort (), можно задать второй аргумент — функциональный объект, определяющий отношение сортировки.



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

Функция splice () является специальным вариантом вставки. Она удаляет вставляемый элемент или элементы списка, из которого производится вставка.

Описанные функции частично иллюстрирует следующая программа.

#include <iostream>

#include <list>

#pragma hdrstop

#include <condefs.h>

using namespace std;

//

// Операция передачи списка в поток.

//

template<class T>

ostream &operator“(ostream &os, const list<T> &c)

{

cout << "{ ";

copy (c. begin (), c.end(),

ostream_iterator<T> (os, " "));

os << "} Size: " “ c.size();

return os;

}

int main() {

int iarrl[5] = {5, 7, 3, 1, 9};

list<int> lintl(iarr1, iarr1 + 5);

cout<< "Initial list : "<< linti << endl;

linti.sort (); // Сортировка.

cout << "After sort : "<< lint1 << end1;

int iarr2[6] = {6, 2, 4, 8, 2, 6};

list<int> lint2(iarr2, iarr2 + 6);

cout << "Second list : " << lint2 << end1;

lint2.sort () ;

lint2.unique(); // Удаление повторов.

cout<< "Sorted unique: " << lint2 “ endl;

linti.merge(lint2); // Слияние.

cout <<"After merge : " << lint1 “ end1;

linti.reverse (); // Обращение порядка.

cout << "After reverse: "<< lint1 << end1;

return 0;

}

Программа выводит:

Initial list : {57319} Size: 5

After sort : {13579} Size: 5

Second list : {624826} Size: 6

Sorted unique:(2468) Size: 4

After merge :{123456789} Size:9

After reverse:{987654321}Size:9


Содержание раздела