跳至主要內容

无序关联容器、有序关联容器

张威大约 6 分钟c/c++页面配置使用指南

无序关联容器、有序关联容器

一、无序关联容器

关联容器分为：无序关联容器与有序关联容器，简单对比下：

在这里插入图片描述
在这里插入图片描述

无序关联容器：底层为，里面，。

1.1单重集合与多重集合

set:集合，存储的是unordered_set：单重集合：不允许key重复。unordered_multiset：多重集合：允许key重复。 包含的头文件：

#include <unordered_set>

unordered_set与unordered_multiset常用方法： 增加：insert(val); 遍历：iterator自己搜索，调用find()； 删除：erase(key); 或 erase(it); size();//返回容器中元素个数。 count(val);//返回元素值为val的个数，val不会重复。 find(val);在集合容器中查找key,存在返回迭代器，不存在返回容器末尾迭代器。

实例1：unordered_set使用1

unordered_set<int> set1;//不允许存储key值重复的元素
for (int i=0; i<50; ++i)
{
	set1.insert(rand()%20 + 1);//与vector/deque/list插入不同
}

cout << set1.size() << endl;
cout << set1.count(15) << endl;//返回key为15的元素的个数

测试成功：有许多重复的元素，但是unordered_set不存储key值重复元素，15出现了一次。

实例2：unordered_set使用2

unordered_set<int> set1;//不允许存储key值重复的元素
for (int i=0; i<50; ++i)
{
	set1.insert(rand()%20 + 1);//与vector/deque/list插入不同
}

auto it1 = set1.begin();//迭代器遍历容器
for (; it1!=set1.end(); ++it1)
{
	cout << *it1 << " ";
}
cout << endl;

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

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

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

实例3：unordered_multiset使用

unordered_multiset<int> set1;//允许存储key值重复的元素
for (int i=0; i<50; ++i)
{
	set1.insert(rand()%20 + 1);//与vector/deque/list插入不同	
}

cout << set1.size() << endl;
cout << set1.count(15) << endl;//返回key为15的元素的个数

测试成功：允许key值重复。

1.2单重映射表与多重映射表

map:映射表，存储的是unordered_map：单重映射表，存储的键值对unordered_multimap：多重映射表 包含的头文件：

#include <unordered_map>

实例1：unordered_map使用1

unordered_map<int,string> map1;
map1.insert(make_pair(1000,"张三"));//打包成键值对
map1.insert(make_pair(1010,"李四"));
map1.insert(make_pair(1020,"王五"));

map1.insert(make_pair(1000,"王五"));

cout << map1.size() << endl;//键值对个数

测试成功：unordered_map不允许重复。

实例2：unordered_multimap使用

unordered_multimap<int,string> map1;
map1.insert(make_pair(1000,"张三"));//打包成键值对
map1.insert(make_pair(1010,"李四"));
map1.insert(make_pair(1020,"王五"));

map1.insert(make_pair(1000,"王五"));

cout << map1.size() << endl;//键值对个数

测试成功：unordered_multimap允许重复值。

实例3：unordered_map使用2

unordered_map<int,string> map1;
map1.insert(make_pair(1000,"张三"));//打包成键值对
map1.insert(make_pair(1010,"李四"));
map1.insert(make_pair(1020,"王五"));

map1.insert(make_pair(1030,"王五"));

cout << map1.size() << endl;//键值对个数
//map operator[](key) =>value
cout << map1[1000] << endl;

测试成功：unordered_map提供[]运算符重载查询。

unordered_map<int,string> map1;
map1.insert(make_pair(1000,"张三"));//打包成键值对
map1.insert(make_pair(1010,"李四"));
map1.insert(make_pair(1020,"王五"));

map1.insert(make_pair(1030,"王五"));

map1.erase(1020);//删除
map1[2000] = "刘帅";//相当于插入
map1[1000] = "张三2";//相当于修改操作

cout << map1.size() << endl;//键值对个数
//map operator[](key) =>value 查询
cout << map1[1000] << endl;

测试成功：

实例4：查找

auto it1 = map1.find(1030);
if (it1 != map1.end())
{
	cout << "key:" << it1->first << "value:" << it1->second << endl;
}

测试成功：

1.3海量数据

案例1：。

const int ARR_LEN = 1000;
int arr[ARR_LEN] = {0};
for (int i=0; i<ARR_LEN; i++)
{
	arr[i] = rand()%20 + 1;
}
//上面的1000个整数中，统计哪些数字重复了，并且统计数字重复的次数
unordered_map<int, int> map1;
for (int k : arr)
{
	/*auto it = map1.find(k);
	if (it == map1.end())//数字没出现过
	{
		map1.insert(make_pair(k,1));
	}
	else
	{
		it->second++;
	}*/
	map1[k]++;
}

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

查询成功：

案例2：海量数据去重。

const int ARR_LEN = 1000;
int arr[ARR_LEN] = {0};
for (int i=0; i<ARR_LEN; i++)
{
	arr[i] = rand()%20 + 1;
}
	
//上面的整数中，将数字进行去重打印
unordered_set<int> set;
for (int v : arr)
{
	set.insert(v);
}

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

去重成功：

二、有序关联容器

有序关联容器：底层为，里面，。 有序关联容器包含的头文件：

#include <map>
#include <set>

set：单重集合，重复的只出现一次，从小到大元素有序排列(红黑树的中序遍历)。 multiset:：多重集合，可以存储重复的元素，从小到大元素有序排列。 map：单重映射表，重复的只出现一次，从小到大元素有序排列。 multimap：多重映射表，可以存储重复的元素，从小到大元素有序排列。

无序关联容器与有序关联容器用法几乎都是一样的。我们直接看实例： 实例1：set实例

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

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

测试成功：

实例2：set存放自定义类型

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

测试成功：

实例3：map实例

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(make_pair(1010,Student(1010,"张文")));
	stuMap.insert(make_pair(1020,Student(1020,"李广")));
	stuMap.insert(make_pair(1030,Student(1030,"高阳")));

	//stuMap.erase(it) stuMap.erase(1020)
	//cout << stuMap[1020] << endl;
	auto it = stuMap.begin();
	for (; it!=stuMap.end(); ++it)
	{
		cout << "key:" << it->first << "value:" << it->second << endl;
	}
	cout << endl;

	return 0;
}

总结

最后对我们常用的容器简单总结下：

在这里插入图片描述
在这里插入图片描述
Copyright © 2024 张威