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

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

  ForwardIterator
  unique (ForwardIterator beg, ForwardIterator end)
  ForwardIterator
  unique (ForwardIterator beg, ForwardIterator end, 
          BinaryPredicate op)

    Обе формы "сворачивают" серии одинаковых элементов, оставляя начальный элемент и удаляя последующие дубликаты.

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

    Вторая форма удаляет все элементы, следующие за элементом e, для которых бинарный предикат op(elem,e) возвращает true. Иначе говоря, предикат используется для сравнения элемента не с предшественником, а с предыдущим элементом, который не был удален (смотри пример).

    Обе формы возвращают новый логический конец модифицированного интервала (то есть позицию за последним элементом, который не был удален).

    Алгоритмы заменяют "удаленные" элементы следующими элементами, которые не были удалены.

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

    Вызывающая сторона должна использовать новый логический конец интервала вместо исходного конца end.

    Предикат ор не должен изменять свое состояние во время вызова.

    Вследствие модификации эти алгоритмы не могут использоваться с ассоциативными контейнерами.

    Для списков определена аналогичная функция unique(), которая часто работает более эффективно, поскольку она меняет внутренние указатели вместо присваивания значений элементам (смотри 204 шаг).

    Сложность линейная (numberOfElements сравнений или вызовов ор соответственно).

    Пример использования алгоритма unique():

//---------------------------------------------------------------------------

#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;
}


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]);

  list<int> coll;

  // Инициализация coll элементами source
  copy (source, source+sourceNum,           // Источник
        back_inserter(coll));               // Приемник
  PRINT_ELEMENTS(coll,"Исходная коллекция:\n");

  // Удаление последовательных дубликатов
  list<int>::iterator pos;
  pos = unique (coll.begin(), coll.end());

  // Вывод оставшихся элементов
  //   - с использованием нового логического конца
  cout << ToRus("Коллекция после удаления последовательных дубликатов:\n");
  copy (coll.begin(), pos,                  // Источник
        ostream_iterator<int>(cout," "));   // Приемник
  cout << "\n\n";

  // Повторная инициализация coll элементами source
  copy (source, source+sourceNum,           // Источник
        coll.begin());                      // Приемник
  PRINT_ELEMENTS(coll,"Исходная коллекция:\n");

  // Удаление элемента, если ему предшествует элемент с большим значением
  coll.erase (unique (coll.begin(), coll.end(),
                      greater<int>()),
              coll.end());
  PRINT_ELEMENTS(coll,"Коллекция после удаления элементов, которым\n
                       предшествует элемент с большим значением:\n");


  getch();
  return 0;
}

//---------------------------------------------------------------------------

    Результат выполнения программы выглядит так:

Рис.1. Результат работы приложения

    Первый вызов unique() уничтожает последовательные дубликаты. Второй вызов показывает, как работает вторая форма алгоритма. Из коллекции удаляются все элементы, следующие за текущим элементом, для которых сравнение критерием greater дает результат true. Например, первый элемент 6 больше следующих за ним элементов 1, 2, 2, 3 и 1, поэтому все эти элементы удаляются. Иначе говоря, предикат сравнивает элемент не с предшественником, а с предыдущим элементом, который не был удален.

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

Предыдущий шаг Содержание Следующий шаг