Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология
Образование Политология Производство Психология Стандартизация Технологии 


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




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

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





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


Читайте также:

  1. A. Притяжения и отталкивания, силы отталкивания больше на малых расстояниях, чем силы притяжения. Б. Притяжения и отталкивания, силы отталкивания меньше на малых расстояниях, чем силы притяжения.
  2. Adjective and adverb. Имя прилагательное и наречие. Степени сравнения.
  3. B. 1. В США говорят по-английски. 2. Эта сумка сделана из кожи. 3. Окно разбито. 4. Владимир был построен в 10 веке. 5. Масло и сыр делают из молока. 6.Этот дом был построен моим дедом.
  4. D. Правоспособность иностранцев. - Ограничения в отношении землевладения. - Двоякий смысл своего и чужого в немецкой терминологии. - Приобретение прав гражданства русскими подданными в Финляндии
  5. D. ПРЕИМУЩЕСТВА ПРИСОЕДИНЕНИЯ К ГААГСКОМУ СОГЛАШЕНИЮ
  6. F70.99 Умственная отсталость легкой степени без указаний на нарушение поведения, обусловленная неуточненными причинами
  7. F71.98 Умственная отсталость умеренная без указаний на нарушение поведения, обусловленная другими уточненными причинами
  8. I Использование заемных средств в работе предприятия
  9. I ЭТАП (1-3 ст.) ОВОДНЕНИЕ ИКРИНКИ И ПОЯВЛЕНИЕ БЛАСТОДИСКА
  10. I этап. Теория рыночных структур (1880-1910 гг.)
  11. I. Методические принципы физического воспитания (сознательность, активность, наглядность, доступность, систематичность)
  12. I. О НОВОПРИБЫВШИХ ГРАЖДАНАХ.


Последнее изменение этой страницы: 2016-03-17; Просмотров: 236; Нарушение авторского права страницы


lektsia.com 2007 - 2018 год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! (0.026 с.) Главная | Обратная связь