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

因为 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
#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_ 时,可能的输出为:

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 当中。

我们用下面这段代码演示这两个函数的用法。

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

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

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

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

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

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