Cpp::set & map 的理解与使用(22)

前言

  刚学完二叉搜索树，我们马上来感受一下直接与它相关的两个容器吧！

一、预备知识

关联式容器

  在以往的 STL 容器学习中，我们接触到的都是 序列式容器，比如 string、vector、list、deque 等，序列式容器的特点就是 底层为线性序列的数据结构，就比如 list，其中的节点是 线性存储 的，一个节点存储一个元素，其中存储的元素都可序，但未必有序

  关联式容器 则比较特殊，其中存储的是 <key, value> 的 键值对，这就意味着可以按照 键值大小 key 以某种特定的规则放置于适当的位置，关联式容器 没有首尾的概念，因此没有头插尾插等相关操作，本文中学习的 set 和 map 就属于 关联式容器

键值对

  键值对是 一种用来表示具有一一对应关系的结构，该结构中一般只包含两个成员变量：key 和 value，前者表示 键值，后者表示 实值

  关联式容器的实现离不开键值对

//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) {}

#ifdef __STL_MEMBER_TEMPLATES
  template <class U1, class U2>
  pair(const pair<U1, U2>& p) : first(p.first), second(p.second) {}
#endif
};

  pair 中的 first 表示 键值，second 则表示 实值，在给 关联式容器 中插入数据时，可以构建 pair 对象
比如下面就构建了一个 键值 key 为 string，实值 value 为 int 的匿名 键值对 pair 对象

pair<string, int>("hehe", 123);

  可以将此匿名对象传入 关联式容器 中，当然这样写未免过于麻烦了，于是库中设计了一个函数模板 make_pair，可以根据传入的参数，去调用 pair 构建对象并返回

make_pair("hehe", 123);	//构建出的匿名对象与上面的一致

二、set

何为set?

  set 其实就是之前在 二叉搜索树 中的K模型

也就是用来解决“在不在”问题的模型

  其中的 T 就是 set 的实值（键值），参数2 Compare 为存储依据，默认为升序，即符合 二叉搜索树 中序遍历的结果：升序，参数3 Alloc 是空间配置器，现在不必深究

  作为 STL 中的容器，set 当然少不了迭代器，树型关联式容器迭代器的遍历结果为有序，所以迭代器遍历的本质是 中序遍历，同时 set 的迭代器还是一个 双向迭代器，支持 ++ 和 – 操作

set的使用

  set 的构造函数如下图所示：

  可以直接创建一个空 set 使用，也可以根据迭代器区间创建 set

#include <iostream>
#include <vector>
#include <set>
using namespace std;

int main()
{
	vector<int> arr = { 8,5,6,7,3,1,1,3 };

	set<int> s1;	//创建一个空的 set
	set<int> s2(arr.begin(), arr.end());	//创建包含数据的 set

	cout << "s1: ";
	for (const auto& e : s1)
		cout << e << " ";
	cout << endl;

	cout << "s2: ";
	for (const auto& e : s2)
		cout << e << " ";
	cout << endl;

	return 0;
}

  就像 二叉搜索树 一样，set 是不支持数据冗余的，如果出现冗余的数据插入时，会失败，如果想存储冗余的数据，可以使用 multiset

set 中的常用功能

#include <iostream>
#include <vector>
#include <set>
using namespace std;

int main()
{
	vector<int> arr = { 7,3,6,9,3,1,6,2 };
	set<int> s1(arr.begin(), arr.end());

	//迭代器遍历
	cout << "迭代器遍历结果: ";
	set<int>::iterator it = s1.begin();
	while (it != s1.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	//判空、求大小
	cout << "===================" << endl;
	cout << "empty(): " << s1.empty() << endl;
	cout << "size(): " << s1.size() << endl;

	//插入元素
	cout << "===================" << endl;
	cout << "insert(5): ";
	s1.insert(5);
	for (const auto& e : s1) cout << e << " ";
	cout << endl;

	//删除元素
	cout << "===================" << endl;
	cout << "erase(6): ";
	s1.erase(6);
	for (const auto& e : s1) cout << e << " ";
	cout << endl;

	//交换、查找、清理
	cout << "===================" << endl;
	set<int> s2(arr.begin() + 5, arr.end());
	s1.swap(s2);
	
	cout << "s1: ";
	for (const auto& e : s1) cout << e << " ";
	cout << endl;

	cout << "s2: ";
	for (const auto& e : s2) cout << e << " ";
	cout << endl;

	cout << "s1.find(9): ";
	cout << (s1.find(9) != s1.end()) << endl;

	cout << "s2.clear(): " << endl;
	s2.clear();

	cout << "s1: ";
	for (const auto& e : s1) cout << e << " ";
	cout << endl;

	cout << "s2: ";
	for (const auto& e : s2) cout << e << " ";
	cout << endl;

	// 查询数量
	cout << "s1.count(2):" << " " << s1.count(2) << endl;

	return 0;
}

其实因为set不允许键值重复，所以 count() 只会有 0 或者 1 两种可能，所以理论上来说你可以用它来判断数字是否在容器中

  另外请注意，二叉搜索树中的键值key是不允许改变的，如果改变了，会破坏二叉搜索树的结构导致失效

因此即使是 set 中的普通迭代器，本质上也是 const 迭代器

set的特点

  总得来说就是下图

multiset

multi前缀在英语中是为 “多” 的意思

  其实对比set，也就是多了支持数据冗余的功能

  另外当查询数字有多个的时候，返回的是 中序遍历中第一次出现的元素

#include <iostream>
#include <vector>
#include <set>
using namespace std;

int main()
{
	vector<int> arr = { 3,5,3,4,5,9,2,3 };
	multiset<int> ms1(arr.begin(), arr.end());

	auto it = ms1.begin();
	while (it != ms1.end())
	{
		cout << *it << " | " << &*(it) << endl;
		++it;
	}

	cout << "================" << endl;
	cout << "ms1.find(3): " << &*(ms1.find(3)) << endl;

	return 0;
}

multiset 才是真正的排序，set 则是去重 + 排序

三、map

何为map?

  map 是 二叉搜索树 改造后的 key / value 模型，是一个真正意义上的 键值对

map其实就是一种映射关系

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int main()
{
	vector<pair<string, int>> arr = { make_pair("G", 71), make_pair("A", 65), make_pair("F", 70) };

	map<string, int> m1;	//创建一个空的 map
	map<string, int> m2(arr.begin(), arr.end());	//创建包含数据的 map

	cout << "m1: " << endl;
	for (const auto& e : m1)
		cout << e.first << " | " << e.second << endl;
	cout << "========================" << endl;
	cout << "m2: " << endl;
	for (const auto& e : m2)
		cout << e.first << " | " << e.second << endl;

	return 0;
}

map 中的常用功能

#include <iostream>
#include <vector>
#include <string>
#include <map>
using namespace std;

int main()
{
	vector<pair<string, int>> arr{ make_pair("z", 122), make_pair("a", 97),  make_pair("K", 75), make_pair("h", 104), make_pair("B", 66) };

	map<string, int> m1(arr.begin(), arr.end());

	//迭代器遍历
	cout << "迭代器遍历结果: ";
	map<string, int>::iterator it = m1.begin();
	while (it != m1.end())
	{
		cout << "<" << it->first << ":" << it->second << "> ";
		++it;
	}
	cout << endl;

	//判空、求大小、解引用
	cout << "===================" << endl;
	cout << "empty(): " << m1.empty() << endl;
	cout << "size(): " << m1.size() << endl;
	cout << "m1[""a""]: " << m1["a"] << endl;

	//插入元素
	cout << "===================" << endl;
	cout << "insert(""a"", 5): ";
	m1.insert(make_pair("a", 5));
	for (const auto& e : m1) cout << "<" << e.first << ":" << e.second << "> ";
	cout << endl;

	//删除元素
	cout << "===================" << endl;
	cout << "erase(""a""): ";
	m1.erase("a");
	for (const auto& e : m1) cout << "<" << e.first << ":" << e.second << "> ";
	cout << endl;

	//交换、查找、清理
	cout << "===================" << endl;
	map<string, int> m2(arr.begin() + 2, arr.end());
	m1.swap(m2);
	cout << "m1.swap(m2)" << endl;
	cout << "m1: ";
	for (const auto& e : m1) cout << "<" << e.first << ":" << e.second << "> ";
	cout << endl;

	cout << "m2: ";
	for (const auto& e : m2) cout << "<" << e.first << ":" << e.second << "> ";
	cout << endl;

	cout << "m1.find(""B""): ";
	cout << (m1.find("B") != m1.end()) << endl;

	cout << "m2.clear()" << endl;
	m2.clear();

	cout << "m1: ";
	for (const auto& e : m1) cout << "<" << e.first << ":" << e.second << "> ";
	cout << endl;

	cout << "m2: " << endl;
	for (const auto& e : m2) cout << "<" << e.first << ":" << e.second << "> ";
	cout << endl;

	return 0;
}

map 不允许数据冗余，如果想插入重复的数据，可以使用 multimap

  map的插入函数比较有意思，因为既要返回插入是否成功，又要返回插入成功的迭代器，所以它的返回值其实是个pair

#include <iostream>
#include <vector>
#include <string>
#include <map>
using namespace std;

int main()
{
	map<string, int> m1;
	auto ret = m1.insert(make_pair("a", 97));
	cout << "<" << ret.first->first << ":" << ret.first->second << ">" << " | " << ret.second << endl;

	ret = m1.insert(make_pair("a", 100));
	cout << "<" << ret.first->first << ":" << ret.first->second << ">" << " | " << ret.second << endl;

	return 0;
}

  至于 find 和 count 跟 set 中的一样，可以用来判断元素是否存在，不过 find 返回的是 迭代器，count 返回的则是 键值数

  map 是支持修改 实值 value 的，因此 可以根据普通迭代器修改实值

#include <iostream>
#include <vector>
#include <string>
#include <map>
using namespace std;

int main()
{
	map<string, int> m1;
	m1.insert(make_pair("a", 97));
	auto it = m1.find("a");
	cout << "<" << it->first << ":" << it->second << ">" << endl;

	it->second = 100;
	cout << "<" << it->first << ":" << it->second << ">" << endl;

	return 0;
}

map中的operator[ ]

  operator[ ] 返回的是当前 键值 对应的 实值，如果当前 键值 不存在，则会插入新的 键值对

这很强大，值得我们单独介绍一下它

  operator[ ] 的返回值为 mapped_type，即 实值 value 的引用，参数 key_type 是 键值 key

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

1. 插入一个新的键值对 this->insert( make_pair(k, mapped_type()) )
2. 获取 insert 返回值中的 键值 返回值.first 即迭代器 iterator
3. 最后通过迭代器获取 实值 (*iterator).second

所以说，这个operator[ ]包含了插入、修改、插入+修改、查找等功能

multimap

既然允许冗余数据插入，自然也就没有了operator[ ]

总结

  复杂链表的复制
  前K个高频单词

  两道很有意思的题目，大家可以尝试运用本篇文章的内容来尝试一下