С++ STL установить разницу

Ответ 1

Да, есть, он находится в <algorithm> и называется: std::set_difference. Использование:

#include <algorithm>
#include <set>
#include <iterator>
// ...
std::set<int> s1, s2;
// Fill in s1 and s2 with values
std::set<int> result;
std::set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(),
    std::inserter(result, result.end()));

В конце, набор result будет содержать s1-s2.

Ответ 2

Да, в заголовке алгоритмов есть функция set_difference.

редактирует:

FYI, структура данных набора может эффективно использовать этот алгоритм, как указано в его документации. Алгоритм также работает не только по наборам, но и по любой паре итераторов по отсортированным наборам.

Как уже упоминалось, это внешний алгоритм, а не метод. Предположительно, это хорошо для вашего приложения.

Ответ 3

Не является "оператором" в смысле языка, но в стандартной библиотеке есть алгоритм set_difference:

http://www.cplusplus.com/reference/algorithm/set_difference.html

Конечно, присутствуют и другие операции с базовыми множествами - (объединение и т.д.), как было предложено в разделе "См. также" в конце связанной статьи.

Ответ 4

Выбранный ответ правильный, но имеет некоторые синтаксические ошибки.

Вместо

#include <algorithms>

использование

#include <algorithm>

Вместо

std::insert_iterator(result, result.end()));

использование

std::insert_iterator<set<int> >(result, result.end()));

Ответ 5

Не как метод, а там функция внешнего алгоритма set_difference

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1,
                              InputIterator2 first2, InputIterator2 last2,
                              OutputIterator result);

http://www.sgi.com/tech/stl/set_difference.html

Ответ 6

По-видимому, это так.

SGI - set_difference

Ответ 7

Вновь повышаем уровень спасения:

#include <string>
#include <set>
#include <boost/range/algorithm/set_algorithm.hpp>

std::set<std::string> set0, set1, setDifference;
boost::set_difference(set0, set1, std::inserter(setDifference, setDifference.begin());

setDifference будет содержать set0-set1.

Ответ 8

C++ не определяет оператор разницы набора, но вы можете определить свой собственный (используя код, указанный в других ответах):

template<class T>
set<T> operator -(set<T> reference, set<T> items_to_remove)
{
    set<T> result;
    std::set_difference(
        reference.begin(), reference.end(),
        items_to_remove.begin(), items_to_remove.end(),
        std::inserter(result, result.end()));
    return result;
}

Ответ 9

Все ответы, которые я вижу здесь, O (n). Разве это не было бы лучше?:

template <class Key, class Compare, class Allocator>   
std::set<Key, Compare, Allocator> 
set_subtract(std::set<Key, Compare, Allocator>&& lhs,
             const std::set<Key, Compare, Allocator>& rhs) {
    if (lhs.empty()) { return lhs; }
    // First narrow down the overlapping range:
    const auto rhsbeg = rhs.lower_bound(*lhs.begin());
    const auto rhsend = rhs.upper_bound(*lhs.rbegin());
    for (auto i = rhsbeg; i != rhsend; ++i) {
        lhs.erase(*i);
    }
    return std::move(lhs);
}

Кажется, это правильно. Я не уверен, как справиться со случаем, когда тип Compare не полностью определяет его поведение, как в случае, если Compare является std::function<bool(int,int)>, но помимо этого, это, кажется, работает правильно и должно быть как O ((перекрытие номеров) • log (lhs.size())).

В случае, если lhs не содержит *i, вероятно, можно дополнительно оптимизировать, выполняя O (log (rhs.size())) поиск следующего элемента в rhs, который> = следующий элемент в lhs. Это позволило бы оптимизировать случай, когда lhs = {0, 1000} и rhs = {1, 2, ..., 999} выполняют вычитание во время регистрации.

Ответ 10

можем ли мы использовать

 set_difference(set1.begin(), set1.end(), set2.begin(). set2,end(),std::back_inserter(result)).