Если я знаю, что один набор является подмножеством другого набора, и я хотел бы найти разницу, какой наиболее эффективный способ сделать это?
ех. 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}
Используйте 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()));
Я бы использовал std::set_difference, который работает в O (n) времени.
Я знаю, что вы попросили решение на С++, но если кто-то ищет здесь решение 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]
Вы можете использовать std::set_difference.
выходной диапазон содержит копию каждый элемент, содержащийся в [first1, last1) и не содержится в [first2, last2).