Программирование. Принципы и практика использования C++ Исправленное издание, стр. 427

{

  cout << s;

  while (b!=e) { cout << *b; ++b; }

  cout << '\n';

}

void ff()

{

  int a[] = { 1,1,1,2,2,3,4,4,4,3,3,3,5,5,5,5,1,1,1 };

  vector<int> v(a,a+sizeof(a)/sizeof(int));

  print_digits("all: ",v.begin(), v.end());

  vector<int>::iterator pp = unique(v.begin(),v.end());

  print_digits("head: ",v.begin(),pp);

  print_digits("tail: ",pp,v.end());

  pp=remove(v.begin(),pp,4);

  print_digits("head: ",v.begin(),pp);

  print_digits("tail: ",pp,v.end());

}

Результат приведен ниже.

all: 1112234443335555111

head: 1234351

tail: 443335555111

head: 123351

tail: 1443335555111

Б.5.3. Вспомогательные алгоритмы

С формальной точки зрения вспомогательные алгоритмы также могут модифицировать последовательности, но мы считаем, что лучше их перечислить отдельно, чтобы они не затерялись в длинном списке.

Программирование. Принципы и практика использования C++ Исправленное издание - _400.png

Обратите внимание на то, что неинициализированные последовательности должны использоваться только на самых нижних уровнях программирования, как правило, в реализации контейнеров. Элементы, представляющие собой цели алгоритмов

uninitialized_fill
и
uninitialized_copy
, должны иметь встроенный тип или быть неинициализированными.

Б.5.4. Сортировка и поиск

Сортировка и поиск относятся к категории фундаментальных алгоритмов. В то же время потребности программистов довольно разнообразны. Сравнение по умолчанию выполняется с помощью оператора

<
, а эквивалентность пар значений
a
и
b
определяется условием
!(a<b)&&!(b<a)
, а не оператором
==
.

Программирование. Принципы и практика использования C++ Исправленное издание - _401.png

Рассмотрим следующий пример:

vector<int> v;

list<double> lst;

v.push_back(3); v.push_back(1);

v.push_back(4); v.push_back(2);

lst.push_back(0.5); lst.push_back(1.5);

lst.push_back(2); lst.push_back(2.5); // список lst упорядочен

sort(v.begin(),v.end());              // сортировка вектора v

vector<double> v2;

merge(v.begin(),v.end(),lst.begin(),lst.end(),back_inserter(v2));

for (int i = 0; i<v2.size(); ++i) cout << v2[i] << ", ";

Алгоритмы вставки описаны в разделе Б.6.1. В итоге получается следующий результат:

0.5, 1, 1.5, 2, 2, 2.5, 3, 4,

Алгоритмы

equal_range
,
lower_bound
и
upper_bound
используются точно так же, как и их эквиваленты для ассоциативных контейнеров (раздел Б.4.10).

Б.5.5. Алгоритмы для множеств

Эти алгоритмы интерпретируют последовательность как множество элементов и выполняют основные операции над множествами. Входные и выходные последовательности предполагаются упорядоченными.

Программирование. Принципы и практика использования C++ Исправленное издание - _402.png

Б.5.6. Кучи

 Куча — это структура данных, в вершине которой находится элемент с наибольшим значением. Алгоритмы над кучами позволяют программистам работать с последовательностями произвольного доступа.

Программирование. Принципы и практика использования C++ Исправленное издание - _403.png

Куча позволяет быстро добавлять элементы и обеспечивает быстрый доступ к элементу с наибольшим значением. В основном кучи используются при реализации очередей с приоритетами.

Б.5.7. Перестановки

Перестановки используются для генерирования комбинаций элементов последовательности. Например, перестановками последовательности

abc
являются последовательности
abc
,
acb
,
bac
,
bca
,
cab
и
cba
.

Программирование. Принципы и практика использования C++ Исправленное издание - _404.png

Если последовательность

[b:e]
уже содержит последнюю перестановку (в данном примере это перестановка
cba
), то алгоритм
next_permutation
возвращает значение
x
, равное
false
; в таком случае алгоритм создает первую перестановку (в данном примере это перестановка
abc
). Если последовательность
[b:e]
уже содержит первую перестановку (в данном примере это перестановка
abc
), то алгоритм
prev_permutation
возвращает значение
x
, равное
false
; в таком случае алгоритм создает последнюю перестановку (в данном примере это перестановка
cba
).

Б.5.8. Функции min и max

Сравнение значений полезно во многих случаях.

Программирование. Принципы и практика использования C++ Исправленное издание - _405.png