3.7-STL(七)(map篇)

### 这里重点学习map### 在实际做题过程中,multimap几乎用不到### unordered_map拥有极好的平均时间复杂度和极差的最坏时间复杂度,所以他的时间复杂度是不稳定的,unordered_map一般用不到,要做一个了解1.mapmap是一种关联容器,用于存储一组键值对(key-value pairs),其中每个键(key)都是唯一的map容器根据键来自动进行排序,并且可以通过键快速查找对应的值map容器使用红黑树(Red-Black Tree)数据结构来实现,具有较快的插入,删除和查找操作的时间复杂度0(logn)map的定义和结构如下:template class Key, class T,class Compare lessKey, class Allocatorallocatorpairconst Key, T class map;Key:表示存储在map中的键(key)的类型T:表示存储在map中的值(value)的类型Compare:表示用于比较键的函数对象的类型,默认为less,使用键类型的默认比较函数Allocator:表示用于分配内存的分配器类型,默认为allocator2.multimapmultimap是一种关联容器,类似于map,但允许存储多个具有相同键的键值对multimap容器根据键来自动进行排序,并且可以通过键快速查找对应的值multimap容器使用红黑树(Red-Black Tree)数据结构来实现,具有较快的插入,删除和查找操作的时间复杂度multimap的定义和结构如下:template class Key,class T,class Compare lesskey, class Allocatorallocatorpairconst Key,T class multimap;Key:表示存储在multimap中的键(key)的类型T:表示存储在multimap中的值(value)的类型Compare:表示用于比较键的函数对象的类型,默认为less,使用键类型的默认比较函数Allocator:表示用于分配内存的分配器类型,默认为allocator3.unordered_mapunordered_map是一种关联容器,用于存储一组键值对(key-value pairs),其中每个键(key)都是唯一的与map和multimap不同,unordered_map不会根据键的顺序进行排序,而是使用哈希函数将键映射到存储桶中,这使得unordered_map具有更快的插入,删除和查找操作的时间复杂度,但不保证元素的顺序unordered_map的定义和结构如下:template class Key, class T, class Hash hashKey, class KeyEqualequal_toKey, class Allocatorallocatorpairconst Key,T class unordered_map;Key:表示存储在unordered map中的键(key)的类型。T:表示存储在unordered map中的值(value)的类型。Hash:表示用于计算键的哈希值的函数对象的类型,默认为hash,使用键类型的默认哈希函数KeyEqual:表示用于比较键的函数对象的类型,默认为equal_to,使用键类型的默认比较函数Allocator:表示用于分配内存的分配器类型,默认为allocator### 一般情况下我们更愿意使用复杂度稳定的map而不是unordered map4.代码示例map#includeiostream #includemap using namespace std; int main(){ //创建并初始化map mapint,stringmyMap{{1,Apple},{2,Banana},{3,Orange}}; //插入函数 myMap.insert(make_pair(4,Grapes)); //查找和访问元素 coutValue at key 2:myMap[2]\n; //遍历并打印map中的元素 for(const autopair:myMap){ coutKey:pair.first,Value:pair.second\n; } //删除元素 myMap.erase(3); //判断元素是否存在 if(myMap.count(3)0){ coutKey 3 not found.\n; } //清空map myMap.clear(); //判断map是否为空 if(myMap.empty()){ coutMap is empty.\n; } return 0; }### 一般不会手动初始化### insert那行也可以这样写myMap.insert({Key,Value}### 注意myMap[3]0时,这个count(3)依然是不为0的,因为它的键值对存在,只不过值为0输出:multimap#includeiostream #includemap using namespace std; int main(){ //创建并初始化 multimap multimapint,stringmyMultimap{{1,Apple},{2,Banana},{2,Orange}}; //插入元素 myMultimap.insert(make_pair(3,Grapes)); //查找和访问元素 auto rangemyMultimap.equal_range(2); for(auto itrange.first;it!range.second;it){ coutKey:it-first,Value:it-second\n; } //遍历并打印multimap中的元素 for(const autopair:myMultimap){ coutKey:pair.first,Value:pair.second\n; } //删除元素 myMultimap.erase(2); //判断元素是否存在 if(myMultimap.count(2)0){ coutKey 2 not found.\n; } //清空multimap myMultimap.clear(); //判断multimap是否为空 if(myMultimap.empty()){ coutMultimap is empty.\n; } return 0; }### 因为它允许有多个相同键,所以它就不能用[ ]来取出,要用equal_range(Key); //range它表示迭代器的一个范围,range.first就是起始迭代器,range.second就是终止迭代器的下一位输出:unordered_map#includeiostream #includeunordered_map using namespace std; int main(){ //创建并初始化unordered_map unordered_mapstring,intmyMap{{Apple,3},{Banana,5},{Orange,2}}; //插入元素 myMap.insert(make_pair(Grapes,4)); //查找和访问元素 coutValue for key Banana:myMap[Banana]\n; //遍历并打印undordered_map中的元素 for(const autopair:myMap){ coutKey:pair.first,Value:pair.second\n; } //删除元素 myMap.erase(Orange); // 判断元素是否存在 if(myMap.count(Orange)0){ coutKey Orange not found.\n; } //清空undorderd_map myMap.clear(); //判断undorderd_map是否为空 if(myMap.empty()){ coutUnordered_map is empty.\n; } return 0; }输出: