【C++】STL — map和set的使用详细介绍

前言
本章将继续学习STL中的两个很重要的容器map和set，其底层实现是封装了一个红黑树，我们通过本节来学习和深入了解一下这两大容器。。。
序列式容器： string 、Vector、List 、dequeue
关联式容器：MAP 、SET、nordered_map、unordered_set。
关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是**<key, value>结构的键值对**，在数据检索时比序列式容器效率更高。
除此之外，序列式容器中存储的元素默认都是未经过排序的，而使用关联式容器存储的元素，默认会根据各元素的键值的大小做升序排序。

1. 键值对的引入

用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息.
在这里插入图片描述
它实际是一个类模板，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)
{}
};

2. set的介绍 + 使用

使用 set 容器，必须引入该头文件#include < set >

Set是按照一定次序存储元素的容器
Set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们
在set中，存放的是Value**(value就是key，类型为T)，并且每个value必须是唯一的.**
在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序
Set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对子集进行直接迭代
set在底层是用二叉搜索树(红黑树)实现的。

注意：（与MAP的区别）

与map/multimap不同，set中只放 value，map 中存储的是真正的键值对<key, value>.
Set中插入元素时，只需要插入value即可，不需要构造键值对
set中的元素不可以重复(因此可以使用set进行去重)
使用set的迭代器遍历set中的元素，可以得到有序序列

2.1 set的构造

在这里插入图片描述

T: set中存放元素的类型，实际在底层存储<value, value>的键值对。
Compare：set中元素默认按照小于来比较
Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理

#include <set>
void TestSet()
{
// 用数组array中的元素构造set
int array[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9, 2, 4,
6, 8, 0 };
set<int> s(array, array+sizeof(array)/sizeof(array));
cout << s.size() << endl;

// 正向打印set中的元素，从打印结果中可以看出：set可去重
for (auto& e : s)
{
   cout << e << " ";
}
cout << endl;
}
//使用迭代器逆向打印set中的元素
for (auto it = s.rbegin(); it != s.rend(); ++it)
{
   cout << *it << " ";
   cout << endl;
}

2.2 set的插入

在这里插入图片描述
set自带的Find()和算法库中的Find（）有什么区别

1.set自带的查找是利用了搜索树的特点，查找时间复杂度为〇（logN）
2.如果用算法库中的查找则是通过暴力查找的方式进行的，时间复杂度为〇（N）

2.2 set的删除

在这里插入图片描述

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

3. Map 的介绍 + 使用

map是关联容器，它按照特定key的次序存储由键值key和值value组合而成的元素。
typedef pair<const key, T> value_type
在内部，map中的元素总是按照键值key进行比较排序的.
map支持下标访问符，即在[ ]中放入key，就可以找到与key对应的value
map通常被实现为二叉搜索树((红黑树))
统计value相同的次数时，使用[ ]操作符,见下面解释

使用 map 容器，必须引入该头文件#include < map >
在这里插入图片描述

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

3.1 Map 的构造

在这里插入图片描述

int main ()
{
  std::map<char,int> first;

  first['a']=10;
  first['b']=30;
  first['c']=50;
  first['d']=70;

  std::map<char,int> second (first.begin(),first.end());

  std::map<char,int> third (second);
 return 0;
 }

3.2 Map 的插入Insert

在这里插入图片描述

map插入的是一对键值对Pair<K ,v>
通过pair的first和second，即可访问到两个值
Key_value模型中，修改不能修改key，但是可以修改value

3.3 利用map统计次数

有两种方案：
（1）通过查找来挨个遍历查找统计次数
（2）使用operator [ ]来进行统计次数

1.通过查找来挨个遍历查找统计个数

void test_map2()
{
	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果",
					 "西瓜", "苹果", "香蕉", "苹果", "香蕉" };

	map<string, int> countMap;
	for (auto& str : arr)
	{
		map<string, int>::iterator it = countMap.find(str);
		if (it != countMap.end())
		{
			it->second++;
		}
		else
		{
			countMap.insert(make_pair(str, 1));
		}
	}
}

2.使用operator [ ]来进行统计次数

operator[]的参数是key，返回值是value的引用
operator[]都有随机访问的意思，这里的方括号已经没有了随机访问的意思

map<string，int> countMap;
for(auto&str:arr)
{
 //1.str不在countMap中，插入pair（str,int())，然后再对返回次数++；
 //2. str在countMap中，返回value(次数）的引用，次数++
     countMap[str]++;
}

对operator [ ]的讲解：

operator[]兼顾了两个功能：插入 + 修改
Map中有这个key,返回value的引用（查找、修改value）
Map中没有这个key,会插入一个pair(key，v());返回value的引用。（插入+修改）

模拟operator [ ]的实现代码：

v& operator[](const K&key)
{
    pair<iterator,bool> ret=insert(make_pair(key,v());
    return ret.first->second;
}
//STl库里面的实现
mapped_type& operator[](const key_type& k)
{
   return (*((this->insert(make_pair(k,mapped_type()))).first)).second;
}