KJHの博客

记录&回忆

0%

STLset和multiset

发表于 更新于 分类于
本文字数： 7.3k 阅读时长 ≈ 7 分钟

标准的STL关联式容器分为set（集合）和map（映射表）两大类，以及两大类的衍生体multiset（多键集合）和multimap（多键映射表）（还有一些不在标准规格之列的关联式容器）。这些容器的底层机制均以RB-tree（红黑树）完成。

一、set

set 的特性是，所有元素都会根据元素的键值自动被排序，set 只拥有一个元素，它的键值就是实值，实值就是键值，并且set 不允许两个元素有相同的键值。

由于，set 元素值就是其键值，关系到 set 元素的排列规则，所以我们不能通过set 的迭代器来改变set 的元素值。标准的STL set 是以RB-tree 为底层机制，几乎所有的 set 操作行为，都只是转调用 RB-tree 的操作行为而已。

下面我们来看看 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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
class set {
public:
	// typedefs:
	typedef Key key_type;
	typedef Key value_type;
	typedef Compare key_compare;
	typedef Compare value_compare;
private:
	typedef rb_tree<key_type, value_type,
		identity<value_type>, key_compare, Alloc> rep_type;    //typedef RB-tree 类型
	rep_type t;  // 定义一棵红黑树t，也是set的唯一私有成员，set内部的元素皆存放于此
public:
	/*鉴于set特性，不允许修改其元素值，所以迭代器类型被定义为底层RB-tree的const_iterator*/
	typedef rep_type::const_pointer pointer;
	typedef rep_type::const_reference reference;
	typedef rep_type::const_reference const_reference;
	typedef rep_type::const_iterator iterator;
	typedef rep_type::const_iterator const_iterator;
	typedef rep_type::const_reverse_iterator reverse_iterator;
	typedef rep_type::const_reverse_iterator const_reverse_iterator;
	typedef rep_type::size_type size_type;
	typedef rep_type::difference_type difference_type;
	// allocation/deallocation
	/*构造函数*/
	set() : t(Compare()) {}
	explicit set(const Compare& comp) : t(comp) {}
#ifdef __STL_MEMBER_TEMPLATES
	template <class InputIterator>
	set(InputIterator first, InputIterator last)
		: t(Compare()) {
		t.insert_unique(first, last);
	}
	template <class InputIterator>
	set(InputIterator first, InputIterator last, const Compare& comp)
		: t(comp) {
		t.insert_unique(first, last);
	}
#else
	/*将[first,end)之间的元素插入set中*/
	set(const value_type* first, const value_type* last)
		: t(Compare()) {
		t.insert_unique(first, last);
	}
	set(const value_type* first, const value_type* last, const Compare& comp)
		: t(comp) {
		t.insert_unique(first, last);
	}
	set(const_iterator first, const_iterator last)
		: t(Compare()) {
		t.insert_unique(first, last);
	}
	set(const_iterator first, const_iterator last, const Compare& comp)
		: t(comp) {
		t.insert_unique(first, last);
	}
#endif /* __STL_MEMBER_TEMPLATES */
	//赋值运算符重载
	set(const set<Key, Compare, Alloc>& x) : t(x.t) {}
	set<Key, Compare, Alloc>& operator=(const set<Key, Compare, Alloc>& x) {
		t = x.t; //直接调用RB-tree的赋值操作函数
		return *this;
	}
	// accessors:
	/*实值，键值都是同一元素值*/
	key_compare key_comp() const { return t.key_comp(); }
	value_compare value_comp() const { return t.key_comp(); }
	/*下面的接口函数都是调用RB-tree的*/
	iterator begin() const { return t.begin(); }
	iterator end() const { return t.end(); }
	reverse_iterator rbegin() const { return t.rbegin(); }
	reverse_iterator rend() const { return t.rend(); }
	bool empty() const { return t.empty(); }
	size_type size() const { return t.size(); }
	size_type max_size() const { return t.max_size(); }
	void swap(set<Key, Compare, Alloc>& x) { t.swap(x.t); }
	// insert/erase
	typedef  pair<iterator, bool> pair_iterator_bool;
	/*插入一个元素值，返回pair类型（分别是插入元素的迭代器和是否插入成功）*/
	pair<iterator, bool> insert(const value_type& x) 
	{
		//RB-tree的insert_unique()返回一个pair类型
		pair<rep_type::iterator, bool> p = t.insert_unique(x);//调用RB-tree的插入函数(自动排序)
		return pair<iterator, bool>(p.first, p.second);
	}
	/*从position开始寻找一个可以插入值为x 的元素的位置将其插入并返回其迭代器*/
	//set(RB_tree)内部元素是自动排序，均不能在指定位置插入元素(或替换元素)
	iterator insert(iterator position, const value_type& x) 
	{
		return t.insert_unique((rep_type::iterator&)position, x);
	}
#ifdef __STL_MEMBER_TEMPLATES
	template <class InputIterator>
	void insert(InputIterator first, InputIterator last) {
		t.insert_unique(first, last);
	}
#else
	void insert(const_iterator first, const_iterator last) {
		t.insert_unique(first, last);
	}
	void insert(const value_type* first, const value_type* last) {
		t.insert_unique(first, last);
	}
#endif /* __STL_MEMBER_TEMPLATES */
	/*删除迭代器position所指元素*/
	void erase(iterator position)
	{
		t.erase((rep_type::iterator&)position);
	}
	/*删除key值为x的元素并返回被删除元素的个数*/
	size_type erase(const key_type& x) 
	{
		return t.erase(x);
	}
	/*删除[first，end)之间的元素*/
	void erase(iterator first, iterator last) 
	{
		t.erase((rep_type::iterator&)first, (rep_type::iterator&)last);
	}
	/*清空容器*/
	void clear() { t.clear(); }
	// set operations:
	iterator find(const key_type& x) const { return t.find(x); }
	size_type count(const key_type& x) const { return t.count(x); }//统计元素值为 x的个数
	/*返回一个迭代器，指向键值>=key的第一个元素*/
	iterator lower_bound(const key_type& x) const
	{
		return t.lower_bound(x);
	}
	/*返回一个迭代器，指向键值>key的第一个元素*/
	iterator upper_bound(const key_type& x) const {
		return t.upper_bound(x);
	}
	//查找键值等于x 的元素，返回pair
	pair<iterator, iterator> equal_range(const key_type& x) const 
	{
		return t.equal_range(x);

	}
	friend bool operator==(const set&, const set&);
	friend bool operator<(const set&, const set&);
};
/*调用RB-tree底层机制*/
template <class Key, class Compare, class Alloc>
inline bool operator==(const set<Key, Compare, Alloc>& x,
	const set<Key, Compare, Alloc>& y) {
	return x.t == y.t;
}
template <class Key, class Compare, class Alloc>
inline bool operator<(const set<Key, Compare, Alloc>& x,
	const set<Key, Compare, Alloc>& y) {
	return x.t < y.t;
}

set 包括下面将提到的multiset 其内部结构都是RB-tree，元素的存储以及相应操作都是引用Rb-tree的操作行为。set和multiset 内部元素都是自动排序的，这就意味着set和multiset 不提供用来直接存取元素的任何操作函数。另外对于迭代器而言，所有元素都被视为常数，这保证了不会人为的改变元素值，从而打乱既定排序。如果一定要改变元素值，必须先删除指定元素值，然后再重新插入新元素。

二、multiset

multiset 的特性以及用法和 set 完全相同，唯一的差别在于它允许键值重复，因此它的插入操作采用的是底层机制RB-tree 的insert_equal() 而非set 采用的 insert_unique()。

从上面的源代码可以看出，set 和 multiset 的操作函数都是转而去调用RB-tree的操作函数，其具体实现都在RB-tree中。

我们知道了set 和multiset 的内部结构是RB-tree（存储方式） ，有利于我们更好的把握这两个关联式容器的函数操作。

set 的 multiset 的区别

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
#include <iostream>
#include <set>
using namespace std;

int main()
{
	int i;
	int ia[] = { 0, 1, 2, 3, 4 };
	set<int> iset(ia, ia + 5);//set的构造函数
	multiset<int> imset(ia, ia + 5);
	cout << "iset size = " << iset.size() << endl;//iset size = 5
	cout << "iset 3 count = " << iset.count(3) << endl;//iset 3 count = 1
	iset.insert(3);
	cout << "iset size = " << iset.size() << endl;//iset size = 5
	cout << "iset 3 count = " << iset.count(3) << endl;//iset 3 count = 1
    imset.insert(3);
	cout << "imset size = " << imset.size() << endl;//imset size = 6
	cout << "imset 3 count = " << imset.count(3) << endl;//imset 3 count = 2
	/*面对关联式容器，应该使用其所提供的find函数来搜寻元素*/
	set<int>::iterator iter;
	iter = iset.find(3);
	if (iter != iset.end())
		cout << "3 found" << endl;
	//*iter = 4; error，不能修改元素值
}

multiset 应用案例：最小的k个数（适合海量数据处理）

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
#include <iostream> 
#include <set>
using namespace std;

int main()
{
	int m, k;
	int val;
	cin >> m >> k;
	multiset<int> mset;
	multiset<int>::iterator iter;
	for (int i = 0; i < m; ++i)
	{
		cin >> val;
		if (mset.size() < k)
		{
			mset.insert(val);
		}
		else
		{
			/*求最大的k个数，只需修改下面的迭代器和后面的if判断语句即可*/
			iter = --mset.end();
			if (*iter > val)
			{
				mset.erase(*iter);
				mset.insert(val);
			}
		}
	}
	iter = mset.begin();
	for (int i = 0; i < k; ++i)
	{
		cout << *(iter++) << endl;
	}
	return 0;
}