在数学中,集合是最基本的概念之一。编程时,我们不可避免地会涉及到集合及其相关操作。在 C++ 中,标准模板库(STL)提供了 std::set
/std::unordered_set
两种传统意义上的集合(除此之外,还有 std::multiset
和 std::unordered_multiset
)。其中,std::set
(和 std::multiset
)定义在头文件 set
当中,从 C++98 起就有支持;而 std::unordered_set
(和 std::unordered_multiset
)则定义在头文件 unordered_set
当中,从 C++11 开始支持。
此篇我们讨论如何在 C++ 中集合如何进行交集和并集操作。
std::set
和 std::unordered_set
简介
在 C++ 标准中,std::set
是基于平衡二叉树的(经典的 SGI STL 以红黑树实现),因而是有序的。以恰当的方式,比如以 std::set
的迭代器,遍历,可以得到有序的结果。在 C++ 标准中,std::unordered_set
则是基于哈希表的。因此,遍历 std::unordered_set
得到的顺序是不被保证的。std::unordered_set
的插入、查找、计数等操作的时间复杂度是 O(1)。
如果你更喜欢 hash_set
这个名字,你也可以借助 C++11 的 using
关键字的新功能,将 hash_set
作为 unordered_set
的别名。
因为 std::set
和 std::unordered_set
底层使用了不同的数据结构,它们对外表现出来的性能也不相同。std::set
的插入、查找、计数等操作的时间复杂度是 O(logn)。std::unordered_set
的插入、查找、计数等操作的时间复杂度是 O(1)。因此,在集合中元素的顺序很重要时,可以考虑使用 set::set
来保存元素;当顺序相对不重要,但会反复进行插入、查找等操作时,则应考虑使用 set::unordered_set
。
我们用下面这段代码来演示 std::set
和 std::unordered_set
的用法。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
| #include <iostream> #include <string>
#ifdef HASH_ #include <unordered_set> #else #include <set> #endif
namespace test { #ifdef HASH_ template <typename Key, typename Hash = std::hash<Key>, typename KeyEqual = std::equal_to<Key>, typename Allocator = std::allocator<Key>> using set = std::unordered_set<Key, Hash, KeyEqual, Allocator>; #else template <typename Key, typename Compare = std::less<Key>, typename Allocator = std::allocator<Key>> using set = std::set<Key, Compare, Allocator>; #endif }
int main() { test::set<std::string> set{"Hello", "world", "!"}; set.insert("hello"); set.insert("world"); for (const auto& i : set) { std::cout << i; if ((set.count(i) > 0) == (set.find(i) != set.end())) { std::cout << "\tYES!\n"; } }
return 0; }
|
当定义 HASH_
时,可能的输出为:
1 2 3 4 5 6
| $ g++ -std=c++11 foo.cpp -DHASH_ $ ./a.out hello YES! ! YES! world YES! Hello YES!
|
当不定义 HASH_
时,输出应为:
1 2 3 4 5 6
| $ g++ -std=c++11 foo.cpp $ ./a.out ! YES! Hello YES! hello YES! world YES!
|
不难发现,不论是使用 std::set
还是 std::unordered_set
,重复插入的 "hello"
在集合中都只存在一份;此外,std::set
是有序的,而 std::unordered_set
是无序的。另一方面,我们发现,使用 set.count(i) > 0
和 set.find(i) != set.end()
判断集合中是否存在元素 i
是等价的。
标准库提供的 std::set_intersection
和 std::set_union
标准库提供了 std::set_intersection
和 std::set_union
两个函数,用于对容器内的元素进行集合求交、求并,而后将得到的结果保存在 OutputIt
对应的容器当中。这两个函数定义在头文件 algorithm
当中。
我们用下面这段代码演示这两个函数的用法。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
| #include <iostream> #include <iterator> #include <algorithm>
#ifdef HASH_ #include <unordered_set> #else #include <set> #endif
namespace test { #ifdef HASH_ template <typename Key, typename Hash = std::hash<Key>, typename KeyEqual = std::equal_to<Key>, typename Allocator = std::allocator<Key>> using set = std::unordered_set<Key, Hash, KeyEqual, Allocator>; #else template <typename Key, typename Compare = std::less<Key>, typename Allocator = std::allocator<Key>> using set = std::set<Key, Compare, Allocator>; #endif }
int main() { test::set<int> lhs{1, 2, 3, 4}; test::set<int> rhs{3, 4, 5, 6}; test::set<int> result;
std::set_intersection(lhs.begin(), lhs.end(), rhs.begin(), rhs.end(), std::inserter(result, result.end())); for (const auto& i : result) { std::cout << i << ' '; } std::cout << '\n';
result.clear(); std::set_union(lhs.begin(), lhs.end(), rhs.begin(), rhs.end(), std::inserter(result, result.end())); for (const auto& i : result) { std::cout << i << ' '; } std::cout << '\n';
return 0; }
|
如此一来,我们应有可能的输出:
1 2 3 4 5 6 7 8
| $ g++ -std=c++11 foo.cpp -DHASH_ $ ./a.out
5 6 1 2 3 4 $ g++ -std=c++11 foo.cpp $ ./a.out 3 4 1 2 3 4 5 6
|
不难发现,当使用 std::unordered_set
时,函数 std::set_intersection
工作不正常(std::set_union
恰好看起来正常,实际也不正常)。当使用 std::set
时,由于基于平衡二叉树的集合是有序的,因此两个函数工作正常。
由于 std::set_intersection
和 std::set_union
接受的输入是迭代器;事实上,这两个函数不光能对集合求交集和并集,还能接收任意有序的序列的迭代器并求交集和并集。可见,虽然名字是「集合交集」和「集合并集」,但这两个函数的行为与我们默认的交集和并集的概念并不一致。更有甚者,由于这两个函数要求容器有序,所以不能作用在 std::unoredered_set
类型的对象上。因此,我们可以考虑定义自己的求交、求并函数。
定义自己的求交、求并函数
我们以下面的例子呈现我们自己定义的求交、求并函数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
| #include <iostream>
#ifdef HASH_ #include <unordered_set> #else #include <set> #endif
namespace test { #ifdef HASH_ template <typename Key, typename Hash = std::hash<Key>, typename KeyEqual = std::equal_to<Key>, typename Allocator = std::allocator<Key>> using set = std::unordered_set<Key, Hash, KeyEqual, Allocator>; #else template <typename Key, typename Compare = std::less<Key>, typename Allocator = std::allocator<Key>> using set = std::set<Key, Compare, Allocator>; #endif }
namespace setop { template <typename Set> static inline Set set_union(const Set& lhs, const Set& rhs) { Set uset{lhs}; uset.insert(rhs.begin(), rhs.end()); return std::move(uset); }
template <typename Set, typename Key = typename Set::value_type> static inline Set set_intersection(const Set& lhs, const Set& rhs) { if (lhs.size() <= rhs.size()) { Set iset; for (const Key& key : lhs) { if (rhs.count(key) > 0) { iset.insert(key); } } return std::move(iset); } else { return set_intersection(rhs, lhs); } } }
int main() { test::set<int> lhs{1, 2, 3, 4}; test::set<int> rhs{3, 4, 5, 6};
const auto iset = setop::set_intersection(lhs, rhs); const auto uset = setop::set_union(lhs, rhs);
for (const auto& i : iset) { std::cout << i << ' '; } std::cout << '\n';
for (const auto& i : uset) { std::cout << i << ' '; } std::cout << '\n'; return 0; }
|
如此一来,我们有可能的输出:
1 2 3 4 5 6 7 8
| $ g++ -std=c++11 foo.cpp -DHASH_ $ ./a.out 3 4 5 6 1 2 3 4 $ g++ -std=c++11 foo.cpp $ ./a.out 3 4 1 2 3 4 5 6
|
不难发现,两个函数工作良好。