Удаление дубликатов. Удаление дубликатов при копировании

   
На этом шаге мы рассмотрим алгоритмы, удаляющие дубликаты при копировании.

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

  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.

   
На следующем шаге мы закончим изучение этого вопроса.



Вы можете оставить комментарий, или Трекбэк с вашего сайта.

Оставить комментарий