Стенли Липпман - Язык программирования C++. Пятое издание

Например, алгоритм replace()читает последовательность и заменяет каждый экземпляр заданного значения другим значением. Алгоритм получает четыре параметра: два итератора, обозначающих исходный диапазон, и два значения. Он заменяет вторым значением значение каждого элемента, которое равно первому.

// заменить во всех элементах значение 0 на 42

replace(ilst.begin(), ilst.end(), 0, 42);

Этот вызов заменяет все экземпляры со значением 0на 42. Если исходную последовательность следует оставить неизменной, необходимо применить алгоритм replace_copy(). Этой версии функции передают третий аргумент: итератор, указывающий получателя откорректированной последовательности.

// использовать функцию back_inserter() для увеличения контейнера

// назначения до необходимых размеров

replace_copy(ilst.cbegin(), ilst.cend(),

back_inserter(ivec), 0, 42);

После этого вызова список ilstостанется неизменным, а вектор ivecбудет содержать копию его элементов, но со значением 42вместо 0.

Некоторые алгоритмы изменяют порядок элементов в пределах контейнера. Яркий пример такого алгоритма — sort(). Вызов функции sort()упорядочивает элементы исходного диапазона в порядке сортировки, используя оператор < типа элемента.

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

Для иллюстрации поставленной задачи используем в качестве исходного текста следующую простую историю:

the quick red fox jumps over the slow red turtle

В результате обработки этого текста программа должна создать следующий вектор:

Для устранения повторяющихся слов сначала отсортируем вектор так, чтобы дубликаты располагались рядом друг с другом. После сортировки вектора можно использовать другой библиотечный алгоритм, unique(), чтобы расположить уникальные элементы в передней части вектора. Поскольку алгоритмы не могут работать с самими контейнерами, используем функцию-член erase() класса vectorдля фактического удаления элементов:

void elimDups(vector &words) {

// сортировка слов в алфавитном порядке позволяет найти дубликаты

sort(words.begin(), words.end());

// функция unique() переупорядочивает исходный диапазон так, чтобы

// каждое слово присутствовало только один раз в начальной части

// диапазона, и возвращает итератор на элемент, следующий после

// диапазона уникальных значений

auto end_unique = unique(words.begin(), words.end());

// для удаления не уникальных элементов используем

// функцию erase() вектора

words.erase(end_unique, words.end());

}

Алгоритм sort()получает два итератора, обозначающих диапазон элементов для сортировки. В данном случае сортируется весь вектор. После вызова функции sort()слова упорядочиваются так:

Обратите внимание: слова redи theвстречаются дважды.

Алгоритм unique()

После сортировки слов необходимо оставить только один экземпляр каждого из них. Алгоритм unique()перестраивает исходный диапазон так, чтобы устранить смежные повторяющиеся элементы, и возвращает итератор, обозначающий конец диапазона уникальных значений. После вызова функции unique()вектор выглядит так:

Размер вектора wordsне изменился: в нем все еще десять элементов. Изменился только порядок этих элементов — смежные дубликаты были как бы "удалены". Слово удалены заключено в кавычки потому, что функция unique()не удаляет элементы. Она переупорядочивает смежные дубликаты так, чтобы уникальные элементы располагались в начале последовательности. Возвращенный функцией unique()итератор указывает на следующий элемент после последнего уникального. Последующие элементы все еще существуют, но их значение уже не важно.

Библиотечные алгоритмы работают с итераторами, а не с контейнерами. Поэтому алгоритм не может непосредственно добавить или удалить элементы.

Применение функций контейнера для удаления элементов

Для фактического удаления неиспользуемых элементов следует использовать контейнерную функцию erase()(см. раздел 9.3.3). Удалению подлежит диапазон элементов от того, на который указывает итератор end_unique, и до конца контейнера words. После вызова контейнер wordsсодержит восемь уникальных слов из исходного текста.

Следует заметить, что вызов функции erase()окажется безопасным, даже если вектор не содержит совпадающих слов. В этом случае функция unique()возвратит итератор, совпадающий с возвращенным функцией word.end(). Таким образом, оба аргумента функции erase()будут иметь одинаковое значение, а следовательно, обрабатываемый ею диапазон окажется пустым. Удаление пустого диапазона не приводит ни к какому результату, поэтому программа будет работать правильно даже тогда, когда в исходном тексте нет повторяющихся слов.

Упражнение 10.6. Напишите программу, использующую функцию fill_n()для обнуления последовательности целых чисел.

Упражнение 10.7. Определите, есть ли ошибки в следующих фрагментах кода, и, если есть, как их исправить:

(a) vector vec; list lst; int i;

while (cin >> i)

lst.push_back(i);

copy(lst.cbegin(), lst.cend(), vec.begin());

(b) vector vec;

vec.reserve(10); // reserve рассматривается в разделе 9.4

fill_n(vec.begin(), 10, 0);

Упражнение 10.8. Как упоминалось, алгоритмы не изменяют размер контейнеров, с которыми они работают. Почему использование функции back_inserter()не противоречит этому утверждению?

Упражнение 10.9. Реализуйте собственную версию функции elimDups(). Проверьте ее в программе, выводящей содержимое вектора после чтения ввода, после вызова функции unique()и после вызова функции erase().