set

set简介

文档介绍：set - C++ Reference (cplusplus.com)

set 是按照特定顺序存储不重复元素的容器。

在一个 set 中，一个元素的值也是它的标识（值本身就是 key，类型为 T），并且每个值必须是唯一的。set 中的元素的值不能在容器中被修改（元素是常数），但是可以从容器中插入或删除它们。

在内部，set 中的元素总是按照其内部比较对象（Compare 类型）所指示的严格弱序标准进行排序。

set 容器通过 key 来访问单个元素通常比 unordered_set 容器要慢一些，但是它们允许根据顺序对子集进行直接迭代。

set 底层是用二叉搜索树（红黑树）实现的。

set使用

void test1()
{
	set<int> s;
	s.insert(4);
	s.insert(5);
	s.insert(5);
	s.insert(2);
	s.insert(1);
	s.insert(2);
	s.insert(3);
	for (set<int>::iterator it = s.begin(); it != s.end(); ++it)
	{
		cout << *it << " ";
	}
	cout << endl;
}
//结果：1 2 3 4 5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

可以看到它带有排序+去重的功能。

迭代器：set 的普通迭代器和 const迭代器是一样的，都不支持修改。

查找

void test3()
{
	set<int> s;
	s.insert(4);
	s.insert(5);
	s.insert(5);
	s.insert(2);
	s.insert(1);
	s.insert(2);
	s.insert(3);

	set<int>::iterator pos = s.find(2);
	if (pos != s.end())
	{
		cout << "s.find找到了" << endl;
	}
	pos = find(s.begin(), s.end(), 2);
	if (pos != s.end())
	{
		cout << "find找到了" << endl;
	}
}
//结果：
//s.find找到了
//find找到了
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

set 自带 find 查找，算法库里通用的 find 也可以用。但是这两者的效率差距非常大。

set 自带的 find 会按照二叉搜索树查找规则进行查找，时间复杂度为 $O(\log n)$

库里的 find 是遍历，时间复杂度为 $O(n)$

删除

void test4()
{
	set<int> s;
	s.insert(4);
	s.insert(5);
	s.insert(5);
	s.insert(2);
	s.insert(1);
	s.insert(2);
	s.insert(3);

	int x;
	while (cin >> x)
	{
		set<int>::iterator pos = s.find(x);
		if (pos != s.end())
		{
			s.erase(pos);
			cout << "删除" << x << "成功" << endl;
		}
		else
		{
			cout << x << "不在set中" << endl;
		}
	}
    for (auto e : s)
	{
		cout << e << ' ';
	}
	cout << endl;
}
//1
//删除1成功
//2
//删除2成功
//20
//20不在set中
//^Z
//3 4 5
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

erase 是有返回值的，表示删除数据的个数，对于 set 来说，只有 0 或 1。

---

使用 count 可以方便地查看某个元素在不在：

if (s.count(5))
{
	cout << "5在" << endl;
}
1
2
3
4

---

lower_bound、upper_bound

lower_bound 传入一个值，它会返回容器中，指向大于等于这个值的第一个元素的迭代器。

upper_bound 传入一个值，它会返回容器中，指向大于这个值的第一个元素的迭代器。

利用它们我们可以轻松获得一个迭代器区间：

void test5()
{
	set<int> s;
	s.insert(4);
	s.insert(5);
	s.insert(2);
	s.insert(1);
	s.insert(3);

	int x, y;
	cin >> x >> y;
	set<int>::iterator leftIt = s.lower_bound(x);	//返回>=x的第一个元素的迭代器
	set<int>::iterator rightIt = s.upper_bound(y);	//返回>y的第一个元素的迭代器
	s.erase(leftIt, rightIt);	//范围，[leftIt, rightIt)其实就是[x, y]
	for (auto e : s)
	{
		cout << e << ' ';
	}
	cout << endl;
}
//结果：
//2
//4
//1 5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

---

multiset

multiset 允许插入重复数据，其接口和 set 一样。

值得注意的是：

• multiset 的 erase 会将某个 val 包括与其重复的元素全部删除，最后返回删除个数。

• find 一个有重复数据的 val，会返回中序的第一个 val 元素的迭代器

map

map简介

文档介绍：map - C++ Reference (cplusplus.com)

map 是关联式容器，按照特定的顺序存储由键值（key value）和映射值（mapped value）组合形成的元素。

在一个 map 中，key values 通常用于排序和唯一识别元素，而 mapped values 则存储与此 key 相关的内容。key 和 mapped value 的类型可能不同，在成员类型 value_type 中被组合在一起，它是一个结合两者的 pair 类型：

typedef pair<const Key, T> value_type;
1

在内部，一个 map 中的元素总是按照其内部比较对象（类型为 Compare）所指定的严格弱序标准按其 key 进行排序。

map 容器按 key 访问单个元素的速度通常比 unordered_map 容器要慢，但是它们允许根据顺序对子集进行直接迭代。

map 中的映射值可以使用括号运算符（operator[]）和其相应的键直接访问。

map 底层是用二叉搜索树（红黑树）实现的。

关联式容器

在初阶阶段，我们已经接触过STL中的部分容器，比如：vector、list、deque等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。那什么是关联式容器？它与序列式容器有什么区别？

关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是 结构的键值对，在数据检索时比序列式容器效率更高

键值对

用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量 key 和 value，key 代表键值，value 表示与 key 对应的信息。

SGI-STL 中关于 pair 的定义：

template <class T1, class T2>
struct pair
{
	typedef T1 first_type;
	typedef T2 second_type;
	T1 first;
	T2 second;
	pair() : first(T1()), second(T2())
	{}
	pair(const T1& a, const T2& b) : first(a), second(b)
	{}
};
1
2
3
4
5
6
7
8
9
10
11
12

你可以使用构造函数创建 pair 对象：

pair<string, string> kv("banana", "香蕉");
1

也可以使用函数模板 make_pair：

auto kv = make_pair("cherry", "樱桃");
1

因为 make_pair 是函数模板，所以它能自动推导键值和映射值的类型，它的定义如下：

template <class T1,class T2>
pair<T1,T2> make_pair (T1 x, T2 y)
{
    return ( pair<T1,T2>(x,y) );
}
1
2
3
4
5

map使用

插入

关于插入，有以下四种方式：

void test6()
{
	map<string, string> dict;

	dict.insert(pair<string, string>("apple", "苹果"));	//匿名对象

	pair<string, string> kv("banana", "香蕉");	//普通对象
	dict.insert(kv);

	dict.insert(make_pair("cherry", "樱桃"));	//make_pair

	dict.insert({ "pear", "梨" });	//C++11
}
1
2
3
4
5
6
7
8
9
10
11
12
13

第四种是C++11的方法，其原理涉及到C++11的新特性，具体会在以后讲解。

遍历

键值对是不支持直接打印的，但是我们可以直接访问里面的 first 和 second 成员变量：

for (auto it = dict.begin(); it != dict.end(); ++it)
{
    cout << it->first << " : " << it->second << endl;
}
//结果：
//apple : 苹果
//banana : 香蕉
//cherry : 樱桃
//pear : 梨
1
2
3
4
5
6
7
8
9

简单使用：

统计水果出现的次数

void test7()
{
	string str[] = { "苹果","橘子","香蕉","香蕉", "苹果","西瓜","苹果","梨","苹果","梨","苹果","橘子","苹果","香蕉" };
	map<string, int> countMap;
	for (auto& str : str)
	{
		auto it = countMap.find(str); //通过find来判断map中是否已经有了这个水果
		if (it != countMap.end())
		{
			++it->second;
		}
		else
		{
			countMap.insert(make_pair(str, 1));
		}
	}
	for (const auto& kv : countMap)
	{
		cout << kv.first << " : " << kv.second << endl;
	}
}
//结果：
//梨: 2
//苹果 : 6
//西瓜 : 1
//香蕉 : 3
//橘子 : 2
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

这段程序可以优化：

insert 函数原型：

pair<iterator,bool> insert (const value_type& val);
1

它会返回一个键值对，该键值对的 first 是一个迭代器，指向新插入的元素或 map 中与 val 相等 key 的一个元素。second 是一个 bool 值，true 表示成功插入新元素 val，false 表示 map 中已经存在和 val 相等 key 的元素，插入失败。

优化后：

void test7()
{
	string str[] = { "苹果","橘子","香蕉","香蕉", "苹果","西瓜","苹果","梨","苹果","梨","苹果","橘子","苹果","香蕉" };
	map<string, int> countMap;
	for (auto& str : str)
	{
		auto ret = countMap.insert(make_pair(str, 1));
		if (!ret.second)
		{
			++ret.first->second;
		}
	}
	for (const auto& kv : countMap)
	{
		cout << kv.first << " : " << kv.second << endl;
	}
}
//结果：
//梨: 2
//苹果 : 6
//西瓜 : 1
//香蕉 : 3
//橘子 : 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

但这还不是最优秀的方式，最优秀的应该是用[]：

void test7()
{
	string str[] = { "苹果","橘子","香蕉","香蕉", "苹果","西瓜","苹果","梨","苹果","梨","苹果","橘子","苹果","香蕉" };
	map<string, int> countMap;
	for (auto& str : str)
	{
		++countMap[str];
	}
	for (const auto& kv : countMap)
	{
		cout << kv.first << " : " << kv.second << endl;
	}
}
//结果：
//梨: 2
//苹果 : 6
//西瓜 : 1
//香蕉 : 3
//橘子 : 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

map::operator[]

mapped_type& operator[] (const key_type& k);
1

如果 k 与容器中的一个元素的键相匹配，该函数返回对其映射值的引用。

如果 k 与容器中任何元素的键都不匹配，该函数将插入一个带有该键的新元素，并返回一个对其映射值的引用。请注意，即使没有给元素分配映射值，这也会使容器的大小增加一（元素是用其默认构造函数构造的）。

类似的成员函数，map::at，在有键的元素存在时有同样的行为，但在没有的时候抛出一个异常。

调用此函数相当于：

(*((this->insert(make_pair(k,mapped_type()))).first)).second
1

最后这一行代码可以说是很难看了，我们有必要对其分解后再理解：

mapped_type& operator[] (const key_type& k)
{
	// 原代码：
	//return (*((this->insert(make_pair(k, mapped_type()))).first)).second; 
	// 
	// 去掉显式的this指针：
	//return (*((insert(make_pair(k, mapped_type()))).first)).second; 
	//
	// 将insert函数调用提取出来，接收返回值ret：
	//pair ret = insert(make_pair(k, mapped_type())); 
	//return (*(ret.first)).second;
	// 
	// 对return返回值进行简化：
	pair<iterator, bool> ret = insert(make_pair(k, mapped_type()));
	return ret.first->second;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

mapped_type() 就是一个匿名对象，类似于我们之前写的 T()，这里相当于给元素的映射值进行了初始化。

对于 ret，有两种情况：

1. 如果容器中没有 key 为 k 的元素，则插入成功，ret.first 指向新插入的元素，ret.second 为 true
2. 容器中已有 key 为 k 的元素，则插入失败，ret.first 指向已有的元素，ret.second 为 false

ret.first->second 则是新元素或已有元素的映射值

所以方括号运算符重载的底层就是复用了 insert，统计水果代码第二次优化前后底层逻辑本质上是一样的。

multimap

multimap 允许键值重复的元素存在。

multimap 使用 insert 返回类型是 iterator ，连 bool 都没有，因为它永远是插入成功的。

multimap 不支持使用 [] 访问，因为同一个键可能有多个映射值，无法区分。