C++ за 21 день седьмое издание

#include

2. 
   #include
   

3. 
   #include
   

4. 
   using namespace std;
   

4:

0. 
   template
   

0. 
   void DisplayContents (const T& Input)
   

0. 
   {
   

0. 
   for(auto iElement = Input.cbegin() // auto, cbegin и cend: C++11
   

0. 
   ; iElement != Input.cend()
   

0. 
   ; ++ iElement )
   

11: cout « *iElement « endl;
1 2 :

0. 
   cout « endl;
   

0. 
   }
   

15:

0. 
   struct Contactltem
   

0. 
   {
   

0. 
   string strContactsName;
   

0. 
   string strPhoneNumber;
   

0. 
   string strDisplayRepresentation;
   

2 1 :

22: // Конструктор и деструктор

436 ЗАНЯТИЕ 18. Классы двухсвязного и односвязного списков библиотеки STL

0. 
   Contactltem (const strings strName, const string & strNumber)
   

0. 
   {
   

0. 
   strContactsName = strName; '
   

0. 
   strPhoneNumber = strNumber;
   

0. 
   strDisplayRepresentation = (strContactsName + ": "\
   

1. 
   strPhoneNumber);
   

0. 
   }
   

29:

0. 
   // используется list::remove() для элемента списка контактов
   

0. 
   bool operator == (const ContactltemS itemToCompare) const
   

0. 
   {
   

0. 
   return (itemToCompare.strContactsName == \
   

this->strContactsName);

0. 
   }
   

0. 
   

0. 
   // используется в list::sort() без параметров
   

0. 
   bool operator < (const Contactltems itemToCompare) const
   

0. 
   {
   

0. 
   return (this->strContactsName < \ itemToCompare.strContactsName);
   

40:


41:


42:


43:


44:


45:


46:

0. 
   };
   

0. 
   

}

0. 
   Используется в DisplayContents через cout operator const char*() const
   

{


return strDisplayRepresentation.c_str();

}

49: bool SortOnPhoneNumber (const ContactltemS iteml,


50: const ContactltemS item2)

0. 
   {
   

0. 
   return (iteml.strPhoneNumber < item2.strPhoneNumber);
   

0. 
   }
   

54:

0. 
   int main ()
   

0. 
   {
   

0. 
   list Contacts;
   

0. 
   Contacts.push_back(Contactltem("Jack Welsch",
   

"[phone]"));

0. 
   Contacts.push_back(Contactltem("Bill Gates",
   

"[phone]"));

0. 
   Contacts.push_back(Contactltem("Angela Merkel", "[phone]"));
   
1. 
   Contacts.push_back(Contactltem("Vladimir Putin",
   

"[phone]"));

0. 
   Contacts.push_back(Contactltem("Manmohan Singh", "[phone]"));
   

0. 
   Contacts.push_back(Contactltem("Barack Obama",
   

"[phone]"));


64:

0. 
   cout « "List in initial order: " « endl;
   

0. 
   DisplayContents(Contacts);
   

Обращение списка и сортировка его элементов

437

57:

0. 
   Contacts.sort ();
   

69: cout « "After sorting in alphabetical order via operator<:"

1. 
   endl;
   

0. 
   DisplayContents(Contacts);
   

0. 
   

"2:Contacts.sort(SortOnPhoneNumber);


"З: cout « "After sorting in order of phone numbers via predicate:"

0. 
   endl;
   

^4: DisplayContents(Contacts);
75 :


76: cout « "After erasing Putin from the list: ";

0. 
   Contacts.remove(Contactltem("Vladimir Putin", ""));
   

0. 
   DisplayContents(Contacts);
   

79:

0. 
   return 0;
   

0. 
   }
   

Результат


List in initial order:


Jack Welsch: [phone]


Bill Gates: [phone]


Angela Merkel: [phone]


Vladimir Putin: [phone]


Manmohan Singh: [phone]


Barack Obama: [phone]


After sorting in alphabetical order via operatorC Angela Merkel: [phone] Barack Obama: [phone] Bill Gates: [phone] Jack Welsch: [phone] Manmohan Singh: [phone] Vladimir Putin: [phone]


After sorting in order of phone numbers via predicate:


Barack Obama: [phone]


Jack Welsch: [phone]


Bill Gates: [phone]


Angela Merkel: [phone]


Vladimir Putin: [phone]


Manmohan Singh: [phone]


After erasing Putin from the list:


Barack Obama: [phone]


Jack Welsch: [phone]


Bill Gates: [phone]


Angela Merkel: [phone]


Manmohan Singh: [phone]

0. 
   ЗАНЯТИЕ 18. Классы двухсвязного иодносвязного списков библиотеки STL
   

Анализ

Сначала сосредоточимся на строках 57-81 функции m a in () . В строке 57 создается экземпляр списка элементов книги адресов типа C o n t a c t lt e m . В строках 58-63 этот спи­ сок заполняется вымышленными номерами телефонов и именами нескольких знаменито­ стей и политических деятелей. В строке 66 осуществляется вывод этого списка на экран. Функция l i s t : : s o r t без предиката используется в строке 68. При отсутствии предиката эта функция сортировки ищет оператор o p e r a t o r < в классе C o n t a c t lt e m , где он и был определен в строках 37 -40 . Оператор C o n t a c t lt e m : : o p e r a t o r < позволяет контейне­ ру l i s t : : s o r t сортировать свои элементы в алфавитном порядке хранимых имен (а не номеров телефонов или произвольно). Чтобы отсортировать тот же список по номерам телефонов, используйте функцию l i s t : : s o r t ( ) , предоставив ей как аргумент бинарный предикат S o rtO n P h o n e N u m b e r () (строка 72). Эта функция, реализованная в строках 49-53, гарантирует, что входные аргументы типа C o n t a c t lt e m сравниваются с другими по номеру телефона, а не по имени. Таким образом, это позволяет функции l i s t :: s o r t () сортировать список знаменитостей на основе их номеров телефонов, как свидетельству­ ет вывод. И наконец, в строке 77 используется метод l i s t : : re m o v e () для удаления контакта из списка. Объект контакта передается как параметр. Метод l i s t : : re m o v e () сравнивает этот объект с другими элементами списка с использованием оператора C o n t a c t lt e m : : o p e r a t o r s реализованного в строках 30-34. Этот оператор возвращает значение t r u e , если имена совпадают, предоставляя методу l i s t : : re m o v e () критерий для принятия решения о соответствии.

Данный пример демонстрирует не только применение шаблона связанного списка би­ блиотеки STL для создания списка объектов любого типа, но и важность операторов, пре­ дикатов.
С++11


Шаблон класса std :: forward_list

0. 
   языке C + + 11 появилась возможность использовать класс s t d : : f o r w a r d _ li s t вме­ сто двухсвязного списка класса s t d : : l i s t . Класс s t d : : f o r w a r d _ l i s t предоставляет односвязный список, допускающий перебор только в одном направлении (рис. 18.2).
   

Данные		Связь со (	Данные	Связь со	^	Данные	Связь со
		следующим		следующим			следующим
	Узел 1		Узел 2		-	Узел N
		РИС. 18.2. Визуальное представление односвязного списка
СОВЕТ		Для использования шаблона класса std: :forw ard _ list необходимо вклю­

чить заголовок :


#include

Обращение списка и сортировка его элементов

439

Класс f o r w a r d _ l i s t используется очень похоже на класс l i s t , но перемещ ение итераторов возможно только в одном направлении. Для вставки элементов есть функция p u s h _ f r o n t (), но нет функции p u s h _ b a c k (). Конечно, вы всегда можете использо­ вать функцию i n s e r t () и ее перегруженные версии для вставки элементов в указанную позицию.

В листинге 18.8 показаны некоторые функции класса f o r w a r d _ l i s t .

0. 
   И СТИ Н Г 1 8 .8 . Простые операции вставки и извлечения из односвязного списка____________
   

1. 
   #include
   

2. 
   #include
   

3. 
   using namespace std;
   

3:

0. 
   template
   

0. 
   void DisplayContents (const T& Input)
   

6 : {

0. 
   for (auto iElement = Input.cbegin() // auto и cbegin: C++11
   

0. 
   ; iElement != Input.cend ()
   

0. 
   ; ++ iElement )
   

10: cout << *iElement « '
1 1 :

0. 
   cout « endl;
   

0. 
   }
   

14:

0. 
   int main()
   

0. 
   {
   

0. 
   forward_list flistlntegers;
   

0. 
   flistIntegers.push_front(0);
   

0. 
   flistlntegers.push_front(2);
   

0. 
   flistlntegers.push_front(2);
   

0. 
   flistlntegers.push_front(4);
   

0. 
   flistlntegers.push_front(3);
   

0. 
   flistlntegers.push_front(1);
   

24:

0. 
   cout « "Contents of forward_list:" « endl;
   

0. 
   DisplayContents(flistlntegers);
   

27:

0. 
   flistlntegers.remove(2);
   

0. 
   flistlntegers.sort() ;
   

0. 
   cout « "Contents after removing 2 and sorting: " « endl;
   

0. 
   DisplayContents(flistlntegers);
   

32:

0. 
   return 0;
   

0. 
   }
   

Результат


Contents of forward_list:


134220


Contents after removing 2 and sorting:


013 4
[40 ЗАНЯТИЕ 18. Классы двухсвязного иодносвязного списков библиотеки STL


Анализ

Как видно из примера, функционально класс f o r w a r d l i s t весьма похож на класс i s t . Поскольку класс fo rw a rd l i s t не поддерживает двунаправленный перебор, вы мо-сете использовать для итератора оператор o p e ra to r+ + , но не оператор o p e r a t o r — . Этот [ример демонстрирует применение функции rem ove (2) для удаления всех элементов со начением 2 (строка 28). Строка 29 демонстрирует функцию s o r t () для сортировки с ис-юльзованием предиката по умолчанию s t d : : le ss< T > .

Преимущество класса f o r w a r d l i s t заключается в том, что это односвязный список,

1. 
   использует меньше памяти, чем класс l i s t (поскольку элемент содержит ссылку толь-
   

0. 
   на следующий элемент, но не на предыдущий).
   

РЕКОМЕНДУЕТСЯ

Используйте класс s t d : : l i s t вместо класса

s t d : :v ec to r, когда необходимо частое уда­ ление и вставка элементов, особенно в середи­ ну, поскольку вектор должен изменять размеры своего внутреннего буфера для обеспечения семантики, как у массива, что вызывает про­ должительные операции копирования, а список только привязывает или отцепляет элементы

Помните, что методы p u sh ^ fro n t О и push_ back {} позволяют вставлять элементы в нача­ ло и в конец списка соответственно

Помните о необходимости реализовать опе­ раторы o p era to r< и o p e r a to r - - в клас­ се, объекты которого будут храниться в таком контейнере STL, как l i s t , чтобы предоставить предикат по умолчанию для сортировки и уда­ ления

Помните, что вы всегда можете определить ко­ личество элементов в списке, используя метод l i s t " : : s iz e (), как и в любом другом контей­ нере библиотеки STL

Помните, что вы можете освободить список, ис­ пользуя метод l i s t :: c le a r (), как и в любом другом контейнере библиотеки STL