c++ Primer 第九章：顺序容器 练习答案记录

c++ Primer 第九章：顺序容器 练习答案记录

下面的练习别忘记都加上下面这一语句

#include
1

9.1 顺序容器概述

练习9.1 对于下面的程序任务，vector、deque和list哪种容器最为适合？解释你的选择的理由。如果没有哪一种容器优于其他容器，也请解释理由。

(a)读取固定数量的单词，将它们按字典序插入到容器中。我们将在下一章中看到，关联容器更适合这个问题：
list，需要在中间插入数据，list最好；

(b) 读取未知数量的单词，总是将单词插入到末尾。删除操作在头部进行。
deque，需要在头部和尾部插入或删除元素，选deque；

©从一个文件读取未知数量的整数。将这些数排序，然后将它们打印到标准输出。
vector，没有特别的需求选vector。

9.2 容器库概览

练习9.2 定义一个list对象，其元素类型是int的deque

#include
#include
using namespace std;
int main()
{
	list<deque<int>> a;
}
1
2
3
4
5
6
7

9.2.1 迭代器

练习9.3 构成迭代器范围的迭代器有何限制？

forward_list迭代器不支持递减运算符（–）
iter+n,iter-n,iter1+=n,iter1-=n,iter1-iter2,>,>=,<,<=这些运算只能应用于string、vector、deque和array迭代器
一个迭代器范围一般为左闭合区间【begin，end）

练习9.4 编写函数，接受一对指向vector的迭代器和一个int值。在两个迭代器指定的范围中查找给定的值，返回一个布尔值来指出是否找到。

#include
using namespace std;
int main()
{
	vector<int> a = { 1,2,3,4 };
	int b = 3;
	for (auto i = a.begin(); i != a.end(); ++i) {
		if (*i == b) {
			cout << true << endl;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12

练习9.5 重写上一题的函数，返回一个迭代器指向找到的元素。注意，程序必须处理未找到给定值的情况。

#include
using namespace std;
int main()
{
	vector<int> a = { 1,2,3,4 };
	int b = 0, digit = 0;
	for (auto i = a.begin(); i != a.end(); ++i) {
		if (*i == b) {
			cout << "找到的数是：" << b << endl;
			digit = 1;
		}
		if (i == (a.end() - 1) && digit == 0) {
			cout << "未找到给定值" << endl;
		}
	}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

练习9.6 下面的程序有何错误？你应该如何修改它？

#include
#include
using namespace std;
int main()
{
	list<int> lst1;
	list<int>::iterator iter1 = lst1.begin(),iter2 = lst1.end();
	while (iter1 < iter2) /* ... */
}
1
2
3
4
5
6
7
8
9

修改后

#include
#include
using namespace std;
int main()
{
	list<int> lst1;
	list<int>::iterator iter1 = lst1.begin(),iter2 = lst1.end();
	while (iter1 != iter2) /* ... */
}
1
2
3
4
5
6
7
8
9

9.2.2 容器类

练习9.7 为了索引int 的 vector中的元素，应该使用什么类型？

vector<int>::size_type
1

练习9.8 为了读取string 的list 中的元素，应该使用什么类型？如果写入list，又应该使用什么类型？

list<string>::const_iterator		//read
list<string>::iterator		    //write
1
2

9.2.3 begin和end成员

练习9.9 begin 和 cbegin 两个函数有什么不同？

当auto与begin或end结合使用时，获得的迭代器类型依赖于容器类型，与我们想要如何使用迭代器毫不相干。
但以c开头的版本还是可以获得const_iterator的，而不管容器的类型是什么。

练习9.10 下面四个对象分别是什么类型？

vector<int> v1;          
const vector<int> v2;
auto it1 = v1.begin(), it2 = v2.begin();
auto it3 = v1.cbegin(), it4 = v2.cbegin();
1
2
3
4

it1类型是vector::iterator
it2类型是vector::const_iterator
it3类型是vector::const_iterator
it4类型是vector::const_iterator

9.2.4 容器定义和初始化

练习9.11 对6种创建和初始化 vector 对象的方法，每一种都给出一个实例。解释每个vector包含什么值。

vector a; 默认构造函数，a为空
vector a={0,1,2}; a中为1，2，3
vector a(10); a中10个0
vector a(10,1); a中10个1
vector a{0,1,2}; a中为1，2，3
vector a(b.begin(),b.end()); a中为b的int化的元素
vector a(b); 将b赋给a

练习9.12 对于接受一个容器创建其拷贝的构造函数，和接受两个迭代器创建拷贝的构造函数，解释它们的不同。

1、当将一个容器初始化为另一个容器的拷贝时，两个容器的容器类型的元素类型都必须相同
2、接受两个迭代器创建拷贝的构造函数用这两个迭代器表示我们想要拷贝的一个元素范围，与以往一样，两个迭代器分别标记想要拷贝的第一个元素和尾巴元素之后的位置，新容器中的每个元素都用范围中对应元素的值进行初始化。

练习9.13 如何从一个list初始化一个vector？从一个vector又该如何创建？编写代码验证你的答案。

#include
#include
using namespace std;
int main()
{
	list<int> a = { 1,2,3 };
	vector<int> b(a.begin(), a.end());
	for (auto i : b) {
		cout << i << endl;
	}
	vector<double> c(b.begin(), b.end());
	for (auto i : c) {
		cout << i << endl;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

9.2.5 赋值和swap

练习9.14 编写程序，将一个list中的char * 指针(指向C风格元素）元素赋值给一个vector中的string。

#include
#include
using namespace std;
int main()
{
	list<const char*> a(10, "a");
	vector<string> b;
	b.assign(a.begin(),a.end());
	for (auto i : b) {
		cout << i << endl;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12

9.2.6 容器大小操作

9.2.7 关系运算符

练习9.15 编写程序，判定两个vector是否相等。

#include
using namespace std;
int main()
{
	vector<int> a = { 1,2,3 };
	vector<int> b = { 1,2,3,4 };
	vector<int> c = { 1,2,5 };
	vector<int> d = { 2,1,3 };
	cout << (a < b ? 1 : 0) << endl;
	cout << (a < c ? 1 : 0) << endl;
	cout << (a < d ? 1 : 0) << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12

练习9.16 重写上一题的程序，比较一个list中的元素和一个vector中的元素。

#include
#include
using namespace std;
int main()
{
	vector<int> a = { 1,2,3 };
	vector<int> b = { 1,2,3,4 };
	vector<int> c = { 1,2,5 };
	vector<int> d = { 2,1,3 };
	cout << (a < b ? 1 : 0) << endl;
	cout << (a < c ? 1 : 0) << endl;
	cout << (a < d ? 1 : 0) << endl;

	list<int> e = { 1,2,3 };
	vector<int> f(e.begin(), e.end());
	cout << (a == f ? 1 : 0) << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

练习9.17 假定c1 和 c2 是两个容器，下面的比较操作有何限制？

if(c1<c2)
1

c1和c2不能是无序容器，且容器类型要相同，最后，元素类型要支持运算符。

9.3 顺序容器操作

9.3.1 向顺序容器添加元素

练习9.18 编写程序，从标准输入读取string序列，存入一个deque中。编写一个循环，用迭代器打印deque中的元素。

#include
#include
using namespace std;
int main()
{
	string a;
	deque<string> b;
	while (cin >> a) {
		if (a == "no")
			break;
		b.push_back(a);
	}
	for (auto i : b) {
		cout << i << endl;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

练习9.19 重写上一题的程序，用list替代deque。列出程序要做出哪些改变。

#include
#include
using namespace std;
int main()
{
	string a;
	list<string> b;
	while (cin >> a) {
		if (a == "no")
			break;
		b.push_back(a);
	}
	for (auto i : b) {
		cout << i << endl;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

练习9.20 编写程序，从一个list拷贝元素到两个deque中。值为偶数的所有元素都拷贝到一个deque中，而奇数值元素都拷贝到另一个deque中。

#include
#include
using namespace std;
int main()
{
	int a;
	list<int> input;
	deque<int> output1, output2;
	while (cin >> a) {
		input.push_back(a);
	}
	for (auto i : input) {
		if (i % 2 == 0) {
			output1.push_back(i);
		}
		else {
			output2.push_back(i);
		}
	}
	cout << "偶数是：";
	for (auto i : output1) {
		cout << i << " ";
	}
	cout << endl;
	cout << "奇数是：";
	for (auto i : output2) {
		cout << i << " ";
	}
	cout << endl;
}
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

练习9.21 如果我们将第308页中使用 insert 返回值将元素添加到list中的循环程序改写为将元素插入到vector中，分析循环将如何工作。

一样的操作，实现的是在vector的一个特定位置反复插入元素。

练习9.22 假定iv是一个int的vector，下面的程序存在什么错误？你将如何修改？

#include
using namespace std;
int main()
{
	vector<int> iv(10, 0);
	int some_val = 1;
	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);
}
1
2
3
4
5
6
7
8
9
10
11
12

循环不会停止，一直在头部插入元素；迭代器在插入操作后会变化。

修改后

#include
using namespace std;
int main()
{
	vector<int> iv(10, 0);
	int some_val = 1;
	vector<int>::iterator iter = iv.begin(),
		mid = iv.begin() + iv.size() / 2;
	while (iter != mid)
	{
		if (*iter == some_val)
		{
			iter = iv.insert(iter, 2 * some_val);
			++iter;
		}
		++iter;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

9.3.2 访问元素

练习9.23 在本节第一个程序中，若 c.size() 为1，则val、val2、val3和val4的值会是什么？

都是c中唯一元素的拷贝。

练习9.24 编写程序，分别使用 at、下标运算符、front 和 begin 提取一个vector中的第一个元素。在一个空vector上测试你的程序。

#include
using namespace std;
int main()
{
	vector<int> a;
	cout << a.at(0) << endl;
	cout << a.front() << endl;
	cout << a.back() << endl;
}
1
2
3
4
5
6
7
8
9

9.3.3 删除元素

练习9.25 对于第312页中删除一个范围内的元素的程序，如果 elem1 与 elem2 相等会发生什么？如果 elem2 是尾后迭代器，或者 elem1 和 elem2 皆为尾后迭代器，又会发生什么？

如果elem1与elem2相等，则一个元素都不会删除；
如果elem2是尾后迭代器，则会从elem1元素删除到最后一个元素；
如果elem1与elem2都是尾后迭代器，则一个元素都不会删除。

练习9.26 使用下面代码定义的ia，将ia 拷贝到一个vector和一个list中。使用单迭代器版本的erase从list中删除奇数元素，从vector中删除偶数元素。

int ia[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 55, 89 };

#include
#include
using namespace std;
int main()
{
	int ia[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 55, 89 };
	vector<int> a;
	list<int> b;
	for (auto i : ia) {
		a.push_back(i);
		b.push_back(i);
	}
	for (auto i = a.begin(); i != a.end(); i) {
		if (*i % 2 == 0) {
			i = a.erase(i);
		}
		else
			i++;
	}
	for (auto i = b.begin(); i != b.end(); i) {
		if (*i % 2 != 0) {
			i = b.erase(i);
		}
		else
			i++;
	}
	for (auto i : a)
		cout << i << " ";
	cout << endl;
	for (auto i : b)
		cout << i << " ";
	cout << endl;
}
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

9.3.4 特殊的forward_list操作