C++学习笔记--关联容器

C++标准库提供8个关联容器：map、multimap、unordered_map、unordered_multimap、set、multiset、unordered_set、unordered_multiset，容器中元素的位置与元素加入容器的顺序无关。 1、不同容器的特点 map                    容器中的关键字是有序非重复的，每个元素类型是pair类型（《C++ Primer》第5版 p379），是一个key-malue对，关键字起到索引的作用，值则表示与索引相关联的数据 multimap            允许容器中的关键字是重复的 unordered_map        容器中的关键字是无序的 unordered_multimap    无序、允许重复关键字的容器 set                    容器中的关键字是有序非重复的，与map不同，set中只有关键字，其他一样 multiset unordered_set unordered_multiset 2、容器选择原则 （1）先选择主要类型map还是set，如果只需要关键字，选择set，否则选择map； （2）根据是否要求无序或重复进一步选择。 3、容器通用操作（以map为例，set类似） （1）构造函数 map<T> m1;                m1是一个空map，它潜在的元素是T类型的，执行默认初始化 map<T> m2(m1);            m2中包含有m1所有元素的副本，m2与m1的T必须相同 map<T> m2 = m1;            等价于m2(m1)，复制初始化 map<T> m3{a,b,c...};        m5包含了右边列表中的元素 map<T> m3 = {a,b,c...};    等价于m5{a,b,c...}，复制初始化 map<T> m4(b,e);            将迭代器b、e指定范围内的元素拷贝到m6 （2）访问 range for语句         迭代器                 下标m[k]            返回关键字为k的元素，如果k不在m中，则会自动添加一个关键字为k的元素，并进行值初始化。 下标m.at(k)            同上，但是若k不在m中，将抛出一个out_of_range异常       注意，下标的含义是通过关键字获取值，set只有关键字，multimap和unordered_multimap有多个值与关键字相关联，所以只有map和unordered_map可以使用下标。

由于使用下标操作m[k]会使一个关键字不在m中的元素被添加进去，所以不能用下标来检测一个元素是否存在，因此关联容器定义了下面的一些查找操作。

m.find(k)            返回一个迭代器，指向第一个关键字为k的元素，若k不存在，则返回尾后迭代器 m.count(k)            返回关键字为k的元素的数量 m.lower_bound(k)    返回一个迭代器，指向第一个关键字不小于k的元素 m.upper_bound(k)    返回一个迭代器，指向第一个关键字大于k的元素 m.equal_range(k)    返回一个迭代器pair，表示关键字等于k的范围，若k不存在，pair的两个成员均等于m.end() （3）插入 m.insert(v)            拷贝插入元素v，对于mat和set，函数返回插入是否成功的bool值，对于multi*,返回指向新元素的迭代器 c.emplace(args)        构造插入args表示的元素 m.insert(b,e)        b和e是迭代器，表示一个key-value类型值的范围 m.insert(i1)        插入花括号列表i1中的元素 m.insert(p,v)        拷贝插入元素v，但是迭代器p仅作为一个提示，指出从哪里开始搜索新元素应该存放的位置 m.emplace(p,args)    构造插入args表示的元素 （4）删除 m.earse(k)            删除每个关键字为k的元素，返回删除的元素的数量：0、1、大于1 m.earse(p)            删除迭代器p指定的元素，p必须指向一个真实元素，不能是m.end() m.earse(b,e)        删除迭代器b和e所指定范围的元素，返回e （5）获取迭代器 begin()、end()、cbegin()、cend()、rbegin()、rend()、crbegin()、crend()（c表示const迭代器，r表示反向迭代器） （6）类型别名 iterator、const_iterator、remerse_iterator、const_remerse_iterator、 size_type、difference_type、malue_type、reference、const_reference、 key_type、mapped_type（只适用于map）、value_type（对于set，与key_type相同，对于map，为pair类型） 4、无序关联容器       有序关联容器中的关键字是有序排列的，所以要求关键字可以进行<运算符比较或满足自定义的比较操作。无序关联容器不是使用比较运算符来组织元素，而是使用一个哈希函数和关键字类型的==运算符。       无序容器可以使用上述所有的与有序容器相同的操作，由于无序容器在存储上组织为桶，每个桶保存零个或多个元素，容器的性能依赖于哈希函数的质量和桶的数量和大小，因此无序容器多了一些哈希函数和桶相关的操作。 （1）桶接口 m.bucket_count()        正在使用的桶的数目 m.max_bucket_count()    容器能容纳的最多的桶的数量 m.bucket_size(n)        第n个桶中有多少个元素 m.bucket(k)                关键字为k的元素在哪个桶 （2）桶迭代 local_iterator            可以用来访问桶中元素的迭代器类型 const_local_iterator    桶迭代器的const版本 m.begin(n)、m.end(n)    桶n的首元素迭代器和尾后迭代器（n是什么类型？） m.cbegin(n)、m.cend(n)    与前两个函数类似，但返回const_local_iterator （3）哈希策略 m.load_factor()            每个桶的平均元素数量，返回float值 m.max_load_factor()        m试图维护的平均桶大小，返回float值，要求创建的新桶的load_factor<=max_load_factor m.rehash(n)                重新存储，使得bucket_count>=n，且bucket_count>size/max_load_factor m.reserve(n)            重新存储，使得m可以保存n个元素且不必rehash （重新存储的意思是重新调整哈希策略？这点没有搞明白）