一、关联容器概述

关联容器通过 ​键（Key）​ 高效存储和访问元素，它们的元素位置取决于键值，而非插入顺序。主要分为两类：

1.无序关联容器，依赖于链式哈希表，增删查O(1)

使用头文件：#include<unordered_set>、#include<unordered_map>

set：集合  key       map：映射表[key, value]（键值对）
unordered_set：单重集合
unordered_multiset：多重集合
unordered_map：单重映射表
unordered_multimap：多重映射表

2.有序关联容器，依赖于红黑树，增删查O(log2n)，2是底数（树的层数，树的高度）

使用头文件：#include<set>、#include<map>

set
multiset
map
multimap

map 和 set：每个关键字（Key）必须是唯一的。如果插入重复的关键字，操作会被忽略（不会报错）。

#include<iostream>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
using namespace std;

int main()
{
	unordered_set<int> set1;  //不会存储key值重复的元素
	for (int i = 0; i < 50; i++)
	{
		set1.insert(rand() % 20 + 1); 
	}
	cout << set1.size() << endl;
	cout << set1.count(15) << endl;
	return 0;
}

得到的输出是18和1，说明有很多元素是重复的，15只出现1次。

multiset 和 multimap：允许重复的关键字。插入操作始终成功，不检查重复性。

#include<iostream>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
using namespace std;

int main()
{
	unordered_multiset<int> set1;  //改为多重集合
	for (int i = 0; i < 50; i++)
	{
		set1.insert(rand() % 20 + 1); 
	}
	cout << set1.size() << endl;
	cout << set1.count(15) << endl;
	return 0;
}

得到的输出是50和2，说明重复的元素也可以存储。

二、无序关联容器

1.无序set

各个容器底层的数据结构   O(1)   O(log2n)

增加：insert（val）
遍历：iterator自己搜索，调用find成员方法
删除：erase（key）、erase（it）

#include<iostream>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
using namespace std;

int main()
{
	unordered_set<int> set1;  //不会存储key值重复的元素
	for (int i = 0; i < 50; i++)
	{
		set1.insert(rand() % 20 + 1);
	}
	auto it1 = set1.begin();
	for (; it1 != set1.end(); ++it1)
	{
		cout << *it1 << " ";
	}
	cout << endl;

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

	it1 = set1.find(20);
	if (it1 != set1.end())
	{
		set1.erase(it1);
	}

	for (int v : set1)
	{
		cout << v << " ";
	}
	return 0;
}

2.无序map

map的operator[ ]
1）查询
2）如果key不存在，它会插入一对数据[key, string( )]

因为：
[key, value]

struct pair

{

  first: =>key

  second: =>value

}

所以，访问迭代器时可以用first和second访问键值对

int main()
{
	unordered_map<int, string>map1;
	map1.insert(make_pair(1000, "张三"));
	map1.insert({ 1010,"李四" });
	map1.insert({ 1020,"王五" });
	map1.insert({ 1030,"王凯" });

	map1.erase(1020);
	map1[2000];

	cout << map1.size() << endl;
	//map operator[](key) => value 查询
	cout << map1[1000] << endl;
	return 0;
}

输出结果，size得到4，但实际只有3，说明使用map的operator[ ]时，当kye不存在，就会插入一对数据。

#include<iostream>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<string>
using namespace std;

int main()
{
	unordered_map<int, string>map1;
	map1.insert(make_pair(1000, "张三"));
	map1.insert({ 1010,"李四" });
	map1.insert({ 1020,"王五" });
	map1.insert({ 1030,"王凯" });

	map1.erase(1020);

    auto it1 = map1.find(1030);
	if (it1 != map1.end())
	{
		cout << "key:" << it1->first << " value:" << it1->second << endl;
	}
	//map1[2000];
	map1[2000] = "刘说";  //根据key对其value进行插入操作
	map1[1000] = "张三2"; //根据key对其value进行修改操作

	cout << map1.size() << endl;
	//map operator[](key) => value 查询
	cout << map1[1000] << endl;
	return 0;
}

3.什么时候使用哈希表？

①处理海量数据查重复

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;
	}
	// 上面的100个整数中，统计哪些数字重复了，并且统计数字重复的次数
	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++;
		}
	}
	for (pair<int, int>p : map1)
	{
		if (p.second > 1)
		{
			cout << "key:" << p.first << " count:" << p.second << endl;
		}
	}
    cout << endl;

	auto it = map1.begin();
	for (; it != map1.end();++it)
	{
		if (it->second > 1)
		{
			cout << "key:" << it->first << " count:" << it->second << endl;
		}
	}
    return 0;
}

②去重复的时候

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;
	}
	//上面的100个整数中，把数字进行去重打印
	unordered_set<int> set;
	for (int v : arr)
	{
		set.insert(v);
	}
	for (int v : set)
	{
		cout << v << " ";
	}
	cout << endl;
    return 0;
}

三、有序关联容器

输出是有序的！！！

1.有序set

int main()
{
	set<int> set1;
	for (int i = 0; i < 20; ++i)
	{
		set1.insert(rand() % 20 + 1);
	}
	for (int v : set1)
	{
		cout << v << " ";
	} //输出1 2 3 5 6 8 10 12 15 16 17 19，是有序的
	return 0;
}

#include<iostream>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<string>
using namespace std;

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(1000, "张问"));
	set1.insert(Student(1020, "李广"));
	for (auto it = set1.begin(); it != set1.end(); ++it)
	{
		cout << *it << endl;
	}
	return 0;
}

2.有序map

//对上面代码做出部分修改，其余地方保持不变
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;
	for (auto it = stumap.begin(); it != stumap.end(); ++it)
	{
		cout << "key:" << it->first << " value:" << it->second << endl;
	}
	cout << endl;
	return 0;
}