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

Question

Мне нужно взять вектор C ++ с потенциально большим количеством элементов, стереть дубликаты и отсортировать его.

У меня сейчас есть код ниже, но он не работает.

vec.erase(
      std::unique(vec.begin(), vec.end()),
      vec.end());
std::sort(vec.begin(), vec.end());

Как мне правильно это сделать?

Кроме того, быстрее ли сначала удалить дубликаты (аналогично приведенному выше) или сначала выполнить сортировку? Если я сначала выполню сортировку, гарантированно ли она останется отсортированной после выполнения std::unique?

Или есть другой (возможно, более эффективный) способ сделать все это?

Answer 1

Я согласен с R. Паштет и Тодд Гарднер ; std::set может быть хорошей идеей здесь. Даже если вы застряли с использованием векторов, если у вас достаточно дубликатов, вам лучше создать набор для грязной работы.

Давайте сравним три подхода:

Просто используя вектор, сортировка + уникальный

sort( vec.begin(), vec.end() );
vec.erase( unique( vec.begin(), vec.end() ), vec.end() );

Преобразовать для установки (вручную)

set<int> s;
unsigned size = vec.size();
for( unsigned i = 0; i < size; ++i ) s.insert( vec[i] );
vec.assign( s.begin(), s.end() );

Преобразовать в набор (используя конструктор)

set<int> s( vec.begin(), vec.end() );
vec.assign( s.begin(), s.end() );

Вот как они работают при изменении количества дубликатов:

Сводка : когда количество дубликатов достаточно велико, на самом деле быстрее преобразовать в набор и затем сбросить данные обратно в вектор .

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

Answer 2

Я переделал профилирование Нейта Коля и получил разные результаты. В моем тестовом примере прямая сортировка вектора всегда более эффективна, чем использование набора. Я добавил новый, более эффективный метод, используя unordered_set.

Имейте в виду, что метод unordered_set работает только в том случае, если у вас есть хорошая хеш-функция для типа, который вам нужен, uniqued и отсортирован. Для малышей это просто! (Стандартная библиотека предоставляет хэш по умолчанию, который является просто функцией идентификации.) Кроме того, не забудьте отсортировать в конце, поскольку unordered_set, ну, в общем, неупорядоченный:)

Я немного покопался в реализации set и unordered_set и обнаружил, что конструктор фактически создает новый узел для каждого элемента, прежде чем проверять его значение, чтобы определить, должен ли он быть вставлен (в реализации Visual Studio, в как минимум).

Вот 5 методов:

f1: просто с помощью vector, sort + unique

sort( vec.begin(), vec.end() );
vec.erase( unique( vec.begin(), vec.end() ), vec.end() );

f2: преобразовать в set (используя конструктор)

set<int> s( vec.begin(), vec.end() );
vec.assign( s.begin(), s.end() );

f3: преобразовать в set (вручную)

set<int> s;
for (int i : vec)
    s.insert(i);
vec.assign( s.begin(), s.end() );

f4: преобразовать в unordered_set (используя конструктор)

unordered_set<int> s( vec.begin(), vec.end() );
vec.assign( s.begin(), s.end() );
sort( vec.begin(), vec.end() );

f5: преобразовать в unordered_set (вручную)

unordered_set<int> s;
for (int i : vec)
    s.insert(i);
vec.assign( s.begin(), s.end() );
sort( vec.begin(), vec.end() );

Я провел тест с вектором из 100 000 000 вставок, выбранным случайным образом в диапазонах [1,10], [1 000] и [1 100 000]

Результаты (в секундах, чем меньше, тем лучше):

range         f1       f2       f3       f4      f5
[1,10]      1.6821   7.6804   2.8232   6.2634  0.7980
[1,1000]    5.0773  13.3658   8.2235   7.6884  1.9861
[1,100000]  8.7955  32.1148  26.5485  13.3278  3.9822

Answer 3

std::unique удаляет повторяющиеся элементы только в том случае, если они являются соседями: сначала нужно отсортировать вектор, прежде чем он будет работать так, как вы собираетесь.

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

Answer 4

Я не уверен, для чего вы используете это, поэтому я не могу сказать это со 100% уверенностью, но обычно, когда я думаю, что «отсортированный, уникальный» контейнер, я думаю о std :: set . Это может быть лучше подходит для вашего варианта использования:

std::set<Foo> foos(vec.begin(), vec.end()); // both sorted & unique already

В противном случае сортировка перед вызовом уникального (как указывалось в других ответах) - это путь.

Answer 5

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

Answer 6

Вот шаблон, чтобы сделать это для вас:

template<typename T>
void removeDuplicates(std::vector<T>& vec)
{
    std::sort(vec.begin(), vec.end());
    vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
}

назовите это как:

removeDuplicates<int>(vectorname);

Answer 7

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

редактировать: 38 секунд ...

Answer 8

Эффективность - сложная концепция. Существуют временные и пространственные соображения, а также общие измерения (где вы получаете только расплывчатые ответы, такие как O (n)) и конкретные (например, пузырьковая сортировка может быть намного быстрее быстрой сортировки, в зависимости от входных характеристик).

Если у вас сравнительно мало дубликатов, то сортировка с последующим уникальным и стирание кажется подходящим. Если у вас было относительно много дубликатов, создание набора из вектора и выполнение тяжелой работы может легко обойти его.

Не просто сосредоточьтесь на эффективности времени. Sort + unique + erase работает в пространстве O (1), а конструкция множества работает в пространстве O (n). И ни один из них не поддается прямому распараллеливанию с уменьшением карты (для действительно огромных наборов данных).

Answer 9

Если вы не хотите менять порядок элементов, то вы можете попробовать это решение:

template <class T>
void RemoveDuplicatesInVector(std::vector<T> & vec)
{
    set<T> values;
    vec.erase(std::remove_if(vec.begin(), vec.end(), [&](const T & value) { return !values.insert(value).second; }), vec.end());
}

Answer 10

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