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

#include

0. 
   #include
   

0. 
   #include
   

0. 
   #include
   

0. 
   using namespace std;
   

0. 
   

0. 
   template ctypename T>
   

0. 
   void DisplayContents(const T& Input)
   

   8 :	{	= Input.cbegin()	//	auto, cbegin: C++11
   9:	for ( auto iElement
   10:	; iElement	!= Input.cend()	//	cend(): C++11

1. 
   ; ++ iElement)
   

0. 
   cout « *iElement « endl;
   

0. 
   }
   

0. 
   int main ()
   

0. 
   {
   

0. 
   list listNames;
   

0. 
   

0. 
   // Вставить примеры значений
   

   19:	listNames.push_back	("John Doe");
   20:	listNames.push_back	("Brad Pitt");
   21:	listNames.push_back	("Jack Nicholson");
   22:	listNames.push_back	("Sean Penn");
   23:	listNames.push_back	("Anna Hoover");
   24:

1. 
   cout « "The sorted contents of the list are: " « endl;
   

0. 
   listNames.sort ();
   

Использование алгоритмов STL

541

0. 
   DisplayContents(listNames);
   

0. 
   

0. 
   cout «
   

"The lowest index where V'Brad Pitt\" can be inserted is: ";

0. 
   auto iMinlnsertPos = lower_bound ( listNames.begin (), listNames.end ()
   

   31:	cout «	, "Brad Pitt" );
   32:		distance (listNames.begin (), iMinlnsertPos) « endl;
   33:

1. 
   cout «
   

"The highest index where V'Brad Pitt\" can be inserted is: ";

0. 
   auto iMaxInsertPos = upper_bound ( listNames.begin (), listNames.end (),
   

   36:	cout «	"Brad Pitt" );
   37:		distance (listNames.begin (), iMaxInsertPos) « endl;
   38:

1. 
   cout « endl;
   

0. 
   

41: cout « "List after inserting Brad Pitt in sorted order: "

1. 
   endl;
   

0. 
   listNames.insert (iMinlnsertPos, "Brad Pitt");
   

0. 
   

0. 
   DisplayContents(listNames);
   

0. 
   return 0;
   

0. 
   }
   

Результат


The sorted contents of the list are:


Anna Hoover


Brad Pitt


Jack Nicholson


John Doe


Sean Penn


The lowest index where "Brad Pitt" can be inserted is: 1


The highest index where "Brad Pitt" can be inserted is: 2


List after inserting Brad Pitt in sorted order:


Anna Hoover


Brad Pitt


Brad Pitt


Jack Nicholson


John Doe


Sean Penn


Анализ

Элемент может быть вставлен в отсортированную коллекцию в двух потенциальных позициях: ближе к началу коллекции (итератор, возвращенной функцией lo w er_ b o u n d ()) и ближе к концу коллекции (итератор, возвращенный функцией u p p e r b o und ()). В слу­ чае листинга 23.12, где в отсортированную коллекцию вставляется строка "B ra d P i t t " , уже существующая в ней (вставлена в строке 20), верхняя и нижняя границы различаются

542 ЗАНЯТИЕ 23. Алгоритмы библиотеки STL

(в противном случае они бы совпадали). Применение этих функций представлено в стро­ ках 30 и 35 соответственно. Как демонстрирует вывод, при использовании для вставки строки в список итератора, возвращенного функцией lower_bound () (строка 42), список сохраняет отсортированное состояние. Таким образом, эти алгоритмы позволяют осуще­ ствить вставку в коллекцию, не нарушая порядок отсортированного содержимого. Итера­ тор, возвращенный функцией upper_bound (), также сработал бы прекрасно.

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

Используйте метод erase () класса контей­ нера после использования алгоритмов re­ move О, remove_if() и unique () для из­ менения размера контейнера

Проверяйте на допустимость итератор, воз­ вращенный функциями find(), findJLf (), search() и searchjnO, прежде чем ис­ пользовать его для сравнения с результатом метода end () контейнера

Предпочитайте использовать функцию sta­ blejpartition{), а не функцию parti­ tion () и функцию stable_sort(), а не функцию sort () только тогда, когда относи­ тельный порядок отсортированных элементов важен, поскольку версии stablej* могут сни­ зить производительность приложения

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

Не забывайте сортировать содержимое кон­ тейнера при помощи метода sort О, прежде чем вызывать метод unique () для удаления повторяющихся смежных значений. Функция sort О гарантирует, что все элементы с со­ впадающими значениями расположатся рядом друг с другом, делая эффективной работу функ­ ции unique {)

Не забывайте, что функцию binaryjsearch () следует вызывать только для отсортированного контейнера

Резюме

На сегодняшнем занятии рассматривался один из самых важных аспектов библиотеки STL: алгоритмы. Вы изучили различные типы алгоритмов, а примеры помогли вам лучше понять применение алгоритмов.

Вопросы и ответы

0. 
   М огу ли я прим енить изм еняю щ ий алгоритм , такой к а к s t d : : tr a n s f o r m (), к ас­
   

социативном у контейнеру, таком у к ак s t d : : s e t ?

Даже если бы это было возможно, то поступать так не нужно. Содержимое ассоциатив­ ного контейнера следует обрабатывать как константное. Дело в том, что ассоциативные контейнеры сортируют свои элементы при вставке, и относительные позиции элемен­ тов играют важную роль в таких функциях, как fin d (), а также в эффективности ра­ боты контейнера. Поэтому изменяющие алгоритмы, такие как s td : : tran sfo rm (), не должны использоваться с наборами библиотеки STL.

Коллоквиум 543

0. 
   Я должен присвоить определенное значение каждому элементу последовательного контейнера. Могу ли я использовать для этого алгоритм s t d : : transform () ?
   

Хотя алгоритм s t d : : tr a n s f o r m () для этого вполне применим, лучш е использовать алгоритм f i l l () или f i l l _ n ( ) .

0. 
   Изменяет ли алгоритм copy_bac]cward() расположение элементов контейнера на обратное?
   

Нет, он этого не делает. Алгоритм co p y b a c k w a rd () библиотеки STL изменяет на обратный порядок элементов при копировании, но не порядок хранимых элементов, т.е. копирование начинается с конца диапазона и продолжается к началу. Чтобы обра­ тить содержимое коллекции, используйте алгоритм s t d : : r e v e r s e ().

0. 
   Могу ли я использовать алгоритм s td :: sort () в списке?
   

Алгоритм s t d : : s o r t () применяется в списке таким же образом, как и в любом дру­

гом последовательном контейнере. Однако у списка есть специальное свойство: суще­ ствующие итераторы остаю тся допустимыми при операциях со списком, а функция s t d : : s o r t () не может этого гарантировать. Поэтому список STL предоставляет соб­ ственный алгоритм s o r t () в форме функции-члена l i s t :: s o r t (), который и следует использовать, поскольку он гарантирует, что итераторы на элементы списка останутся допустимыми, даже если их относительные позиции в списке изменятся.

0. 
   Почему так важно использовать такую функцию, как lower_bound() или upper_ bound(), при вставке в отсортированный диапазон?
   

Эти функции предоставляю т первую и последнюю позиции в отсортированной кол­ лекции соответственно, куда может быть вставлен элемент без нарушения порядка со­ ртировки.

Коллоквиум

0. 
   этом разделе предлагаются вопросы для самоконтроля и закрепления полученных знаний, а также упражнения, которые помогут применить на практике полученные навы­ ки. Попытайтесь самостоятельно ответить на эти вопросы и выполнить задания, а потом сверьте полученные результаты с ответами в приложении Г, “Ответы”. Если остались не­ ясными хотя бы некоторые из предложенных ниже вопросов, не приступайте к изучению материала следующего занятия.