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

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

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 Следующая ⇒

Рекомендуемые страницы: