![]() |
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
При выполнении эта программа генерирует следующие результаты.
Исходное содержимое вектора: 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 Рекомендуемые страницы:
Читайте также:
![]() |
Последнее изменение этой страницы: 2016-03-17; Просмотров: 669; Нарушение авторского права страницы