C++ Primer学习笔记：(九)顺序容器

本章是第三章内容的扩展，完成本章的学习后，对标准库顺序容器知识的掌握就完整了。

元素在顺序容器中的位置与其加入容器时的位置相对应。标准库还定义了几种关联容器（第11章），关联容器中元素的位置由元素相关联的关键字决定。

顺序容器有：vector、deque、list、forward_list、array与string。
容器适配器有：stack、queue与priority_queue。

顺序容器概述（9.1，P292）

顺序容器类型	含义
vector	可变大小数组。支持快速随机访问。在尾部之外的位置插入或删除元素可能很慢
deque	双端队列。支持快速随机访问。在头尾位置插入/删除速度很快
list	双向链表。只支持双向顺序访问。在list中任何位置进行插入/删除操作速度都很快
forward_list	单向链表。只支持单向顺序访问。在链表任何位置进行插入/删除操作速度都很快
array	固定大小数组。支持快速随机访问。不能添加或删除元素。
string	与vector相似的容器，但专门用于保存字符。随机访问快。在尾部插入/删除速度快。

以下是一些选择容器的基本原则：

⑴.除非你有很好的理由选择其他容器，否则应使用vector

⑵.如果你的程序有很多小的元素，且额外开销很重要，则不要使用list或forward_list

⑶.如果程序要求随机访问元素，应使用vector或deque

⑷.如果程序需要在中间位置插入或删除元素，应使用list或forward_list

⑸.如果程序需要在头尾位置插入或删除元素，但不会在中间位置进行插入或删除操作，则使用deque

⑹.如果程序只有在读取输入时才需要再容器中间位置插入元素，随后需要随机访问元素，则

–首先，确定是否真的需要再容器中间位置添加元素。当处理输入数据时，通常可以很容易地向vector追加数据，然后再调用标准库的sort函数来重排容器中的元素，从而避免在中间位置添加元素。

–如果必须在中间位置插入元素，考虑在输入阶段使用list，一旦输入完成，将list中的内容拷贝到一个vector中。

容器库概览（9.2，P294）

本节介绍对所有容器都适用的操作。

容器操作表

类型别名
iterator	此容器类型的迭代器类型
const_iterator	可以读取元素，但不能修改元素的迭代器类型
size_type	无符号整数类型，足够保存此种容器类型最大可能容器的大小
different_type	带符号整数类型，足够保存两个迭代器之间的距离
value_type	元素类型
reference	元素的左值类型；与value_type含义相同
const_reference	元素的const左值类型

构造函数
C c;	默认构造函数，构造空容器
C c1(c2);	构造c2的拷贝c1
C c(b,e);	构造c，将迭代器b和e指定范围内的元素拷贝到c(array不支持)
C c{a,b,c…};	列表初始化c

赋值与swap
c1 = c2	将c1中的元素替换为c2中元素
c1 = {a,b,c..}	将c1中的元素替换为列表中的元素
a.swap(b)	交换a和b的元素
swap(a,b)	与a.swap(b)等价

大小
c.size()	c中元素的数目（不支持forward_list）
c.max_size()	c可保存的的最大元素数目
c.empty()	若c中存储了元素，返回false，否则返回true

添加/删除元素（不适用于array）
注：在不同容器中，这些操作的接口都不同
c.insert(args)	将args中的元素拷贝进c
c.emplace(inits)	使用inits构造c中的一个元素
c.erase(args)	删除args指定的元素
c.clear()	删除c中的所有元素，返回void

关系运算符
==,!=	所有容器都支持相等（不等）操作
<,<=,>,>=	关系运算符(无序关联容器不支持)

获取迭代器
c.begin(),c.end()	返回指向c的首元素和尾元素之后位置的迭代器
c.cbegin(),c.cend()	返回const_iterator

反向容器的额外成员
reverse_iterator	按逆序寻址元素的迭代器
const_reverse_iterator	不能修改元素的逆序迭代器
c.rbegin(),c.rend()	返回指向c的尾元素和首元素之前位置的迭代器
c.crbegin(),c.crend()	返回const_reverse_iterator

迭代器

迭代器范围(iterator range)：[begin,end)，左闭合区间(left-inclusive interval)

迭代器的运算符（表3.6，P96）

迭代器的运算符	含义
`*iter`	返回迭代器所指元素的引用
iter->mem	解引用iter并获取该元素的名为mem的成员，等价于`(*iter).mem`
++iter	令iter指示容器中的下一个元素
++iter	令iter指示容器中的上一个元素
iter1 == iter2	判断两个迭代器是否相等（指向同一个位置则相等，包括尾后）
iter1 != iter2	判断两个迭代器是否不相等（指向同一个位置则相等，包括尾后）

while(begin != end){
	*begin = val;
    ++begin;
}

如果begin与end相等，则范围为空；如果begin与end不等，则范围至少包含一个元素，且begin指向该范围中的第一个元素；我们可以对begin递增若干次，使得begin==end。

容器类型成员

容器定义和初始化(9.2.4，P299)

容器定义和初始化
C c	默认构造函数。如果C是一个array，则c中元素按默认方式初始化，否则c为空
`C c1(c2)` 与 `C c1 = c2`	c1初始化为c2的拷贝。c1和c2必须是相同类型。
`C c{a,b,c...}`与`C c = {a,b,c..}`	c初始化为初始化列表中元素的拷贝。列表中元素的类型必须与C的元素类型相容。对于array类型，列表中元素数目必须等于或少于array的大小，任何遗漏的元素都进行值初始化。
C c(b,e)	c初始化为迭代器b和e指定范围中的元素的拷贝。范围中元素的类型必须与C的元素类型相容（对array不适用）
C seq(n)	seq包含n个元素，这些元素进行了值初始化；此构造函数是explicit的
C seq(n,t)	seq包含n个初始化为值t的元素

$\color{red}{\heartsuit}$ 只有顺序容器（不包括array）的构造函数才能接受大小参数。关联容器并不支持。【上表中的倒数两个】

$\color{red}{\heartsuit}$ 当一个容器初始化为另一个容器的拷贝时，两个容器的容器类型必须相同。

标准库array的大小也是类型的一部分。定义一个array时，除了指定元素类型，还需要指定容器大小。

1 2	array<int,42> array<string,10>::size_type i;

赋值与swap(9.2.5，P302)

赋值、交换以及assign：

容器赋值运算
`c1 = c2`	将c1中的元素替换为c2中元素的拷贝。c1和c2必须具有相同的类型
`c = {a,b,c..}`	将c1中元素替换为初始化列表中元素的拷贝
`swap(c1,c2)`与`c1.swap(c2)`等价	交换c1和c2中的元素。c1和c2必须具有相同的类型。swap通常比从c2向c1拷贝元素快得多。
assign操作不适用于关联容器和array
seq.assign(b,e)	将seq中的元素替换为迭代器b和e所表示的范围中的元素。迭代器b和e不能指向seq中的元素
seq.assign(il)	将seq中的元素替换为初始化列表il中的元素
seq.assign(n,t)	将seq中的元素替换为n个值为t的元素

$\color{red}{\heartsuit}$ 使用assign：允许我们使用不同但相容的类型赋值。

除了array外，swap不对任何元素进行拷贝、删除或者插入操作，因此可以保证常数时间内完成。
与其它容器不同，swap两个array会真正交换它们的元素。指针和迭代器所绑定的元素保持不变，但元素值已经与另一个array中对应的元素的值进行了交换。

除了string外，指向容器的迭代器、引用和指针在swap操作之后都不会失效。
特殊的，对一个string 调用swap会导致迭代器和指针失效。

forward_list支持max_size和empty，但不支持size。其它每个容器都有三个有关大小的操作。

顺序容器操作(9.3，P305)

向顺序容器中添加元素

向顺序容器添加元素的操作	含义
c.push_back(t)	在c的尾部创建一个值为t或由args创建的元素，返回void
c.emplace_back(args)
c.push_front(t)	在c的头部创建一个值为t或由args创建的元素。返回void
c.emplace_front(args)
c.insert(p,t)	在迭代器p指向的元素之前创建一个值为t或由args创建的元素。返回指向新添加元素的迭
c.emplace(p,args)	代器。
c.insert(p,n,t)	在迭代器p指向的元素之前插入n个值为t的元素。返回指向新添加的第一个元素的迭代器；若n为0，则返回p
c.insert(p,b,e)	将迭代器b和e指定的范围内的元素插入迭代器p指向的元素之前。b和e不能指向c中的元素。返回指向新添加的第一个元素的迭代器；若范围为空，则返回p
c.insert(p,il)	il是一个花括号包围的元素值列表。将这些给定值插入到迭代器p指向的元素之前。返回指向新添加的第一个元素的迭代器；若列表为空，则返回p

添加元素操作	描述	vector	list	forward_list	array	deque
push_back/emplace_back	尾部添加元素	ok	ok	不支持	不支持	ok
push_front/emplace_front	首部添加元素	不支持	ok	OK	不支持	ok
insert(p, t)/insert(p, n, t)/insert(p, b, e)/insert(p, {…})	在指定p位置之前插入元素	ok	ok	有自己专用版本	不支持	ok
emplace	插入元素	ok	ok	有自己专用版本	不支持	ok

添加元素会改变容器的大小，array不支持这些操作。forward_list有自己专有版本的insert和emplace。forward_list不支持push_back和emplace_back。

vector和string不支持push_front和emplace_front。将元素insert插入到vector、deque和string中的任何位置都是合法的。然而，这样做可能很耗时。

emplace函数直接在容器中构造函数，传递给emplace函数的参数必须与元素类型相匹配。

访问元素(9.3.2，P309)

访问元素的操作	含义
c.back()	返回c中尾元素的引用。若c为空，函数行为未定义
c.front()	返回c中首元素的引用。若c为空，函数行为未定义
c[n]	返回c中下标为n的元素的引用，n是一个无符号的整数。若n>=c.size()，则函数行为未定义。
c.at(n)	返回下标为n的元素的引用。如果下标越界，则抛出一out_of_range异常。

at和下标操作只适用于string,vector,deque和array。
back不适用于forward_list。

if(!c.empty())
{
    c.front() = 42;
    auto &v = c.back(); // 获得指向最后一个元素的引用
    v = 1024;
    auto v2 = c.back(); // v2不是引用，只是c.back()的一个拷贝
    v2 = 0; // 没有改变c中的元素
    cout << "v: "<< v <<"  v2: " << v2 << endl;
}

如果希望下标是合法的，可以使用at函数；如果下标越界，则抛出一个out_of_range异常。

删除元素（9.3.3，P311）

这些操作会改变容器大小，所以不适用于array；forward_list有特殊版本的erase；forward_list不支持pop_back；vector和string不支持pop_front。

删除元素操作	含义
c.pop_back()	删除c中尾元素。若c为空，则函数行为未定义。函数返回void
c.pop_front()	删除c中首元素。若c为空，则函数行为未定义。函数返回void
c.erase(p)	删除迭代器p所指定的元素，返回一个指向被删元素之后元素的迭代器，若p指向尾元素，则返回尾后(off_the_end)迭代器。若p是尾后迭代器，则函数行为未定义。
c.erase(b,e)	删除迭代器b和e所指定范围内的元素。返回一个指向最后一个被删元素之后元素的迭代器，若e本身就是尾后迭代器，则函数也返回尾后迭代器
c.clear()	删除c中所有元素。返回void

删除一个list中的所有奇数：

#include<list>
list<int> lst = {0,1,2,3,4,5,6,7,8,9};
auto it = lst.begin();
while(it != lst.end())
{
    if(*it % 2)  // 如果是奇数
        it = lst.erase(it); //删除此元素，返回下一个元素
    else
        ++it; // 递增
}

特殊的forward_list操作

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

删除一个forward_list中的所有奇数：

forward_list<int> flst = {0,1,2,3,4,5,6,7,8,9};
auto curr = flst.begin();
auto prev = flst.before_begin();
while(curr != flst.end())
{
    if(*curr % 2)
        curr = flst.erase_after(prev);
    else 
        prev = curr++; //或者 prev=curr; curr++; //或者 prev++;curr++; 
}

改变容器大小（9.3.5，P314）

顺序容器大小操作	含义
c.resize(n)	调整c的大小为n个元素。若`n<c.size()`，则多出的元素被丢弃。若必须添加新元素，对新元素进行值初始化
c.resize(n,t)	调整c的大小为n个元素。任何新添加的元素都初始化为值t。

resize不适用于array。resize用来增大或者缩小容器。

容器操作可能使迭代器失效

向容器添加元素之后：

⑴.如果容器是vector或string，且存储空间被重新分配，则指向容器的迭代器、指针和引用都会失效。如果存储空间未被重新分配，指向插入位置之前的元素的迭代器、指针和引用仍有效，但指向插入位置之后元素的迭代器、指针和引用将会失效。

⑵.对于deque，插入到除首尾位置之外的任何位置都会导致迭代器、指针和引用失效。如果在首尾位置添加元素，迭代器会失效，但指向存在的元素的引用和指针不会失效。

⑶.对于list和forward_list，指向容器的迭代器(包括尾后迭代器和首前迭代器)、指针和引用仍然有效。

当我们删除一个元素后：

⑴.对于list和forward_list，指向容器其他位置的迭代器(包括尾后迭代器和首前迭代器)、指针和引用仍然有效。

⑵.对于deque，如果在首尾之外的任何位置删除元素，那么指向被删除元素之外其他元素的迭代器、引用或指针也会失效。如果是删除deque的尾元素，则尾后迭代器也会失效，但其他迭代器、引用和指针不受影响；如果是删除首元素，这些也不会受影响。

⑶.对于vector和string，指向被删元素之前元素的迭代器、引用和指针仍然有效。

注：当我们删除元素时，尾后迭代器总是会失效。

$\color{red}{\heartsuit}$ 由于向迭代器添加元素和从迭代器删除元素的代码可能会使得迭代器失效，因此必须保证每次改变容器的操作之后都能正确地重新定位迭代器。

$\color{red}{\heartsuit}$ 添加或删除元素的循环过程必须反复调用end，而不能在循环之前保存end返回的迭代器。

vector是如何增长的（9.4，P317）

1.容器大小管理操作

shrink_to_fit只使用于vector、string和deque；capacity和reserve只适用于vector和string

容器大小管理操作	含义
c.shrink_to_fit()	请将capacity()减少为与size()相同大小
c.capacity()	不重新分配内存空间的话，c可以保存多少元素
c.reserve(n)	分配至少能容纳n个元素的内存空间

2.当添加的数超出了vector原本分配的最大容量，vector的实现采用的策略是在每次需要分配新内存空间时将当前容量翻倍。

程序测试：

vector<int> vec;
   for(auto i = 0; i <= 33; ++i){
       cout << "size: "<< vec.size() <<"capacity: "<< vec.capacity() << endl;
       vec.push_back(i);
   }

额外的string操作（9.5，P320）

构造string的其他方法

构造string的其他方法	含义
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个字符。

子字符串操作

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

改变string的其他方法

修改string的操作	含义
s.insert(pos,args)	在pos之前插入args指定的字符。pos可以是一个下标或一个迭代器。接受下标的版本返回一个指向s的引用；接受迭代器的版本返回指向第一个插入字符的迭代器。
s.earse(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的引用

string搜索操作（9.5.3，P325）

string类提供了6个不同的搜索函数，每个函数都有4个重载版本。

每个搜索操作都会返回一个string::size_type值，表示匹配发生位置的下标。

如果搜索失败，则返回一个名为string::npos的static成员。标准库将npos定义成一个const string::size_type类型，并初始化为-1。

string搜索函数返回string::size_type值，该类型时一个unsigned类型，因此我们应该尽量不要使用带符号类型来保存这些返回值。

string搜索操作	含义
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无默认值

字符串比较函数(9.5.4，P327)

s.compare(args)中args形式	含义
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中从pos1开始的n1个字符与cp指向的地址开始的n2个字符进行比较

string和数值之间的转换(9.5.5，P327)

string参数中第一个非空白符必须是符号(+或-)或数字。它可以以0x或0X开头来表示十六进制数。对那些将字符串转换为浮点值的函数，string参数也可以以小数点开头，并可有包含e或E来表示指数部分。对于那些将字符串转换为整型值的函数，根据基数不同，string参数可以包含字母字符，对应大于数字9的数

如果string不能转换为一个数值，这些函数抛出一个invalid_argument异常。如果转换得到的数值无法用任何类型表示，则抛出一个out_of_range异常

string和数值之间的转换	含义
to_string(val)	一组重载函数，返回数值val的string表示。val可以是任何算术类型。对每个浮点类型和int或更大的整型，都有相应版本的to_string。与往常一样，小整型会被提升。
stoi(s,p,b)	返回s的起始子串(表示整数内容)的数值，返回值类型分别是int,long,unsigned long,long long,
stol(s,p,b)	unsigned long long。b表示转换所用的基数，默认值是10。p是size_t指针，用来保存s中第一个
stoul(s,p,b)	非数值字符下标，p默认为0，即函数不保存下标。
stoll(s,p,b)
stoull(s,p,b)
stof(s,p)	返回s的起始子串(表示浮点数内容)的数值，返回值类型分别是float,double或long double。参数
stod(s,p)	p的作用于整数转换函数中一样
stold(s,p)

容器适配器（9.6，P329）

标准库定义了三个顺序容器适配器：stack、queue和priority_queue。一个容器适配器接受一种已有的容器类型，使其行为看起来像一种不同的类型。例如，stack适配器接受一个顺序容器（除array或forward_list）。

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

容器适配器都支持的操作和类型	含义
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(b)

栈适配器的其他操作

栈适配器的其他操作	含义
s.pop()	删除栈顶元素，但不返回该元素值
s.push(item)	创建一个新元素压入栈顶，该元素通过拷贝或移动item而来，或者由args构造
s.emplace(args)
s.top()	返回栈顶元素，但不将元素弹出栈

`queue`和`priority_queue`的其他操作

`queue`和`priority_queue`的其他操作	含义
q.pop()	返回queue的首元素或priority_queue的最高优先级元素，但不删除此元素
q.front()	返回首元素，但不删除此元素
q.back()	返回尾元素，但不删除此元素，只适用于queue
q.top()	返回优先级最高的元素，但不删除此元素，只适用于priority_queue
q.push(item)	在queue末尾或priority_queue中恰当的位置创建一个元素，其值为item，或者有args构造
q.emplace(args)

术语表

适配器：adaptor
容器：container
迭代器范围：iterator range
首前迭代器： off-the-beginning iterator
尾后迭代器： off-the-end iterator
顺序容器： sequential container
左闭合区间： left-inclusive interval