3.7-STL(七)(map篇)

1. ### 这里重点学习map
2. ### 在实际做题过程中,multimap几乎用不到
3. ### 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;

1. Key:表示存储在map中的键(key)的类型
2. T:表示存储在map中的值(value)的类型
3. Compare:表示用于比较键的函数对象的类型,默认为less,使用键类型的默认比较函数
4. 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;

1. Key:表示存储在multimap中的键(key)的类型
2. T:表示存储在multimap中的值(value)的类型
3. Compare:表示用于比较键的函数对象的类型,默认为less,使用键类型的默认比较函数
4. 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; }

输出: