第11章 关联容器

关联容器类型

map   关联数组；保存键值对

set   关键字即值

multimap   关键字可重复出现的map

multiset   关键字可重复出现的set

unordered_   在上述名字前加上unordered_；无序集合（用哈希函数来组织元素）

 

使用关联容器

pair类型

pair定义在头文件utility中。

pair上的操作

pair<T1, T2> p   p是一个pair，两个成员都进行了值初始化

pair<T1, T2> p(v1, v2)   分别用v1、v2进行初始化

pair<T1, T2> p = {v1, v2}   同上

make_pair(v1, v2)   返回一个由v1、v2初始化的pair

p.first   p.second   获取（公有）数据成员

p1 relop p2   relop是关系运算符（<、>、<=、>=）；按字典序比较，通过元素的<运算符实现

p1==p2   p1!=p2   当first、second成员分别相等时，两个pair相等；利用元素的==运算符实现

 

关联容器操作

除第9章列出的类型之外，关联容器还定义了额外的类型别名。

key_type   此容器类型的关键字

mapped_type   每个关键字关联的值的类型；只适用于map

value_type    对于set与key_type相同（set中保存的值就是关键字）；对于map，为pair<const key_type, mapped_type>

 

对于map而言，value_type是一个pair类型，其first成员保存const的关键字，second成员保存值。我们能改变一个pair的值，但不能改变关键字成员的值。

解引用一个关联容器的迭代器时，会得到一个类型为容器value_type的值的引用。

例子：

　　map<string, int> mp = {{"hello", 5}};
　　auto it = mp.begin();   //PS：*it是一个指向pair<const string, int>对象的引用
　　cout<< it->first <<" "<< it->second <<endl; //输出“hello 5”

 

set的迭代器是const的。虽然set类型同时定义了iterator和const_iterator类型，但两种类型都只允许只读访问set中的元素。

set中的关键字也是const的。

 

当一个迭代器遍历一个map、multimap、set、multiset时，迭代器按关键字升序遍历元素。

 

关联容器的insert操作

c.insert(v)   c.emplace(args)   对于map、set，只有当元素的关键字不在c中时才插入（或构造）元素；函数返回一个pair，包含一个迭代器（指向具有指定关键字的元素），以及一个bool值（指示插入是否成功）；对于multimap、multiset，总会插入（或构造）元素，并返回一个指向新元素的迭代器。

c.insert(p, v)   c.emplace(p, args)    类似c.insert(v)或c.emplace(args)，但将迭代器p作为一个提示，指出从哪里开始搜索新元素应该存储的位置；返回一个迭代器，指向具有给定关键字的元素

c.insert(b, e)   c.insert(li)   将迭代器[b,e)范围或花括号列表li的值插入；返回void

 

向map添加元素

对一个map进行insert操作时，必须记住元素类型是pair。

向map插入元素的4中方法：

c.insert({"hi", 2}) //C++11

c.insert(make_pair("hi", 2))

c.insert(pair<string, int>("hi", 2))

c.insert(map<string, int>::value_type("hi", 2))

 

删除元素

c.erase(k)   删除关键字为k的元素；返回一个size_type类型的值，指出删除的元素的数量

c.erase(p)   删除迭代器p指向的元素；返回指向p之后元素的迭代器

c.erase(b,e)    删除迭代器[b,e)范围的元素；返回迭代器e

 

map的下标操作

仅map和unordered_map提供下标运算符和at函数。

c[k]   返回关键字为k的元素；若k不在c中，添加一个关键字为k的元素，对其进行值初始化

c.at(k)   访问关键字为k的元素；若k不在c中，抛出out_of_range异常

 

例子：当关键字不在map中时

　　word_count["hi"] = 1;

在word_count中搜索关键字为"hi"的元素，未找到；

将一个新的键值对插入到word_count中，关键字是一个const string，保存"hi"；值进行值初始化，本例为0；

再提取新插入的元素，并将值1赋给它。

PS：如上，由于下标运算可能要插入一个新元素，故只能对非const的map或unordered_map使用下标操作。（at操作也只适用于非const的map或unordered_map）

 

通常情况下，解引用一个迭代器所返回的类型与下标运算符返回的类型是一样的，但对map则不然；

当对一个map进行下标操作时，会获得一个mapped_type对象；但当解引用一个map迭代器时，会得到一个value_type对象。

 

访问元素

在一个关联容器中查找元素的操作

c.find(k)   返回一个迭代器，指向第一个关键字为k的元素，若k不在c中，则返回尾后迭代器

c.count(k)   返回关键字等于k的元素数量

c.lower_bound(k)   返回一个迭代器，指向第一个关键字>=k的元素

c.upper_bound(k)   返回一个迭代器，指向第一个关键字>k的元素

c.equal_range(k)   返回一个pair，包含两个迭代器，表示关键字等于k的元素范围；若k不存在，pair的两个成员都为c.end()

PS：lower_bound、upper_bound不适用于无序容器

 

如果元素不在multimap中，则lower_bound、upper_bound会返回相等的迭代器：一个指向不影响排序的关键字插入位置。

 

无序容器

C++11定义了4个无序关联容器，这些容器不是使用比较运算符来组织元素，而是使用哈希函数和关键字类型的==运算符。

在关键字类型没有明显的序关系的情况下，或者维护元素的序代价很高时，可用无序容器。

无序容器在存储上组织为一组桶；无序容器的性能依赖于哈希函数的质量、桶的数量和大小。

 

无序容器管理操作

桶接口

c.bucket_count()   正在使用的桶的数目

c.max_bucket_count()   容器能容纳的最多的桶的数量

c.bucket_size(n)   第n个桶中有多少个元素

c.bucket(k)   关键字为k的元素在哪个桶中

桶迭代

local_iterator   可以用来访问桶中元素的迭代器类型

const_local_iterator   桶迭代器的const版本

c.begin(n)   c.end(n)   桶n的首元素迭代器和尾后迭代器

c.cbegin(n)   c.cend(n)   返回const_local_iterator

哈希策略

c.load_factor()   每个桶的平均元素数量；返回float

c.max_load_factor()   c试图维护的平均桶大小；返回float；c会在需要时添加新的桶，使得load_factor<=max_load_factor

c.rehash(n)   重组存储；使得bucket_count>=n且bucket_count>size/max_load_factor

c.reserve(n)   重组存储；使得c可以保存n个元素且不必rehash

 

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有