Tips for C++ Primer Chapter 11 关联容器

2018-06-17 21:39:17来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

第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
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:双冒号&quot;::&quot;

下一篇:lintcode_69_二叉树的层次遍历