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

за последним удаленным элементом. 

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

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

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

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

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

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

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

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

Упорядоченные ассоциативные контейнеры (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. Немодицифирующие алгоритмы для последовательностей

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

Предотвратить модификацию элементов операцией, передаваемой алгоритму 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. Алгоритмы, модифицирующие последовательности

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

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

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

typedef vector<int>::iterator VII;

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

{

  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. Вспомогательные алгоритмы

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

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

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

Сортировка и поиск относятся к категории фундаментальных алгоритмов. В то же время потребности программистов довольно разнообразны. Сравнение по умолчанию выполняется с помощью оператора <, а эквивалентность пар значений a и b определяется условием !(a<b)&&!(b<a), а не оператором ==.

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

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. Алгоритмы для множеств

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