Как сохранить только дубликаты эффективно?

Вы даже можете использовать несоответствие для дополнительных очков!
Кстати: хорошее упражнение.

template<class TIter>
/** Moves duplicates to front, returning end of duplicates range.
 *  Use a sorted range as input. */
TIter Duplicates(TIter begin, TIter end) {
    TIter dup = begin;
    for (TIter it = begin; it != end; ++it) {
        TIter next = it;
        ++next;
        TIter const miss = std::mismatch(next, end, it).second;
        if (miss != it) {
            *dup++ = *miss;
            it = miss;
        }
    }
    return dup;
}

Я думаю, что с большой точки зрения у вас это реализовано настолько хорошо, насколько это возможно. Преобладающая стоимость - это сортировка, которая равна O (N log N). Однако одна из возможностей состоит в том, чтобы создать новый вектор с повторяющимися записями, а не использовать существующий вектор с операцией удаления, удаляющей недубликаты. Однако это будет лучше только в том случае, если различное количество дубликатов невелико по сравнению с общим количеством записей.

Рассмотрим крайний пример. Если исходный массив состоял из 1000 записей только с одним дубликатом, то на выходе был бы вектор только с одним значением. Было бы немного эффективнее создать новый вектор с одной записью, чем удалять другие 999 записей из исходного вектора. Однако я подозреваю, что при тестировании в реальном мире экономию от этого изменения может быть трудно измерить.

Править Я как раз думал об этом с точки зрения вопроса "интервью". Другими словами, это не очень полезный ответ. Но можно было бы решить это за O (N) (линейное время), а не за O (N Log N). Используйте дисковое пространство вместо ЦП. Создайте два «битовых» массива с изначально очищенными. Прокрутите свой вектор целочисленных значений. Найдите каждое значение в первом битовом массиве.Если он не установлен, установите бит (установите его в 1). Если он установлен, то установите соответствующий бит во втором массиве (с указанием дубликата). После обработки всех векторных записей просканируйте второй массив и выведите повторяющиеся целые числа (обозначенные битами, установленными во втором битовом массиве). Причина использования битовых массивов просто для экономии места. При работе с 4-байтовыми целыми числами требуется необработанное пространство (2 * 2 ^ 32/8) . Но на самом деле это можно было бы превратить в полезный алгоритм, сделав его разреженным массивом. Сам псевдопсевдокод будет примерно таким:

bitarray1[infinite_size];
bitarray2[infinite_size];

clear/zero bitarrays

// NOTE - do not need to sort the input
foreach value in original vector {
    if ( bitarray1[value] ) 
        // duplicate
        bitarray2[value] = 1
    bitarray1[value] = 1
}

// At this point, bitarray2 contains a 1 for all duplicate values.
// Scan it and create the new vector with the answer
for i = 0 to maxvalue
    if ( bitarray2[i] )
        print/save/keep i

Я с треском провалил свою первую попытку, предполагая, что std :: unique перемещает все дубликаты в конец диапазона (это не так). Ой. Вот еще одна попытка:

Вот реализация not_unique . Он удаляет все элементы, которые появляются только один раз в отсортированном диапазоне и дубликаты любых элементов, которые появляются более одного раза. Таким образом, результирующий диапазон представляет собой уникальный список элементов, которые встречаются более одного раза.

Функция имеет линейную сложность и выполняет один проход по диапазону ( std :: unique имеет линейную сложность). Он должен соответствовать требованиям прямого итератора. Возвращается конец результирующего диапазона.

template <typename It>
It not_unique(It first, It last)
{
    if (first == last) { return last; }

    It new_last = first;
    for (It current = first, next = ++first; next != last; ++current, ++next)
    {
        if (*current == *next)
        {
            if (current == new_last)
            {
                ++new_last;
            }
            else
            {
                *new_last++ = *current;
                while (next != last && *current == *next)
                {
                    ++current;
                    ++next;
                }
                if (next == last)
                    return new_last;
            }
        }
    }
    return new_last;
}

Я предлагаю модифицированную сортировку вставкой, чтобы вы могли сортировать и фильтровать дубликаты одновременно.

Вызов "erase (it_start + keep, it_stop);" из цикла while приведет к многократному копированию оставшихся элементов.

Я бы посоветовал переставить все уникальные элементы в начало вектора, а затем стереть все оставшиеся элементы сразу.

int num_repeats(vector<int>::const_iterator curr, vector<int>::const_iterator end) {
  int same = *curr;
  int count = 0;
  while (curr != end && same == *curr) {
    ++curr;
    ++count;
  }
  return count;
}

void dups(vector<int> *v) {
  sort(v->begin(), v->end());
  vector<int>::iterator current = v->begin();
  vector<int>::iterator end_of_dups = v->begin();
  while (current != v->end()) {
    int n = num_repeats(current, v->end());
    if (n > 1) {
      swap(*end_of_dups, *current);
      end_of_dups++;
    }
    current += n;
  }
  v->erase(end_of_dups, v->end());
}

Еще один:

template <typename T>
void keep_duplicates(vector<T>& v) 
{
    set<T> 
        u(v.begin(), v.end()), // unique 
        d; // duplicates
    for (size_t i = 0; i < v.size(); i++)
        if (u.find(v[i]) != u.end())
            u.erase(v[i]);
        else
            d.insert(v[i]);

    v = vector<T>(d.begin(), d.end());
}

Что означает выражение «столь же эффективно, как std :: unique»? Эффективен с точки зрения времени выполнения, времени разработки, использования памяти или чего-то еще?

Как отмечали другие, std :: unique требует отсортированного ввода, который вы не предоставили, поэтому это не лучший тест для начала.

Лично я бы просто std :: map делал всю мою работу за меня. У него много свойств, которые мы можем использовать для максимальной элегантности / лаконичности. Он сохраняет свои элементы уже отсортированными, и operator [] вставит нулевое значение, если ключ еще не существует. Используя эти свойства, мы можем сделать это в двух или трех строках кода и при этом достичь разумной сложности во время выполнения.

По сути, мой алгоритм таков: для каждого элемента в векторе увеличить на единицу запись карты, привязанную к значению этого элемента. После этого просто пройдитесь по карте, выводя любой ключ, значение которого больше 1. Не может быть проще.

#include <iostream>
#include <vector>
#include <map>

void
output_sorted_duplicates(std::vector<int>* v)
{
   std::map<int, int> m;  

   // count how many of each element there are, putting results into map
   // map keys are elements in the vector, 
   // map values are the frequency of that element
   for (std::vector<int>::iterator vb = v->begin(); vb != v->end(); ++vb)
      ++m[*vb];

   // output keys whose values are 2 or more
   // the keys are already sorted by the map
   for (std::map<int, int>::iterator mb = m.begin(); mb != m.end(); ++mb)
      if ( (*mb).second >= 2 ) 
         std::cout << (*mb).first << " "; 
   std::cout << std::endl;
}

int main(void) 
{ 
   int initializer[] = { 4, 4, 1, 2, 3, 2, 3 };
   std::vector<int> data(&initializer[0], &initializer[0] + 7);
   output_sorted_duplicates(&data);
}

janks@phoenix:/tmp$ g++ test.cc && ./a.out
2 3 4

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

Сделать мою функцию шаблоном и заставить ее работать с диапазонами в стиле STL, а не просто с векторами целых чисел, остается в качестве упражнения.

Это в стиле стандартной библиотеки. Заслуга за алгоритм принадлежит Джеймсу! (Если вы ставите +1 мне, то лучше поставьте +1 ему, или иначе). Все, что я сделал, это привел его в стиль стандартной библиотеки:

#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>
#include <vector>

// other stuff (not for you)
template <typename T>
void print(const char* pMsg, const T& pContainer)
{
    std::cout << pMsg << "\n    ";
    std::copy(pContainer.begin(), pContainer.end(),
        std::ostream_iterator<typename T::value_type>(std::cout, " "));
    std::cout << std::endl;
}

template <typename T, size_t N>
T* endof(T (&pArray)[N])
{
    return &pArray[0] + N;
}

// not_unique functions (for you)
template <typename ForwardIterator, typename BinaryPredicate>
ForwardIterator not_unique(ForwardIterator pFirst, ForwardIterator pLast,
                           BinaryPredicate pPred)
{
    // correctly handle case where an empty range was given:
    if (pFirst == pLast) 
    { 
        return pLast; 
    }

    ForwardIterator result = pFirst;
    ForwardIterator previous = pFirst;

    for (++pFirst; pFirst != pLast; ++pFirst, ++previous)
    {
        // if equal to previous
        if (pPred(*pFirst, *previous))
        {
            if (previous == result)
            {
                // if we just bumped bump again
                ++result;
            }
            else if (!pPred(*previous, *result))
            {
                // if it needs to be copied, copy it
                *result = *previous;

                // bump
                ++result;
            }
        }
    }

    return result;
}

template <typename ForwardIterator>
ForwardIterator not_unique(ForwardIterator pFirst, ForwardIterator pLast)
{
    return not_unique(pFirst, pLast,
                std::equal_to<typename ForwardIterator::value_type>());
}


//test
int main()
{
    typedef std::vector<int> vec;

    int data[] = {1, 4, 7, 7, 2, 2, 2, 3, 9, 9, 5, 4, 2, 8};
    vec v(data, endof(data));

    // precondition
    std::sort(v.begin(), v.end());
    print("before", v);

    // duplicatify (it's a word now)
    vec::iterator iter = not_unique(v.begin(), v.end());
    print("after", v);

    // remove extra
    v.erase(iter, v.end());
    print("erased", v);
}

Это исправляет ошибки в исходной версии Джеймса Макнеллиса . Я также предоставляю версии на месте и вне места.

// In-place version.  Uses less memory and works for more container
// types but is slower.
template <typename It>
It not_unique_inplace(It first, It last)
{
    if (first == last)
        return last;

    It new_last = first;
    for (It current = first, next = first + 1; next != last; ++current, ++next)
    {
        if (*current == *next && 
            (new_last == first || *current != *(new_last-1)))
            *new_last++ = *current;
    }
    return new_last;
}

// Out-of-place version. Fastest.
template <typename It, typename Container>
void not_unique(It first, It last, Container pout)
{
    if (first == last || !pout)
        return;

    for (It current = first, next = first + 1; next != last; ++current, ++next)
    {
        if (*current == *next && 
            (pout->empty() || *current != pout->back()))
            pout->push_back(*current);
    }
}