11.关联容器

关联容器和顺序容器有着根本的不同:关联容器中的元素是按关键字来保存和访问的。与之相对,顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的。

关联容器的主要包括$map$和$set$两大类，标准库提供8个关联容器。这8个关联容器间的不同主要体现在以下三个维度

或者是一个$set$或者是一个$map$
或者要求不重复的关键字，或者允许重复的关键字
按顺序保存元素或者无序保存

按关键字有序保存元素	说明	头文件
$map$	关联数组，保存关键字-值对	$map$
$set$	关键字即值，即保存关键字的容器	$set$
$multimap$	关键字可以重复的$map$	$map$
$multiset$	关键字可以重复的$set$	$set$
无序集合
$unordered_map$	用哈希函数组织的$map$	$unordered_map$
$unordered_set$	用哈希函数组织的$set$	$unordered_set$
$unordered_multimap$	用哈希函数组织的$map$,关键字可以重复	$unordered_map$
$unordered_multiset$	用哈希函数组织的$set$,关键字可以重复	$unordered_set$

11.1关联容器概述

11.1.1定义关联容器

定义$map$的时候需要指明关键字类型以及值的类型，而定义$set$的时候只需要指明关键字类型造函数,每个关联容器都有自己的默认构造函数。它创建一个指定类型的空容器。我们也可以将关联容器初始化为另一个同类型容器的拷贝,或是从一个值范围来初始化关联容器,只要这些值可以转化为容器所需类型就可以。在新标准下,我们也可以对关联容器进行值初始化:

int main(int argc, const char * argv[]) {
    map<int,int>empty;//空容器
    map<int,int>exclude={ {1,2},{3,4}};//列表初始化
    set<int>myset={1,2,3,4,5,6};//列表初始化
    return 0;
}

对于$multiset$和$multimap$来说，可以允许重复的数值，这里以$multiset$为例

int main(int argc, const char * argv[]) {
    vector<int>nums={1,1,2,2,3,3,4,4};
    set<int>s(nums.begin(),nums.end());//大小为4
    multiset<int>ms(nums.begin(),nums.end());//大小为8
    return 0;
}

11.1.2pair类型

$pair$被定义在头文件$utility$中，$pair$保存两个数据成员，定义的时候需要声明成员类型，分别命名为$first$和$second$。操作如下

11.2关联容器操作

下表中的的类型表示了关联容器中关键字和值类型。

获取方式为

set<int>::key_type s1;//s1为int
set<int>::value_type s2;//s2为int
map<int,string>key_type m1;//m1为int
map<int,string>value_type m2;//m2为pair<const key_type,mapped_type>也就是pair<const int,string>
map<int,string>mapped_type m3;//m3为string

11.2.1关联容器迭代器

当解引用一个关联容器的迭代器的时候，我们得到的是类型为容器的$value_type$的值的引用，对于$map$我们得到的是一个键值对。对于$set$,它的迭代器是$const$的，只可以读，不可以修改

int main(int argc, const char * argv[]) {
    set<int>a={1,2,3,4};
    set<int>::iterator it=a.begin();
    //*it=5;//这个是错误的，不能修改
    cout<<*it;//这个对的可以读
    return 0;
}

11.2.2添加元素

int main(int argc, const char * argv[]) {
    set<int>a;
    a.insert(1);//直接插入
    vector<int>v={1,2,3};//重复的不要紧，会忽略
    a.insert(v.begin(),v.end());
    a.insert({6,5});
    map<int,int>b;
    b.insert({1,1});
    b.insert(make_pair(1, 1));
    b.insert(map<int,int>::value_type(1,1));
    b.insert(pair<int,int>(1,1));
    return 0;
}