cpp学习-第十一章-关联容器

发表于 | 分类于

核心简记

顺序容器:以位置保存元素。关联容器:以关键字保存元素

关联容器分为如下:
按map|set、有序|无序、不重复|重复

1
2
3
4
5
6
7
8
9
10
有序:
map 关联数组、有序、不重复
set 仅存关键字、有序、不重复
multimap 重复关键字的map
multiset 重复关键字的set
无序:
unordered_map 哈希组织的map
unordered_set 哈希组织的set
unordered_multimap 关键字可重复的hashmap
unordered_multiset 关键字可重复的hashset

map、multimap定义在map。set与multiset定义在set。无序定义在unordered_map与unordered_set中。
都是模板定义。

简单使用:

1
2
3
4
map<string,string> ls;//每个节点使用的是pair
ls["123"]="123";//不在会自动添加。
set<string> ls2={"132"};
ls2.find("123");//返回迭代器

c++对象构造:

1
2
A a(args);//显式 用args区别函数声明
A a=A(args);//隐式

用 A()可以调用构造返回匿名的对象。对类直接使用()为调用构造

关联容器概述

所有关联容器都支持之前定义的容器通用操作。
关联容器的迭代器都是双向的。

构造函数可:空、拷贝、迭代器范围拷贝、列表。非multi会自动去重复

对有序容器，要求关键字定义<。定义符合:俩个关键字不同时<=对方、可传递、俩个关键字不<=对方则相等。
可以传入比较函数:因为元素的操作类型属于容器类型的一部分，因此要提供此类型

1
2
3
bool comp(A &a,A &b)
{}
set<A,decltype(comp)*> ls(comp);//必修加*，因为decltype返回的是函数类型

pair:表示俩个数据成员，定义在utility

1
2
3
4
5
6
7
8
9
10
pair<T1,T2> p;          值初始化成员
pair<T1,T2> p(v1,v2);   指定初始化
pair<T1,T2> p={v1,v2};  等价上
make_pair(v1,v2)        返回自动推断的pair
p.first                 p的公有数据成员
p.second
p1 比较 p2              先判断first再判断second。使用元素<排序
p1==p2                  f与s都等则等
p1!=p2

注意其成员是public的

关联容器的操作

为有序与无序的通用操作。

类型

额外的类型:使用::

1
2
3
4
key_type    关键字类型
mapped_type 关键字关联的类型，只适用于map
value_type  全类型，对于set为key_type，对于map为pair<const key_type,mapped_type>
            注意key为const

迭代器

当解引用关联容器的迭代器，得到的类型为value_type的引用。
set的迭代器是const的。有序时迭代器按关键字升序遍历。
迭代器不适合泛型算法，可当做源或目的位置

添加元素

1
2
3
4
5
6
7
8
c.insert(v)         拷贝插入,要value_type类型
c.emplace(arg)      直接构造，对于不重复的只有不存在才插入，返回一个pair，f为指定关键字的迭代器，s为是否插入
c.insert(b,e)       多个插入，不重复的自动去重复
c.insert(il) 
c.insert(p,v)       p迭代器指出从哪开始搜索新元素的位置
c.emplace(p,arg)

删除元素

1
2
3
c.erase(k)      从c中删除每个关键字为k的元素，返回size_type，表示删除的数量
c.erase(p)      删除迭代器p指定的元素，返回p之后的迭代器
c.erase(b,e)    删除[b,e)范围的元素，返回e

下标操作

1
2
c[k]    返回关键字为k的元素，若不在则值初始化一个关键字k的元素。
c.at(k) 访问关键字k的元素，不在就抛出异常

如:a[1]=1;
将执行:

  1. 在a中找关键字1
  2. 未找到就将新关键字1插入，并值初始化
  3. 提出新插入的元素，将值1赋予

set不可，没有值。下标访问返回的是值，不是整体了。不想添加用find。

访问元素

1
2
3
4
5
6
c.find(k)           返回迭代器，指向第一个关键字为k的元素
c.count(k)          返回关键字等于k的数量
简化multi的，不用于无序
c.lower_bound(k)    返回迭代器，指向第一个关键字>=k的元素，不在会指向合适的插入点
c.upper_bound(k)    返回迭代器，指向第一个关键字>k的元素，不在会指向合适的插入点并等于上
c.equal_range(k)    返回迭代器pair，关键字等于k的范围，同上俩。无序可用，因为无序的关键字相同元素仍相邻

无序容器

无序容器特有一些操作，之前的是通用的，如迭代器仍然可以遍历，只不过顺序不保证。相同的关键字在无序中仍然相邻！
无序关联容器采用hash函数与关键字类型的==组织元素。新能依赖函数质量与桶数量大小。
无序容器管理操作

1
2
3
4
5
6
7
8
9
10
11
12
13
桶接口
c.bucket_count() - 返回使用桶的数量
c.max_bucket_count() - 返回桶的最大数量
c.bucket_size(n) - 返回在特定的桶中的元素数量 
c.bucket(key) -  返回带有特定键的桶 
桶迭代
local_iterator 访问桶中元素的迭代器类型，有const版本
c.begin(n),c.end(n) 桶n的首与尾后迭代器
*哈希策略*
c.load_factor() - 返回每个桶的平均元素数量，float
c.max_load_factor() -  试图维护的平均桶大小，float。会在需要时添加新的桶使lf<=mlf
c.rehash(n) -  重新存储，使得bucket_count>=n且bucket_count>size/mfl  
c.reserve(n)   重新存储，使c可以保存n个元素不必rehash

无序容器要求使用关键字的==与hash< key>类型的对象。每个标准库类型都有hash< type>。自定义的类型必须提供hash模板版本-见模板章节
在这里还可以自定义操作:

1
2
3
4
5
6
7
8
9
10
int hashls(A &a)
{
    return hash<string>()(a.a);//隐式构造，使用其调用运算符
}
bool eq(A &a,A&b)
{
    return a.a==b.b;
}
使用:
unordered_set<A,decltype(hashls)*,decltype(eq)*> nameset(42,hashls,eq);//参数：桶大小、哈希函数指针、相等条件

反汇编

无反汇编新知识。有一句感慨…cpp的语法操作大量渗透到了编译器的前端阶段，用的好的话确实无敌….