Удалить общие сущности из двух векторов?

Question

скажем, у меня есть vector<class1a>,vector<class1b> как удалить общие сущности из них обоих Я определил == оператор для объектов class1 class1a, class1b

Answer 1

Алгоритмы stl предоставляют несколько функций для выполнения операций над множествами, в частности вычисление симметричной разности множества , что вам и нужно.

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

#include <algorithm>
#include <vector>

int main(int argc, char **argv) {

    std::vector<int> v1;
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);
    v1.push_back(5);
    v1.push_back(6);

    std::vector<int> v2;
    v2.push_back(2);
    v2.push_back(4);
    v2.push_back(6);
    v2.push_back(8);

    // Ranges must be sorted!
    std::sort(v1.begin(), v1.end());
    std::sort(v2.begin(), v2.end());

    std::vector<int> res; // Will contain the symmetric difference
    std::set_symmetric_difference(v1.begin(), v1.end(), 
                                  v2.begin(), v2.end(), 
                                  std::back_inserter(res));

    // Copy result to the output
    std::copy(res.begin(), res.end(), std::ostream_iterator<int>(cout, " "));
    // Prints "1 3 5"

    return 0;
}

std::set_symmetric_difference принимает два диапазона (то есть две пары OutputIterator) и InputIterator, в который он помещает результат. Он также возвращает итератор в конец диапазона результатов.

---

EDIT

Я только что прочитал ваши комментарии на ваш вопрос. Если вы хотите изменить два исходных вектора, вы можете использовать std::set_difference:

vector<int>::iterator endRange;
endRange = set_difference(v1.begin(), v1.end(), 
                          v2.begin(), v2.end(), 
                          v1.begin());
v1.erase(endRange, v1.end());

Здесь мы помещаем результат разности множеств v1 - v2 в v1. Однако, мы не можем сделать наоборот, так как v1 теперь изменен. Решение состоит в том, чтобы вычислить пересечение v1 и v2, а затем разность с этим пересечением:

vector<int> inter;
set_intersection(v1.begin(), v1.end(),
                 v2.begin(), v2.end(),
                 back_inserter(inter));
// inter is "2 4 6"

v1.erase(set_difference(v1.begin(), v1.end(),
                        inter.begin(), inter.end(),
                        v1.begin())
         v1.end());
// v1 is "1 3 5"

v2.erase(set_difference(v2.begin(), v2.end(),
                        inter.begin(), inter.end(),
                        v2.begin())
         v2.end());
// v2 is "8"

Я думаю, что есть гораздо более эффективные решения, но это ясно, и действительно передать ваши намерения с помощью широко известных алгоритмов stl.

Answer 2

В алгоритме заголовка stl есть функция с именем "set_symmetric_difference", которая помещает все элементы одного, но не обоих исходных диапазонов в один целевой диапазон.

Помните, что оба диапазона должны начать сортироваться.

MSDN документация

Answer 3

Начните добавлять значение вектора в Set. Переопределите метод equals для class1 и class2, чтобы решить, как вы хотите, чтобы объект был равен. Если вы не переопределите «равно», по умолчанию == будет использоваться для сравнения, а поскольку объекты другого класса == всегда будут возвращать значение «ложь» Поэтому вам нужно переопределить метод equals.

Answer 4

Для каждой пары элементов в class1a и class1b добавьте их в выходной набор, если они не равны. Иначе, добавьте только один такой экземпляр. Повторите для минимальной длины массивов. Если один длиннее, у вас останется еще немного - попробуйте добавить все это в набор.

Answer 5

Наивный способ - выполнить n ^ 2 итерации, сравнивая каждый элемент в первом векторе с каждым элементом во втором массиве и добавляя любые совпадения к третьему вектору. Когда вы закончите итерацию n ^ 2, вы пройдете третий вектор и удалите эти объекты из первых двух.

Не лучшее решение, но в зависимости от того, насколько велики ожидаемые векторы, оно может быть одним из самых простых.

Answer 6

Сортируйте 2 вектора, а затем пройдитесь по ним параллельно, выполняя обычную операцию слияния. Это скажет вам, какие предметы идентичны.