C++@顺序容器(笔记)
标准库中的顺序容器如下：
- vector ：可变大小数组，支持快速随机访问，在尾部之外的外置插入或删除元素会很慢。
- deque ：双端队列，支持快速随机访问，在头尾位置插入/删除速度很快。
- list ：双向链表，支持双向顺序访问，在list中任意位置进行插入/删除操作速度都很快。
- forward_list ：单向链表，支持单向顺序访问，在链表任意位置插入/删除操作速度都很快。
- array ：固定大小数组，支持快速随机访问，不能添加或删除元素。
- string ：与vector相似的容器，但专门用于保存字符，随机访问很快，在尾部插入/删除速度很快。
顺序容器都提供了快速访问元素的能力，但是这些容器在以下方面都有不同的性能折中。
- 向容器中添加或从容器中删除元素的代价
- 非顺序访问容器中元素的代价
选择容器的基本原则：
通常，使用vector是最好的选择，除非你有很好的理由选择其他容器。
- 除非你有很好的理由选择其他的容器，否则应该使用vector。
- 如果你的程序有很多小的元素，且额外的空间开销很重要，则不要使用list或forward_list。
- 如果程序要求随机访问元素，应该使用vector和deque。
- 如果程序要求在容器的中间插入或删除元素，应该使用list或forward_list。
- 如果程序要求在头尾位置插入或删除元素，不要求在中间位置插入删除元素，则应该使用deque。
- 如果程序只有在读取输入时才需要在容器中间位置插入删除元素，随后需要随机访问元素，则：
- 如是容器是中的数据是顺序的，可以使用vector在尾部插入然后sort排序，以避免在中间插入数据。
- 如果必须在中间位置插入数据，可以考虑在输入阶段使用list，输入完成拷贝到vector中。
所以，当我们既要在容器中间插入数据，又想支持随机访问，就需要在链表和数组中考虑这两者之间的相对性能了。一般来说，占主导地位的操作决定了容器类型的选择。
容器库概览
容器库中几乎可以保存任意类型的数据。顺序容器构造函数的一个版本接受容器大小参数，比如：vectorval(10); 它使用了类型的默认构造函数，但是某些类型没有构造函数（比如我们自己定义的一个类）我们在使用的时候就不能直接传递给它一个数目参数，还要传递一个初始化器。如：vectorv1(10, init);
迭代器的范围由一对迭代器来表示，两个迭代器分别指向第一个元素和尾元素之后的位置，通常使用begin和end 表示，这是一种左闭合范围 [begin, end)，当begin和end指向相同的位置时，表明容器为空。
常见对容器的操作 |
|---|
类型别名 |
iterator-----------------迭代器类型 |
const_iterator----------只读类型的迭代器 |
reverse_iterator--------逆序迭代器类型 |
const_reverse_iterator-只读类型逆序迭代器 |
size_type---------------无符号整数类型，容器的大小类型 |
difference_type--------带符号整数类型 |
value_type--------------元素类型 |
reference----------------元素的左值类型；与value_type& 含义相同 |
const_reference---------元素的const左值类型，与 const value_type& 含义相同 |
构造函数 |
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 = {a1,a2,a3,...}-------将c1中的元素替换为列表元素 |
a.swap(b);--------------交换a和b的元素 |
swap(a, b);-------------和a.swap(b)等价 |
大小 |
c.size()-----------------c中元素的个数 |
c.max_size()-----------c中可保存的最大元素个数 |
c.empty() -------------容器c是否为空 |
添加/删除元素 |
c.insert(args);-----------将args中的元素拷贝到c中 |
c.emplace(inits);--------使用inits构造c中的一个元素 |
c.erase(args);------------删除args指定的元素 |
c.clear() ------------------清空c中的所有元素 |
获取迭代器 |
c.begin(),c.end();--------返回指向c的首元素和尾元素之后位置的迭代器 |
c.cbegin(),c.cend();------返回const_iterator类型迭代器 |
c.rbegin(),c.rend();------返回指向尾元素和首元素之前的位置 |
c.crbegin(),c.crend();----返回const_reverse_iterator类型的逆序迭代器 |
顺序容器的操作
向顺序容器中添加元素
array 不支持这些操作 forward_list 有自己的insert 和 emplace且不支持 push_back和emplace_back vector 和 string 不支持 push_front 和 emplace_front
c.push_back(t) 在c的尾部创建一个值为t的元素
c.push_front(t) 在c的头部创建一个值为t的元素
c.emplace_back(args) 在c的尾部创建一个由 args初始值 的元素
c.emplace_front(args) 在c的头部创建一个由args初始值的 元素
c.insert(it,p) 在迭代器 it 指向的元素之前创建一个值为p的元素
c.emplace(it,args) 在迭代器it指向的元素之前，创建一个由 args 初始化的元素
c.insert(it,n,p) 在迭代器it之前 插入 n个值为p的元素
c.insert(it,b,e) 在迭代器it之前 插入 迭代器b和迭代器e指定范围内的元素
我们可以将 元素插入到 vector ，deque，string 中的任何位置，但是这样做会很耗时
顺序容器访问元素
一般情况下，使用 迭代器 iterator 从 begin() 元素到 end() 元素进行遍历访问。或者 vector 和string 我们可以直接像使用数组的方式，使用下标进行访问元素。 c[n] 返回下标为n的元素的引用。如果n大于size 则函数未定义。
还可以使用at进行访问元素： 不过at只使用于 string vector deque 和array
c.at(n) 返回下标为n 的元素的引用，如果下标越界 抛出out_of_range 的异常
c.back() 返回容器c中的尾元素的引用 如果c为空 函数行为 未定义, back不适用 forward_list。
c.front() 返回容器c中的首元素的引用 如果c为空 函数行为未定义。
顺序容器删除元素
主要函数有:
pop_back() 删除容器中尾元素 返回void
pop_front() 删除容器中首元素，返回void
erase(p) 删除迭代器p指向的元素
erase(b,e) 删除 迭代器 b和e指定范围的元素。
clear() 清空容器 返回 void 。
改变容器的大小
resize(n) 调整容器的大小为n个元素，如果n 小于size，则多出的元素被丢弃，若必须添加新元素，则对新元素的值进行初始化。
resize(n,t) 调整容器的大小为n个元素，任何新添加的元素都初始值为t。
容器的操作可能会导致迭代器失效
向容器中添加元素和从一个容器中删除一个元素的操作，可能会使指向容器元素的指针，引用或迭代器失效。一个失效的指针，引用或迭代器 将不再指向任何一个有效的元素，如果使用失效的指针，引用或迭代器将会引发严重的运行时错误问题。
所以我们在使用的容器的时候一定要考虑到迭代器和指针引用失效的情况。end返回的迭代器不要保存，因为容器在进行增删之后，end返回的迭代器总是会失效。
vector 对象是如何增长的
我们知道，vector 是一种灵活的数组，长度会随着新增元素的个数自动的增长。那么vector的长度是怎么增长的呢？
先了解几个方法：
capacity() 不重新分配内存的情况下，容器最大能保存多少个元素。
size() 当前容器中当前有多少个元素。
reserve(n) 给容器分配那个元素存储的空间。
首先，我们创建一个空的vector 容器，然后一个一个的添加元素。打印出size和capacity 进行观察。
size=0, capacity=0； size=1, capacity=1； size=2, capacity=2； size=3, capacity=4； size=4, capacity=4； size=5, capacity=8； size=6, capacity=8； size=7, capacity=8； size=8, capacity=8； size=9, capacity=16；
由上面的结果，可以看出，vector的空间增长是翻倍增长的。那么，分配的空间一定是2的指数吗？使用reserve(50) 将容器空间预分配为50的元素的空间，然后添加元素将预留的空间填满，再添加一个元素。打印：
size=51, capacity=100； 可以看出，，每次需要新分配空间的时候，新内存空间的大小都是当前容量的翻倍。
string的一些操作
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默认为0 |
string和数值之间的转换：
to_string(val) 返回数值 val的string表示， val可以是任意数据类型。|
stoi(s,p,b) stol(s,p,b) stoul(s,p,b) stoll(s,p,b) stoull(s,p,b) 返回s的起始子串的数值，返回类型分别是 int ，long，unsigned long，long long，unsigned long long。b表示转换所用的基数，默认为10，p是size_t指针，用来表示s第一个非数字字符的下标，p默认为0，即函数不保存下标。
stof(s,p) stod(s,p) stold(s,p) 返回s的起始子串的数值，返回类型分别是float，double，long double。参数p的作用和整数转换函数中的一样。