STL(七)(map篇)

### 这里重点学习map
### 在实际做题过程中,multimap几乎用不到
### unordered_map拥有极好的平均时间复杂度和极差的最坏时间复杂度,所以他的时间复杂度是不稳定的,unordered_map一般用不到,要做一个了解

1.map

map是一种关联容器,用于存储一组键值对(key-value pairs),其中每个键(key)都是唯一的
map容器根据键来自动进行排序,并且可以通过键快速查找对应的值
map容器使用红黑树(Red-Black Tree)数据结构来实现,具有较快的插入,删除和查找操作的时间复杂度0(logn)

map的定义和结构如下:

template <class Key, class T,class Compare =less<Key>,
    class Allocator=allocator<pair<const Key, T>>>
class map;

Key:表示存储在map中的键(key)的类型
T:表示存储在map中的值(value)的类型
Compare:表示用于比较键的函数对象的类型,默认为less,使用键类型的默认比较函数
Allocator:表示用于分配内存的分配器类型,默认为allocator

2.multimap

multimap是一种关联容器,类似于map,但允许存储多个具有相同键的键值对
multimap容器根据键来自动进行排序,并且可以通过键快速查找对应的值
multimap容器使用红黑树(Red-Black Tree)数据结构来实现,具有较快的插入,删除和查找操作的时间复杂度

multimap的定义和结构如下:

template <class Key,class T,class Compare =less<key>,
    class Allocator=allocator<pair<const Key,T>>>
class multimap;

Key:表示存储在multimap中的键(key)的类型
T:表示存储在multimap中的值(value)的类型
Compare:表示用于比较键的函数对象的类型,默认为less,使用键类型的默认比较函数
Allocator:表示用于分配内存的分配器类型,默认为allocator

3.unordered_map

unordered_map是一种关联容器,用于存储一组键值对(key-value pairs),其中每个键(key)都是唯一的
与map和multimap不同,unordered_map不会根据键的顺序进行排序,而是使用哈希函数将键映射到存储桶中,这使得unordered_map具有更快的插入,删除和查找操作的时间复杂度,但不保证元素的顺序

unordered_map的定义和结构如下:

template <class Key, class T, class Hash = hash<Key>,
    class KeyEqual=equal_to<Key>,
    class Allocator=allocator<pair<const Key,T>>>
class unordered_map;

Key:表示存储在unordered map中的键(key)的类型。
T:表示存储在unordered map中的值(value)的类型。
Hash:表示用于计算键的哈希值的函数对象的类型,默认为hash,使用键类型的默认哈希函数
KeyEqual:表示用于比较键的函数对象的类型,默认为equal_to,使用键类型的默认比较函数
Allocator:表示用于分配内存的分配器类型,默认为allocator

### 一般情况下我们更愿意使用复杂度稳定的map而不是unordered map

4.代码示例

map

#include<iostream>
#include<map>
using namespace std;
int main(){
	//创建并初始化map
	map<int,string>myMap={{1,"Apple"},{2,"Banana"},{3,"Orange"}};
	
	//插入函数
	myMap.insert(make_pair(4,"Grapes"));
	
	//查找和访问元素
	cout<<"Value at key 2:"<<myMap[2]<<"\n";
	
	//遍历并打印map中的元素
	for(const auto&pair:myMap){
		cout<<"Key:"<<pair.first<<",Value:"<<pair.second<<"\n";
	} 
	
	//删除元素
	myMap.erase(3);
	
	//判断元素是否存在
	if(myMap.count(3)==0){
		cout<<"Key 3 not found."<<"\n";
	} 
	
	//清空map
	myMap.clear();
	
	//判断map是否为空
	if(myMap.empty()){
		cout<<"Map is empty."<<"\n";
	} 
	
	return 0;
}

### 一般不会手动初始化
### insert那行也可以这样写myMap.insert({Key,Value}
### 注意myMap[3]=0时,这个count(3)依然是不为0的,因为它的键值对存在,只不过值为0

输出:

multimap

#include<iostream>
#include<map>
using namespace std;
int main(){
	//创建并初始化 multimap
	multimap<int,string>myMultimap={{1,"Apple"},{2,"Banana"},{2,"Orange"}};
	
	//插入元素
	myMultimap.insert(make_pair(3,"Grapes"));
	
	//查找和访问元素
	auto range=myMultimap.equal_range(2);
	for(auto it=range.first;it!=range.second;++it){
		cout<<"Key:"<<it->first<<",Value:"<<it->second<<"\n"; 
	}
	
	//遍历并打印multimap中的元素
	for(const auto&pair:myMultimap){
		cout<<"Key:"<<pair.first<<",Value:"<<pair.second<<"\n";
	} 
	
	//删除元素
	myMultimap.erase(2);
	
	//判断元素是否存在
	if(myMultimap.count(2)==0){
		cout<<"Key 2 not found."<<"\n";
	} 
	
	//清空multimap
	myMultimap.clear();
	
	//判断multimap是否为空
	if(myMultimap.empty()){
		cout<<"Multimap is empty."<<"\n";
	} 
	
	return 0;
}

### 因为它允许有多个相同键,所以它就不能用[ ]来取出,要用equal_range(Key); //range它表示迭代器的一个范围,range.first就是起始迭代器,range.second就是终止迭代器的下一位

输出:

unordered_map

#include<iostream>
#include<unordered_map>
using namespace std;
int main(){
	//创建并初始化unordered_map
	unordered_map<string,int>myMap={{"Apple",3},{"Banana",5},{"Orange",2}};
	
	//插入元素 
	myMap.insert(make_pair("Grapes",4)); 
	
	//查找和访问元素
	cout<<"Value for key 'Banana':"<<myMap["Banana"]<<"\n";
	
	//遍历并打印undordered_map中的元素
	for(const auto&pair:myMap){
		cout<<"Key:"<<pair.first<<",Value:"<<pair.second<<"\n";
	}  
	
	//删除元素
	myMap.erase("Orange");
	
	// 判断元素是否存在
	if(myMap.count("Orange")==0){
		cout<<"Key 'Orange' not found."<<"\n";
	} 
	
	//清空undorderd_map
	myMap.clear();
	
	//判断undorderd_map是否为空
	if(myMap.empty()){
		cout<<"Unordered_map is empty."<<"\n";
	} 
	
	return 0; 
}

输出: