Получение уникальных элементов из контейнера [C++]

Question

Я искал, чтобы получить только уникальные элементы из контейнера. Скажем, srcContainer - это контейнер, из которого я хочу уникальные элементы. Я посмотрел на три варианта:

1. Использование зЬй :: уникальный

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

2. Использование BOOST :: уникальный

   boost::erase(srcContainer, boost::unique<boost::return_found_end>(boost::sort(srcContainer))); 
   

3. Мой собственный метод

   std::set<T> uniqueElems(srcContainer.begin(), srcContainer.end()); 
   srcContainer.clear(); 
   srcContainer.insert(srcContainer.end(), uniqueElems.begin(), uniqueElems.end()); 
   

Проблема с 1. и 2. заключается в том, что они меняют порядок, в котором члены произошли в исходном srcContainer. С 3. нет изменений в порядке, и, кроме того, он дает гораздо лучшую производительность по сравнению с 1. и 2 (это потому, что явная сортировка в 3. ??) выше. Истекшее время настенных часов в течение 3 методов выше, и количества элементов в srcContainer приведено ниже:

1. размера srcContainer (содержит целые числа) = 1e +-
   - STD :: уникальный = 1,04779 сек
   - BOOST :: уникальный = 1,04774 сек
   - Собственный метод = 0,481638 сек

2. размер srcContainer (содержит Int egers) = 1e + 8
   - станд :: Уникальные = 151,554 ИКС
   - BOOST :: Уникальный = 151,474 ИКС
   - Собственный метод = 57,5693 сек

Мой вопрос :

1. Есть ли лучший способ найти уникальное использование std :: unique или BOOST :: уникальный или любой другой код и поддерживающий первоначальный заказ в контейнере?
2. Любая проблема с использованием метода 3. выше.

Для профилирования производительности srcContainer был создан следующим образом:

std::vector<int> srcContainer; 
int halfWay = numElems/2; 
for (size_t k=0; k<numElems; ++k) { 
    if (k < halfWay) 
     srcContainer.push_back(k); 
    else 
     srcContainer.push_back(k - halfWay); 
} 

правок:
Согласовано с комментариями, что метод 3. также изменяет порядок элементов. Есть ли лучший способ получить уникальные элементы без изменения порядка?

Благодаря

Answer 1

EDIT на основе информации о исходных данных: Причина вы видите вставки набор выполняется быстрее, чем сортировка вектора является то, что ваш входные данные два уже отсортированных диапазоны.Для quicksort (обычно используется std::sort), это дегенеративный случай и один из худших возможных входов, которые вы могли бы ему дать. Для входного размера 1e8, сменив сортировку с std::sort на std::stable_sort, отрезали время от ~ 25 до < 9s.

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

struct Remover 
{ 
    explicit Remover(hash& found_items) : found_items_(found_items) { } 
    bool operator()(const Iter& item) { retval = <does exist in hash>; add to hash; return retval; } 

    hash& found_items_; 
}; 

hash dup_finder; 
Remover remover(dup_finder); 
std::erase(std::remove_if(src.begin(), src.end(), remover), src.end()); 

Оригинальные компоненты моего ответа:

Если элементы в исходном контейнере уже в основном отсортированы, вы можете увидеть более высокую производительность с stable_sort, а не сортировать до вызова unique. Я не могу угадать без дополнительной информации о наборе данных yoru, что может привести к тому, что вариант 3 будет работать лучше, чем 1 & 2.

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