Извлечь элемент из 2 векторов? - PullRequest
Новая
       31

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

0 голосов
/ 02 февраля 2009

У меня есть 2 вектора с одним vec1 {e1, e2, e3, e4} и другим вектором с vec2 {e2, e4, e5, e7}

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

Ответы [ 4 ]

6 голосов
/ 02 февраля 2009

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, и для каждого элемента используйте std :: find, чтобы увидеть, существует ли он в vec2.

3 голосов
/ 02 февраля 2009

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

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

vec1 := vec1 \ vec3;
vec2 := 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;
1 голос
/ 02 февраля 2009

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

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

0 голосов
/ 02 февраля 2009

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

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

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

...