При выполнении эта программа генерирует следующие результаты.

Исходное содержимое вектора:

A B C D E F G H I J

Содержимое вектора v после вставки:

A B C D E - S T L -- это cилa! - F G H I J

Как видите, содержимое вектора v2 вставлено в середину вектора v.

По мере дальнейшего изучения возможностей, предоставляемых STL, вы узнаете, что итераторы являются связующими средствами, которые делают библиотеку единым целым. Они позволяют работать с двумя (и больше) объектами STL одновременно, но особенно полезны при использовании алгоритмов, описанных ниже в этой главе.

Списки

Список — это контейнер с двунаправленным последовательным доступом к его элементам.

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

Шаблонная спецификация класса list выглядит следующим образом.

template < class Т, class Allocator = allocator< T> > class list

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

explicit list(const Allocator & а = Allocator() );

explicit list(size_type num, const T & val = T(), const Allocator & a = Allocator());

list(const list< T, Allocator> & ob);

template < class InIter> list(InIter start, InIter end, const Allocator & a = Allocator());

Конструктор, представленный в первой форме, создает пустой список. Вторая форма предназначена для создания списка, который содержит num элементов со значением val. Третья создает список, который содержит те же элементы, что и объект ob. Четвертая создает список, который содержит элементы в диапазоне, заданном параметрами start и end.

Для класса list определены следующие операторы сравнения:

==, <, < =, ! =, > и > =

Функции-члены, определенные в классе list, перечислены в табл. 21.3. В конец списка, как и в конец вектора, элементы можно помещать с помощью функции push_back(), но с помощью функции push_front() можно помещать элементы в начало списка. Элемент можно также вставить и в середину списка, для этого используется функция insert(). Один список можно поместить в другой, используя функцию splice(). А с помощью функции merge() два списка можно объединить и упорядочить результат.

Чтобы достичь максимальной гибкости и переносимости для любого объекта, который подлежит хранению в списке, следует определить конструктор по умолчанию и оператор " < " (и желательно другие операторы сравнения). Более точные требования к объекту (как к потенциальному элементу списка) необходимо согласовывать в соответствии с документацией на используемый вами компилятор.

Рассмотрим простой пример списка.

// Базовые операции, определенные для списка.

#include < iostream>

#include < list>

using namespace std;

Int main()

{

　 list< char> lst; // создание пустого списка

　 int i;

　 for(i=0; i< 10; i++) lst.push_back('A'+i);

　 cout < < " Размер = " < < lst.size() < < endl;

　 cout < < " Содержимое: ";

　 list< char>:: iterator p = lst.begin();

　 while(p! = lst.end()) {

　　 cout < < *p;

　　 p++;

　 }

　 return 0;

}

Результаты выполнения этой программы таковы:

Размер = 10

Содержимое: ABCDEFGHIJ

При выполнении эта программа создает список символов. Сначала создается пустой объект списка. Затем в него помещается десять букв (от А до J). Заполнение списка реализуется путем использования функции push_back(), которая помещает каждое новое значение в конец существующего списка. После этого отображается размер списка и его содержимое. Содержимое списка выводится на экран в результате выполнения следующего кода.

list< char>:: iterator р = lst.begin();

while(p! = lst.end()) {

　 cout < < *p;

　 p++;

}

Здесь итератор p инициализируется таким образом, чтобы он указывал на начало списка. При выполнении очередного прохода цикла итератор р инкрементируется, чтобы указывать на следующий элемент списка. Этот цикл завершается, когда итератор р указывает на конец списка. Применение подобных циклов — обычная практика при использовании библиотеки STL. Например, аналогичный цикл мы применили для отображения содержимого вектора в предыдущем разделе.

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

/* Элементы можно помещать в список как с начала, так и с конца.

#include < iostream>

#include < list>

using namespace std;

Int main()

{

　 list< char> lst;

　 list< char> revlst;

　 int i;

　 for(i=0; i< 10; i++ ) lst.push_back('A'+i);

　 cout < < " Размер списка lst = " < < lst.size() < < endl;

　 cout < < " Исходное содержимое списка: ";

　 list< char>:: iterator p;

　 /* Удаляем элементы из списка lst и помещаем их в список revlst в обратном порядке. */

　 while(! lst.empty()) {

　　 р = lst.begin();

　　 cout < < *р;

　　 revlst.push_front(*р);

　　 lst.pop_front();

　 }

　 cout < < endl < < endl;

　 cout < < " Размер списка revlst = ";

　 cout < < revlst.size() < < endl;

　 cout < < " Реверсированное содержимое списка: ";

　 p = revlst.begin();

　 while(p! = revlst.end()) {

　　 cout < < *p;

　　 p++;

　 }

　 return 0;

}

Эта программа генерирует такие результаты.

Размер списка lst = 10

Исходное содержимое списка: ABCDEFGHIJ

Размер списка revlst = 10

Реверсированное содержимое списка: JIHGFEDCBA

В этой программе список реверсируется путем удаления элементов с начала списка lst и занесения их в начало списка revlst.

Сортировка списка

Список можно отсортировать с помощью функции-члена sort(). При выполнении следующей программы создается список случайно выбранных целых чисел, который затем упорядочивается по возрастанию.

// Сортировка списка.

#include < iostream>

#include < list>

#include < cstdlib>

using namespace std;

Int main()

{

　 list< int> lst;

　 int i;

　 // Создание списка случайно выбранных целых чисел.

　 for(i=0; i< 10; i++ )lst.push_back(rand() );

　 cout < < " Исходное содержимое списка: ";

　 list< int>:: iterator p = lst.begin();

　 while(p! = lst.end()) {

　　 cout < < *p < < " ";

　　 p++;

　 }

　 cout < < endl < < endl;

　 // Сортировка списка.

　 lst.sort();

　 cout < < " Отсортированное содержимое списка: ";

　 p = lst.begin();

　 while(p! = lst.end()) {

　　 cout < < *p < < " ";

　　 p++;

　 }

　 return 0;

}

Вот как может выглядеть один из возможных вариантов выполнения этой программы.

Исходное содержимое списка:

41 18467 6334 26500 19169 15724 11478 29358 26962 24464

Отсортированное содержимое списка:

41 6334 11478 15724 18467 19169 24464 26500 26962 29358

Объединение одного списка с другим

Один упорядоченный список можно объединить с другим. В результате мы получим упорядоченный список, который включает содержимое двух исходных списков. Новый список остается в вызывающем списке, а второй список становится пустым. В следующем примере выполняется слияние двух списков. Первый список содержит буквы ACEGI, а второй— буквы BDFHJ. Эти списки затем объединяются, в результате чего образуется упорядоченная последовательность букв ABCDEFGHIJ.

// Слияние двух списков.

#include < iostream>

#include < list>

using namespace std;

Int main()

{

　 list< char> lst1, lst2;

　 int i;

　 for(i=0; i< 10; i+=2) lst1.push_back('A'+i);

　 for(i=1; i< 11; i+=2) lst2.push_back('A'+i);

　 cout < < " Содержимое списка lst1: ";

　 list< char>:: iterator p = lst1.begin();

　 while(p! = lst1.end()) {

　　 cout < < *p;

　　 p++;

　 }

　 cout < < endl < < endl;

　 cout < < " Содержимое списка lst2: ";

　 р = lst2.begin();

　 while(p! = lst2.end()) {

　　 cout < < *p;

　　 p++;

　 }

　 cout < < endl < < endl;

　 // Теперь сливаем эти два списка.

　 lst1.merge(lst2);

　 if(lst2.empty())

　　 cout < < " Список lst2 теперь пуст.";

　 cout < < " Содержимое списка lst1 после объединения: ";

　 р = lst1.begin();

　 while(p! = lst1.end()) {

　　 cout < < *p;

　　 p++;

　 }

　 return 0;

}

Результаты выполнения этой программы таковы.

Содержимое списка lst1: ACEGI

Содержимое списка lst2: BDFHJ

Список lst2 теперь пуст.

Содержимое списка lst1 после объединения:

ABCDEFGHIJ

Хранение в списке объектов класса

Рассмотрим пример, в котором список используется для хранения объектов типа myclass. Обратите внимание на то, что для объектов типа myclass перегружены операторы " < " , " > " , "! =" и " ==" . (Для некоторых компиляторов может оказаться излишним определение всех этих операторов или же придется добавить некоторые другие.) В библиотеке STL эти функции используются для определения упорядочения и равенства объектов в контейнере. Несмотря на то что список не является упорядоченным контейнером, необходимо иметь средство сравнения элементов, которое применяется при их поиске, сортировке или объединении.

// Хранение в списке объектов класса.

#include < iostream>

#include < list>

#include < cstring>

using namespace std;

class myclass {

　　 int a, b;

　　 int sum;

　 public:

　　 myclass() { a = b = 0; }

　　 myclass(int i, int j) {

　　　 a = i;

　　　 b = j;

　　　 sum = a + b;

　　 }

　　 int getsum() { return sum; }

　　 friend bool operator< (const myclass & o1, const myclass & o2);

　　 friend bool operator> (const myclass & o1, const myclass & o2);

　　 friend bool operator==(const myclass & o1, const myclass & o2);

　　 friend bool operator! =(const myclass & o1, const myclass & o2);

};

bool operator< (const myclass & o1, const myclass & o2)

{

　 return o1.sum < o2.sum;

}

bool operator> (const myclass & o1, const myclass & o2)

{

　 return o1.sum > o2.sum;

}

bool operator==(const myclass & o1, const myclass & o2)

{

　 return o1.sum == o2.sum;

}

bool operator! =(const myclass & o1, const myclass & o2)

{

　 return o1.sum! = o2.sum;

}

Int main()

{

　 int i;

　 // Создание первого списка.

　 list< myclass> lst1;

　 for(i=0; i < 10; i++) lst1.push_back(myclass(i, i));

　 cout < < " Первый список: ";

　 list< myclass>:: iterator p = lst1.begin();

　　 while(p! = lst1.end()) {

　　 cout < < p-> getsum() < < " ";

　　 p++;

　 }

　 cout < < endl;

　 // Создание второго списка.

　 list< myclass> lst2;

　 for(i=0; i< 10; i++) lst2.push_back(myclass(i*2, i*3));

　 cout < < " Второй список: ";

　 p = lst2.begin();

　 while(p! = lst2.end()) {

　　 cout < < p-> getsum() < < " ";

　　 p++;

　 }

　 cout < < endl;

　 // Теперь объединяем списки lst1 и lst2.

　　 lst1.merge(lst2);

　 // Отображаем объединенный список.

　 cout < < " Объединенный список: ";

　 р = lst1.begin();

　 while(p! = lst1.end()) {

　　 cout < < p-> getsum() < < " ";

　　 p++;

　 }

　 return 0;

}

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

Первый список: 0 2 4 6 8 10 12 14 16 18

Второй список: 0 5 10 15 20 25 30 35 40 45

⇐ Предыдущая 59 60 61 62 636465 66 67 68 Следующая ⇒