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

Ответ 1

Более короткий и более STL-ish, чем предыдущие записи. Предполагает сортированный ввод.

#include <algorithm>
#include <functional>

template< class I, class P >
I remove_unique( I first, I last, P pred = P() ) {
    I dest = first;
    while (
        ( first = std::adjacent_find( first, last, pred ) )
            != last ) {
        * dest = * first;
        ++ first;
        ++ dest;
        if ( ( first = std::adjacent_find( first, last, std::not2( pred ) ) )
            == last ) break;
        ++ first;
    }
    return dest;
}

template< class I >
I remove_unique( I first, I last ) {
    return remove_unique( first, last,
        std::equal_to< typename std::iterator_traits<I>::value_type >() );
}

Ответ 2

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

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

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

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

Ответ 3

Вы даже можете использовать несоответствие, за дополнительные баллы!
Btw: хорошее упражнение.

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

Ответ 4

Мое предложение было бы измененной сортировкой вставки, чтобы вы могли сортировать и фильтровать обманки одновременно.

Ответ 5

Это в стиле стандартной библиотеки. Кредит для алгоритма идет к Джеймсу! (Если вы +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 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);
}

Ответ 6

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

Ответ 7

Вызов "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());
}

Ответ 8

Другой:

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());
}

Ответ 9

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

// 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);
    }
}

Ответ 10

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

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

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

В принципе, мой алгоритм таков: для каждого элемента в векторе увеличивайте на единицу запись карты, введенную значением этого элемента. Затем просто пройдите по карте, выведя любую клавишу, значение которой больше 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);
}

[email protected]:/tmp$ g++ test.cc && ./a.out
2 3 4

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

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