C++ STL关联式容器简介

前面我们已经把序列式容器全部学习了，包括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值进行字典序排序，所以我们能够输出一段完整的话：

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