Исходное содержимое вектора:
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