[C++ 面试基础知识总结] 关联容器[C++ 面试基础知识总结] 关联容器

参考书籍：《c++ primer》

<a href="#c-%e9%9d%a2%e8%af%95%e5%9f%ba%e7%a1%80%e7%9f%a5%e8%af%86%e6%80%bb%e7%bb%93-%e5%85%b3%e8%81%94%e5%ae%b9%e5%99%a8">c 面试基础知识总结 关联容器</a>

<a href="#%e7%9b%ae%e5%bd%95">目录</a>

<a href="#%e5%85%b3%e8%81%94%e5%ae%b9%e5%99%a8%e7%b1%bb%e5%9e%8b">关联容器类型</a>

<a href="#%e5%85%b3%e8%81%94%e5%ae%b9%e5%99%a8%e6%a6%82%e8%bf%b0">关联容器概述</a>

<a href="#%e5%ae%9a%e4%b9%89%e5%85%b3%e8%81%94%e5%ae%b9%e5%99%a8">定义关联容器</a>

<a href="#%e5%85%b3%e9%94%ae%e5%ad%97%e7%b1%bb%e5%9e%8b%e7%9a%84%e8%a6%81%e6%b1%82">关键字类型的要求</a>

<a href="#pair">pair</a>

<a href="#%e5%85%b3%e8%81%94%e5%ae%b9%e5%99%a8%e6%93%8d%e4%bd%9c">关联容器操作</a>

<a href="#%e5%85%b3%e8%81%94%e5%ae%b9%e5%99%a8%e8%bf%ad%e4%bb%a3%e5%99%a8">关联容器迭代器</a>

<a href="#%e6%b7%bb%e5%8a%a0%e5%85%83%e7%b4%a0">添加元素</a>

<a href="#%e5%88%a0%e9%99%a4%e5%85%83%e7%b4%a0">删除元素</a>

<a href="#%e8%ae%bf%e9%97%ae%e5%85%83%e7%b4%a0">访问元素</a>

<a href="#%e6%97%a0%e5%ba%8f%e5%ae%b9%e5%99%a8">无序容器</a>

标准库共提供了8个关联容器

map 关联数组：保存关键字-值对

set 关键字即值，即只保存关键字的容器

multimap 关键字可重复出现的map

multiset 关键字可重复出现的set

unordered_map 用哈希函数组织的map

unordered_set 用哈希函数组织的set

unordered_multimap 用哈希函数组织,关键字可重复出现的map

unordered_multiset 用哈希函数组织,关键字可重复出现的set

map是关键字-值对的集合，通常被称为关联数组。关联数组与正常数组类似，不同之处在于其下标不必是整数，是一个关键字。而set就是关键字的简单集合。

map和set的关键字必须是唯一的，而multimap和multiset没有此限制

有序关联容器的关键字类型必须定义元素比较的方法，默认情况下，标准库使用关键字类型的<code>&lt;</code>运算符来比较两个关键字。也提供一个自定义的运算符。所提供的操作必须在关键字类型上定义一个严格弱序。即具备以下性质：

1.两个关键字不能同时“小于等于”对方。

2.如果k1“小于等于”k2，且k2“小于等于”k3，那么k1必须“小于等于”k3。

3.如果存在两个关键字，任何一个都不“小于等于”另一个，那么两个关键字“等价”，如果k1“等价于”k2，且k2“等价于”k3，那么k1必须“等价于”k3。

pair定义在头文件utility中，一个pair保存两个数据对象，类似容器，创建pair时必须提供两个类型名，pair的数据成员将具有对应的类型。

map和set的关键字都为常量，不能改变。

注意：由于关联容器关键字的const属性，不能讲关联容器传递给修改或重排容器元素的算法，所以通常不对关联容器使用泛型算法。

调用insert函数可向map或set中添加一个元素或一个范围，若元素关键字已经存在，则不会有任何操作。

insert函数的返回值类型pair&lt;指向指定关键字的迭代器,bool(成功标志)&gt;

例如上述map执行insert后返回的类型为pair

可以使用insert的返回值

对于multimap，multiset，insert函数不返回标志是否成功bool值，因为可以插入相同关键字的元素。

erase函数可以删除指定关键字的元素，迭代器所指的元素或者某个范围内的所有元素，返回值是实际删除的元素。

map和unordered_map可以采取下标的方式对其中与关键字相关联的值进行操作，而set只有关键字而没有与其关联的值，所以不支持下标。map下标的索引是关键字。

除了下标之外，还有其他的查找元素的方法。

无序关联容器不是使用比较运算法来组织元素，而是用一个哈希函数和关键字类型的==运算法。通常无序容器和其对应的有序容器是可以相互替换的，只是由于元素未按顺序存储，无序容器的输出通常会与有序容器不同。