Как удалить дубликаты из массива C ++? - PullRequest
Новая
       16

Как удалить дубликаты из массива C ++?

2 голосов
/ 24 августа 2011

У меня есть массив структур;размер массива N.

Я хочу удалить дубликаты из массива;то есть, сделайте изменение на месте, преобразовав массив в единый вид каждой структуры.Кроме того, я хочу знать новый размер M (самый высокий индекс в сокращенном массиве).

Структуры включают в себя примитивы, поэтому их тривиально тривиально.

Как эффективно это сделать в C ++?

Я реализовал следующие операторы: 

bool operator==(const A &rhs1, const A &rhs2) 
{       
    return ( ( rhs1.x== rhs2.x )  &&
             ( rhs1.y == rhs2.y ) );
}

bool operator<(const A &rhs1, const A &rhs2) 
{       
    if ( rhs1.x == rhs2.x )  
             return ( rhs1.y < rhs2.y );

    return ( rhs1.x < rhs2.x );
}

Однако я получаю сообщение об ошибке при запуске: 

std::sort(array, array+ numTotalAvailable);

 * array will have all elements here valid.

std::unique_copy(
        array, 
        array+ numTotalAvailable, 
        back_inserter(uniqueElements)); 

 * uniqueElements will have non-valid elements.

Что здесь не так?

Ответы [ 4 ]

6 голосов
/ 24 августа 2011

Для этого можно использовать комбинацию алгоритмов std::sort и std::unique: 

std::sort(elems.begin(), elems.end());                  // Now in sorted order.
iterator itr = std::unique(elems.begin(), elems.end()); // Duplicates overwritten
elems.erase(itr, elems.end());                          // Space reclaimed

Если вы работаете с необработанным массивом (скажем, не std::vector), то вы не сможете восстановить пространство без копирования элементов в новый диапазон. Однако, если вы в порядке, начиная с необработанного массива и заканчивая чем-то вроде std::vector или std::deque, вы можете использовать unique_copy и адаптер итератора для копирования только уникальных элементов: 

std::sort(array, array + size); // Now in sorted order

std::vector<T> uniqueElements;
std::unique_copy(array, array + size,
                 back_inserter(uniqueElements)); // Append unique elements

На данный момент uniqueElements теперь содержит все уникальные элементы.

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

std::sort(elems, elems + N);                // Now in sorted order.
T* endpoint = std::unique(elems, elems + N);// Duplicates overwritten
ptrdiff_t M = endpoint - elems;             // Find number of elements left

Надеюсь, это поможет!

1 голос
/ 24 августа 2011 
std::set<T>  uniqueItems(v.begin(), v.end());

Теперь uniqueItems содержит только уникальные предметы.Делай что хочешь с этим делать.Возможно, вы бы хотели, чтобы v содержал все уникальные предметы.Если это так, то сделайте следующее: 

//assuming v is std::vector<T>
std::vector<T>(uniqueItems.begin(), uniqueItems.end()).swap(v);

Теперь v содержит все уникальные предметы.Он также сжимается v до минимального размера.Используется Shrink-to-fit идиома.

0 голосов
/ 24 августа 2011

Альтернативным подходом к применению алгоритмов к вашему массиву будет вставка его элементов в std::set.Разумно ли сделать это таким образом, зависит от того, как вы планируете использовать свои вещи.

0 голосов
/ 24 августа 2011

Вы можете использовать шаблон веса в полете .Самый простой способ сделать это - использовать библиотеку Boost Flyweight.

Редактировать : я не уверен, есть ли способ узнать, сколько объектовхранятся в расширенной реализации Boost, если она есть, я не могу найти ее в документации.

...