一、标准容器

3、关联容器

主要分为两类：

• set：集合，存的是关键字key
• map：映射表存的是 [key,value]键值对

常用增删查方法：

• 增加：insert(val);

• 遍历：iterator自己搜索或调用find成员方法，

  unordered_set<int>::iterator it = set1.find(15); cout << *it;

• 删除：erase(key) erase(it)

3.1、无序关联容器 => 链式哈希表

无序关联容器底层是链式哈希表，里边元素是无序的，增删查O(1)

无序关联容器在有序关联容器前面加了个unordered_，这些容器操作都是一模一样的，无非就是底层数据结构不同，90%的情况都是在使用无序关联容器，因为大部分应用场景只在乎增删查的时间复杂度要快，如果对元素的顺序有要求则只能选择基于红黑树的有序关联容器

四种无序关联容器

• unordered_set 单重集合：不允许key重复
• unordered_multiset 多重集合：允许key重复
• unordered_map 单重映射表
• unordered_multimap 多重映射表

头文件

//无序关联容器头文件
#include <unordered_set>  //unordered_set  unordered_multiset
#include <unordered_map>  //unordered_map  unordered_multimap 
using namespace std;

unordered_set代码示例

int main()
{
    
    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的元素的个数，单重集合，key唯一，输出0或1
}

存了50个元素却只有18个元素，说明添加的时候有很多是重复的，单重集合是不存储重复的key的

unordered_map代码示例

/*
map中存的是[key,value]键值对
struct
{
	first;    //key，struct默认访问权限公有
	seconde;  //value
};
*/
int main()
{
    
	unordered_map<int, string> map1;
    
    //增加
	map1.insert(make_pair(1000, "张三"));  //将键值对打包成pair对象插入到map表中
    map1.insert({
    1010, "李四"});
    map1.insert({
    1020, "王五"});
    
    //范文
    cout<<map1.size()<<endl;
    cout<<map1[1000]<<endl;  
    cout<<map1[1010]<<endl;  
    map1[2000] = "wang";  //就相当于 map1.insert({2000,"wang"});
    cout<<map1[2000]<<endl;
    
    //查询
    auto it1 = map1.find(1000);  //find返回的是打包的pair对象
    if(it1 != map1.end())
    {
    
        cout<<"key: "<<it1->first<<endl;
        cout<<"value: "<<it1->second<<endl;
    }
    
    //删除
    map1.erase(1020);
}

应用场景

• 处理海量数据查重时候经常用到哈希表

//海量数据查重
#include <iostream>
#include <unordered_map>
using namespace std;

int main()
{
    
	const int ARR_LEN = 1000;
	int arr[ARR_LEN] = {
     0 };
	for (int i = 0; i < ARR_LEN; ++i)
	{
    
		arr[i] = rand() % 200 + 1;
	}

	//上面的1000个整数中，统计那些数字重复了，并且统计数字重复的次数
	unordered_map<int, int> map1;  //<数字,次数>
	for (int k : arr)
	{
    
        /*
		auto it = map1.find(k);
		if (it == map1.end())  //该数字还没存入map表
		{
			map1.insert({ k, 1 });
		}
		else  //之前出现过
		{
			it->second++;
		}*/
        map1[k]++;  //k不存在，[]副作用插入一个新的[k,0]，++到[k,1]
	}

    //打印方式1：
	for (const pair<int, int> &p : map1)  //foreach遍历必须用常引用，只是读操作
	{
    
		if (p.second > 1)
		{
    
			cout << "key: " << p.first << "重复次数：" << p.second << endl;
		}
	}
    
    //打印方式2：
    auto it = map1.begin();
    for(; it != map1.end(); ++it)
    {
    
        if(it->second > 1)
        {
    
            cout << "key: " << it->first << "重复次数：" << it->second << endl;
        }
    }
}

• 海量数据去重用单重set

//海量数据去重
//海量数据查重
#include <iostream>
#include <unordered_set>
using namespace std;

int main()
{
    
	const int ARR_LEN = 1000;
	int arr[ARR_LEN] = {
     0 };
	for (int i = 0; i < ARR_LEN; ++i)
	{
    
		arr[i] = rand() % 200 + 1;
	}

	//上面的1000个整数中，把数字进行去重，打印出只出现一次的数字
	unordered_set<int> uset;
	for (int v : arr)
	{
    
		uset.insert(v);
	}

	for (int v : uset)
	{
    
		cout << v << " ";
	}
	cout << endl;
}

3.2、有序关联容器 => 红黑树

有序关联容器底层是红黑树，元素是经过排序的，增删查O(log2n) 2是底数(树的层数，树的高度)

有序关联容器的操作与无序关联容器一模一样

用迭代器去遍历有序集合容器时，其实就是对底层红黑树中序遍历的结果

四种有序关联容器

• set 单重集合
• multiset 多重集合
• map 单重映射表
• multimap 多重映射表

头文件

//有序关联容器头文件
#include <set>  //set  multiset
#include <map>  //map  multimap
using namespace std;

有序set示例

int main()
{
    
	set<int> set1;  //有序单重集合
	for (int i = 0; i < 20; ++i)
	{
    
		set1.insert(rand() % 20 + 1);
	}
	
	for (int v : set1)
	{
    
		cout << v << " ";
	}
	cout << endl;
}

向有序容器中添加自定义类型时注意：要提供默认的<运算符的重载函数

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)
{
    
	cout << "id: " << stu._id << " name: " << stu._name << endl;
	return out;
}

int main()
{
    
	set<Student> set1;
	set1.insert(Student(1020, "wang"));
	set1.insert(Student(1010, "yang"));
	set1.insert(Student(1030, "zhang"));

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

有序map示例

map表中要求value有默认的构造函数，因为[]去引用元素如果不存在会构造一个对象，因此要有默认构造函数

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)
{
    
	cout << "id: " << stu._id << " name: " << stu._name << endl;
	return out;
}

int main()
{
    
	map<int, Student> stuMap;
	stuMap.insert({
     3, Student(1030, "wang") });
	stuMap.insert({
     1, Student(1010, "yang") });
	stuMap.insert({
     2, Student(1020, "zhang") });

	cout << stuMap[4] << endl;

	//打印方式1：
	for (auto it : stuMap)  //stuMap中元素是什么类型，it就是什么类型
	{
    
		cout <<"key: "<<it.first<<"  value: "<< it.second << endl;
	}

	cout << "-------------------------------------------------------------" << endl;

	//打印方式2：
	auto it = stuMap.begin();
	for (; it != stuMap.end(); it++)
	{
    
		cout <<"key: "<<it->first<<"  value: "<< it->second << endl;
	}
	
}