🌈前言

本篇文章进行C++STL中set和map的学习！！！

🌷1、关联式容器

🌹1.1、概念

概念：

1. 我们前面学习的vector、list、deque，还有C++11新增的forward_list都是序列式容器，因为它们底层都是线性序列的结构，里面存储的元素本身
2. 关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是结构的键值对，在数据检索时比序列式容器效率更高

---

🌺1.2、键值对

概念：

• 用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息
• 比如：我们要存储一个汉字，而汉字有对应的英文拼音，这时就可以使用键对值，可以通过汉字找到其对应的英文拼音

SGI-STL中关于键值对的定义：

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

注意：我们不需要自己实现，了解就好，标准库中已经对其实现

---

🎡1.3、树形结构的关联式容器

概念：

• 根据应用场景的不同，STL总共实现了两种不同结构的管理式容器：“树型结构与哈希结构”
• 树型结构的关联式容器主要有四种：map、set、multimap、multiset
• 它们共同特点是：使用平衡搜索树(即红黑树)作为其底层结果，容器中的元素是一个有序的序列

---

🎡2、set

🎨2.1、set的介绍

【set的文档】

概念：

1. set是按照一定次序（根据先后排序）来存储元素的容器
2. 在set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的
3. set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们
4. set在底层是用二叉搜索树(红黑树)实现的

特点：

1. 与map不同，map中存储的是真正的键值对，set中只放value，但在底层实际存放的是由构成的键值对
2. set中插入元素时，只需要插入value即可，不需要构造键值对
3. set中的元素不可以重复(因此可以使用set进行去重)
4. 使用set的迭代器遍历set中的元素，可以得到有序序列
5. set中的元素默认按照小于（默认仿函数：less< T >）来比较
6. set中查找某个元素，时间复杂度为：O（long₂ⁿ）
7. set中的元素不允许修改，因为它存储的vale是关键字也是值，关键字被const修饰

---

🎪2.2、set的使用

• set的模板参数列表：

template < class T,                        // set::key_type/value_type
           class Compare = less<T>,        // set::key_compare/value_compare
           class Alloc = allocator<T>      // set::allocator_type
           > class set;
1
2
3
4

注意：

1. T：set中存放元素的类型，实际在底层存储的键值对
2. Compare：set中元素默认按照小于来比较，默认为仿函数的less
3. Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理

---

• set的构造函数：–【constructor】–

void Testset()
{
	int Array[] = { 1, 2, 3 ,4, 5 };
	set<int> s1;
	set<int> s2(Array, Array + sizeof(Array) / sizeof(int));
	set<int> s3;
	s3 = s2;
}
1
2
3
4
5
6
7
8

---

• set的迭代器：

注：这里就不演示迭代器了，与前面的序列式容器使用方法一样

---

• set的容量

---

• set的修改

template <typename T>
void Show(set<T>& s)
{
	typename set<T>::iterator It = s.begin();
	while (It != s.end()) {
		cout << *It << ' ';
		++It;
	}
	cout << endl;
}

void Testset2()
{
	set<int> s;
	for (int i = 1; i <= 5; ++i) {
		s.insert(i);
	}
	Show(s);

	int x;
	while (cin >> x) {
		if (s.empty()) break;
		set<int>::iterator Pos = s.find(x);
		if (Pos != s.end())
		{
			s.erase(Pos);
			Show(s);
			cout << "删除" << x << "成功！！！" << endl;
		}
		else {
			cout << "删除" << x << "失败！！！" << endl;

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

---

🎳3、multiset

🕃3.1、multiset的介绍

【mulriset文档介绍】
概念：

1. multiset是按照特定顺序存储元素的容器，其中元素是可以重复的
2. 在multiset中，元素的value也会识别它(因为multiset中本身存储的就是组成
   的键值对，因此value本身就是key，key就是value，类型为T)
3. multiset元素的值不能在容器中进行修改(因为元素总是const的)，但可以从容器中插入或删除
4. set在底层是用二叉搜索树(红黑树)实现的

特点：

1. multiset的底层中存储的是的键值对
2. mtltiset的插入接口中只需要插入即可
3. 与set的区别是，multiset中的元素可以重复，set是中value是唯一的
4. 使用迭代器对multiset中的元素进行遍历，可以得到有序的序列
5. multiset中的元素不能修改
6. 在multiset中找某个元素，时间复杂度为O（long₂ⁿ）
7. multiset的作用：可以对元素进行排序

---

🕃3.2、multiset的使用

multiset的接口与set一样，主要区别是multiset的插入可以"数据冗余"，并且不能"去重"

template <typename T>
void Show(multiset<T>& s)
{
	typename multiset<T>::iterator It = s.begin();
	while (It != s.end()) {
		cout << *It << ' ';
		++It;
	}
	cout << endl;
}

void Testmultiset()
{
	multiset<int> ms;
	ms.insert(5);
	ms.insert(3);
	ms.insert(4);
	ms.insert(1);
	ms.insert(1);
	ms.insert(2);
	ms.insert(1);
	Show(ms);

	cout << ms.erase(1) << endl; // 删除了三个1，erase返回删除的数量
	cout << ms.count(1) << endl; // 查找1在ms中的个数
	Show(ms);
}
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

---

🎡4、map

🌚4.1、map的介绍

【map文档介绍】
概念：

1. map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素
2. 在map中，键值key通常用于排序和惟一的标识元素，而值value中存储与此键值key关联的内容键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型
   value_type绑定在一起，为其取别名称为pair

typedef pair<const key, T> value_type
1

3. 在内部，map中的元素总是按照键值key进行比较排序的。
4. map支持下标访问符，即在[]中放入key，就可以找到与key对应的value
5. map通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))

---

🌒4.2、map的介绍

• map的模板参数说明

template < class Key,                                     // map::key_type
           class T,                                       // map::mapped_type
           class Compare = less<Key>,                     // map::key_compare
           class Alloc = allocator<pair<const Key,T> >    // map::allocator_type
           > class map;
1
2
3
4
5

1. key: 键值对中key的类型
2. T： 键值对中value的类型
3. Alloc：通过空间配置器来申请底层空间，不需要用户传递
4. Compare: 比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比较，一般情况下(内置类型元素)该参数不需要传递，如果无法比较时(自定义类型)，需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)

---

• map的构造：【constructor】

void Testmap()
	{
		// 构造空的map
		map<int, int> m1;
		m1[1] = 2;
		m1[2] = 3;

		// 通过区间迭代器来构造
		map<int, int> m2(m1.begin(), m1.end());
		// 拷贝构造
		map<int, int> m3(m2);
	}
1
2
3
4
5
6
7
8
9
10
11
12

---

• map的迭代器

注：这里就不演示迭代器了，与前面的序列式容器使用方法一样

---

• map的容量与元素访问 – Capacity

问题：当key不在map中时，通过operator获取对应value时会发生什么问题？

• 在元素访问时，有一个与operator[]类似的操作at()(该函数不常用)函数，都是通过key找到与key对应的value然后返回其引用，
• 不同的是：当key不存在时，operator[]用默认value与key构造键值对然后插入，返回该默认value，at()函数直接抛异常。

例子：

void Testmap1()
{
	string Fruit[]{ "苹果", "雪梨", "栗子", "香蕉", "苹果", "苹果", "雪梨", "苹果", "栗子" };
	map<string, int> CountF;
	
	for (const auto& e : Fruit)
	{
		//auto ret = CountF.insert(make_pair(e, 1));
		//map::iterator It = CountF.begin();
		 如果ret的bool为false，说明遇到相同的key，让second自增
		//if (ret.second == false) {
		//	++ret.first->second; // 访问ret的iterator中的value且自增
		//}
		//++It;

		++CountF[e]; // 如果e不存在则直接初始化(调用inset)，已存在则跳过，直接返回iterator->second
	}
	Show(CountF);
}

void Testmap2()
{
	map<string, string> dict;
	// insert返回值为pair -- 第一个类型参数为map的迭代器，第二个为bool类型(判断是否存在(数据冗余)，不存在为true，存在为false)
	pair<map<string, string>::iterator, bool> ret1 = dict.insert(make_pair("left", "左边"));
	auto ret2 = dict.insert(make_pair("right", "右边"));
	
	// []底层为：auto ret = insert(make_pair(k, mapped_type())); -- return ret.first->second -- mapped_type(是map第二个模板参数(T))
	dict["abandom"] = "放弃";		// 插入k + 修改v
	dict["ability"] = "能力";		// 插入k + 修改v
	dict["left"] = "左边，剩余";		// 查找k + 修改v
	dict["operator"];				// 插入k, v默认为map第二个模板参数的默认构造(string为"")
	Show(dict);
}
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

---

• map的修改

void Testmap1()
{
	// 键对值 -- key, value
	map<string, string> dict;
	dict.insert(pair<string, string>("left", "左边"));

	// make_pair是函数模板，底层是返回一个pair的匿名函数 -- return pair(...)
	dict.insert(make_pair("left", "左边"));

	// insert接口返回一个pair类型，如果第一次插入key则bool为true，但是插入相同的key，bool为false
	// first为iterator，second为bool
	pair<map<string, string>::iterator, bool> ret1 = dict.insert(pair<string, string>("abandon", "放弃"));

	auto ret2 = dict.insert(make_pair("ability", "能力")); // make_pair是一个函数模板，用来构造pair
	Show(dict);

	for (const auto& kv : dict) {
		cout << kv.first << ": " << kv.second << endl;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

---

🌓5、multimap

🌔5.1、multimap的介绍

【multimap文档介绍】

概念：

1. Multimaps是关联式容器，它按照特定的顺序，存储由key和value映射成的键值对，其中多个键值对之间的key是可以重复的
2. 在内部，multimap中的元素总是通过其内部比较对象，按照指定的特定严格弱排序标准对
   key进行排序的
3. multimap通过key访问单个元素的速度通常比unordered_multimap容器慢，但是使用迭代
   器直接遍历multimap中的元素可以得到关于key有序的序列
4. multimap在底层用二叉搜索树(红黑树)来实现

注意：multimap和map的唯一不同就是：map中的key是唯一的，而multimap中key是可以重复的

---

🌕5.2、multimap的使用

multimap与set的不同是：

1. multimap中的key是可以重复的。
2. multimap中的元素默认将key按照小于来比较
3. multimap中没有重载operator[]操作，因为插入相同的key时，对其进行修改时，我们不知道应该对哪一个key进行修改，会导致多义性
4. 使用时与map包含的头文件相同