前面我们已经把序列式容器全部学习了,包括array、vector、deque、list和 forward_list,本节我们将进行关联式容器的学习。那什么是关联式容器呢?在回答这个问题之前,读者是否还记得序列式容器查找和修改元素都是按什么条件进行的,答案是“位置”,不管是vector、deque还是 list,他们都是以线性容器的方式,依靠“位置”进行查找和删改;关联式容器并不依靠“位置”进行元素操作,而是通过key(键)的方式对值(value)进行快速操作,其特点就两字——高效!对于有序关联式容器(比如map,基于红黑树实现)其操作一个元素的时间复杂度为O(logn);对于无序关联式容器(如unordered_map,基于哈希表实现),其时间复杂度为O(1),能够快速地操作元素。(如果读者还不知道O(n)的话可自行跳转《“时间复杂度”- 衡量算法效率的核心指标》)读者可以想象一下军训的场景:第一次见到教官,同学们按高矮顺序整整齐齐地排成一队,此时有个同学走神了,没有对齐队伍,教官先数一下再说“从高到矮第几个同学你在干嘛,别开小火车!”;军训一个星期后,同学们和教官都很熟悉了,打成一片,当某个同学开小差时,教官直接叫他名字“某某同学,立正对齐!”此时教官不用再数数了,直接叫他名字,提高了教官调整队伍的效率,关联式容器就像教官直接叫你名字一样,靠名字(key键值)来调整方队,不用再从头到尾一个一个数了。

传统关联式容器有:map、set、multimap、multiset(注意,map包含multimap, set包含multiset,所以无需另外include头文件),其底层是红黑树结构,插入元素后会自动排序,其元素操作时间复杂度为O(logn)。multi的意思是多种,这里map、set容器严格要求key(键值)的唯一性,而multimap、multiset可以存在重复键值;在C++11后,关联式容器迎来新成员,unordered_map、unordered_set、unordered_multimap、unordered_multiset,(同理于前者,包含unordered_map就包含了unordered_multimap,unordered_set就包含了unordered_multiset,切勿另起头文件),他们的底层是基于哈希表实现,访问速度更快,在不发生哈希冲突的情况下其元素操作时间复杂度为O(1),毕竟空间换时间嘛,该有的效率肯定得有。

为了感受一下关联式容器,笔者这里拿map举个例子,简单实现map容器的增查操作,并通过迭代器访问元素:

#include<bits/stdc++.h>//万能头,以效率为中心 
#include<map>//包含头文件,养成好习惯 
#include<string>//包含头文件,养成好习惯 
/*map进行简单的增删查改 */
using namespace std;
void test()
{
map<int,string> mp; 
/*由于重载了'[]',直接通过mp[key键]= value值实现赋值 */
 mp[0] ="算法使人快乐!";
 mp[3]="万丈高楼平地起,一砖一瓦皆根基!";
 mp[2]="因为我知道:";
 mp[1]="我喜欢在Dotcpp上做算法题,";
 
 /*map是有序关联式容器,所以会自动根据key值进字典序排序*/ 
 /*老规矩,通过迭代器访问元素 不过map迭代器是根据:first-键   second-值 进行访问*/
 cout << "我们会看到map容器会自动根据key进行字典序排序,输出后所有的值为:\n" ; 
 for(map<int,string>::iterator it = mp.begin();it!=mp.end();++it) 
 {
  cout << it->second; 
 }
 
}
  
int main(){
    test();
    return 0;
}

可以看到,我们通过'[]'为map增加元素,通过迭代器实现元素访问,还知道map属于有序关联式容器,会自动根据key值进行字典序排序,所以我们能够输出一段完整的话:

简单操作map容器

那我们就简单完成了关联式容器的基本认识,了解到它比我们学过的序列式容器能更高效地操作元素,其元素储存方式为k-v结构(键值对),有有序和无序之分,怀揣着无比激动的心情,让我们开启下一节的学习吧。


点赞(0)

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:

一点编程也不会写的:零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码?手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

Dotcpp在线编译      (登录可减少运行等待时间)