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

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

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

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()будут иметь одинаковое значение, а следовательно, обрабатываемый ею диапазон окажется пустым. Удаление пустого диапазона не приводит ни к какому результату, поэтому программа будет работать правильно даже тогда, когда в исходном тексте нет повторяющихся слов.