519-C++STL(关联容器)

淩亂°似流年 2022-09-10 03:14 190阅读 0赞

## 关联容器 ##

**无序关联容器** =>底层实现是 链式哈希表 **增删查的时间复杂度O(1)**  
set:集合，存储 key  
map:映射表，存储 \[key,value\]键值对

unordered\_set 无序的单重集合  
unordered\_multiset无序的 多重集合  
unordered\_map 无序的 单重映射表  
unordered\_multimap 无序的 多重映射表

**单重就是不允许key重复，多重就是允许key重复**

**有序关联容器** => 底层是 红黑树 **增删查O(log2n)**， 2是底数(树的层数，树的高度)  
set  
multiset  
map  
multimap

![在这里插入图片描述][45ec7670c3744089866136268ce16a4f.png]  
**关联容器：**  
1.各个容器底层的数据结构 O(1) O(log2n)  
**2.常用增删查方法  
增加：insert(val)  
遍历：iterator自己搜索， 调用find成员方法  
删除：erase(key) erase(it)**

## 无序关联容器set的使用方式 ##

unordered_set<int> set1;//不会存储key值重复的元素
    	for (int i = 0; i < 50; ++i)
    	{
        
    		set1.insert(rand()%20+1);//只需要给出值就可以了 
    		//vector/deque/list  insert(it, val)
    	}
    
    	cout << set1.size() << endl;//返回容器的元素的个数 
    	cout << set1.count(15) << endl;//返回key为15的元素的个数

**关联容器插入的时候不用传位置参数(迭代器)，只需要给出元素的值就可以了。**  
![在这里插入图片描述][7e6ce22784b247e1916150d04cfe4662.png]  
我们看到输出的结果：元素的个数是18，说明插入的时候有很多元素的值是重复的相等的。15这个元素出现了1次。这就是单重集合，插入时不允许key值重复。  
**我们换成多重集合来看看**

unordered_multiset<int> set1;//不会存储key值重复的元素
    	for (int i = 0; i < 50; ++i)
    	{
        
    		set1.insert(rand()%20+1);//只需要给出值就可以了 
    		//vector/deque/list  insert(it, val)
    	}
    
    	cout << set1.size() << endl;//返回容器的元素的个数 
    	cout << set1.count(15) << endl;//返回key为15的元素的个数

![在这里插入图片描述][7772db95b8ea4a7db7a22032c1d8acb6.png]  
**多重集合，允许key值重复，插入几个元素，它就存储几个。**

auto it1 = set1.begin();
    	for (; it1 != set1.end(); ++it1)
    	{
        
    		cout << *it1 << " ";
    	}
    	cout << endl;

**删除操作**  
**erase可以接收key值或者迭代器**

set1.erase(20);//按key值删除元素
       
    	for (it1 = set1.begin(); it1 != set1.end(); )//迭代器遍历
    	{
        
    		if (*it1 == 30)
    		{
        
    			it1 = set1.erase(it1);//调用erase，it1迭代器就失效了
    		}
    		else
    		{
        
    			++it1;//删除了，要往下再走1步
    		}
    	}

**find方法**

it1 = set1.find(20);
    	//存在的话返回指向这个元素的迭代器，不存在的话返回末尾迭代器
    	if (it1 != set1.end())
    	{
        
    		set1.erase(it1);//找到了，删除掉
    	}
    
    	for (int v : set1)//遍历
    	{
        
    		cout << v << " ";
    	}
    	cout << endl;

## 无序关联容器map的使用方式 ##

**map存储的是\[key, value\]键值对**  
**map存储的是pair对象**

struct pair
    {
        
    	first; = > 表示的是key
    	second; = > 表示的是value
    }

**map使用代码：**

unordered_map<int, string> map1;
    map1.insert(make_pair(1000, "张三"));
    map1.insert({
         1010, "李四" });//map表增加元素
    map1.insert({
         1020, "王五" });
    map1.insert({
         1030, "王凯" });
    map1.erase(1020); //{1020, "王五" }删除了
    
    cout << map1.size() << endl;//键值对的个数

auto it1 = map1.find(1030);
    if (it1 != map1.end())
    {
        
    	//it1 -> 打包成pair对象
    	cout << "key:" << it1->first << " value:" << it1->second << endl;
    }

**单重映射表不允许键重复**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][ce5897c35bc2436ba14939412619b9b7.png]  
**多重映射表允许键重复**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]

![在这里插入图片描述][dc1ec5b3cbde4cf4bc82ad285af3d375.png]

**map的operator\[\]的功能**

1.查询的功能  
2.如果key不存在，它会插入一对数据\[key, string()\]  
如果key不存在，它会把key，然后默认构造一个实例对象，组成键值对插入。

V& operator[](const K& key)
    {
        
    	insert({
         key, V() });
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
![在这里插入图片描述][005200329ba245369610cfb6010176d8.png]  
**键值对变成4对了**

map1[2000];//插入功能，key:2000 value:""
    map1[2000] = "刘硕";//插入功能，map1.insert({2000, "刘硕"});
    map1[1000] = "张三2";//修改功能

## 处理海量数据查重 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]  
**键代表插入的数字，值代表这个数字的重复次数**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]  
**方法1**

for (const pair<int, int>& p : map1)
    {
        
    	if (p.second > 1)//有重复
    	{
        
    		cout << "key:" << p.first << " count:" << p.second << endl;
    	}
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 5]  
**方法2**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 6]  
**方法3：**

//上面的10万个整数中，统计哪些数字重复了，并且统计数字重复的次数
    unordered_map<int, int> map1;
    for (int k : arr)
    {
        
    	/*
    	auto it = map1.find(k);
    	if (it == map1.end())
    	{
    		map1.insert({k, 1});
    	}
    	else
    	{
    		it->second++;
    	}
    	*/
    	map1[k]++;//map1[k] 生成[k, 1]
    }

## 处理海量数据去重 ##

**set只存储key，所以这次用set比较好。**

int main()
    {
        
    	//处理海量数据去重复
    	const int ARR_LEN = 100;
    	int arr[ARR_LEN] = {
         0 };
    	for (int i = 0; i < ARR_LEN; ++i)
    	{
        
    		arr[i] = rand() % 20 + 1;
    	}
    
    	//上面的10万个整数中，把数字进行去重打印
    	unordered_set<int> set;
    	for (int v : arr)//O(n)
    	{
        
    		set.insert(v);//O(1)的操作
    	}
    
    	for (int v : set)
    	{
        
    		cout << v << " ";
    	}
    	cout << endl;
    
    	return 0;
    }

![在这里插入图片描述][93d9645ab0ef48bf9f35585107d2e8b7.png]

## 有序关联容器的使用方式 ##

![在这里插入图片描述][286a7766e1274390ae612489b6ed6897.png]  
**底层是红黑树。**

set<int> set1;
    for (int i = 0; i < 20; ++i)
    {
        
    	set1.insert(rand() % 20 + 1);
    }
    
    for (int v : set1)
    {
        
    	cout << v << " ";
    }
    cout << endl;

![在这里插入图片描述][af192798a4434b0680ad9efeb82ba8d9.png]  
**因为set是单重有序集合，所以默认按升序打印出来（就是通过中序遍历把红黑树访问了1遍），而且插入的key值不能重复。**

**如果是存放自定义的类型**

class Student
    {
        
    public:
    	Student(int id, string name)
    		:_id(id), _name(name) {
        }
    	bool operator<(const Student &stu)const
    	{
        
    		return _id < stu._id;
    	}
    private:
    	int _id;
    	string _name;
    	friend ostream& operator<<(ostream &out, const Student &stu);
    };
    ostream& operator<<(ostream &out, const Student &stu)
    {
        
    	out << "id:" << stu._id << " name:" << stu._name << endl;
    	return out;
    }
    int main()
    {
        
    	set<Student> set1;
    
    	set1.insert(Student(1020, "李广"));
    	set1.insert(Student(1000, "张雯"));
    	
    	for (auto it = set1.begin();
    		it != set1.end(); ++it)
    	{
        
    		cout << *it << endl;
    	}
    
    	return 0;
    }

![在这里插入图片描述][c9fd871353ee4d3e899872da7bec4419.png]  
**按照key值从小到大排序的。**

class Student
    {
        
    public:
    	Student(int id=0, string name="")
    		:_id(id), _name(name) {
        }
    private:
    	int _id;
    	string _name;
    	friend ostream& operator<<(ostream &out, const Student &stu);
    };
    ostream& operator<<(ostream &out, const Student &stu)
    {
        
    	out << "id:" << stu._id << " name:" << stu._name << endl;
    	return out;
    }
    int main()
    {
        
    	map<int, Student> stuMap;
    	stuMap.insert({
         1000, Student(1000, "张雯") });
    	stuMap.insert({
         1020, Student(1020, "李广") });
    	stuMap.insert({
         1030, Student(1030, "高洋") });
    
    	//删除的方法：stuMap.erase(it)  stuMap.erase(1020)  
    	//查询的方法：cout << stuMap[1020] << endl;   stuMap.find(key)
    	//stuMap[2000]-----》如果key不存在，就会构建 [2000, V()]键值对插入map表中 
    	//这里的key是整数，编译器知道如何给这个key进行排序 
    	auto it = stuMap.begin();
    	for (; it != stuMap.end(); ++it)
    	{
        
    		cout << "key:" << it->first << " value:" << it->second << endl;
    	}
    	cout << endl;
    
    	return 0;
    }

![在这里插入图片描述][38f0bd938cc14f07967c6328ea325a1f.png]

[45ec7670c3744089866136268ce16a4f.png]: /images/20220829/5a3fd0b51bad438d9e3971b7d54003bf.png
[7e6ce22784b247e1916150d04cfe4662.png]: /images/20220829/0152f13dc5fc464492813c430a008b15.png
[7772db95b8ea4a7db7a22032c1d8acb6.png]: /images/20220829/7844a82fc12e4cc6b0ff8771ed127766.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/0dd9ccdcf0fa49b5832e65e7a4c0bbee.png
[ce5897c35bc2436ba14939412619b9b7.png]: /images/20220829/cd55bf760587436eb29aad3c6b4aa9da.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/d0bbcb37a1af4617b753e89b40b03b93.png
[dc1ec5b3cbde4cf4bc82ad285af3d375.png]: /images/20220829/c6e8df4fd96e47c0aa1a0197785d7b1e.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220829/581728f0295545948f260872e85edaa8.png
[005200329ba245369610cfb6010176d8.png]: /images/20220829/90e5b08c0d4a4c2385fb740511aefbb3.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220829/4961a82132fd45e2b7156a8f84b31cc3.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220829/33c0d688ec544a6abe4a9408ef48f423.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220829/333cf49c3a8d4536a5e96d46783142fa.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 6]: /images/20220829/6451c42727d54d0abef636f2a528e917.png
[93d9645ab0ef48bf9f35585107d2e8b7.png]: /images/20220829/35fb0a5e8d544116979bed3dfd3b275f.png
[286a7766e1274390ae612489b6ed6897.png]: /images/20220829/59a966a85d83451ab4efea9d33fe2414.png
[af192798a4434b0680ad9efeb82ba8d9.png]: /images/20220829/c0a51a0463fa4e91804467af869aaab6.png
[c9fd871353ee4d3e899872da7bec4419.png]: /images/20220829/9a446813b5ed4880be424d68dd7a8a75.png
[38f0bd938cc14f07967c6328ea325a1f.png]: /images/20220829/1151b5ddd0ef41248c802c937dbb5a89.png