0%

谈谈 C++ 中集合的交集和并集

在数学中,集合是最基本的概念之一。编程时,我们不可避免地会涉及到集合及其相关操作。在 C++ 中,标准模板库(STL)提供了 std::set/std::unordered_set 两种传统意义上的集合(除此之外,还有 std::multisetstd::unordered_multiset)。其中,std::set(和 std::multiset)定义在头文件 set 当中,从 C++98 起就有支持;而 std::unordered_set(和 std::unordered_multiset)则定义在头文件 unordered_set 当中,从 C++11 开始支持。

此篇我们讨论如何在 C++ 中进行集合的交集和并集操作。

std::setstd::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 的别名。

1
2
3
4
5
6
7
8
#include <unordered_set>
namespace std {
template <typename Key,
typename Hash = std::hash<Key>,
typename KeyEqual = std::equal_to<Key>,
typename Allocator = std::allocator<Key>>
using hash_set = unordered_set<Key, Hash, KeyEqual, Allocator>;
} // namespace std

之后,就能像使用 std::unordered_set 那样使用 std::hash_set 了。

因为 std::setstd::unordered_set 底层使用了不同的数据结构,它们对外表现出来的性能也不相同。std::set 的插入、查找、计数等操作的时间复杂度是 $O(\log n)$。std::unordered_set 的插入、查找、计数等操作的时间复杂度是 $O(1)$。因此,在集合中元素的顺序很重要时,可以考虑使用 set::set 来保存元素;当顺序相对不重要,但会反复进行插入、查找等操作时,则应考虑使用 set::unordered_set

我们用下面这段代码来演示 std::setstd::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
38
#include <iostream>
#include <string>

#ifdef HASH_ // 1.
#include <unordered_set>
#else // HASH_
#include <set>
#endif

namespace test {
#ifdef HASH_ // 1.
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", "!"}; // 2.
set.insert("hello"); // 3.
set.insert("world"); // 4.

for (const auto& i : set) {
std::cout << i; // 5.
if ((set.count(i) > 0) == (set.find(i) != set.end())) { // 6.
std::cout << "\tYES!\n";
}
}

return 0;
}

(1) 利用预处理器,在 HASH_ 有定义时,加载 unordered_set 头文件,并将 test::set 作为 std::unordered_set 的等价类型;否则,加载 set 头文件,并将 test::set 作为 std::set 的等价类型。(2) 声明并定义了名为 set 的变量,其中包含 "Hello"/"world"/"!" 三个元素。注意,这里的 set 不带名字空间前缀,因而不会与 std::set 或者 test::set 冲突。(3) 和 (4) 处分别将 "hello""world" 插入 set。(5) 在按迭代器顺序遍历集合。(6) 则给出了查询元素是否属于集合的两种等价方式。

当定义 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) > 0set.find(i) != set.end() 判断集合中是否存在元素 i 是等价的。

标准库提供的 std::set_intersectionstd::set_union

标准库提供了 std::set_intersectionstd::set_union 两个函数,用于对容器内的元素进行集合求交、求并,而后将得到的结果保存在 OutputIt 对应的容器当中。这两个函数定义在头文件 algorithm 当中。

不过,这两个函数都要求原始集合是排序的。因此,我们无法将这两个函数直接运用在 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
38
39
40
41
42
43
44
45
46
47
48
49
50
#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}; // 1.
test::set<int> rhs{3, 4, 5, 6}; // 2.

test::set<int> result;

std::set_intersection(lhs.begin(), lhs.end(), // 3.
rhs.begin(), rhs.end(), // 4.
std::inserter(result, result.end())); // 5.
for (const auto& i : result) {
std::cout << i << ' ';
}
std::cout << '\n';

result.clear();
std::set_union(lhs.begin(), lhs.end(), // 6.
rhs.begin(), rhs.end(), // 7.
std::inserter(result, result.end())); // 8.
for (const auto& i : result) {
std::cout << i << ' ';
}
std::cout << '\n';

return 0;
}

(1) 和 (2) 声明并定义了两个 test::set<int> 类的对象:lhsrhs。在 (3) 处,我们向 std::set_intersection 传入了 lhs 的首末位置迭代器;在 (4) 处,我们向函数传入了 rhs 的首末位置迭代器;在 (5) 处,我们向函数传入了 result 的输出迭代器。随后,我们在 (6)(7)(8) 处做了类似的事情,不过是把函数 std::set_intersection 替换成了 std::set_union

如此一来,我们应有可能的输出:

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_intersectionstd::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
64
65
66
67
#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> // 1.
static inline Set
set_union(const Set& lhs, const Set& rhs) {
Set uset{lhs}; // 2.
uset.insert(rhs.begin(), rhs.end()); // 3.
return std::move(uset); // 4.
}

template <typename Set, typename Key = typename Set::value_type> // 5.
static inline Set
set_intersection(const Set& lhs, const Set& rhs) {
if (lhs.size() <= rhs.size()) { // 6.
Set iset;
for (const Key& key : lhs) {
if (rhs.count(key) > 0) { // 7.
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); // 8.
const auto uset = setop::set_union(lhs, rhs); // 9.

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) 和 (5) 表明,setop::set_unionsetop::set_intersection 都是函数模板,可以接受任何符合要求的容器。其中,在 (5) 的模板声明中,我们使用了 typename Set::value_type 这样的语法。这是因为,对于编译器来说,它并不知道 Set::value_type 是一个类型还是 Set 这个名字空间地下的名为 value_type;此处我们明确地告诉编译器,它应当是一个类型名。

在 (2) 处,我们通过 Set 的拷贝构造函数,将 lhs 中的元素全都拷贝到 uset 当中。这样一来,uset 当中就包含了 lhs 中的所有元素。在 (3) 处,我们通过 insert 函数,将 rhs 的全部元素依次插入到 uset 当中。这样一来,uset 当中也包含了 rhs 中的所有元素。因此,此时它是 lhsrhs 的并集;我们在 (4) 处将 uset 返回。值得一提的是,为了避免可能的额外拷贝(返回值拷贝),我们明确使用了 std::moveuset 作为右值返回。不过,即使不这么写,现代编译器也会优化这一拷贝过程。

(6) 比较了 lhsrhs 的大小。这里使用 <= 而不使用 <,是为了避免两个集合元素个数相同时无限递归。(7) 处使用了 rhs.count(key) > 0 的方式,验证 key 是否在 rhs 这一集合当中。显然,它比使用 find 然后与 rhs.end() 进行比较来得自然。

如此一来,我们有可能的输出:

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

不难发现,两个函数工作良好。

俗话说,投资效率是最好的投资。 如果您感觉我的文章质量不错,读后收获很大,预计能为您提高 10% 的工作效率,不妨小额捐助我一下,让我有动力继续写出更多好文章。