C++ 中集合及其交集和并集
在数学中，集合是最基本的概念之一。编程时，我们不可避免地会涉及到集合及其相关操作。在 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 的用法。
#include <iostream>
#include <string>
#ifdef HASH_
#include <unordered_set>
#else // HASH_
#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 // HASH_
template <typename Key,
typename Compare = std::less<Key>,
typename Allocator = std::allocator<Key>>
using set = std::set<Key, Compare, Allocator>;
#endif // HASH_
} // namespace test
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_ 时，可能的输出为：
$ g++ -std=c++11 foo.cpp -DHASH_
$ ./a.out
hello YES!
! YES!
world YES!
Hello YES!
当不定义 HASH_ 时，输出应为：
$ 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 当中。
我们用下面这段代码演示这两个函数的用法。
#include <iostream>
#include <iterator>
#include <algorithm>
#ifdef HASH_
#include <unordered_set>
#else // HASH_
#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 // HASH_
template <typename Key,
typename Compare = std::less<Key>,
typename Allocator = std::allocator<Key>>
using set = std::set<Key, Compare, Allocator>;
#endif // HASH_
} // namespace test
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;
}
如此一来，我们应有可能的输出：
$ 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 类型的对象上。因此，我们可以考虑定义自己的求交、求并函数。
定义自己的求交、求并函数
我们以下面的例子呈现我们自己定义的求交、求并函数。
#include <iostream>
#ifdef HASH_
#include <unordered_set>
#else // HASH_
#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 // HASH_
template <typename Key, typename Compare = std::less<Key>,
typename Allocator = std::allocator<Key>>
using set = std::set<Key, Compare, Allocator>;
#endif // HASH_
} // namespace test
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);
}
}
} // namespace setop
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;
}
如此一来，我们有可能的输出：
$ 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
不难发现，两个函数工作良好。