Установить разницу в C ++

Question

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

ех. КОД ПСЕВДО

> set<int> set1 = {1 2 3 4 5 6 7 8 9 10}
> set<int> set2 = {5 6 7}

Я хочу вычесть set2 из set1:

Ответ здесь будет

{1 2 3 4 8 9 10}

Answer 1

Использование std::set_difference найдено в <algorithm>:

#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()));

Источник фрагмента

Answer 2

Я бы использовал std::set_difference, который работает за O (n) время.

Answer 3

Я знаю, что вы спрашивали о решении C ++, но если кто-то придет сюда в поисках решения Haskell:

import Data.Set ((\\), fromList)

main = do
    let s1 = fromList [1,2,3,4,5,6,7,8,9,10]
    let s2 = fromList [5,6,7]
    print $ s1 \\ s2

Результаты: [1, 2, 3, 4, 8, 9, 10]

Answer 4

Вы можете использовать функцию std::set_difference.

выходной диапазон содержит копию каждый элемент, который содержится в [first1, last1) и не содержится в [first2, last2).

Answer 5

set_symmetric_difference