面向对象编程基础¶
本课程入选教育部产学合作协同育人项目 课程主页:http://cpp.njuer.org 课程老师:陈明 http://cv.mchen.org
ppt和代码下载地址
git clone https://gitee.com/cpp-njuer-org/book
第9章¶
顺序容器¶
顺序容器¶
一个容器就是一些特定类型对象的集合。
- 顺序容器（sequential container）为程序员提供了控制元素存储和访问顺序的能力。
- 这种顺序不依赖于元素的值，而是与元素加入容器时的位置相对应。
- 关联容器中元素的位置由元素相关联的关键字值决定。
- 有序和无序关联容器，则根据关键字的值来存储元素。
顺序容器概述¶
所有顺序容器都提供了快速顺序访问元素的能力。
但是，这些容器在以下方面都有不同的性能折中：
- 向容器添加或从容器中删除元素的代价·
- 非顺序访问容器中元素的代价
顺序容器类型¶
vector 可变大小数组。支持快速随机访问。
在尾部之外的位置插入或删除元素可能很慢。
deque 双端队列。支持快速随机访问。在头尾位置插入/删除速度很快。
list 双向链表。只支持双向顺序访问。
在list中任何位置进行插入/删除操作速度都很快。
forward_list 单向链表。只支持单向顺序访问。
在链表任何位置进行插入/删除操作速度都很快。
array 固定大小数组。支持快速随机访问。不能添加或者删除元素。
string 与vector相似的容器，但专门用于保存字符。
随机访问快。在尾部插入/删除速度快。
顺序容器类型¶
- 除了固定大小的array外，其他容器都提供高效、灵活的内存管理。
- string和vector将元素保存在连续的内存空间中
- 计算地址快，中间位置添加删除元素慢
- list和forward_list 添加和删除操作都很快速
- 不支持元素的随机访问 只能遍历
- 与vector、deque和array相比，这两个容器的额外内存开销也很大。
- deque 与string和vector类似
- 支持快速的随机访问 中间位置添加或删除元素的代价（可能）很高
- 两端添加或删除元素都是很快的
- forward_list和array是新C++标准增加的类型。
- 与内置数组相比，array是一种更安全、更容易使用的数组类型
- forward_list 达到与最好的手写的单向链表数据结构相当的性能
- 没有size操作
- 通常使用vector是最好的选择，除非你有很好的理由选择其他容器。
- 新标准库的容器比旧版的快得多。
确定使用哪种顺序容器¶
通常，使用vector是最好的选择，除非你有很好的理由选择其他容器。
选择容器的基本原则：
- 除非你有很好的理由选择其他容器，否则应使用vector。
- 如果你的程序有很多小的元素，且空间的额外开销很重要，
则不要使用list或forward_list。
- 如果程序要求随机访问元素，应使用vector或deque。
- 如果程序要求在容器的中间插入或删除元素，应使用list或forward_list。
- 如果程序需要在头尾位置插入或删除元素，
但不会在中间位置进行插入或删除操作，则使用deque。
确定使用哪种顺序容器¶
- 如果只有在读取输入时才需要在容器中间位置插入元素, 随后需要随机访问元素，则
— 首先，确定是否真的需要在容器中间位置添加元素。
当处理输入数据时，通常可以很容易地向vector追加数据，
然后再调用标准库的sort函数来重排容器中的元素，从而避免在中间位置添加元素。
— 如果必须在中间位置插入元素，考虑在输入阶段使用list，
一旦输入完成，将list中的内容拷贝到一个vector中。
- 如果既需要随机访问元素，又需要在容器中间位置插入元素
- 在list或forward_list中访问元素与vector或deque中插入/删除元素的相对性能。
- 一般来说，应用中占主导地位的操作（执行的访问操作更多还是插入/删除更多）
决定了容器类型的选择
- 在此情况下，对两种容器分别测试应用的性能可能就是必要的了。
- 如果你不确定应该使用哪种容器，那么可以在程序中只使用vector和list公共的操作：
- 使用迭代器，不使用下标操作，避免随机访问
练习¶
对于下面的程序任务，vector、deque和list哪种容器最为适合？
解释你的选择的理由。如果没有哪一种容器优于其他容器，也请解释理由。
(a) 读取固定数量的单词，将它们按字典序插入到容器中。
我们将在下一章中看到，关联容器更适合这个问题。
(b) 读取未知数量的单词，总是将单词插入到末尾。删除操作在头部进行。
(c) 从一个文件读取未知数量的整数。将这些数排序，然后将它们打印到标准输出。
(a) list ，因为需要频繁的插入操作。
(b) deque ，总是在头尾进行插入、删除操作。
(c) vector ，不需要进行插入删除操作。
容器库概览¶
容器类型上的操作形成了一种层次：
- 某些操作是所有容器类型都提供的
- 另外一些操作仅针对顺序容器 关联容器或无序容器
- 还有一些操作只适用于一小部分容器。
在本节中，我们将介绍对所有容器都适用的操作。
容器库概览¶
一般来说，每个容器都定义在一个头文件中，文件名与类型名相同。
- deque定义在头文件deque中
- list定义在头文件list中 以此类推。
- 容器均定义为模板类
- 例如对vector，我们必须提供额外信息来生成特定的容器类型。
- 对大多数，但不是所有容器，我们还需要额外提供元素类型信息：
list<Sales_date>; //保存Sales_data对象的list
deque<double>; //保持double的deque
对容器可以保存的元素类型的限制¶
顺序容器几乎可以保存任意类型的元素。
- 特别是，我们可以定义一个容器，其元素的类型是另一个容器。
vector<vector<string>> lines; //vector的vector
//此处lines是一个vector，其元素类型是string的vector。
- 较旧的编译器可能需要在两个尖括号之间键入空格，
- 例如，vector<vector<string> >
对容器可以保存的元素类型的限制¶
某些容器操作对元素类型有其自己的特殊要求。
- 例如，顺序容器构造函数的一个版本接受容器大小参数
它使用了元素类型的默认构造函数。但某些类没有默认构造函数。
我们可以定义一个保存这种类型对象的容器，
但我们在构造这种容器时不能只传递给它一个元素数目参数：
//假定noDefault是以个没有默认构造函数的类型
vector<noDefault> v1(10,init); //正确，提供元素初始化器
vector<noDefault> v2(10); //错误，必须提供元素初始化器
容器操作 类型别名¶
iterator 此容器类型的迭代器类型
const_iterator 可以读取元素但不能修改元素的迭代器类型
size_type 无符号整数类型，足够保存此种容器类型最大可能的大小
difference_type 符号整数类型，足够保存两个迭代器之间的距离
value_type 元素类型
reference 元素的左值类型；和value_type &含义相同
const_reference 元素的const左值类型，即const value_type &
容器操作 构造函数¶
C c; 默认构造函数，构造空容器
C c1(c2);或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中的元素替换成列表中的元素（不适用于array）
c1.swap(c2) 交换c1和c2的元素
swap(c1, c2) 等价于c1.swap(c2)
容器操作 大小¶
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
容器操作 反向容器的额外成员¶
//不支持forward_list
reverse_iterator 按逆序寻址元素的迭代器
const_reverse_iterator 不能修改元素的逆序迭代器
c.rbegin() c.rend() 返回c的尾元素和首元素之前位置的迭代器
c.crbegin() c.crend() 返回const_reverse_iterator
练习¶
定义一个list对象，其元素类型是int的deque。
std::list<std::deque<int>> l;
迭代器¶
迭代器有着公共的接口：如果一个迭代器提供某个操作，
那么所有提供相同操作的迭代器对这个操作的实现方式都是相同的。
- 例如，标准容器类型上的所有迭代器都允许我们访问容器中的元素，
而所有迭代器都是通过解引用运算符来实现这个操作的。
- 类似的，标准库容器的所有迭代器都定义了递增运算符，
从当前元素移动到下一个元素。
- forward_list迭代器不支持递减运算符（--）
迭代器范围¶
迭代器范围的概念是标准库的基础。
一个迭代器范围（iterator range）由一对迭代器表示， - 两个迭代器分别指向同一个容器中的元素或者是尾元素之后的位置 （one past the last element）。 - 这两个迭代器通常被称为begin和end，或者是first和last（可能有些误导）， 它们标记了容器中元素的一个范围。 - 迭代器范围中的元素包含first所表示的元素以及从first开始直至last （但不包含last）之间的所有元素。
迭代器范围¶
这种元素范围被称为左闭合区间（left-inclusive interval），其标准数学描述为
[begin,end)
- 表示范围自begin开始，于end之前结束。
- 迭代器begin和end必须指向相同的容器。
- end可以与begin指向相同的位置，但不能指向begin之前的位置。
对构成范围的迭代器的要求¶
如果满足如下条件，两个迭代器begin和end构成一个迭代器范围
- 它们指向同一个容器中的元素，或者是容器最后一个元素之后的位置，且
- 我们可以通过反复递增begin来到达end。换句话说，end不在begin之前。
编译器不会强制这些要求。 确保程序符合这些约定。
使用左闭合范围蕴含的编程假定¶
左闭合范围有三种方便的性质。
假定begin和end构成一个合法的迭代器范围，则·
- 如果begin与end相等，则范围为空
- 如果begin与end不等，则范围至少包含一个元素且begin指向该范围中的第一个元素
- 我们可以对begin递增若干次，使得begin==end
意味着我们可以像下面的代码一样用一个循环来处理一个元素范围，而这是安全的：
while ( begin != end ){
*begin = val;
++begin;
}
练习¶
构成迭代器范围的迭代器有何限制？
两个迭代器 begin 和 end需满足以下条件：
- 它们指向同一个容器中的元素，或者是容器最后一个元素之后的位置。
- 我们可以通过反复递增begin来到达end。换句话说，end 不在begin之前。
练习¶
编写函数，接受一对指向vector<int>的迭代器和一个int值。
在两个迭代器指定的范围中查找给定的值，返回一个布尔值来指出是否找到。
bool find(vector<int>::const_iterator begin,
vector<int>::const_iterator end, int i)
{
while (begin != end)
{
if (*begin == i)
return true;
++begin;
}
return false;
}
练习¶
重写上一题的函数，返回一个迭代器指向找到的元素。注意，程序必须处理未找到给定值的情况。
vector<int>::const_iterator find(vector<int>::const_iterator begin,
vector<int>::const_iterator end, int i)
{
while (begin != end)
{
if (*begin == i)
return begin;
++begin;
}
return end;
}
练习¶
下面的程序有何错误？你应该如何修改它？
list<int> lst1;
list<int>::iterator iter1 = lst1.begin(),
iter2 = lst1.end();
while (iter1 < iter2) /* ... */
修改成如下：
while (iter1 != iter2)
//list迭代器不支持<,只支持++ -- == !=,因为链表中指针大小与顺序不一定吻合
容器类型成员¶
每个容器都定义了多个类型
- 我们已经使用过其中三种：size_type、iterator和const_iterator
- 除了已经使用过的迭代器类型，大多数容器还提供反向迭代器
- 类型别名。 通过类型别名，我们可以在不了解容器中元素类型的情况下使用它
- 如果需要元素类型，可以使用容器的value_type。
- 如果需要元素类型的一个引用，可以使用reference或const_reference。
//为了使用这些类型，必须显式使用其类名
list<string>::iterator iter;
vector<int>::difference_type count;
练习¶
为了索引int的vector中的元素，应该使用什么类型？
vector<int>::size_type
练习¶
为了读取string的list中的元素，应该使用什么类型？
如果写入list，又应该使用什么类型？
list<string>::const_iterator // 读
list<string>::iterator // 写
begin和end成员¶
begin和end操作生成指向容器中第一个元素和尾元素之后位置的迭代器。
这两个迭代器最常见的用途是形成一个包含容器中所有元素的迭代器范围。
begin和end有多个版本
- 带r的版本返回反向迭代器
- 以c开头的版本则返回const迭代器
list<string> a = {"Milton", "Shakespeare", "Austen"};
auto it1 = a.begin(); //list<string>::iterator
auto it2 = a.rbegin(); //list<string>::reverse_iterator
auto it3 = a.cbegin(); //list<string>::const_iterator
auto it4 = a.crbegin(); //list<string>::const_reverse_iterator
list<string>::iterator it5 = a.begin();
list<string>::const_iterator it6 = a.begin();
auto it7 = a.begin();//当a是const时，it7是const_iterator
auto it8 = a.cbegin();//const_iterator
//当不需要写访问时，应使用cbegin和cend。
练习¶
begin和cbegin两个函数有什么不同？
begin 返回的是普通迭代器，cbegin 返回的是常量迭代器。
练习¶
下面4个对象分别是什么类型？
vector<int> v1;
const vector<int> v2;
auto it1 = v1.begin(), it2 = v2.begin();
auto it3 = v1.cbegin(), it4 = v2.cbegin();
it1 是 vector<int>::iterator
it2，it3 和 it4 是 vector<int>::const_iterator
容器定义和初始化¶
每个容器类型都定义了一个默认构造函数
- 除array之外，其他容器的默认构造函数都会创建一个指定类型的空容器，
- 且都可以接受指定容器大小和元素初始值的参数。
C c; 默认构造函数，对于array,按默认方式初始化,否则构造空容器。
C c1(c2);或C c1 = c2; 构造c2的拷贝c1。
将一个容器复制给另一个容器时，类型必须匹配：容器类型和元素类型都必须相同。
对于array则两者大小相同
C c(a, b, c...)或C c={a,b,c... } 列表初始化c。
对于array，列表需要小于等于array大小，遗漏元素进行值初始化
C c(b, e) 构造c，将迭代器b和e指定范围内的所有元素拷贝到c
(array不支持)
只有顺序容器(不包括array)的构造函数才接受大小参数，关联容器并不支持。
C c(n) 只支持顺序容器，且不包括array，包含n个元素，这些元素进行了值初始化
此构造函数是explicit的。 string 不适用
C c(n, t) 包含n个初始值为t的元素
将一个容器初始化为另一个容器的拷贝¶
将一个新容器创建为另一个容器的拷贝的方法有两种：
- 可以直接拷贝整个容器，
- 两个容器的类型及其元素类型必须匹配。
- 或者（array除外）拷贝由一个迭代器对指定的元素范围。
- 不要求容器类型是相同的
- 新容器和原容器中的元素类型也可以不同，只要能元素转换即可。
将一个容器初始化为另一个容器的拷贝¶
list<string> authors = {"Milton", "Shakespeare", "Austen"};
vector<const char*> articles = {"a","an","the"};
list<string> list2(authors);//ok
deque<string> authList(authors);//error 容器类型不匹配
vector<string> words(articles);//error 容器类型必须匹配
//元素类型转换
forward_list<string> words(articles.begin(),articles.end());
//拷贝元素直到(但不包括)it指向的元素。it是迭代器，指向authors中一个元素
deque<string> authList(authors.begin(),it);
列表初始化¶
在新标准中，我们可以对一个容器进行列表初始化
list<string> authors = {"Milton", "Shakespeare", "Austen"};
vector<const char*> articles = {"a","an","the"};
//当这样做时，我们就显式地指定了容器中每个元素的值。
//对于除array之外的容器类型，初始化列表还隐含地指定了容器的大小：
//容器将包含与初始值一样多的元素。
与顺序容器大小相关的构造函数¶
顺序容器（array除外）还接受一个容器大小和一个（可选的）元素初始值。
- 如果我们不提供元素初始值，则标准库会创建一个值初始化器
vector<int> ivec(10,-1); //10个-1
list<string> svec(10,"hi!");//10个"hi!"
forward_list<int> ivec(10); //10个0
deque<string> svec(10); //10个空string
- 如果元素类型是内置类型或者是具有默认构造函数的类类型，
可以只为构造函数提供一个容器大小参数。
- 如果元素类型没有默认构造函数，除了大小参数外，还必须指定一个显式的元素初始值。
只有顺序容器的构造函数才接受大小参数，关联容器并不支持。
标准库array具有固定大小¶
标准库array的大小也是类型的一部分
array<int,42>; //保存42个int 的数组
array<string,10>; //保存10个string的数组
//为了使用array类型，我们必须同时指定元素类型和大小
array<int,10>::size_type i; //数组类型包括元素类型和大小
array<int>::size_type j; //错误 array<int> 不是一个类型
由于大小是array类型的一部分，array不支持普通的容器构造函数。
这些构造函数都会确定容器的大小，要么隐式地，要么显式地。
而允许用户向一个array构造函数传递大小参数，最好情况下也是多余的而且容易出错。
标准库array具有固定大小¶
array大小固定的特性也影响了它所定义的构造函数的行为。
- 与其他容器不同，一个默认构造的array是非空的：它包含了与其大小一样多的元素。
- 这些元素都被默认初始化，就像一个内置数组中的元素那样。
- 如果我们对array进行列表初始化，初始值的数目必须等于或小于array的大小。
- 初始化array中靠前的元素，所有剩余元素都会进行值初始化
- 如果元素类型是一个类类型，那么该类必须有一个默认构造函数以使值初始化能够进行
标准库array具有固定大小¶
array<int,10> ia1; //10个默认初始化的int
array<int,10> ia2={0,1,2,3,4,5,6,7,8,9}; //列表初始化
array<int,10> ia3={42}; //ia[3]为42，其余为0
//我们不能对内置数组类型进行拷贝或对象赋值操作 但array并无此限制
int digs[10] = {0,1,2,3,4,5,6,7,8,9};
int cpy[10] = digs; //错误，内置类型不支持拷贝或赋值
array<int,10> digits = {0,1,2,3,4,5,6,7,8,9};
array<int,10> copy = digits; //正确，数组类型匹配合法
//与其他容器一样，array也要求初始值的类型必须与要创建的容器类型相同。
//此外，array还要求元素类型和大小也都一样，因为大小是array类型的一部分。
练习¶
对6种创建和初始化vector对象的方法，每一种都给出一个实例。
解释每个vector包含什么值。
vector<int> vec; // 0
vector<int> vec(10); // 10个0
vector<int> vec(10, 1); // 10个1
vector<int> vec{ 1, 2, 3, 4, 5 }; // 1, 2, 3, 4, 5
vector<int> vec(other_vec); // 拷贝 other_vec 的元素
vector<int> vec(other_vec.begin(), other_vec.end()); // 拷贝other_vec的元素
练习¶
对于接受一个容器创建其拷贝的构造函数，和接受两个迭代器创建拷贝的构造函数，
解释它们的不同。
接受一个容器创建其拷贝的构造函数，必须容器类型和元素类型都相同。
接受两个迭代器创建拷贝的构造函数，只需要元素的类型能够相互转换，
容器类型和元素类型可以不同。
练习¶
如何从一个list<int>初始化一个vector<double>？
从一个vector<int>又该如何创建？编写代码验证你的答案。
list<int> ilst(5, 4);
vector<int> ivc(5, 5);
vector<double> dvc(ilst.begin(), ilst.end());
vector<double> dvc2(ivc.begin(), ivc.end());
赋值和swap¶
赋值运算符将其左边容器中的全部元素替换为右边容器中元素的拷贝：
c1 = c2;
c1 = {a,b,c};
标准库array类型允许赋值。赋值号左右两边的运算对象必须具有相同的类型：
array<int,10> a1 = {0,1,2,3,4,5,6,7,8,9};
array<int,10> a2 = {0};//所有元素为0
a1 = a2;
a2 = {0};//错误 不能将一个花括号列表赋予数组
//由于右边运算对象的大小可能与左边运算对象的大小不同，
//因此array类型不支持assign，也不允许用花括号包围的值列表进行赋值。
c1 = c2; 将c1中的元素替换成c2中的元素
c1 = {a, b, c...} 将c1中的元素替换成列表中的元素（不适用于array）
c1.swap(c2) 交换c1和c2的元素
swap(c1, c2) 等价于c1.swap(c2)
// assign操作不适用于关联容器和array
c.assign(b, e) 将c中的元素替换成迭代器b和e表示范围中的元素，
b和e不能指向c中的元素
c.assign(il) 将c中的元素替换成初始化列表il中的元素
c.assign(n, t) 将c中的元素替换为n个值是t的元素
//赋值相关运算会导致指向左边容器的内部迭代器 引用和指针失效。
//swap操作将容器内容交换不会导致指向容器的迭代器 引用和指针失效
//(array string 除外)
使用assign（仅顺序容器）¶
顺序容器（array除外）还定义了一个名为assign的成员，
允许我们从一个不同但相容的类型赋值，或者从容器的一个子序列赋值。
list<string> names;
vector<const char*> oldstyle;
names = oldstyle; //错误 类型不匹配
//正确 可以转换
names.assign(oldstyle.cbegin(),oldstyle.cend());
- 由于其旧元素被替换，因此传递给assign的迭代器不能指向调用assign的容器。
assign的第二个版本接受一个整型值和一个元素值。
//等价于slist1.clear(); slist1.insert(slist1.begin(),10,"Hiya!");
list<string> slist1(1);//1个元素 空string
slist1.assign(10,"Hiya!");// 10个元素，"Hiya!"
使用swap¶
swap操作交换两个相同类型容器的内容。调用swap之后，两个容器中的元素将会交换：
vector<string> svec1(10);
vector<string> svec2(24);
swap(svec1,svec2);
//调用swap后，svec1将包含24个string元素，svec2将包含10个string。
//除array外，交换两个容器内容的操作保证会很快——元素本身并未交换，
//swap只是交换了两个容器的内部数据结构。
使用swap¶
- 除array外，swap不对任何元素进行拷贝、删除或插入操作，
因此可以保证在常数时间内完成。
- 元素不会被移动的事实意味着，
除string外，指向容器的迭代器、引用和指针在swap操作之后都不会失效。
- 它们仍指向swap操作之前所指向的那些元素。
但是，在swap之后，这些元素已经属于不同的容器了。
- 对一个string调用swap会导致迭代器、引用和指针失效。
- swap两个array会真正交换它们的元素
- 对于array，在swap操作之后，指针、引用和迭代器所绑定的元素保持不变，
但元素值已经与另一个array中对应元素的值进行了交换。
练习¶
编写程序，将一个list中的char *指针元素赋值给一个vector中的string。
std::list<const char*> l{ "hello", "world" };
std::vector<std::string> v;
v.assign(l.cbegin(), l.cend());
容器大小操作¶
每个容器类型都有三个与大小相关的操作。
- 成员函数size 返回容器中元素的数目；
- empty当size为0时返回布尔值true，否则返回false；
- max_size返回一个大于或等于该类型容器所能容纳的最大元素数的值。
forward_list支持max_size和empty，但不支持size
关系运算符¶
每个容器类型都支持相等运算符（==和！=）；
除了无序关联容器外的所有容器都支持关系运算符（>、>=、<、<=）。
关系运算符左右两边的运算对象必须是相同类型的容器，且必须保存相同类型的元素。
比较两个容器实际上是进行元素的逐对比较。
这些运算符的工作方式与string的关系运算类似
- 如果两个容器具有相同大小且所有元素都两两对应相等，则这两个容器相等；
- 否则两个容器不等。
- 如果两个容器大小不同，但较小容器中每个元素都等于较大容器中的对应元素，
则较小容器小于较大容器。
- 如果两个容器都不是另一个容器的前缀子序列，则它们的比较结果取决于第一个
关系运算符¶
vector<int> v1 = {1,3,5,7,9,12};
vector<int> v2 = {1,3,9};
vector<int> v3 = {1,3,5,7};
vector<int> v4 = {1,3,5,7,9,12};
vector<int> v2 = {1,3,9};
v1<v2 //true
v1<v3 //false
v1==v4//true
v1==v2//false
容器的关系运算符使用元素的关系运算符完成比较¶
- 只有当其元素类型也定义了相应的比较运算符时，我们才可以使用关系运算符来比较两个容器。
容器的相等运算符实际上是使用元素的==运算符实现比较的， 而其他关系运算符是使用元素的<运算符。 如果元素类型不支持所需运算符，那么保存这种元素的容器就不能使用相应的关系运算。 //定义的Sales_data类型并未定义==和<运算。 //因此，就不能比较两个保存Sales_data元素的容器： vector<Sales_date> storeA, storeB; if(storeA<storeB) //错误 Sales 没有<运算符
练习¶
编写程序，判定两个vector<int>是否相等。
std::vector<int> vec1{ 1, 2, 3, 4, 5 };
std::vector<int> vec2{ 1, 2, 3, 4, 5 };
std::vector<int> vec3{ 1, 2, 3, 4 };
std::cout << (vec1 == vec2 ? "true" : "false") << std::endl;
std::cout << (vec1 == vec3 ? "true" : "false") << std::endl;
练习¶
重写上一题的程序，比较一个list<int>中的元素和一个vector<int>中的元素。
std::list<int> li{ 1, 2, 3, 4, 5 };
std::vector<int> vec2{ 1, 2, 3, 4, 5 };
std::vector<int> vec3{ 1, 2, 3, 4 };
std::cout << (std::vector<int>(li.begin(), li.end()) == vec2 ?
"true" : "false") << std::endl;
std::cout << (std::vector<int>(li.begin(), li.end()) == vec3 ?
"true" : "false") << std::endl;
练习¶
假定c1和c2是两个容器，下面的比较操作有何限制？
if (c1 < c2)
- c1和c2必须是相同类型的容器并且保存相同类型的元素
- 元素类型要支持关系运算符
顺序容器操作¶
- 上一节介绍了所有容器都支持的操作。
- 本章剩余部分将介绍顺序容器所特有的操作。
向顺序容器添加元素¶
除array外，所有标准库容器都提供灵活的内存管理。
在运行时可以动态添加或删除元素来改变容器大小。
不同容器使用不同的策略来分配元素空间，而这些策略直接影响性能。
- 在一个vector或string的尾部之外的任何位置，或是一个deque的首尾之外的
任何位置添加元素，都需要移动元素。
- 向一个vector或string添加元素可能引起整个对象存储空间的重新分配。
- 重新分配一个对象的存储空间需要分配新的内存，
并将元素从旧的空间移动到新的空间中。
向一个vector string deque 插入元素会使所有指向容器的迭代器、引用和指针失效。
- 因为这些操作会改变大小，因此不适用于array。
- forward_list有自己专有版本的insert和emplace。
- forward_list不支持push_back和emplace_back。
c.push_back(t) 在c尾部创建一个值为t的元素，返回void
c.emplace_back(args) 同上
c.push_front(t) 在c头部创建一个值为t的元素，返回void
c.emplace_front(args) 同上
c.insert(p, t) 在迭代器p指向的元素之前创建一个值是t的元素，
返回指向新元素的迭代器
c.emplace(p, args) 同上
c.insert(p, n, t) 在迭代器p指向的元素之前插入n个值为t的元素，
返回指向第一个新元素的迭代器；如果n是0，则返回p
c.insert(p, b, e) 将迭代器b和e范围内的元素，插入到p指向的元素之前；
如果范围为空，则返回p
c.insert(p, il) il是一个花括号包围中的元素值列表，
将其插入到p指向的元素之前；如果il是空，则返回p
使用push_back¶
push_back可将一个元素追加到一个vector的尾部。
除array和forward_list之外，每个顺序容器（包括string类型）都支持push_back。
//对push_back的调用在container尾部创建了一个新的元素，
//将container的size增大了1。
//该元素的值为word的一个拷贝。container的类型可以是list、vector或deque。
string word;
while (cin >> word)
container.push_back(word);
//也可以用push_back在string末尾添加字符：
void pluralize(size_t cnt, string& word){
if(cnt > 1)
word.push_back('s');//等价于word+='s'
}
关键概念：容器元素是拷贝¶
用一个对象来初始化容器时，或将一个对象插入到容器中时，
实际上放入到容器中的是对象值的一个拷贝，而不是对象本身。
就像我们将一个对象传递给非引用参数一样，
容器中的元素与提供值的对象之间没有任何关联。
随后对容器中元素的任何改变都不会影响到原始对象，反之亦然。
使用push_front¶
除了push_back，list、forward_list和deque容器还支持名为push_front的操作。
此操作将元素插入到容器头部：
list<int> ilist;
//将元素添加到ilist开头
for (size_t ix = 0;ix!=4;++ix)
ilist.pushfront(ix);
//此循环将元素0、1、2、3添加到ilist头部。
//每个元素都插入到list的新的开始位置（new beginning）
//在循环执行完毕后，ilist保存序列3、2、1、0。
注意，deque像vector一样提供了随机访问元素的能力，
但它提供了vector所不支持的push_front。
deque保证在容器首尾进行插入和删除元素的操作都只花费常数时间。
与vector一样，在deque首尾之外的位置插入元素会很耗时。
在容器中的特定位置添加元素¶
insert成员允许在容器中任意位置插入0个或多个元素。
- vector、deque、list和string都支持insert成员。
- forward_list提供了特殊版本的insert成员
insert函数都接受一个迭代器作为其第一个参数,指出在容器中什么位置放置新元素
slist.insert(iter,"Hello");
//将一个值为"Hello"的string插入到iter指向的元素之前的位置。
在容器中的特定位置添加元素¶
某些容器不支持push_front操作，但它们对于insert操作并无类似的限制
将元素插入到vector、deque和string中的任何位置都是合法的。这样做可能很耗时。
vector<string> svec;
list<string> slist;
//等价于slist.push_front("Hello");
slist.insert(slist.begin(),"Hello");
//vector 不支持push_front, 插入末尾之外的位置都可能很慢
svec.insert(svec.begin(),"Hello!");
插入范围内元素¶
insert函数还可以接受更多的参数
- 其中一个版本接受一个元素数目和一个值，
它将指定数量的元素添加到指定位置之前，这些元素都按给定值初始化：
- 接受一对迭代器或一个初始化列表的insert版本
将给定范围中的元素插入到指定位置之前
插入范围内元素¶
//将10个元素插入到svec的末尾，并将所有元素都初始化为string"Anna"。
svec.insert(svec.end(),10,"Anna");
vector<string> v = {"quasi","simba","frollo","scar"};
//将v的最后两个元素添加到slist开始位置
slist.insert(slist.begin(),v.end()-2,v.end());
slist.insert(slist.end(),{"these","words","will","go","at","the","end"});
//运行时错误 迭代器表示要拷贝的范围 不能指向与目的位置相同的容器
slist.insert(slist.begin(),slist.begin(),slist.end());
在新标准下，接受元素个数或范围的insert版本返回指向第一个新加入元素的迭代器。
在旧版本的标准库中，这些操作返回void。
如果范围为空，不插入任何元素，insert操作会将第一个参数返回。
使用insert的返回值¶
通过使用insert的返回值，可以在容器中一个特定位置反复插入元素：
list<string> lst;
auto iter=lst.begin();
while(cin>>word)
iter = lst.insert(iter,word);//等价于push_front
//每步while循环就会将一个新元素插入到iter之前
//并将iter改变为新加入元素的位置。
理解这个循环是如何工作的非常重要，
特别是理解这个循环为什么等价于调用push_front尤为重要。
使用emplace操作¶
新标准引入了三个新成员——emplace_front、emplace和emplace_back，
- 这些操作构造而不是拷贝元素。
- 当调用push或insert成员函数时，我们将元素类型的对象传递给它们
这些对象被拷贝到容器中。
- 而当我们调用一个emplace成员函数时，则是将参数传递给元素类型的构造函数。
emplace成员使用这些参数在容器管理的内存空间中直接构造元素。
//假定c保存Sales_data,在c的末尾构造一个对象，使用三个参数构造函数
c.emplace_back("987",25,15.99);
//错误 没有接受三个参数的push_back
c.push_back("987",25,15.99);
//正确 创建临时对象 传递给push_back
c.push_back(Sales_data("987",25,15.99));
//其中对emplace_back的调用和第二个push_back调用都会创建新的Sales_data对象。
//在调用emplace_back时，会在容器管理的内存空间中直接创建对象。
//而调用push_back则会创建一个局部临时对象，并将其压入容器中。
使用emplace操作¶
emplace函数的参数根据元素类型而变化，参数必须与元素类型的构造函数相匹配：
//iter 指向 c中一个元素 其中保存Sales_data 元素
c.emplace_back(();//使用Sales_data 默认构造函数
c.emplace_back(iter,"987");//使用Sales_data(string)
//使用Sales_data三个参数的构造函数
c.emplace_back("987",25,15.99);
emplace函数在容器中直接构造元素。
传递给emplace函数的参数必须与元素类型的构造函数相匹配。
练习¶
编写程序，从标准输入读取string序列，存入一个deque中。
编写一个循环，用迭代器打印deque中的元素。
#include <iostream>
#include <string>
#include <deque>
using std::string; using std::deque;
using std::cout; using std::cin; using std::endl;
int main()
{
deque<string> input;
for (string str; cin >> str; input.push_back(str));
for (auto iter = input.cbegin(); iter != input.cend(); ++iter)
cout << *iter << endl;
return 0;
}
练习¶
重写上一题的程序，用list替代deque。列出程序要做出哪些改变。
只需要在声明上做出改变即可，其他都不变。
deque<string> input;
//改为
list<string> input;
练习¶
编写程序，从一个list<int>拷贝元素到两个deque中。
值为偶数的所有元素都拷贝到一个deque中，而奇数值元素都拷贝到另一个deque中。
#include <iostream>
#include <deque>
#include <list>
using std::deque; using std::list; using std::cout;
using std::cin; using std::endl;
int main()
{
list<int> l{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
deque<int> odd, even;
for (auto i : l)
(i & 0x1 ? odd : even).push_back(i);
for (auto i : odd) cout << i << " ";
cout << endl;
for (auto i : even)cout << i << " ";
cout << endl;
return 0;
}
练习¶
如果我们使用insert返回值将元素添加到list中的循环程序改写为
将元素插入到vector中，分析循环将如何工作。
一样的。
第一次调用insert会将我们刚刚读入的string插入到iter所指向的元素之前的位置。
insert 返回的迭代器恰好指向这个新元素。
我们将此迭代器赋予 iter 并重复循环，读取下一个单词。
只要继续有单词读入，每步 while 循环就会将一个新元素插入到 iter 之前，
并将 iter 改变为新加入元素的尾置。此元素为（新的）首元素。
因此，每步循环将一个元素插入到 list(改写后为vector) 首元素之前的位置。
练习¶
假定iv是一个int的vector，下面的程序存在什么错误？你将如何修改？
vector<int>::iterator iter = iv.begin(),
mid = iv.begin() + iv.size() / 2;
while (iter != mid)
if (*iter == some_val)
iv.insert(iter, 2 * some_val);
* 循环不会结束
* 迭代器可能会失效
要改为下面这样：
int count=0;
while (iter != (iv.begin() + iv.size() / 2+count))
{
if (*iter == some_val)
{
iter = v.insert(iter, 2 * some_val);
++count;
++iter;
}
++iter;
}
访问元素¶
- at和下标操作只适用于string、vector、deque、array。
- back不适用于forward_list。
c.back() 返回c中尾元素的引用。若c为空，函数行为未定义
c.front() 返回c中头元素的引用。若c为空，函数行为未定义
c[n] 返回c中下标是n的元素的引用，n无符号整数。
若n>=c.size()，则函数行为未定义
c.at(n) 返回下标为n的元素引用。如果下标越界，则抛出out_of_range异常
访问元素¶
如果容器中没有元素，访问操作的结果是未定义的。
包括array在内的每个顺序容器都有一个front成员函数，
而除forward_list之外的所有顺序容器都有一个back成员函数。
这两个操作分别返回首元素和尾元素的引用：
//判断非空
if(!c.empty()){
//val val2是c中第一个元素的拷贝
auto val = *c.begin(),val2=c.front();
//val3 val4 是c中最后一个元素的拷贝
auto last = c.end();
auto val3 = *(--last);//不能递减forward_list迭代器
auto val4 = c.back();//forward_list 不支持
}
访问成员函数返回的是引用¶
在容器中访问元素的成员函数（即，front、back、下标和at）返回的都是引用。
如果容器是一个const对象，则返回值是const的引用。
如果容器不是const的，则返回值是普通引用，我们可以用来改变元素的值：
if(!c.empty()){
c.front()=42;//42赋给第一个元素
auto &v = c.back();
v =1024;//改变c中的值
auto v2 = c.back();
v2 = 0; //未改变c中的值
}
下标操作和安全的随机访问¶
提供快速随机访问的容器（string、vector、deque和array）也都提供下标运算符
- 下标运算符接受一个下标参数，返回容器中该位置的元素的引用。
- 给定下标必须“在范围内”（即，大于等于0，且小于容器的大小）。
- 保证下标有效是程序员的责任，下标运算符并不检查下标是否在合法范围内。
- 使用越界的下标是一种严重的程序设计错误，而且编译器并不检查这种错误。
- 如果我们希望确保下标是合法的，可以使用at成员函数。
- 但如果下标越界，at会抛出一个out_of_range异常
vector<string> svec; //空vector
cout<<svec[0]; //运行时错误 svec没有元素
cout<<svec.at(0);//抛出out_of_range异常
练习¶
在本节第一个程序中，若c.size() 为1，则val、val2、val3和val4的值会是什么？
都会是同一个值（容器中仅有的那个）。
练习¶
编写程序，分别使用at、下标运算符、front 和 begin
提取一个vector中的第一个元素。在一个空vector上测试你的程序。
#include <iostream>
#include <vector>
int main()
{
std::vector<int> v;
std::cout << v.at(0); // out_of_range
std::cout << v[0]; // Segmentation fault
std::cout << v.front(); // Segmentation fault
std::cout << *v.begin(); // Segmentation fault
return 0;
}
删除元素¶
（非array）容器也有多种删除元素的方式
- 会改变容器大小，不适用于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本身是尾后迭代器，则函数行为未定义
c.erase(b, e) 删除迭代器b和e范围内的元素，返回指向最后一个被删元素之后
元素的迭代器，若e本身就是尾后迭代器，则返回尾后迭代器
c.clear() 删除c中所有元素，返回void
删除元素的成员函数并不检查其参数。
在删除元素之前，程序员必须确保它（们）是存在的。
pop_front和pop_back成员函数¶
pop_front和pop_back成员函数分别删除首元素和尾元素
- vector和string不支持push_front一样，也不支持pop_front。
- forward_list不支持pop_back。
- 不能对一个空容器执行弹出操作。
- 返回void。如果需要弹出的元素的值，就必须在执行弹出操作之前保存它：
while(!ilist.empty()){
process(ilist.front());
ilist.pop_front();
}
从容器内部删除一个元素¶
成员函数erase从容器中指定位置删除元素。
- 我们可以删除由一个迭代器指定的单个元素，
- 也可以删除由一对迭代器指定的范围内的所有元素。
- 两种形式的erase都返回指向删除的（最后一个）元素之后位置的迭代器。
//循环删除一个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;
}
删除多个元素¶
接受一对迭代器的erase版本允许我们删除一个范围内的元素：
//迭代器elem1指向我们要删除的第一个元素，
//elem2指向我们要删除的最后一个元素之后的位置。
elem1 = slist.erase(elem1,elem2);
为了删除一个容器中的所有元素，我们既可以调用clear，
也可以用begin和end获得的迭代器作为参数调用erase：
slist.clear();
slist.erase(slist.begin(),slist.end());//等价调用
练习¶
对于删除一个范围内的元素的程序，如果 elem1 与 elem2 相等会发生什么？
如果 elem2 是尾后迭代器，或者 elem1 和 elem2 皆为尾后迭代器，又会发生什么？
如果 elem1 和 elem2 相等，那么不会发生任何操作。
如果elem2 是尾后迭代器，那么删除从 elem1 到最后的元素。
如果两者皆为尾后迭代器，也什么都不会发生。
练习¶
使用下面代码定义的ia，将ia拷贝到一个vector和一个list中。
用单迭代器版本的erase从list中删除奇数元素，从vector中删除偶数元素。
int ia[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 55, 89 };
vector<int> vec(ia, end(ia));
list<int> lst(vec.begin(), vec.end());
for (auto it = lst.begin(); it != lst.end(); )
if (*it & 0x1)
it = lst.erase(it);
else
++it;
for (auto it = vec.begin(); it != vec.end(); )
if (!(*it & 0x1))
it = vec.erase(it);
else
++it;
特殊的forward_list操作¶
为了理解forward_list为什么有特殊版本的添加和删除操作，
考虑当我们从一个单向链表中删除一个元素时会发生什么。
elem1->elem2->elem3->elem4
删除elem3改变elem2的值
elem1->elem2->elem4
当添加或删除一个元素时，删除或添加的元素之前的那个元素的后继会发生改变。
这样，我们总是可以访问到被添加或删除操作所影响的元素。
forward_list并未定义insert、emplace和erase，
而是定义了名为insert_after、emplace_after和erase_after的操作
- 例如为了删除elem3，应该用指向elem2的迭代器调用erase_after。
- forward_list也定义了before_begin，它返回一个首前（off-the-beginning）迭代器。
- 这个迭代器允许我们在链表首元素之前并不存在的元素“之后”
添加或删除元素（亦即在链表首元素之前添加删除元素）。
在forward_list中插入或删除元素的操作¶
lst.before_begin() 返回指向链表首元素之前不存在的元素的迭代器，
此迭代器不能解引用。
lst.cbefore_begin() 同上，但是返回的是常量迭代器。
lst.insert_after(p, t) 在迭代器p之后插入元素。t是一个对象
lst.insert_after(p, n, t) 在迭代器p之后插入元素。t是一个对象，
n是数量。若n是0则函数行为未定义
lst.insert_after(p, b, e) 在迭代器p之后插入元素。由迭代器b和e指定范围。
lst.insert_after(p, il) 在迭代器p之后插入元素。由il指定初始化列表。
emplace_after(p, args) 使用args在p之后的位置，创建一个元素，
返回一个指向这个新元素的迭代器。
若p为尾后迭代器，则函数行为未定义。
lst.erase_after(p) 删除p指向位置之后的元素，
返回一个指向被删元素之后的元素的迭代器，
若p指向lst的尾元素或者是一个尾后迭代器，
则函数行为未定义。
lst.erase_after(b, e) 类似上面，删除对象换成从b到e指定的范围。
特殊的forward_list操作¶
当在forward_list中添加或删除元素时，我们必须关注两个迭代器
一个指向我们要处理的元素，另一个指向其前驱。
//改写从list中删除奇数元素的循环程序，将其改为从forward_list中删除元素：
forward_list<int> flst(begin(lstarr), end(lstarr));
auto prev = flst.before_begin(); // element "off the start" of flst
auto curr = flst.begin(); // denotes the first element in flst
while (curr != flst.end()) { // while there are still elements
if (*curr % 2) // if the element is odd
curr = flst.erase_after(prev); // erase it and move curr
else {
prev = curr; // move the iterators to denote the next
++curr; // element and one before the next element
}
}
练习¶
编写程序，查找并删除forward_list<int>中的奇数元素。
#include <iostream>
#include <forward_list>
using std::forward_list;
using std::cout;
auto remove_odds(forward_list<int>& flist)
{
auto is_odd = [] (int i) { return i & 0x1; };
flist.remove_if(is_odd);
}
int main()
{
forward_list<int> data = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
remove_odds(data);
for (auto i : data)
cout << i << " ";
return 0;
}
练习¶
编写函数，接受一个forward_list<string>和两个string共三个参数。
函数应在链表中查找第一个string，并将第二个string插入到紧接着第一个string
之后的位置。若第一个string未在链表中，则将第二个string插入到链表末尾。
void find_and_insert(forward_list<string>& flst, const string& s1, const string& s2)
{
auto prev = flst.before_begin();
auto curr = flst.begin();
while (curr != flst.end())
{
if (*curr == s1)
{
flst.insert_after(curr, s2);
return;
}
prev = curr;
++curr;
}
flst.insert_after(prev, s2);
}
改变容器大小¶
我们可以用resize来增大或缩小容器，与往常一样，array不支持resize。
- 如果当前大小大于所要求的大小，容器后部的元素会被删除；
- 如果当前大小小于新大小，会将新元素添加到容器后部：
list<int> ilist(10,42);//10个42
ilist.resize(15); //末尾添加5个0
ilist.resize(25,-1); //末尾添加10个-1
ilist.resize(5); //末尾删除20个元素
如果容器保存的是类类型元素，且resize向容器添加新元素，
则我们必须提供初始值，或者元素类型必须提供一个默认构造函数。
改变容器大小¶
c.resize(n) 调整c的大小为n个元素，若n<c.size()，则多出的元素被丢弃。
若必须添加新元素，对新元素进行值初始化
c.resize(n, t) 调整c的大小为n个元素，任何新添加的元素都初始化为值t
如果resize缩小容器，则指向被删除元素的迭代器、引用和指针都会失效；
对vector string 或 deque 进行resize可能导致迭代器、引用和指针失效。
练习¶
假定vec包含25个元素，那么vec.resize(100)会做什么？
如果接下来调用vec.resize(10)会做什么？
将75个值为0的元素添加到vec的末尾
从vec的末尾删除90个元素
练习¶
接受单个参数的resize版本对元素类型有什么限制（如果有的话）？
元素类型必须提供一个默认构造函数。
容器操作可能使迭代器失效¶
向容器中添加元素和从容器中删除元素的操作可能会使指向容器元素的指针、
引用或迭代器失效。
- 一个失效的指针、引用或迭代器将不再表示任何元素。
- 使用失效的指针、引用或迭代器是一种严重的程序设计错误，
很可能引起与使用未初始化指针一样的问题
在向容器添加元素后：
- 如果容器是vector或string，且存储空间被重新分配，则指向容器的迭代器、指针
和引用都会失效。如果存储空间未重新分配，指向插入位置之前的元素的迭代器、
指针和引用仍有效，但指向插入位置之后元素的迭代器、指针和引用将会失效。
- 对于deque，插入到除首尾位置之外的任何位置都会导致迭代器、指针和引用失效。
如果在首尾位置添加元素，迭代器会失效，但指向存在的元素的引用和指针不会失效。
- 对于list和forward_list，指向容器的迭代器（包括尾后迭代器和首前迭代器）、
指针和引用仍有效。
容器操作可能使迭代器失效¶
当我们从一个容器中删除元素后，指向被删除元素的迭代器、指针和引用会失效
- 对于list和forward_list，指向容器其他位置的迭代器（包括尾后迭代器和
首前迭代器）、引用和指针仍有效。
- 对于deque，如果在首尾之外的任何位置删除元素，那么指向被删除元素外其他元素
的迭代器、引用或指针也会失效。如果是删除deque的尾元素，则尾后迭代器也会失
效，但其他迭代器、引用和指针不受影响；如果是删除首元素，这些也不会受影响。
- 对于vector和string，指向被删元素之前元素的迭代器、引用和指针仍有效。
注意：当我们删除元素时，尾后迭代器总是会失效。
建议：管理迭代器¶
当使用迭代器（或指向容器元素的引用或指针）时，
最小化要求迭代器必须保持有效的程序片段是一个好的方法。
由于向迭代器添加元素和从迭代器删除元素的代码可能会使迭代器失效，
因此必须保证每次改变容器的操作之后都正确地重新定位迭代器。
这个建议对vector、string和deque尤为重要。
编写改变容器的循环程序¶
添加/删除vector、string或deque元素的循环程序必须考虑迭代器、引用和指针
可能失效的问题。程序必须保证每个循环步中都更新迭代器、引用或指针。
如果循环中调用的是insert或erase，那么更新迭代器很容易。
这些操作都返回迭代器，我们可以用来更新：
//傻瓜循环 删除偶数
vector<int> vi = {0,1,2,3,4,5,6,7,8,9};
auto iter = vi.begin();
while (iter != vi.end()) {
if (*iter % 2) { // if the element is odd
iter = vi.insert(iter, *iter); // duplicate it
iter += 2; // advance past this element and the new one
} else
iter = vi.erase(iter); // remove even elements
// don't advance the iterator;
// iter denotes the element after the one we erased
}
不要保存end返回的迭代器¶
当我们添加/删除vector或string的元素后，或在deque中首元素之外任何位置添加/
删除元素后，原来end返回的迭代器总是会失效。因此，添加或删除元素的循环程序
必须反复调用end，而不能在循环之前保存end返回的迭代器，一直当作容器末尾使用。
通常C++标准库的实现中end（）操作都很快，部分就是因为这个原因。
//在循环之前保存end（）返回的迭代器，一直用作容器末尾，就会导致一场灾难：
//灾难 循环行为未定义
auto begin = v.begin(),
end = v.end();//坏主意
while(begin!=end){
//处理
//插入新值
++begin;
begin = v.insert(begin,42);
++begin;
}
//在循环体中，我们向容器中添加了一个元素，这个操作使保存在end中的迭代器失效了。
//这个迭代器不再指向v中任何元素，或是v中尾元素之后的位置。
不要保存end返回的迭代器¶
- 如果在循环中插入/删除deque、string或vector中的元素，不要缓存end返回的迭代器。
- 必须在每次插入操作后重新调用end（），而不能在循环开始前保存它返回的迭代器：
//更安全的方法 重新计算end
while(begin!=v.end()){
//处理
++begin;
begin = v.insert(begin,42);//插入新值
++begin;
}
练习¶
删除偶数值元素并复制奇数值元素的程序不能用于list或forward_list。
为什么？修改程序，使之也能用于这些类型。
iter += 2;
因为复合赋值语句只能用于string、vector、deque、array，所以要改为：
++iter;
++iter;
如果是forward_list的话，要增加一个首先迭代器prev：
auto prev = flst.before_begin();
//...
curr == flst.insert_after(prev, *curr);
++curr; ++curr;
++prev; ++prev;
练习¶
向下面语句这样调用insert是否合法？如果不合法，为什么？
iter = vi.insert(iter, *iter++);
不合法。因为参数的求值顺序是未指定的。第一个参数？
练习¶
在本节最后一个例子中，如果不将insert的结果赋予begin，将会发生什么？
编写程序，去掉此赋值语句，验证你的答案。
begin将会失效。
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::vector;
int main()
{
vector<int> data { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
for(auto cur = data.begin(); cur != data.end(); ++cur)
if(*cur & 0x1)
cur = data.insert(cur, *cur), ++cur;
for (auto i : data)
cout << i << " ";
return 0;
}
练习¶
假定vi是一个保存int的容器，其中有偶数值也有奇数值，分析下面循环的行为，
然后编写程序验证你的分析是否正确。
iter = vi.begin();
while (iter != vi.end())
if (*iter % 2)
iter = vi.insert(iter, *iter);
++iter;
循环永远不会结束。
vector对象是如何增长的¶
vector和string在内存中是连续保存的，如果原先分配的内存位置已经使用完，
则需要重新分配新空间，将已有元素从就位置移动到新空间中，然后添加新元素。
标准库实现者采用了可以减少容器空间重新分配次数的策略。
当不得不获取新的内存空间时，vector和string的实现通常会分配比新的空间
需求更大的内存空间。
管理容量的成员函数¶
capacity操作告诉我们容器在不扩张内存空间的情况下可以容纳多少个元素。
reserve操作允许我们通知容器它应该准备保存多少个元素。
- shrink_to_fit只适用于vector、string和deque
- capacity和reserve只适用于vector和string。
c.shrink_to_fit() 将capacity()减少到和size()相同大小
c.capacity() 不重新分配内存空间的话，c可以保存多少个元素
c.reserve(n) 分配至少能容纳n个元素的内存空间
- reserve并不改变容器中元素的数量，它仅影响vector预先分配多大的内存空间。
- resize成员函数只改变容器中元素的数目，而不是容器的容量
- 调用shrink_to_fit也并不保证一定退回内存空间。
capacity和size¶
容器的size是指它已经保存的元素的数目；
capacity则是在不分配新的内存空间的前提下它最多可以保存多少元素。
vector<int> ivec;
// size should be zero; capacity is implementation defined
cout << "ivec: size: " << ivec.size()
<< " capacity: " << ivec.capacity() << endl;
// give ivec 24 elements
for (vector<int>::size_type ix = 0; ix != 24; ++ix)
ivec.push_back(ix);
// size should be 24; capacity will be >= 24 and is implementation defined
cout << "ivec: size: " << ivec.size()
<< " capacity: " << ivec.capacity() << endl;
//输出：
//ivec: size: 0 capacity: 0
//ivec: size: 24 capacity: 32
capacity和size¶
ivec.reserve(50); // sets capacity to at least 50; might be more
// size should be 24; capacity will be >= 50 and is implementation defined
cout << "ivec: size: " << ivec.size()
<< " capacity: " << ivec.capacity() << endl;
//程序的输出表明reserve严格按照我们需求的大小分配了新的空间：
//ivec: size: 24 capacity: 50
// add elements to use up the excess capacity
while (ivec.size() != ivec.capacity())
ivec.push_back(0);
// capacity should be unchanged and size and capacity are now equal
cout << "ivec: size: " << ivec.size()
<< " capacity: " << ivec.capacity() << endl;
//程序输出表明此时我们确实用光了预留空间，size和capacity相等：
//ivec: size: 50 capacity: 50
capacity和size¶
ivec.push_back(42); // add one more element
// size should be 51; capacity will be >= 51 and is implementation defined
cout << "ivec: size: " << ivec.size()
<< " capacity: " << ivec.capacity() << endl;
//如果我们现在再添加一个新元素，vector就不得不重新分配空间：
//这段程序的输出为ivec: size: 51 capacity: 100
ivec.shrink_to_fit(); // ask for the memory to be returned
// size should be unchanged; capacity is implementation defined
cout << "ivec: size: " << ivec.size()
<< " capacity: " << ivec.capacity() << endl;
//可以调用shrink_to_fit来要求vector将超出当前大小的多余内存退回给系统
//调用shrink_to_fit只是一个请求，标准库并不保证退还内存。
- 只有在执行insert操作时size与capacity相等，或者调用resize或reserve时给定
的大小超过当前capacity，vector才可能重新分配内存空间。
- 会分配多少超过给定容量的额外空间，取决于具体实现。
练习¶
解释一个vector的capacity和size有何区别。
capacity的值表明，在不重新分配内存空间的情况下，容器可以保存多少元素
而size的值是指容器已经保存的元素的数量
练习¶
一个容器的capacity可能小于它的size吗？
不可能。
练习¶
为什么list或array没有capacity成员函数？
因为list是链表，而array不允许改变容器大小。
## 练习9.38
练习¶
编写程序，探究在你的标准实现中，vector是如何增长的。
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main()
{
vector<int> v;
for (int i = 0; i < 100; i++)
{
cout << "capacity: " << v.capacity() << " size: " << v.size() << endl;
v.push_back(i);
}
return 0;
}
练习¶
解释下面程序片段做了什么：
vector<string> svec;
svec.reserve(1024);
string word;
while (cin >> word)
svec.push_back(word);
svec.resize(svec.size() + svec.size() / 2);
定义一个vector，为它分配1024个元素的空间。然后通过一个循环从标准输入中
读取字符串并添加到vector当中。循环结束后，改变vector的容器大小（元素数量）
为原来的1.5倍，使用元素的默认初始化值填充。如果容器的大小超过1024，
vector也会重新分配空间以容纳新增的元素。
练习¶
如果上一题的程序读入了256个词，在resize之后容器的capacity可能是多少？
如果读入了512个、1000个、或1048个呢？
如果读入了256个词，capacity 仍然是 1024
如果读入了512个词，capacity 仍然是 1024
如果读入了1000或1048个词，capacity 取决于具体实现。
额外的string操作¶
string类型还提供了一些额外的操作。
- 这些操作中的大部分要么是提供string类和C风格字符数组之间的相互转换
- 要么是增加了允许我们用下标代替迭代器的版本。
可以在需要使用一个特定操作时回过头来仔细阅读。
构造string的其他方法¶
string类型还支持另外三个构造函数
- n,len2,pos2都是无符号值。
string s(cp, n) s是cp指向的数组中前n个字符的拷贝，此数组
string s(s2, pos2) s是string s2从下标pos2开始的字符的拷贝。
若pos2 > s2.size()，则构造函数的行为未定义。
string s(s2, pos2, len2) s是string s2从下标pos2开始的len2个字符的拷贝。
- 这些构造函数接受一个string或一个const char*参数，
还接受（可选的）指定拷贝多少个字符的参数。
- 当我们传递给它们的是一个string时，还可以给定一个下标来指出从哪里开始拷贝：
构造string的其他方法¶
const char* cp= "hello world!!!";
char noNull[]= {'H','i'};
string s1(cp);
string s2(noNull,2);
string s3(noNull); //未定义 noNull不以空字符结束
string s4(cp+6,5);//从cp[6]开始5个字符
string s5(s1,6,5);//从s1[6]开始5个字符
string s6(s1,6);//从s1[6]开始直到末尾
string s7(s1,6,20);//正确,从s1[6]开始直到末尾
string s8(s1,16); //抛出out_of_range异常
substr操作¶
substr操作返回一个string，它是原始string的一部分或全部的拷贝。
可以传递给substr一个可选的开始位置和计数值：
s.substr(pos, n) 返回一个string，包含s中从pos开始的n个字符的拷贝。
pos的默认值是0，n的默认值是s.size() - pos，
即拷贝从pos开始的所有字符。
string s("hello world");
cout << s.substr(0, 5) << endl; // prints hello
cout << s.substr(6) << endl; // prints world
cout << s.substr(6, 11) << endl; // prints world
cout << s.substr(12) << endl; // throws out_of_range
练习¶
编写程序，从一个vector<char>初始化一个string。
vector<char> v{ 'h', 'e', 'l', 'l', 'o' };
string str(v.cbegin(), v.cend());
练习¶
假定你希望每次读取一个字符存入一个string中
而且知道最少需要读取100个字符，应该如何提高程序的性能？
使用 reserve(100) 函数预先分配100个元素的空间。
改变string的其他方法¶
除了接受迭代器的insert和erase版本外，string还提供了接受下标的版本。
下标指出了开始删除的位置，或是insert到给定值之前的位置：
s.insert(s.size(),5,'!');//在末尾插入5个！
s.erase(s.size()-5,5);//从s删除最后5个字符
标准库string类型还提供了接受C风格字符数组的insert和assign版本。
const char* cp="Stately, plump Buck";
s.assign(cp,7);//s=== "Stately"
s.insert(s.size(),cp+7);//s=== "Stately, plump Buck"
也可以指定将来自其他string或子字符串的字符插入到当前string中或赋予当前string：
string s = "some string",s2="some other string";
s.insert(0,s2);
s.insert(0,s2,0,s2.size());
append和replace函数¶
string 类定义了两个额外的成员函数 append 和replace 可改变string的内容
s.insert(pos, args) 在pos之前插入args指定的字符。pos可以使是下标或者迭代器。
接受下标的版本返回指向s的引用；
接受迭代器的版本返回指向第一个插入字符的迭代器。
s.erase(pos, len) 删除从pos开始的len个字符，
如果len被省略，则删除后面所有字符，返回指向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 制定范围的字符
初始化列表 花括号包围的，以逗号分隔的字符列表
append和replace函数¶
//append操作是在string末尾进行插入操作的一种简写形式：
string s("C++ Primer"),s2=s;
s.insert(s.size()," 4th Ed.");//s== "C++ Primer 4th Ed."
s2.append(" 4th Ed.");//将" 4th Ed."追加到s2
//replace操作是调用erase和insert的一种简写形式：
//"4th"替换为"5th"
s.erase(11,3); //s=="C++ Primer Ed."
s.insert(11,"5th");//s=="C++ Primer 5th Ed."
//从位置11开始 删除3个字符并插入"5th"
s2.replace(11,3,"5th");//s==s2
s.replace(11,3,"Fifth");//s=="C++ Primer Fifth Ed."
改变string的多种重载函数¶
//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
否 是 否 是 初始化列表
改变string的多种重载函数¶
append、assign、insert和replace函数有多个重载版本。
- 根据如何指定要添加的字符和string中被替换的部分，这些函数的参数有不同版本。
assign和append函数无须指定要替换string中哪个部分：
- assign总是替换string中的所有内容，
- append总是将新字符追加到string末尾。
replace函数提供了两种指定删除元素范围的方式。
- 可以通过一个位置和一个长度来指定范围，
- 也可以通过一个迭代器范围来指定。
insert函数允许我们用两种方式指定插入点：
- 用一个下标
- 或一个迭代器。
在两种情况下，新元素都会插入到给定下标（或迭代器）之前的位置。
改变string的多种重载函数¶
可以用好几种方式来指定要添加到string中的字符。
- 新字符可以来自于另一个string，
- 来自于一个字符指针（指向的字符数组）
- 来自于一个花括号包围的字符列表
- 或者是一个字符和一个计数值。
- 当字符来自于一个string或一个字符指针时，
我们可以传递一个额外的参数来控制是拷贝部分还是全部字符。
并不是每个函数都支持所有形式的参数。
- 例如，insert就不支持下标和初始化列表参数。
- 类似的，如果我们希望用迭代器指定插入点，就不能用字符指针指定新字符的来源。
练习¶
编写一个函数，接受三个string参数是s、oldVal 和newVal。
使用迭代器及insert和erase函数将s中所有oldVal替换为newVal。
测试你的程序，用它替换通用的简写形式，
如，将"tho"替换为"though",将"thru"替换为"through"。
#include <iterator>
#include <iostream>
#include <string>
#include <cstddef>
using std::cout;
using std::endl;
using std::string;
auto replace_with(string &s, string const& oldVal, string const& newVal){
for (auto cur = s.begin(); cur <= s.end() - oldVal.size(); )
if (oldVal == string{ cur, cur + oldVal.size() })
cur = s.erase(cur, cur + oldVal.size()),
cur = s.insert(cur, newVal.begin(), newVal.end()),
cur += newVal.size();
else
++cur;
}
练习¶
int main()
{
string s{ "To drive straight thru is a foolish, tho courageous act." };
replace_with(s, "tho", "though");
replace_with(s, "thru", "through");
cout << s << endl;
return 0;
}
练习¶
重写上一题的函数，这次使用一个下标和replace。
#include <iostream>
#include <string>
using std::cout;
using std::endl;
using std::string;
auto replace_with(string &s, string const& oldVal, string const& newVal)
{
for (size_t pos = 0; pos <= s.size() - oldVal.size();)
if (s[pos] == oldVal[0] && s.substr(pos, oldVal.size()) == oldVal)
s.replace(pos, oldVal.size(), newVal),
pos += newVal.size();
else
++pos;
}
练习¶
int main()
{
string str{ "To drive straight thru is a foolish, tho courageous act." };
replace_with(str, "tho", "though");
replace_with(str, "thru", "through");
cout << str << endl;
return 0;
}
练习¶
编写一个函数，接受一个表示名字的string参数和两个分别表示前缀
（如"Mr."或"Mrs."）和后缀（如"Jr."或"III"）的字符串。使用迭代器及insert
和append函数将前缀和后缀添加到给定的名字中，将生成的新string返回。
#include <iostream>
#include <string>
using std::string;
using std::cin;
using std::cout;
using std::endl;
auto add_pre_and_suffix(string name, string const& pre, string const& su){
name.insert(name.begin(), pre.cbegin(), pre.cend());
return name.append(su);
}
int main(){
string name("Wang");
cout << add_pre_and_suffix(name, "Mr.", ", Jr.") << endl;
return 0;
}
练习¶
重写上一题的函数，这次使用位置和长度来管理string，并只使用insert。
#include <iostream>
#include <string>
auto add_pre_and_suffix(std::string name, std::string const& pre,
std::string const& su){
name.insert(0, pre);
name.insert(name.size(), su);
return name;
}
int main(){
std::string name("alan");
std::cout << add_pre_and_suffix(name, "Mr.", ",Jr.");
return 0;
}
string搜索操作¶
string类提供了6个不同的搜索函数，每个函数都有4个重载版本。
- 每个搜索操作都返回一个string：：size_type值，表示匹配发生位置的下标。
- 如果搜索失败，则返回一个名为string：：npos的static成员。
- 标准库将npos定义为一个const string：：size_type类型，并初始化为值-1。
- npos是一个unsigned类型，此初始值意味着npos等于任何string最大的可能大小
string搜索函数返回string：：size_type值，该类型是一个unsigned类型。
因此，用一个int或其他带符号类型来保存这些函数的返回值不是一个好主意
string搜索操作¶
//搜索操作返回指定字符出现的下标，未找到返回npos
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_first_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无默认值。
string搜索操作¶
//find函数完成最简单的搜索。它查找参数指定的字符串，
//若找到，则返回第一个匹配位置的下标，否则返回npos：
string name("AnnaBelle");
auto pos1=name.finde("Anna");//pos1==0
//这段程序返回0，即子字符串"Anna"在"AnnaBelle"中第一次出现的下标。
//搜索（以及其他string操作）是大小写敏感的。
string lowercase("annabelle");
pos1=lowercase.finde("Anna");//pos1==npos
//查找与给定字符串中任何一个字符匹配的位置
string numbers("0123456789"), name("r2d2");
auto pos = name.find_first_of(numbers);//返回1
//搜索第一个不在参数中的字符
string dept("03714p3");
//返回5 p的下标
auto pos = dept.find_first_not_of(numbers);
指定在哪里开始搜索¶
可以传递给find一个可选的开始位置。这个可选的参数指出从哪个位置开始进行搜索。
- 默认情况下，此位置被置为0。
- 一种程序设计模式是用这个可选参数在字符串中循环地搜索子字符串出现的所有位置
string::size_type pos = 0;
while ((pos = name.find_first_of(numbers, pos))
!= string::npos) {
cout << "found number at index: " << pos
<< " element is " << name[pos] << endl;
++pos; // move to the next character
}
//while的循环条件将pos重置为从pos开始遇到的第一个数字的下标。
//只要find_first_of返回一个合法下标，我们就打印当前结果并递增pos。
//如果我们忽略了递增pos，循环就永远也不会终止。
逆向搜索¶
标准库还提供了类似的，但由右至左搜索的操作。
rfind成员函数搜索最后一个匹配，即子字符串最靠右的出现位置：
string river("Mississippi");
auto first_pos = river.find("is"); // returns 1
auto last_pos = river.rfind("is"); // returns 4
//find返回下标1，表示第一个"is"的位置，
//而rfind返回下标4，表示最后一个"is"的位置。
类似的，find_last函数的功能与find_first函数相似，
只是它们返回最后一个而不是第一个匹配：
- find_last_of搜索与给定string中任何一个字符匹配的最后一个字符。
- find_last_not_of搜索最后一个不出现在给定string中的字符。
- 每个操作都接受一个可选的第二参数，可用来指出从什么位置开始搜索。
练习¶
编写程序，首先查找string"ab2c3d7R4E6"中每个数字字符，
然后查找其中每个字母字符。编写两个版本的程序，
第一个要使用find_first_of，第二个要使用find_first_not_of。
#include <iostream>
#include <string>
using namespace std;
int main(){
string numbers("0123456789");
string s("ab2c3d7R4E6");
cout << "numeric characters: ";
for (int pos = 0;
(pos = s.find_first_of(numbers, pos)) != string::npos; ++pos){
cout << s[pos] << " ";
}
cout << "\nalphabetic characters: ";
for (int pos = 0;
(pos = s.find_first_not_of(numbers, pos)) != string::npos; ++pos){
cout << s[pos] << " ";
}
return 0;
}
练习¶
假定name和numbers的定义如前所示，numbers.find(name)返回什么？
string numbers("0123456789"),name("r2d2");
numbers.find(name)返回 string::npos
练习¶
如果一个字母延伸到中线之上，如d或f，则称其有上出头部分（ascender）。
如果一个字母延伸到中线之下，如p或g，则称其有下出头部分（descender）。
编写程序，读入一个单词文件，输出最长的既不包含上出头部分，
也不包含下出头部分的单词。
#include <string>
#include <fstream>
#include <iostream>
using std::string; using std::cout; using std::endl; using std::ifstream;
int main(){
ifstream ifs("data.txt");
if (!ifs) return -1;
string longest;
for (string curr; ifs >> curr; ){
if (string::npos == curr.find_first_not_of("aceimnorsuvwxz"))
longest = longest.size() < curr.size() ? curr : longest;
}
cout << longest << endl;
return 0;
}
compare函数¶
标准库string类型还提供了一组compare函数，
- 这些函数与C标准库的strcmp函数很相似。
- 类似strcmp，根据s是等于大于还是小于参数指定的字符串
s.compare返回0、正数或负数。
compare有6个版本。
- 根据我们是要比较两个string还是一个string与一个字符数组，参数各有不同。
s.compare的几种参数形式¶
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表示数值15——字符'1'后跟字符'5'。
- 一般情况，一个数的字符表示不同于其数值。
- 数值15如果保存为16位的short类型，则其二进制位模式为0000000000001111，
- 字符串"15"存为两个Latin-1编码的char，二进制位模式为0011000100110101。
- 第一个字节表示字符'1'，其八进制值为061，
- 第二个字节表示'5'，其Latin-1编码为八进制值065。
数值转换¶
新标准引入了多个函数，可以实现数值数据与标准库string之间的转换：
int i = 42;
// converts the int i to its character representation
string s = to_string(i);
double d = stod(s); // converts the string s to floating-point
//要转换为数值的string中第一个非空白符必须是数值中可能出现的字符：
// convert the first substring in s that starts with a digit, d = 3.14
string s2 = "pi = 3.14";
d = stod(s2.substr(s2.find_first_of("+-.0123456789")));
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起始子串（表示整数内容）的数值，
p是s中第一个非数值字符的下标，
默认是0，b是转换所用的基数。返回int
stol(s, p, b) 返回long
stoul(s, p, b) 返回unsigned long
stoll(s, p, b) 返回long long
stoull(s, p, b) 返回unsigned long long
stof(s, p) 返回s起始子串（表示浮点数内容）的数值，p是s中第一个
非数值字符的下标，默认是0。返回float
stod(s, p) 返回double
stold(s, p) 返回long double
练习¶
编写程序处理一个vector<string>，其元素都表示整型值。
计算vector中所有元素之和。修改程序，使之计算表示浮点值的string之和。
#include <iostream>
#include <string>
#include <vector>
auto sum_for_int(std::vector<std::string> const& v){
int sum = 0;
for (auto const& s : v) sum += std::stoi(s);
return sum;
}
auto sum_for_float(std::vector<std::string> const& v){
float sum = 0.0;
for (auto const& s : v) sum += std::stof(s);
return sum;
}
int main(){
std::vector<std::string> v = { "1", "2", "3", "4.5" };
std::cout << sum_for_int(v) << std::endl;
std::cout << sum_for_float(v) << std::endl;
return 0;
}
练习¶
设计一个类，它有三个unsigned成员，分别表示年、月和日。
为其编写构造函数，接受一个表示日期的string参数。你的构造函数应该能
处理不同的数据格式，如January 1,1900、1/1/1990、Jan 1 1900 等。
#include <iostream>
#include <string>
#include <vector>
using namespace std;
class My_date{
private:
unsigned year, month, day;
public:
My_date(const string &s){
unsigned tag;
unsigned format;
format = tag = 0;
练习¶
// 1/1/1900
if(s.find_first_of("/")!= string :: npos)
{
format = 0x01;
}
// January 1, 1900 or Jan 1, 1900
if((s.find_first_of(',') >= 4)
&& s.find_first_of(',')!= string :: npos){
format = 0x10;
}
else{ // Jan 1 1900
if(s.find_first_of(' ') >= 3
&& s.find_first_of(' ')!= string :: npos){
format = 0x10;
tag = 1;
}
}
练习¶
switch(format){
case 0x01:
day = stoi(s.substr(0, s.find_first_of("/")));
month = stoi(s.substr(s.find_first_of("/")
+ 1, s.find_last_of("/")- s.find_first_of("/")));
year = stoi(s.substr(s.find_last_of("/") + 1, 4));
break;
练习¶
case 0x10:
if( s.find("Jan") < s.size() ) month = 1;
if( s.find("Feb") < s.size() ) month = 2;
if( s.find("Mar") < s.size() ) month = 3;
if( s.find("Apr") < s.size() ) month = 4;
if( s.find("May") < s.size() ) month = 5;
if( s.find("Jun") < s.size() ) month = 6;
if( s.find("Jul") < s.size() ) month = 7;
if( s.find("Aug") < s.size() ) month = 8;
if( s.find("Sep") < s.size() ) month = 9;
if( s.find("Oct") < s.size() ) month =10;
if( s.find("Nov") < s.size() ) month =11;
if( s.find("Dec") < s.size() ) month =12;
char chr = ',';
if(tag == 1){
chr = ' ';
}
day = stoi(s.substr(s.find_first_of("123456789"), s.find_first_of(chr) - s.find_first_of("123456789")));
year = stoi(s.substr(s.find_last_of(' ') + 1, 4));
break;
}
}
练习¶
void print(){
cout << "day:" << day << " " << "month: " << month << " " << "year: " << year;
}
};
int main()
{
My_date d("Jan 1 1900");
d.print();
return 0;
}
容器适配器¶
标准库还定义了三个顺序容器适配器：stack、queue和priority_queue。
适配器（adaptor）是标准库中的一个通用概念。容器、迭代器和函数都有适配器。
- 本质上，一个适配器是一种机制，能使某种事物的行为看起来像另外一种事物一样。
- 一个容器适配器接受一种已有的容器类型，使其行为看起来像一种不同的类型。
- 例如，stack适配器接受一个顺序容器（除array或forward_list外），
并使其操作起来像一个stack一样。
所有容器适配器都支持的操作和类型¶
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) 同上
定义一个适配器¶
每个适配器都定义两个构造函数：
- 默认构造函数创建一个空对象，接受一个容器的构造函数拷贝该容器来初始化适配器。
- 例如，假定deq是一个deque<int>，
我们可以用deq来初始化一个新的stack，如下所示：
stack<int> stk(deq);//从deq拷贝元素到stk
- 默认情况下，stack和queue是基于deque实现的，priority_queue是在vector之上实现的。
- 我们可以在创建一个适配器时将一个命名的顺序容器作为第二个类型参数，
来重载默认容器类型。
//在vector上实现的空栈
stack<string,vector<string>> str_stk;
//str_stk2在vector上实现，初始化时保存svec的拷贝
stack<string,vector<string>> str_stk2(svec);
定义一个适配器¶
对于一个给定的适配器，可以使用哪些容器是有限制的。
- 所有适配器都要求容器具有添加和删除元素的能力。
因此，适配器不能构造在array之上。
- 类似的，我们也不能用forward_list来构造适配器，因为所有适配器
都要求容器具有添加、删除以及访问尾元素的能力。
- stack只要求push_back、pop_back和back操作，因此可以使用
除array和forward_list之外的任何容器类型来构造stack。
- queue适配器要求back、push_back、front和push_front，
因此它可以构造于list或deque之上，但不能基于vector构造。
- priority_queue除了front、push_back和pop_back操作之外还要求随机访问能力，
因此它可以构造于vector或deque之上，但不能基于list构造。
栈适配器¶
stack类型定义在stack头文件中。下面的程序展示了如何使用stack：
stack<int> intStack; // empty stack
// fill up the stack
for (size_t ix = 0; ix != 10; ++ix)
intStack.push(ix); // intStack holds 0 . . . 9 inclusive
// while there are still values in intStack
while (!intStack.empty()) {
int value = intStack.top();
// code that uses value
cout << value << endl;
intStack.pop(); // pop the top element, and repeat
}
栈操作¶
s.pop() 删除栈顶元素，不返回。
s.push(item) 创建一个新元素，压入栈顶，该元素通过拷贝或移动item而来
s.emplace(args) 同上，但元素由args来构造。
s.top() 返回栈顶元素，不删除。
- 定义在stack头文件中。
- stack默认基于deque实现，也可以在list或vector之上实现。
栈适配器¶
每个容器适配器都基于底层容器类型的操作定义了自己的特殊操作。
- 我们只可以使用适配器操作，而不能使用底层容器类型的操作。
- 例如，intStack.push(ix);//intStack保存0到9 十个数
- 此语句试图在intStack的底层deque对象上调用push_back。
- 虽然stack是基于deque实现的，但我们不能直接使用deque操作。
- 不能在一个stack上调用push_back，而必须使用stack自己的操作——push。
队列适配器¶
- queue和priority_queue适配器定义在queue头文件中。
- queue默认基于deque实现，priority_queue默认基于vector实现。
- queue可以在list或vector之上实现，priority_queue也可以用deque实现。
q.pop() 删除队首元素，但不返回。
q.front() 返回队首元素的值，不删除。
q.back() 返回队尾元素的值，不删除。只适用于queue
q.top() 返回具有最高优先级的元素值，不删除。 只适用于priority_queue
q.push(item) 在队尾压入一个新元素。
q.emplace(args) 其值为item，或者有args构造
队列适配器¶
标准库queue使用一种先进先出（first-in，first-out，FIFO）的存储和访问策略。
- 进入队列的对象被放置到队尾，而离开队列的对象则从队首删除。
- 饭店按客人到达的顺序来为他们安排座位，就是一个先进先出队列的例子。
priority_queue允许我们为队列中的元素建立优先级。
- 新加入的元素会排在所有优先级比它低的已有元素之前。
- 饭店按照客人预定时间而不是到来时间的早晚来为他们安排座位，
就是一个优先队列的例子。
- 默认情况下，标准库在元素类型上使用<运算符来确定相对优先级。
我们将在后续学习如何重载这个默认设置。
练习¶
使用stack处理括号化的表达式。当你看到一个左括号，将其记录下来。
当你在一个左括号之后看到一个右括号，
从stack中pop对象，直至遇到左括号，将左括号也一起弹出栈。
然后将一个值（括号内的运算结果）push到栈中，
表示一个括号化的（子）表达式已经处理完毕，被其运算结果所替代。
此题留作思考题，计算字符串"5 * ( 3 + 4 )" 的值
实践课¶
- 从课程主页 cpp.njuer.org 打开 《面向对象编程基础》实验课 cloud shell界面 https://developer.aliyun.com/adc/scenario/476f2ff6afad4221bac08e33cf6984fc
- 使用g++编译代码
- 编辑一个 readme.md 文档,键入本次实验心得.
- 使用git进行版本控制 可使用之前的gitee代码仓库
- 云服务器（elastic compute service,简称ecs） - aliyun linux 2是阿里云推出的 linux 发行版 - vim是从vi发展出来的一个文本编辑器. - g++ 是c++编译器
习题1
//输入文件是 "上证指数2021-日期-时间-开-高-低-收-成交量-成交额.csv"
//下载方式 git clone https://gitee.com/cpp-njuer-org/book
//数据文件位于~/book/test/week11/上证指数2021-日期-时间-开-高-低-收-成交量-成交额.csv"
//数据样例：
//2021-01-06 15:00 3549.38 3550.91 3549.38 3550.88 4617728 6464176128
//各数据项分别代表上证指数关于日期-时间-开-高-低-收-成交量-成交额的数据。
//编程计算,仅从2021年每日收盘指数看，连续上涨时间最长的区间是从哪天到哪天？
//编程计算,仅从2021年每日收盘指数看，连续下跌时间最长的区间是从哪天到哪天？
习题2
//设计一个类，它有三个unsigned成员，分别表示年、月和日。
//为其编写构造函数，接受一个表示日期的string参数。你的构造函数应该能
//处理不同的数据格式，如1月1日1990年、January 1,1900、1/1/1990、Jan 1 1900 等。
习题3
//使用stack处理括号化的表达式。当你看到一个左括号，将其记录下来。
//当你在一个左括号之后看到一个右括号，
//从stack中pop对象，直至遇到左括号，将左括号也一起弹出栈。
//然后将一个值（括号内的运算结果）push到栈中，
//表示一个括号化的（子）表达式已经处理完毕，被其运算结果所替代。
//计算字符串"5 * ( 3 + 4 )" 的值
编辑c++代码和markdown文档,使用git进行版本控制
yum install -y git gcc-c++
使用git工具进行版本控制
git clone你之前的网络git仓库test(或其它名字)
cd test 进入文件夹test
(clone的仓库,可移动旧文件到目录weekN: mkdir -p weekN ; mv 文件名 weekN;)
vim test1.cpp
g++ ./test1.cpp 编译
./a.out 执行程序
vim test2.cpp
g++ ./test2.cpp 编译
./a.out 执行程序
vim test3.cpp
g++ ./test3.cpp 编译
./a.out 执行程序
git add . 加入当前文件夹下所有文件到暂存区
git config --global user.email "you@example.com"
git config --global user.name "Your Name"
vim readme.md 键入新内容（实验感想),按ESC 再按：wq退出
git add .
git commit –m "weekN" 表示提交到本地,备注weekN
git push 到你的git仓库
git log --oneline --graph 可看git记录
键入命令并截图或复制文字,并提交到群作业.
cat test* readme.md
提交¶
- 截图或复制文字,提交到群作业.
- 填写阿里云平台（本实验）的网页实验报告栏,发布保存.本次报告不需要分享提交
- 填写问卷调查 https://rnk6jc.aliwork.com/o/cppinfo
关于使用tmux¶
sudo yum install -y tmux
cd ~ && wget https://cpp.njuer.org/tmux && mv tmux .tmux.conf
tmux 进入会话 .
前缀按键prefix= ctrl+a,
prefix+c创建新面板,
prefix+"分屏,
prefix+k选上面,prefix+j选下面,
prefix+1选择第一,prefix+n选择第n,
prefix+d脱离会话
tmux attach-session -t 0 回到会话0
vim 共分为三种模式¶
- 命令模式
- 刚启动 vim,便进入了命令模式.其它模式下按ESC,可切换回命令模式
- i 切换到输入模式,以输入字符.
- x 删除当前光标所在处的字符.
- : 切换到底线命令模式,可输入命令.
- 输入模式
- 命令模式下按下i就进入了输入模式.
- ESC,退出输入模式,切换到命令模式
- 底线命令模式
- 命令模式下按下:（英文冒号）就进入了底线命令模式.
- wq 保存退出
vim 常用按键说明¶
除了 i, Esc, :wq 之外,其实 vim 还有非常多的按键可以使用.命令模式下：
- 光标移动
- j下 k上 h左 l右
- w前进一个词 b后退一个词
- Ctrl+d 向下半屏 ctrl+u 向上半屏
- G 移动到最后一行 gg 第一行 ngg 第n行
- 复制粘贴
- dd 删一行 ndd 删n行
- yy 复制一行 nyy复制n行
- p将复制的数据粘贴在下一行 P粘贴到上一行
- u恢复到前一个动作 ctrl+r重做上一个动作
- 搜索替换
- /word 向下找word ？word 向上找
- n重复搜索 N反向搜索
- :1,$s/word1/word2/g从第一行到最后一行寻找 word1 字符串,并将该字符串
取代为 word2
vim 常用按键说明¶
底线命令模式下：
- :set nu 显示行号
- :set nonu 取消行号
- :set paste 粘贴代码不乱序
【注：把caps lock按键映射为ctrl,能提高编辑效率.】
Markdown 文档语法¶
# 一级标题
## 二级标题
*斜体* **粗体**
- 列表项
- 子列表项
> 引用
[超链接](http://asdf.com)
|表格标题1|表格标题2|
|-|-|
|内容1|内容2|