На этом шаге мы рассмотрим алгоритмы, удаляющие дубликаты при копировании.
Для удаления дубликатов при копировании можно воспользоваться следующими алгоритмами:
OutputIterator
unique_copy (InputIterator sourceBeg, InputIterator sourceEnd,
Outputlterator destBeg)
OutputIterator
unique_copy (InputIterator sourceBeg, InputIterator sourceEnd,
OutputIterator destBeg,
BinaryPredicate op)
Обе формы являются объединением алгоритмов сору() и unique().
Обе формы копируют в приемный интервал, начинающийся с позиции destBeg, все элементы исходного интервала [beg,end), за исключением смежных дубликатов.
Обе формы возвращают позицию за последним скопированным элементом в приемном интервале (то есть позицию первого элемента, который не был заменен).
Перед вызовом необходимо убедиться в том, что приемный интервал имеет достаточный размер, или использовать итераторы вставки.
Сложность линейная (numberOfElements сравнений или вызовов ор и присваиваний соответственно).
Пример использования алгоритма unique_copy():
//--------------------------------------------------------------------------- #include <vcl.h> #include <iterator> #include "algostuff.hpp" #include <conio.h> //необходимо для getch() #pragma hdrstop //--------------------------------------------------------------------------- #pragma argsused using namespace std; std::string ToRus(const std::string &in) { char *buff = new char [in.length()+1]; CharToOem(in.c_str(),buff); std::string out(buff); delete [] buff; return out; } bool differenceOne (int elem1, int elem2) { return elem1 + 1 == elem2 || elem1 - 1 == elem2; } int main() { // Исходные данные int source[] = { 1, 4, 4, 6, 1, 2, 2, 3, 1, 6, 6, 6, 5, 7, 5, 4, 4 }; int sourceNum = sizeof(source)/sizeof(source[0]); // Инициализация coll элементами source list<int> coll; copy(source, source+sourceNum, // Источник back_inserter(coll)); // Приемник PRINT_ELEMENTS(coll,"Исходная коллекция:\n"); // Вывод содержимого coll с удалением смежных дубликатов cout << ToRus("Коллекция с удалением смежных дубликатов:\n"); unique_copy(coll.begin(), coll.end(), // Источник ostream_iterator<int>(cout," ")); // Приемник cout << endl; // Вывод содержимого coll с удалением смежных элементов // со значениями, отличающимися на 1 cout << ToRus("Коллекция с удалением смежных дубликатов\n со значениями, отличающимися на 1:\n"); unique_copy(coll.begin(), coll.end(), // Источник ostream_iterator<int>(cout," "), // Приемник differenceOne); // Критерий удаления cout << endl; getch(); return 0; } //---------------------------------------------------------------------------
Результат выполнения программы выглядит так:
Рис.1. Результат работы приложения
Обратите внимание на второй вызов unique_copy(). Он не удаляет элементы, отличающиеся от своего предшественника на 1, как могло бы показаться на первый взгляд. Вместо этого он удаляет все элементы, отличающиеся на 1 от предыдущего элемента, который не был удален. Например, после трех экземпляров значения 6 следующие элементы 5, 7 и 5 отличаются от 6 на 1, поэтому все они удаляются. Но следующие два экземпляра значения 4 остаются, поскольку при сравнении с 6 разность не равна 1.
На следующем шаге мы закончим изучение этого вопроса.
