cppprimer第九章

第九章 顺序容器

9.1 顺序容器概述

几种顺序容器

vector：支持快速随机访问。在尾部插入/删除速度快。

deque：支持快速随机访问。在头尾插入/删除都很快。

list：双向链表。只支持双向顺序访问。在任何位置插入/删除都很快。

forward_list：单项链表。只支持单向顺序访问。在任何位置插入/删除都很快。

string：支持快速随机访问。在尾部插入/删除速度快。

array：固定大小数组。支持快速随机访问。

可以发现：vector/deque/string/array 都是顺序存储结构。 list 是链式存储结构。但是他们都是顺序容器。

list 的额外内存开销相比其他大很多。

array 是一种比内置数组更好的类型。

farward_list 没有 size 操作。这种列表与最好的手写链表性能一样好。

容器选择

vector/list/deque 三种容器的比较：

1. 如果没有特殊的理由，使用 vector 是最好的选择
2. 如果有很多小的元素，不用 list
3. 如果空间开销很重要，不用 list
4. 如果需要在中间位置插入/删除，用 list
5. 如果需要在头尾位置插入/删除，用 deque
6. 如果需要随机访问，用 vector 或 deque
7. 如果需要在中间位置插入，而后随机访问：

• 如果可以通过排序解决，就先插到尾部，而后排序
• 在输入阶段用 list ，输入完成后拷贝到 vector 中

9.2 容器库概览

9.2.1 迭代器

迭代器之间比较只有 == 和 !=

当不需要写访问时，应使用 cbegin,cend

9.2.4 容器定义和初始化

为了创建一个容器为另一个容器的拷贝，两个容器的类型及其元素类型必须匹配。

当传递迭代器参数来拷贝一个范围时，就不要求容器类型是相同的。新容器和原容器中的元素类型也可以不同，只要能将要拷贝的元素转换为要初始化的容器的元素类型即可。

list<string> authors = {"Milton", "Shakespeare", "Austen"};
vector<const char*> articles = {"a", "an", "the"};
list<string> list2(authors) ; // 正确: 类型匹配
deque<string> authList(authors); //错误:容器类型不匹配
vector<string> words(articles); //错误:容器类型必须匹配
forward_list<string> words(articles.begin(), articles.end());//正确:可以将const char元素转换为string

array初始化

定义一个array，既需要指定元素类型，也需要指定大小：array<int,42>;

array 列表初始化时，列表元素个数小于等于 array 大小，剩余元素默认初始化为 0。

9.2.5 赋值和swap

“=”赋值

要求左右容器类型一样。

对容器使用赋值运算符（除 array 外），将会使该容器的所有元素被替换。如果两个容器大小不等，赋值后都与右边容器的原大小相同。

array要求赋值前大小一样。所以不支持 assign，花列表赋值。

assign

assign 是赋值操作，可以用于顺序容器。

“=” 要求两边类型相同， assign 要求只要可以转换即可

list<string> names;
vector<const char*> oldstyle;
names.assign(oldstyle.cbegin(), oldstyle.cend()); //正确:可以将const char*转换为string

swap

对 array ，swap 交换两个 array 中的元素值。指针、引用和迭代器绑定的元素不变（值变）。

对于其他容器，swap 不交换元素，只交换数据结构，因此 swap 操作非常快。

对于 string，swap 后，指针、引用和迭代器会失效。对于其他容器，交换后指针指向了另一个容器的相同位置。

建议统一使用 swap(a,b)，而非 a.swap(b)

对于 array，swap 操作的时间与元素数目成正比，对于其他容器，swap 操作的时间是常数。

9.2.6 容器大小操作

max_size 返回一个大于或等于该类型容器所能容纳的最大元素数的值。

9.3 顺序容器操作

9.3.1 添加元素

注意向 vector、string 或 deque 插入元素会使所有指向容器的迭代器、引用和指针失效。

添加的都是元素的拷贝，不是元素本身。

头尾添加返回 void，中间添加返回指向新添加元素的迭代器

push

vector 和 string 不支持 push_front 和 emplace_front；forward_list 不支持 push_back 和 emplace_back。

push 头尾是常数时间。

emplace

push 和 insert 传递的是元素类型的对象， emplace 则将参数传递给元素类型的构造对象。

即 emplace参数即为元素类型构造函数的参数，因此可以为空（默认初始化）。

insert

insert 返回值是指向添加的元素中第一个元素的迭代器

c.insert(p, t);       // 在迭代器 p 所指元素之前添加一个 t
c.insert(p, n, t);    // 在迭代器 p 所指元素之前添加 n 个 t
c.insert(p, b, e);    // 在迭代器 p 所指元素之前添加迭代器范围 [b,e) 中的元素。

9.3.2 访问元素

at/下标

可以快速随机访问的容器都可以使用下标。

使用下标一定要保证下标不越界，可以用 at 函数。当下标越界，at 函数会抛出一个 out_of_range 异常: a.at(n)

9.3.3 删除元素

这些操作改变数组大小，故不适用于 array。

pop(front, back), clear 无返回值。

删除返回被删除元素之后元素的迭代器。

vector/string 不支持 pop_front，forward_list 不支持 pop_back。

forward_list 有自己特殊版本的 erase。

c.erase(b, e);  // 删除迭代器范围 [b, e) 内的元素

删除 deque 除首尾之外的任何元素都会使所有迭代器、引用和指针失效。删除 vector 或 string 中的元素会使指向删除点之后位置的迭代器、引用和指针失效。

it = vec.erase(it); // vector 删除写法

9.3.4 特殊的forward_list操作

forward_list 是单向链表，添加和删除操作都会同时改变前驱和后继结点，因此一般的添加和删除都不适用于 forward_list。

forward_list 定义了首前迭代器：before_begin() 可以返回首前迭代器，用来删除首元素，不能解引用。

lst.insert_after(p,t);     // 在迭代器 p 之后添加一个元素 t
lst.insert_after(p,n,t);
lst.insert_after(p,b,e);
lst.insert_after(p,il);    // il是花括号列表
lst.emplace_after(p,args); // 在 p 之后构建新元素
// 以上操作，返回指向最后一个插入元素的迭代器。若范围为空，返回 p
lst.erase_after(p);        // 删除 p 之后的元素，注意 p 不能是尾元素
lst.erase_after(b,e);      // 删除迭代器返回 (b,e) 中的元素，注意不包含 b 和 e
// 返回指向最后一个被删除元素之后的迭代器。

删除所有奇数：

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

9.3.5 改变容器大小

resize() 用来增大或缩小容器。

如果要求的大小小于当前大小，尾部会被删除，如果要求的大小大于当前大小，会把新元素添加到尾部，旧元素不变。

v.resize(n);   // 元素类型必须提供一个默认构造函数
v.resize(n, t);

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

添加和删除元素都可能使指针、引用、迭代器失效。使用失效的指针、引用、迭代器是很严重的错误。

编写改变容器的循环程序

必须保证每次改变容器后都更新迭代器。

insert 和 erase 都会返回迭代器，更新很容易。调用 erase 后，不需要递增迭代器，调用 insert 后，需要递增两次。

不要保存 end() 返回的迭代器

插入删除都会改变尾后迭代器，因此不能保存 end() 返回值作为循环判断条件。

9.4 vector对象是如何增长的

vector 和 string 是连续存储的，为了避免每增加一个元素就要重新分配一次空间，在每次必须获取新的内存空间时，通常会分配比新的空间需求更大的内存空间。容器预留多的空间作为备用。这种方法在实现时性能很好，虽然每次重新分配内存都要移动所有元素，但是其扩张操作通常比 list 和 deque 还快。

管理容量

c.capacity(), c.reserve(), c.shrink_to_fit 都适用于 vector 和 string，c.shrink_to_fit 还另外适用于 deque。

​ c.capacity(); // 不重新分配内存空间的话，c 可以保存多少元素。 c.reserve(n); // 分配至少能容纳 n 个元素的空间（只预分配内存） c.shrink_to_fit(); // 请求将 capacity() 减少为与 size() 相同大小。

c.reserve(n) 不会减小容量，只会增大容量，当需求容量大于当前容量，才会分配内存，否则什么都不做。

c.shrink_to_fit() 只是一个请求，，实现时标准库可能会不执行。

9.5 额外的string操作

9.5.1 构造string的其他方法

构造string的基础方法

string 不支持在初始化时接受一个数字以指定 string 的大小。如果想要指定大小，可以先默认初始化，再调用 resize() 函数调整大小。

构造string的其他方法

string 的构造函数可以接受一个 string 或 const char* 参数用来指定开始位置，然后接受一个计数值用来指定范围。

如果没有传递计数值用来确定范围，拷贝操作遇到空字符停止：

const char *cp = "Hello";
char noNull[] = {'H', 'i'};
string s1(cp);     // 正确
string s2(noNull); // 错误

开始位置必须保证是在拷贝对象的范围内，计数值也没有上限要求，当计数值指定的范围大于拷贝对象，就最多拷贝到结尾。

string s(cp, n);          // cp 是一个字符数组，s 是 cp 指向的字符数组前 n 个字符的拷贝
string s(s2, pos2);       // s2 是一个 string 对象，s 是从 s2 的下标 pos 处开始到最后的字符的拷贝
string s(s2, pos2, len2); // s 是从 s2 的下标 pos2 处开始的 len2 个字符的拷贝。              

substr

s.substr(pos, (n)) 返回 s 的一个子序列，范围由参数指定。

如果 pos 的值超过了 string 的大小，则 substr 函数会抛出一个 out_of_range 异常；若 pos+n 的值超过了 string 的大小，则 substr 会调整 n 的值，只拷贝到 string 的末尾。

9.5.2 改变string的其他方法

string 支持顺序容器的 assign、insert、erase 操作，此外还增加了两个额外的操作

1. 接受下标版本的 insert 和 erase
2. 接受 C 风格字符数组的 insert 和 assign
3. append 和 replace 函数

接受下标的 insert 和 erase

insert 和 erase 接受下标的版本返回的是一个指向 s 的引用（区别于迭代器版本返回指向第一个插入字符的迭代器）

insert 的所有版本都是第一部分参数为 pos，后面的参数为待插入的字符

erase 的所有版本的参数都是 pos，pos 分为 起始位置 和 终止位置/长度

s.insert(s.size(), 5, '!');       // 在 s 末尾（s[s.size()]之前）插入 5 个感叹号
s.insert(0, s2, 3, s2.size()-3);  // 在 s[0] 之前插入 s2 第四个字符开始的 s2.size()-3 个字符
s.erase(s.size()-5, 5);           // 从 s 删除最后 5 个字符         

接受 C 风格字符数组的 insert 和 assign

assign 的所有版本的参数都是要赋的值，由 起始位置 + 终止位置/长度 组成

replace 的所有版本的参数都是第一部分参数为要删除的范围，第二部分为要插入的字符。

const char* cp = "stately,plump Buck";
s.assign(cp, 7);             // 用从 cp 开始的前 7 个字符向 s 赋值
s.insert(s.size(), cp+7);    // 将从 cp+7 开始到 cp 末尾的字符插入到 s 末尾

append 和 replace

append：在 string 末尾进行插入操作的简写形式：s.append(" 4th Ed.");

replace：调用 erase 和 insert 操作的简写形式：s.replace(11, 3, "Fifth"); 从下标 11 开始，删除三个字符并插入 5 个新字符。

9.5.3 string搜索操作

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

搜索操作返回 string::size_type 类型，代表匹配位置的下标。

搜索失败则返回一个名为 string::npos 的 static 成员，值初始化为 -1。因为 npos 是一个 unsigned 类型，这个初始值意味着 npos 等于任何 string 最大的可能大小。

注意：find 和 rfind 查找的是给定的整个 args，而剩下的查找的是给定的 args 中包含的任意一个字符。

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        // 字符，pos 为搜索开始位置
s2,pos       // 字符串
cp,pos       // 以空字符结尾的 c 风格字符串
cp,pos,n     // c 风格字符串的前 n 个字符          

9.5.4 compare函数

用于比较两个字符串，可以是比较整个或一部分字符串。

小于返回负数，大于返回正数，等于返回零

int F = s.compare(s2);
int F = s.compare(pos1,n1,s2);          // 将 s 中 pos1 开始的前 n1 个字符与 s2 比较
int F = s.compare(pos1,n1,s2,pos2,n2);  // 将 s 中 pos1 开始的前 n1 个字符与 s2 中从 pos2 开始的 n2 个字符进行比较 
int F = s.compare(cp)                   // 将 s 与 cp 指向的字符数组比较
int F = s.compare(pos1,n1,cp);
int F = s.compare(pos1,n1,cp,n2);              

9.5.5 数值转换

stoi 中要转换的 string 的第一个非空白符必须是数字或 "+"、"-"、"."，可以以 0x 或 0X 开头表示十六进制数，可以以 e 或 E表示指数部分。

stod, stold

9.6 容器适配器

初始化操作

默认情况下，stack 和 queue 是基于 deque 实现的， priority_queue 是在 vector 之上实现的。

初始化操作：

如果要使用其他顺序容器实现适配器，要在创建适配器时用一个顺序容器作为第二个类型参数。

stack<int, vector<int>> sta;  // 定义基于 vector 实现的 stack

stack 可以构造于 vector, list, deque 之上。

queue 可以构造于 list, deque 之上。queue q(dq);

priority_queue 可以构造于 vector(有序)、deque 之上。