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

; ++ iElement)

0. 
   cout « *iElement « endl;
   

0. 
   }
   

0. 
   int main ()
   

0. 
   {
   

0. 
   vector vecNames;
   

0. 
   vecNames.push_back ("John Doe");
   

0. 
   vecNames.push_back ("Jack Nicholson");
   

0. 
   vecNames.push_back ("Sean Penn");
   

0. 
   vecNames.push_back ("Anna Hoover");
   

21

0. 
   // вставка дубликатов в вектор
   

0. 
   vecNames.push_back ("Jack Nicholson");
   

24

0. 
   cout « "The initial contents of the vector are:" « endl;
   

0. 
   DisplayContents(vecNames);
   

27

0. 
   cout « "The sorted vector contains names in the order:" « endl;
   

0. 
   sort (vecNames.begin (), vecNames.end ());
   

0. 
   DisplayContents(vecNames);
   

31


32 cout « "Searching for V'John Doe\" using 'binary_search':"

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

537

1. 
   endl;
   

0. 
   bool bElementFound = binary_search (vecNames.begin (), vecNames.end (),
   

   34:		"John Doe");
   35:	if (bElementFound)
   36:
   37:	cout «	"Result: \"John Doe\" was found in the vector!"
   	«	endl;

1. 
   else
   

0. 
   cout « "Element not found " « endl;
   

0. 
   

0. 
   // Удаление смежныхдубликатов
   

0. 
   auto iNewEnd = unique (vecNames.begin (), vecNames.end ());
   

0. 
   vecNames.erase (iNewEnd, vecNames.end ());
   

44:


45: cout « "The contents of the vector after using 'unique':"

1. 
   endl;
   

0. 
   DisplayContents(vecNames);
   

0. 
   

0. 
   return 0;
   

0. 
   }
   

Результат


The initial contents of the vector are:


John Doe


Jack Nicholson


Sean Penn


Anna Hoover


Jack Nicholson


The sorted vector contains names in the order:


Anna Hoover


Jack Nicholson


Jack Nicholson


John Doe


Sean Penn


Searching for "John Doe" using 'binary_search':


Result: "John Doe" was found in the vector!


The contents of the vector after using 'unique':


Anna Hoover


Jack Nicholson


John Doe


Sean Penn


Анализ

Приведенный выше код сначала сортирует вектор vecN am es (строка 29), а затем (стро­

ка 33) использует алгоритм b i n a r y _ s e a r c h () для поиска в нем элемента Jo h n Doe.

Точно так же в строке 42 используется алгоритм s t d : :u n iq u e ( ) для удаления смеж ­ ных дубликатов. Обратите внимание, что функция u n iq u e (), как и rem o v e (), не из­ меняет размер контейнера. Это приводит к сдвигу значений, но не сокращению общего количества элементов. Чтобы избавиться от нежелательных или неизвестных значений

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

в конце контейнера, после вызова функции u n iq u e () всегда следует вызвать функцию v e c t o r :: e r a s e (), используя итератор, возвращенный функцией u n iq u e (), как показано в строках 42 и 43.

ВНИМАНИЕ!
ПРИМЕЧАНИЕ
Такие алгоритмы, как binary_search (), эффективны только в отсортирован­ ных контейнерах. При использовании этого алгоритма с неотсортированным вектором могут возникнуть нежелательные последствия.
Функция stable_sort () используется точно так же, как функция sort О , которая была представлена ранее. Функция stable_sort () обеспечивает от­ носительный порядок отсортированных элементов. Поддержка относительного порядка обходится потерей производительности, что следует учитывать, особен­ но если порядок смежных элементов не является необходимым.

Разделение диапазона

Функция s t d : : p a r t i t i o n () позволяет разделить исходный диапазон на два раздела:

тот, который удовлетворяет унарному предикату, и другой, который не удовлетворяет:

bool IsEven (const int& nNumber)		// унарный предикат
{	((nNumber % 2) == 0);
return
}
partition	(veclntegers.begin(),	veclntegers.end(), IsEven);
Однако функция s t d : : p a r t i t i o n		() не гарантирует относительный порядок эле­

ментов в пределах каждого раздела. Когда это важно, следует использовать функцию s t d : : s t a b l e _ p a r t i t i o n ():

stable_partition (veclntegers.begin() , veclntegers.end(), IsEven); В листинге 23.11 показано применение этих алгоритмов.


ЛИСТИНГ 23.11. Использование алгоритмов partition () и stablejpartition ()

для разделения диапазона целых чисел на четные и нечетные значения______________________

0. 
   #include
   

0. 
   #include
   

0. 
   #include
   

0. 
   using namespace std;
   

0. 
   

0. 
   bool IsEven (const int& nNumber)
   

6 : {

0. 
   return ((nNumber % 2) == 0);
   

8 : }
9:

0. 
   template
   

0. 
   void DisplayContents(const T& Input)
   

12: {

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

		Использование алгоритмов STL	539
14:	;	iElement != In p u t .c en d () / / c e n d ( ) : C++11
15:	;	++ iElement)

0. 
   cout « *iElement « '
   

0. 
   

18:	cout	«	"| Number	of	elem ents:		"	«	I n p u t . s i z e () « endl;
19:	}
20:	i n t main	()
2 1 :	{
22:	v e c to r v e c ln te g e r s ;
23:
24:	f o r	( in t	nNum = 0;	nNum < 10;			++	nNum)
25:	v ec ln te g ers .p u sh _ b ac k				(nNum);
26:
27:	cout	«	"The i n i t i a l		c o n te n ts :		"	«	endl;

0. 
   D is p la y C o n te n ts (v e c ln te g e rs );
   

0. 
   

30:	v e c to r		vecCopy	(v e c ln te g e rs );
31:
32:	cout «	"The	e f f e c t	of u sin g	p a r t i t i o n ( ):" « endl;
33:	p a r t i t i o n (v e c ln te g e rs . b e g in				(), v e c ln te g e r s . e n d (), IsEven);

0. 
   D is p la y C o n te n ts (v e c ln te g e rs );
   

0. 
   

   36:	cout « "The e f f e c t of u sing s t a b l e _ p a r t i t i o n ( ) :"	« endl;
   37:	s t a b l e _ p a r t i t i o n (vecCopy.begin (),vecCopy.end (),	IsEven);

1. 
   D isplayC ontents(vecC opy);
   

0. 
   

40:	r e tu r n 0;
41:	}

Результат

The	i n i t i a l	contents:
0 1	23456789		I	Number	of	elements:	10
The	e f f e c t	of using	p a r t i t i o n ():
0 8	26453719		I	Number	of	elements:	10
The	e f f e c t	of using	s t a b le _ p a r titi o n ():
0 2	46813579		|	Number	of	elements:	10

Анализ

Код делит диапазон целых чисел, содержащийся в векторе v e c l n t e g e r s , на четные и нечетные значения. Сначала разделение осущ ествляется с использованием функции s t d : : p a r t i t i o n (), как показано в строке 33, а затем с использованием функции s t a -

b l e _ p a r t i t i o n () в строке 37. Для сравнения пример диапазона v e c l n t e g e r s копиру­

ется в вектор vecC opy, первый разделяется с использованием функции p a r t i t i o n (),

а последний — с использованием s t a b l e j p a r t i t i o n (). Различие в результатах исполь­

зования функций s t a b l e j p a r t i t i o n () и p a r t i t i o n () вполне очевидно в выводе. А л­

горитм s t a b l e j p a r t i t i o n () обеспечивает относительный порядок элементов в каждом

разделе. Обратите внимание, что поддержка этого порядка сказывается на производитель­

ности, которая может быть как незначительной, как в данном случае, так и существенной,

в зависимости от типа содержавшихся в диапазоне объектов.

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