Извлечь элемент из 2 векторов?

Question

У меня есть 2 вектор с один имеет VEC1 {e1, e2, e3, e4}, а другой с vec2 {е2, е4, е5, е7}

Как эффективно получить три вектора из вышеуказанных векторов, таких, что 1.has элементы, которые доступны только в vec1 аналогично 2 имеет только vec2 элементов и 3.with общих элементов

Answer 1

std::set_intersection должен сделать трюк, если оба вектора сортируются: http://msdn.microsoft.com/en-us/library/zfd331yx.aspx

std::set_intersection(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), std::back_inserter(vec3)); 

Пользовательская предикат также могут использоваться для сравнения:

std::set_intersection(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), std::back_inserter(vec3), my_equal_functor()); 

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

Answer 2

Если количество элементов низкое, вы можете использовать наивный подход, который легко реализовать и имеет O (n).

Если у вас есть большое количество элементов, вы можете создать хеш-таблицу из одного из них и найти в ней элементы другого вектора. Кроме того, вы можете сортировать один из них и бинарный поиск через него.

Answer 3

Проблема, которую вы описываете, - это пересечение векторов. Это зависит от размера входных векторов.

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

Это обычная проблема при поиске информации, где вам нужно пересечь инвертированные индексы. Есть несколько научных статей по этому вопросу.

Answer 4

Что вы просите, так это то, что vec3 будет пересечением двух других. Jalf демонстрирует, как заполнить vec3 с помощью функции std::set_intersection от the <algorithm> header. Но помните, что для заданных функций для работы, векторы должны быть отсортированы.

Затем вы хотите vec1 и vec2 быть разница между собой и vec3. В множестве обозначений:

Вы можете использовать std::set_difference функцию для этого, но вы не можете использовать его, чтобы изменить векторы на месте. Вам нужно будет вычислить другой вектор, чтобы удерживать разницу:

std::vector<foo> temp; 
std::set_difference(vec1.begin(), vec1.end(), 
        vec3.begin(), vec3.end(), 
        std::back_inserter(temp)); 
vec1 = temp; 
temp.clear(); 
std::set_difference(vec2.begin(), vec2.end(), 
        vec3.begin(), vec3.end(), 
        std::back_inserter(temp)); 
vec2 = temp;