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

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

ех. PSEUDO CODE

> 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}

Ответы

Ответ 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()));

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

Ответ 2

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

Ответ 3

Я знаю, что вы попросили решение на С++, но если кто-то ищет здесь решение 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]

Ответ 4

Вы можете использовать std::set_difference.

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