Каков наиболее эффективный способ копирования элементов, которые встречаются только один раз в std-векторе?

Question

У меня есть зЬй вектор с элементами, как это:

[0 , 1 , 2 , 0 , 2 , 1 , 0 , 0 , 188 , 220 , 0 , 1 , 2 ] 

Что является наиболее эффективным способом, чтобы найти и скопировать элементы, которые происходят только один раз в этом векторе, за исключением грубой силы O (2 п ^) алгоритм ? В этом случае новый список должен содержать [188, 220]

Answer 1

1. Сделать unordered_map<DataType, Count> count;
2. перебрать входной вектор увеличения количества каждого значения. Сортировать по count[value]++;
3. итерации по count карте копирования ключей, для которых значение 1.

Это O(n). У вас есть хэши, поэтому для небольших наборов данных нормальная карта может быть более эффективной, но технически это будет O(n log n).

Это хороший метод для дискретных наборов данных.

Пример кода:

#include <iostream> 
#include <unordered_map> 
#include <vector> 
#include <algorithm> 
using namespace std; 

int main() { 
    vector<int> v{1,1,2,3,3,4}; 
    unordered_map<int,int> count; 
    for (const auto& e : v) count[e]++; 
    vector<int> once; 
    for (const auto& e : count) if(e.second == 1) once.push_back(e.first); 
    for (const auto& e : once) cout << e << '\n'; 
    return 0; 
} 

Я пытался несколько идей. Но я не вижу пути map. unordered_multiset - это отличный способ ... кроме того, что он не позволяет вам перебирать ключи. У него есть метод проверки количества ключей, но вам нужен другой набор только для ключей для зондирования. Я не считаю это более простым способом. В современном C++ с подсчетом auto s легко. Я также просмотрел библиотеку algorithm, но я не нашел никаких transfrom, copy_if, generate и т. Д., Которые могли условно преобразовать элемент (запись в карте -> значение, если счетчик равен 1).

Answer 2

@ Ответ luk32 - это, безусловно, самый эффективный способ решения этого вопроса. Однако, если у вас мало памяти и вы не можете позволить себе unordered_map, есть и другие способы сделать это.

Вы можете использовать std::sort() для сортировки в векторе сначала. Затем не дубликаты можно найти на одной итерации. Общая сложность - O(nlogn).

Если вопрос немного отличается, и вы знаете, что существует только один не дублируемый элемент, вы можете использовать this code (код на Java). Сложность здесь O(n).

Answer 3

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

v небольшой и заполненный в основном уникальными значениями?

auto lo = v.begin(), hi = v.end(); 
std::sort(lo, hi); 
while (lo != v.end()) { 
    hi = std::mismatch(lo + 1, v.end(), lo).first; 
    lo = (std::distance(lo, hi) == 1) ? hi : v.erase(lo, hi); 
} 

v маленький и заполненный в основном дубликатами?

auto lo = v.begin(), hi = v.end(); 
std::sort(lo, hi); 
while (lo != v.end()) { 
    hi = std::upper_bound(lo + 1, v.end(), *lo); 
    lo = (std::distance(lo, hi) == 1) ? hi : v.erase(lo, hi); 
} 

ли vгигантский?

std::unordered_map<int, bool> keyUniqueness{}; 
keyUniqueness.reserve(v.size()); 
for (int key : v) { 
    bool wasMissing = keyUniqueness.find(key) == keyUniqueness.end(); 
    keyUniqueness[key] = wasMissing; 
} 
v.clear(); 
for (const auto& element : keyUniqueness) { 
    if (element.second) { v.push_back(element.first); } 
} 

И так далее.

Answer 4

Поскольку вы используете std::vector, я предполагаю, что вы хотите максимизировать все его преимущества, включая reference locality. Для этого нам нужно немного ввести текст. И я протестированные ниже код ...

У меня есть линейный O(n) алгоритм здесь (эффективно O(nlog(n))), его немного, как ответ Брайена, но я использую OutputIterators вместо того, чтобы делать это на месте. Предварительное условие состоит в том, что оно сортируется.

---

template<typename InputIterator, typename OutputIterator> 
OutputIterator single_unique_copy(InputIterator first, InputIterator last, OutputIterator result){ 
    auto previous = first; 
    if(previous == last || ++first == last) return result; 
    while(true){ 
     if(*first == *previous) 
      while((++first != last) && (*first == *previous)); 
     else 
      *(result++) = *previous; 
     if(first == last) break; 
     previous = first; 
     ++first; 
    } 
    return ++result; 
} 

А вот использование пример:

int main(){ 
    std::vector<int> vm = {0, 1, 2, 0, 2, 1, 0, 0, 1, 88, 220, 0, 1, 2, 227, -8}; 
    std::vector<int> kk; 
    std::sort(vm.begin(), vm.end()); 
    single_unique_copy(vm.begin(), vm.end(), std::back_inserter(kk)); 
    for(auto x : kk) std::cout << x << ' '; 
    return 0; 
} 

Как и следовало ожидать, выход:

-8, 88, 220, 227 

Ваш случай использования может отличаться от моего, поэтому профиль сначала ... :-)

EDIT:

• Используя алгоритм luk32 и моя ... Использование 13 миллионов элементов ... , созданные в порядке убывания, повторяющиеся на каждом i % 5.
• Под отладочных, luk32: 9.34 секунд и мое: 7.80 секунды
• Под -O3, luk32: 2.71 секунд и мой 0.52 секунд
• Mingw5.1 64bit, Windows 10, 1,73 Core i5 4210U, 6GB DDR3 1600MHz RAM
• Benchmark здесь, http://coliru.stacked-crooked.com/a/187e5e3841439742

Для небольших чисел, разница остается в силе, пока она не станет некритическим кодом