cpp学习-第九章-顺序容器

发表于 | 分类于

核心简记

容器分为顺序容器(不依赖值，与元素加入位置对应)、有序与无序关联容器(根据关键字的值存储)。标准库的容器性能很好

顺序容器类型:在添加删除与查找方面代价侧重不同。

  1. vector:可变大小数组，随机访问，尾部插入快。 空间不够时分配更大的，并拷贝
  2. deque:双端队列，随机访问，头尾插入快 。 一段一段的连续空间链接起来，deque采用一块map（非STL中的map）作为主控，map是一块小的连续空间，其中每个元素都是指针，指向一块较大的线性连续空 间，称为缓冲区。而缓冲区才是存储deque元素的空间主体。
  3. list:双向链表，双向顺序访问，任意插入快 。 底层数据结构为双向循环链表
  4. forward_list:单向链表，单向顺序访问，任意插入快
  5. array:固定大小数组，随机访问，不可改动大小
  6. string:与vector相似，专门保存字符。

容器上的操作层次:

  1. 所有容器类型提供
  2. 仅针对顺序、关联或无序容器
  3. 只适用小部分容器

每个容器定义在头文件中，文件名与类型名相同。均为模板类

所有容器都适用的操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
类型别名:
    iterator 此容器的迭代器类型
    const_iterator 只可读取的迭代器
    size_type 无符号整行，足够保存容器大小
    difference_type 带符号整形，俩个迭代器的距离
    value_type 元素类型
    reference 元素左值类型 为value_type&
    const_reference 元素的const左值类型
构造函数:
    C c 默认构造，空容器
    C c(c1) 拷贝构造  与C c=c1构造没区别，不是类型转化拷贝，直接构造
    C c(b,e) 迭代器b-e拷贝构造，array不可
    C c{...} 列表初始化  ={...}相同
    顺序容器才有的:
        C c(n) 接受大小参数，值初始化
        C c(n,t) 大小初始化，值为t
赋值与swap 整体
    c1=c2 c1元素替换为c2
    c1={a,b,c} c1元素替换为列表中元素
    c1.swap(c2) 交换元素，整体
    swap(c1,c2) 同上
    assign不适用于关联容器与array  作用是从一个不同但相容的类型赋值
        c.assign(b,e) 替换为迭代器范围
        c.assign({...}) 替换为列表内容
        c.assign(n,t) 替换为n个t 
大小
    c.size() c中元素的数目
    c.max_size() c可保存最大元素数目
    c.empty() 判断是否空，空为true
添加删除
    c.insert(...) 拷贝元素进c
    c.emplace(...) 构造c中的一个元素
    c.erase(...) 删除指定元素
    c.clear() 删除c中所有元素
关系
    == !=
    < <= > >=
迭代器
    c.begin() c.end() 返回首与尾后迭代器，含const重载
    c.cbegin() c.cend() 返回const_iterator
反向
    reverse_iterator 逆序迭代器
    const_reverse_iterator 只读逆序迭代器
    c.rbegin() c.rend() 返回首前与尾迭代器，含const重载
    c.crbegin() c.crend() 返回const_reverse_iterator

迭代器是仿指针的类实现，标准库使用范围是左闭右开[)，原因:

  1. begin与end相等则范围为空
  2. b与e不等则至少含一个元素
  3. b递增若干可等于e

这样在许多算法实现中都不用考虑区间问题。一旦改变容器大小，迭代器失效。虽然有的不会失效但防止错误需要时再细看。

拷贝构造类型必须相同，不过用迭代器构造时不必相同，可转化即可。
array的模板中大小也是类型一部分 array< int , 42 > 类型一部分。

容器的比较是进行元素的逐个比较，空<一切。元素以第一个不同的为整体比较结果。元素需要定义==与<

顺序容器操作

顺序容器添加:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
forward_list有自己版本的添加删除,不支持back操作。
vector与string不支持front操作
c.push_back(t) 在c的尾部创建t
c.emplace_back(args) 在c的尾部由args构造元素
c.push_front(t) 头部
c.emplace_front(args) 
c.insert(p,t)  迭代器p前插入t，返回指向新添加元素的迭代器
c.emplace(p,args) 由参数构造
c.insert(p,n,t) n个t返回添加的第一个的迭代器
c.insert(p,b,e) b-e添加。
c.insert(p,{}) 列表插入

传入元素对象时传入的是拷贝。emplace版本是直接构造。
deque保证容器首尾插入删除都是常数时间。

访问操作:

1
2
3
4
5
6
下标只适用于string、vector、deque、array
back不适用于forward_list
    c.back() 返回c中尾元素的引用
    c.front() 返回c中首元素引用
    c[n] 返回下标为n的引用。
    c.at(n) 带检查的下标使用

引用，为左值。auto只能当类型的前半部分，不会自动加&。左值给auto时防止拷贝要加&。

删除元素:

1
2
3
4
5
6
forward_list 不支持back操作，vector与string不支持front
    c.pop_back() 删除尾
    c.pop_front() 删除首
    c.erase(p) 删除迭代器p所指的元素，返回被删元素之后的迭代器
    c.erase(b,e) 删除区间[b,e)返回之后
    c.clean() 删除c中所有

特殊的forward_list操作
因为forwa_list想添加删除必须改前节点，因此只能决定后节点动作。

1
2
3
4
5
6
7
8
9
10
11
lst.before_begin()　返回指向链表首元素之前并不存在的元素的迭代器，此迭代器不能解引用。
lst.cbefore_begin()　cbefore_begin()返回一个const_iterator
lst.insert_after(p,t)　在迭代器p之后的位置插入元素。t是一个对象，n是数量，b和e是表示范围的一对迭代器（b和e不能指向lst内），il是一个花括号列表。返回一个指向最后一个插入lst.insert_after(p,n,t) 元素的迭代器。如果范围为空，则返回p，若p为尾后迭代器，则函数行为未定义。
lst.insert_after(p,b,e)
lst.insert_after(p,il)
emplace_after(p,args)　使用args在p指定的位置之后创建一个元素，返回一个指向这个新元素的迭代器。若p为尾后迭代器，则函数的行为未定义
lst.erase_after(p)　　 删除p指向的位置之后的元素，或删除从b之后直到（但不包含）e之间的元素。返回一个指向被删除元素之后元素的迭代器，若不存在这样的元素，则返回尾后迭代
lst.erase_after(b,e)　　器，如果p指向lst的尾元素或者是一个尾后迭代器，则函数的行为未定义

改变容器大小

1
c.resize(n) 调整大小为n，多余的元素被丢弃，不足的值初始化。可再加个参数t设初始值

vector特有

vector、string分配空间时往往分配比需求大的，因为每次超出都将全部拷贝，这样有效防止拷贝次数。
因此有:capacity操作告诉我们容器在不扩张内存空间的情况下可以容纳多少个元素

1
2
3
4
5
shrink_to_fit只适用于vector、string和deque
capacity和reserve只适用于vector和string
c.shrink_to_fit()    请将capacity减少为size相同大小
c.capacity()　　不重新分配内存空间的话，c可以保存多少元素
c.reserve(n)　　分配至少能容纳n个元素的内存空间,总大小

超过才分配

string特有

构造string的方法还有

1
2
3
4
n、len2和pos2都是无符号值
string s(cp,n) 　　　　s是cp指向的数组中的前n个字符的拷贝，此数组至少应该包含n个字符
string s(s2,pos2)　　  s是string s2从下标pos2开始的字符的拷贝。若pos2>s2.size(),构造函数的行为未定义
string s(s2,pos2,len2) s是string s2从下标pos2开始len2个字符的拷贝。若pos2>s2.size()，构造函数的行为未定义。不管len2的值是多少，构造函数至多拷贝s2.size()-pos2个字符

子字串

1
s.substr(pos,n)　返回一个string，包含s中从pos开始的n个字符的拷贝。pos的默认值为0。n的默认值的s.size()-pos，即拷贝从pos开始的所以字符

改变str其它方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
s.insert(pos,args)　　　　在pos之前插入args指定的字符，pos可以是一个下标或者一个迭代器。接受下标的版本返回一个指向s的引用；接受迭代器的版本返回指向第一个插入字符的迭代器
s.erase(pos,len)　　　　  删除从位置pos开始的len个字符。如果len被省略，则删除从pos开始直至s末尾的所有字符。返回一个指向s的引用
s.assign(args)　　　　　  将s中的字符替换为args指定的字符。返回一个指向s的引用
s.append(args)　　　　　将args追加到s。返回以指向s的引用
s.replace(range,args)     删除s中范围range内的字符，替换为args指定的字符。range或者是一个下标和一个长度，或者是一对指向s的迭代器，返回一个指向s的引用
 
args可以是下列形式之一：append和assign可以使用所有形式：
str不能与s相同，迭代器b和e不能指向s
str 　　　　　　　　　　　字符串str
str,pos,len　　　　　　　str中从pos开始最多len个字符
cp,len　　　　　　　　　 从cp指向的字符数组的前（最多）len个字符
cp　　　　　　　　　　　cp指向的以空字符串结尾的字符数组
n,c　　　　　　　　　　  n个字符c
b,e　　　　　　　　　　 迭代器b和e指定的范围内的字符
初始化列表　　　　　　　花括号包围，以逗号分隔的字符列表
replace和insert所允许的args形式依赖于range和pos是如何指定的
replace　　　　　　replace　　　　　　insert　　　　　　　　insert　　　　　　　　　　args可以是
(pos,len,args)       (b,e,args)　　　　　(pos,args)　　　　　 (iter,args)
是　　　　　　　　　是　　　　　　　　　是　　　　　　　　　　否　　　　　　　　　　　　str
是　　　　　　　　　否　　　　　　　　　是　　　　　　　　　　否　　　　　　　　　　　　str,pos,len
是　　　　　　　　　是　　　　　　　　　是　　　　　　　　　　否　　　　　　　　　　　　cp,len
是　　　　　　　　　是　　　　　　　　　否　　　　　　　　　　否　　　　　　　　　　　　cp
是　　　　　　　　　是　　　　　　　　　是　　　　　　　　　　是　　　　　　　　　　　　n,c
否　　　　　　　　　是　　　　　　　　　否　　　　　　　　　　是　　　　　　　　　　　　b2,e2
否　　　　　　　　　是　　　　　　　　　否　　　　　　　　　　是　　　　　　　　　　　　初始化列表

搜索操作

1
2
3
4
5
6
7
8
9
10
11
12
13
搜索操作返回指定字符出现的下标，如果未找到则返回npos无符号-1
s.find(args)　　　　　　　　　　查找s中args第一次出现的位置
s.rfind(args)　　　　　　　　　 查找s中args最后一次出现的位置
s.find_first_of(args)　 　　　　在s中查找args中任何一个字符第一次出现的位置
s.find_last_of(args)    　　　　在s中查找args中任何一个字符最后一次出现的位置
s.find_first_not_of(args)　　  在s中查找第一个不存在args 中的字符
s.find_last_not_of(args)　　　在s中查找最后一个不在args中的字符
args必须是以下形式之一
c,pos 　　　　　　　　　　　　从s中位置pos开始查找字符c，pos默认为0
s2,pos　　　　　　　　　　　 从s中位置pos开始查找字符串s2，pos默认为0
cp,pos　　　　　　　　　　　 从s中位置pos开始查找指针cp指向的空字符结尾的C风格字符串，pos默认为0
cp,pos,n　　　　　　　　　　 从s中位置pos开始查找指针cp指向的数组的前n个字符。pos和n无默认值

compare
类似strcmp，根据s是等于、大于还是小于参数指定的字符串，s.compare返回0，正数和负数。其参数:

1
2
3
4
5
6
s2　　　　　　　　　　　比较s和s2
pos1,n1,s2　　　　　　 将s中从pos1开始的n1个字符与s2进行比较
pos1,,n1,s2,pos2,n2    将s中从pos1开始的n1个字符与s2中从pos2开始的n2个字符进行比较
cp　　　　　　　　　　　比较s与cp指向的以空字符结尾的字符数组
pos1,n1,cp　　　　　　 将s中从pos1开始的n1个字符和cp指向的以空字符结尾的字符数组进行比较
pos1,n1,cp,n2　　　　  将s中从pos开始的n1个字符与指针cp指向的地址开始的n2个字符进行比较

数据转化

1
2
3
4
5
6
7
8
9
10
to_string(val)　　　　　　　　　　一组重载函数，返回数值val的string表示。val可以是任何算术类型。对每个浮点类型和int或更大的整型，都有相应版本的to_string。
stoi(s,p,b)　　　　　　　　　　　　返回s的起始子串（表示整数内容）的数值。返回值类型是int、long、unsigned long、long long、unsigned long long。b表示转换所用的基数，默认值是10.p是size_t指针，用来stol(s,p,b)　　　　保存s中第一个非数值字符的下标，p默认是0，即，函数不保存下标
stoul(s,p,b)
stoll(s,p,b)
stoull(s,p,b)
stof(s,p) 　　　　　　　　　　　　返回s的起始子串（表示浮点数内容）的数值，返回值类型分别是float、double和long double，参数p的作用与整数转换中相同
stod(s,p)
stold(s,p)

容器适配器

三个顺序容器适配器:
stack 栈，要求back操作
queue 对列，要求back、front 先进先出
priority_queue 优先级队列，还要求随机访问 加入的会按优先级排序，使用元素的<确定
一个容器适配器接受已有的容器类型，使其行为看起来像不同的类型。只能使用适配器的操作，不能用原本容器的。

所以容器适配器都支持的操作和类型

1
2
3
4
5
6
7
8
9
10
size_type　　　　　　一种类型，足以保存当前类型的最大对象的大小
value_type　　　　　元素类型
container_type　　   实现适配器的底层容器类型
A a;　　　　　　　　  创建一个名为a的空适配器
A a(c);　　　　　　　创建一个名为a的适配器，带有容器c的一个拷贝
关系运算符　　　　　 每个适配器都支持所有关系运算符：==、！=、<、<=、>和>=，这些运算符返回底层容器的比较结果
a.empty() 　　　　　若a包含任何元素，返回false，否则返回true
a.size()　　　　　　 返回a中的元素数目
swap(a,b)　　　　　　　交换a和b的内容，a和b必须有相同的类型，包括底层容器类型也必须相同
a.swap(a,b)

使用: stack< int ,vector< int >> 第二个模板参数可选，stack、queue默认基于deque。priority_queue默认vector。

栈操作

1
2
3
4
5
栈默认是基于deque实现，也可以在list或vector上实现
s.pop() 　　　　　　删除栈顶元素，但不返回该元素的值
s.push(item)　　　 创建一个新元素压人栈顶，该元素通过拷贝或移动item而来，或者由args构造
s.emplace(args)　　
s.top()　　　　　　返回栈顶元素，但不将元素弹出栈

对列操作

1
2
3
4
5
6
7
8
9
10
queue默认基于deque实现，priority_queue默认基于vector实现；
queue也可以由list或vector实现，priority_queue也可以用deque实现
q.pop()  　　 　　　　删除queue的首元素或priority_queue的最高优先级的元素，但不删除此元素
q.front()  　　　　　　返回首元素或尾元素，但不删除此元素，只适用于queue
q.back()　　　　　　  
q.top()　　　　　　　返回最高优先级元素，但不删除该元素，只适用于priority_queue
q.push(item)　　　　在queue末尾或priority_queue中恰当的位置创建一个元素。其值为item，或者由args构造
q.emplace(args)

反汇编

这里没什么汇编上的新知识…主要是模板的汇编，在自定义模板时再分析。