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

Б.4.8. Размер и емкость

Размер — это количество элементов в контейнере; емкость — это количество элементов, которое контейнер может содержать до того, как потребуется дополнительно увеличить память

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

Изменяя размер или емкость, можно переместить элементы в новое место. Из этого следует, что итераторы (а также указатели и ссылки) на элементы могут стать некорректными (т.е. относиться к старым адресам).

Б.4.9. Другие операции

Контейнеры можно копировать (см. раздел Б.4.3), сравнивать и обменивать.

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

Если сравнение контейнеров производится с помощью соответствующего оператора (например,

<
), то их элементы сравниваются с помощью эквивалентного оператора для сравнения элементов (например,
<
). 

Б.4.10. Операции над ассоциативными контейнерами

Ассоциативные контейнеры обеспечивают поиск на основе ключей.

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

Упорядоченные ассоциативные контейнеры (

map
,
set
и др.) имеют необязательный шаблонный аргумент, указывающий тип предиката сравнения, например,
set<K,C>
использует предикат
C
для сравнения значений типа
K
.

Первый итератор пары, возвращенной функцией

equal_range
, равен
lower_bound
, а второй —
upper_bound
. Вы можете вывести на печать значения всех элементов, имеющих ключ "
Marian
" в контейнере
multimap<string,int>
, написав следующий код:

string k = "Marian";

typedef multimap<string,int>::iterator MI;

pair<MI,MI> pp = m.equal_range(k);

if (pp.first!=pp.second)

  cout << "elements with value ' " << k << " ':\n";

else

  cout << "no element with value ' " << k << " '\n";

for (MI p = pp.first; p!=pp.second; ++p) cout << p–>second << '\n';

В качестве альтернативы можно выполнить следующую эквивалентную инструкцию:

pair<MI,MI> pp = make_pair(m.lower_bound(k),m.upper_bound(k));

Однако эта инструкция выполняется вдвое дольше. Алгоритмы

equal_range
,
lower_bound
и
upper_bound
можно выполнять также для упорядоченных последовательностей (раздел Б.5.4). Определение класса
pair
приведено в разделе Б.6.3. 

Б.5. Алгоритмы

В заголовке

<algorithm>
определено около 60 алгоритмов. Все они относятся к последовательностям, определенным парами итераторов (для ввода) или одним итератором (для вывода).

При копировании, сравнении и выполнении других операций над двумя последовательностями первая из них задается парой итераторов

[b:e]
, а вторая — только одним итератором
b2
, который считается началом последовательности, содержащей элементы, количество которых достаточно для выполнения алгоритма, например, столько же, сколько элементов в первой последовательности:
[b2:b2+(e–b)]
.

Некоторые алгоритмы, такие как

sort
, используют итераторы произвольного доступа, а многие другие, такие как
find
, только считывают элементы с помощью однонаправленного итератора.

Многие алгоритмы придерживаются обычного соглашения и возвращают конец последовательности в качестве признака события “не найден”. Мы больше не будем упоминать об этом каждый раз, описывая очередной алгоритм.

Б.5.1. Немодицифирующие алгоритмы для последовательностей

Немодифицирующий алгоритм просто считывает элементы последовательности; он не изменяет порядок следования элементов последовательности и не изменяет их значения.

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

Предотвратить модификацию элементов операцией, передаваемой алгоритму

for_each
, невозможно; это считается приемлемым. Передача операции, изменяющей проверяемые ею элементы, другим алгоритмам (например, count или
==
) недопустима.

Рассмотрим пример правильного использования алгоритма.

bool odd(int x) { return x&1; }

int n_even(const vector<int>& v) // подсчитывает количество четных

                                 // чисел в v

{

  return v.size()–count_if(v.begin(),v.end(),odd);

}

Б.5.2. Алгоритмы, модифицирующие последовательности

Модифицирующие алгоритмы могут изменять элементы последовательностей, являющихся их аргументами.

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

Алгоритм

shuffle
перетасовывает последовательность точно так же, как перетасовывается колода карт; иначе говоря, после перетасовки элементы следуют в случайном порядке, причем смысл слова “случайно” определяется распределением, порожденным датчиком случайных чисел.

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

remove
, не может уменьшить длину входной последовательности, удалив (стерев) ее элементы; вместо этого он передвигает эти элементы к началу последовательности.

typedef vector<int>::iterator VII;

void print_digits(const string& s, VII b, VII e)