c++关联容器

介绍

关联容器支持高效的关键字查找和访问。两个主要的关联容器类型是map和set。
map中的元素是关键字-值对：关键字起到索引的作用，值则表示与索引相关联的数据。
set中每个元素只包含一个关键字；set支持高效的关键字查找。
map与multimap定义在头文件map中；set与multiset定义在头文件set中；无序容器则定义在头文件unordered_map和unordered_set中。

操作

所有关联容器都支持普通容器的常用操作。但不支持顺序容器的位置相关操作。关联容器还支持一些顺序容器不支持的操作。

定义

当定义一个map时必须声明其关键字与值的数据类型，而定义set时只需要声明关键字的类型。
当初始化一个map时必须提供关键字与值的数据类型。每个键值对包括在{}中。如下：

1
2
3
4

map<T1,T2> map = { {key1,value1} ,{key2,value2},
    {key3,value3},{key4,value4},{key5,value5}};

set<T> set = {key1,key2,key3,key4};

关联容器对关键字有一定的要求，默认情况下其须支持’<’运算符。

pair类型

map的基础元素是pair。pair类型保存两个数据成员，类似容器。
其定义在头文件utility中。
以下是其操作：

关联容器操作

关联容器除了容器通用的类型，还定义了以下类型。

迭代器

当解引用一个关联容器的迭代器时，会得到一个类型为该容器的value_type的值的引用。
对map而言其value_type是一个pair，其first保存const的关键字，second成员保存值。
set虽然有两个版本的迭代器，但都是const的。
因为关联容器的迭代器中含有const的成员，所以无法使用修改或重排算法。泛型算法中的find效率不如其自带的find。
如果要对其使用算法可以使用copy算法将其复制到另一个序列中。

增删元素

对map进行insert操作时，必须记住元素类型是pair
insert(emplace)返回的值依赖于容器类型和参数。对于不包含重复关键字的容器，添加单一元素的版本返回一个pair，其first指向具有给定关键字的元素(pair类型)，其second成员是bool，若关键字已经在容器中insert(emplace)将什么都不会做且bool为false，若关键字不在，则元素被插入且bool为true。

map下标操作

map与unordred_map容器提供了下标运算符与对应的at函数。
而set不支持下标运算。

访问元素

参考资料

C++primer中文版(第五版) 电子工业出版社。