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

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

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

string k = "Marian";

typedef multimap::iterator MI;

pair 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 pp = make_pair(m.lower_bound(k),m.upper_bound(k));

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

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

В заголовке определено около 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& v) // подсчитывает количество четных

// чисел в v

{

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

}

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

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

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

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

typedef vector::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 v(a,a+sizeof(a)/sizeof(int));

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