C++primer第九章习题解答

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

(a)读取固定数量的单词，将他们按字典顺序插入到容器中。我们将在下一章看到关联容器更适合这个问题。

(b)读取未知数量的单词，总是将新单词插入到末尾。删除操作在头部进行。

(c)从一个文件读取未知数量的整数。将这些数排序，然后将它们打印到标准输出。

(a) “按字典顺序插入到容器中”意味着进行插入排序操作，从而需要在容器内部频繁进行插入操作，vector在尾部之外的位置差如何删除元素很慢，deque在头尾之外的位置插入和删除元素很慢，而list在任何位置插入、删除速度都很快。因此这个任务选择list更为适合。

(b)由于需要在头、尾分别进行插入、删除等操作，因此将vector排除在外，deque和list都可以达到很好的性能。如果还需要频繁进行随机访问，则deque更好。

(c)由于整数占用空间很小，且快速的排序算法需频繁随机访问元素，将list排除在外。由于无需在头部进行插入、删除操作，因此使用vector即可，无需使用deque。

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

list<>> lines;

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

两个迭代器begin和end必须指向同一个容器中的元素，或者是容器最后一个元素之后的位置；而且，对begin反复进行递增操作，可以保证达到end，即end不在begin之前。

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

#include 
#include 
using std::cout;
using std::endl;
using std::vector;

bool find_x(vector::iterator begin, vector::iterator end, int x)
{
	for(; begin != end; ++begin)
		if (*begin == x)
			return true;
	return false;
}

int main()
{
	vector vec={1, 2, 4, 3, 5, 8, 10, 3, 4};
	cout<

练习9.5：重写上一题的函数，返回一个迭代器指向找到的元素。注意，程序必须处理未找到给定值的情况。
 
 
#include 
#include 
using std::cout;
using std::endl;
using std::vector;

vector::iterator find_x(vector::iterator begin, vector::iterator end, int x)
{
	for(; begin != end; ++begin)
		if (*begin == x)
			return begin;
	return end;
}

int main()
{
	vector vec={1, 2, 4, 3, 5, 8, 10, 3, 4};
	cout<

练习9.6：下面程序有何错误？你应该如何修改它？
 
 
list lst1;
list::iterator iter1 = lst1.begin(), iter2 = lst1.end();
while(iter1 < iter2） /*. . .*/
list不支持<运算，只支持递增递减、==以及!=操作。可改成iter1 != iter2.
 
 
练习9.7：为了索引int的vector中的元素，应该使用什么类型？
使用迭代器类型vector::iterator来索引int的vector中的元素。
 
练习9.8：为了读取string的list中的元素，应该使用什么类型？如果写入list又该用什么类型？
为了读取string的list中的元素，应使用list::valus_type，写入数据需要引用类型，使用list::reference。
 
练习9.9：begin和cbegin两个函数有什么不同？
cbegin是C++新标准引入来的，用来与auto结合使用。它返回指向容器第一个元素的const迭代器，可以用来只读地访问容器，但不能对容器元素进行修改。因此，当不需要写访问时，应该使用cbegin。
begin则是被重载过的，有两个版本：其中一个是const成员函数，也返回const迭代器；另一个则返回普通迭代器，可以对容器元素进行修改。
 
练习9.10：下面4个对象分别是什么类型？
 
vector v1;
const vector v2;
auto it1 = v1.begin(), it2 = v2.begin();
auto it3 = v1.begin(), it4 = v2.cbegin();
v1是int的vector类型，可以修改v1的内容，包括添加、删除元素以及修改元素等操作。
 
v2是int的常量vector类型，其内容不能修改，添加、删除元素以及修改元素值等均不允许。
it1是普通迭代器，可对容器元素进行读写访问，it2是const迭代器，不能对容器元素进行写访问。it3和it4都是const迭代器。

 
 
练习9.11：对6种创建和初始化vector对象的方法，每一种都给出一个实例。解释每个vector包含什么值。
vector ilist; 默认初始化，vector为空，容器中尚未有元素。
vector ilist2(ilist); ilist2初始化为ilist的拷贝，ilist必须与ilist2类型相同。
vector ilist = {1,2,3.0,4,5,6,7};初始化为列表中元素的拷贝，列表中的元素类型必须与ilist的元素类型相容，这里必须是与整型相容的数值类型。
vector ilist3(ilist.begin()+2, ilist.end()-1);ilist3初始化为两个迭代器指定范围中的元素的拷贝，范围中的元素类型必须与ilist的元素类型相容，这里ilist3被初始化为{3, 4, 5, 6}.
vector ilist4(7); 默认值初始化，ilist4中将包含7个元素，每个元素进行缺省的值初始化，对于int，也就是被赋值为0.
vector ilist5(7, 3); 指定值初始化，ilist5被初始化为包含7个值为3的int。
 
练习9.12：对于接受一个容器创建其拷贝的构造函数，和接受两个迭代器创建拷贝的构造函数，解释它们的不同。
接受一个已有容器的构造函数会拷贝瓷容器中的所有元素，这样，初始化完成后，我们得到此容器的一个一模一样的拷贝、当我们确实需要一个容器的完整拷贝时，这种初始化方式非常方便。这要求两个容器的类型以及其元素leixi9ng必须匹配。
当我们不需要已有容器中的全部元素，而只是想拷贝其中一部分元素时，可使用接受两个迭代器的构造函数。这不要求容器类型相同，新容器和原容器中的元素类型也可以不同，只要能将要拷贝的元素转换成要初始化的容器的元素类型即可。
 
练习9.13：如何从一个list初始化一个vector? 从一个vector又该如何创建？编写代码验证你的答案。
对于这两个初始化，可以采用范围初始化的方式来构造vector。
 
#include 
using std::cin;
using std::cout;
using std::endl;
using std::ends;
#include 
using std::vector;
#include 
using std::list;

int main()
{
	list li={0,1,2,3,4,5,5,6,7,9};
	list::iterator b=li.begin(), e=li.end();
	vector ivec1={1,2,3,2,5,7,0,2,5};

	for(;b!=e;++b)
		cout<<*b< ivec2(li.begin(), li.end());
	for(auto i:ivec2)
		cout<<> ivec3(ivec1.begin(), ivec1.end());
	for(vector::iterator it=ivec3.begin();it!=ivec3.end();++it)
		cout<<*it<练习9.14：编写程序，讲一个list中的char *指针元素赋值给一个vector中的string。
 
 
#include 
#include 
#include 
#include 
using std::cout;
using std::endl;
using std::string;
using std::vector;
using std::list;

int main()
{
	list slist;
	char s1[] = "Hello";
	char s2[] = "C++";
	char s3[] = "Primer!";
	slist.push_back(s1);
	slist.push_back(s2);
	slist.push_back(s3);
	vector svec;
	svec.assign(slist.begin(), slist.end());
	cout<

练习9.21：如果我们将第308页中使用的insert返回值将元素添加到list中的循环程序改写为将元素插入到vector中，分析循环将如何工作。
 
在循环之前，vector为空，此时将iter初始化为vector首位置，与初始化为尾位置效果是一样的。循环中第一次调用insert会将读取的第一个string插入到iter指向位置之前的位置，即令新元素成为vector的首元素。而insert的返回指向此元素的迭代器，我们将它赋予iter，从而使得iter始终指向vector的首元素。接下来每步亦是如此，将新string插入到vector首元素之前的位置，成为新的首元素，并使iter始终指向vector首。
 
练习9.22：假定iv是一个int的vector，下面的程序存在什么错误？你将如何修改？
 
vector::iterator iter = iv.begin(), mid = iv.begin + iv.size()/2;
while(iter != mid)
	if(*iter == some_val)
		iv.insert(iter, 2*some_val);
循环中未对iter进行递增操作，iter无法向中点推进。其次，即使加入了++iter语句，由于向iv插入元素后，iter已经失效，++iter也不能起到将迭代器向前推进一个元素的作用。
 
 
#include 
#include 
using std::cout;
using std::endl;
using std::vector;

int main()
{
	vector iv= {1, 1, 1, 1, 1};
	int some_val = 1;
	vector::iterator iter = iv.begin();
	int org_size = iv.size(), i = 0;

	while(i <= org_size/2) {
		if(*iter == some_val) {
			iter = iv.insert(iter, 2*some_val);
			++iter;
			++iter;
		}
		++i;
	}

	for(iter = iv.begin(); iter != iv.end(); ++iter)
		cout<<*iter<

练习9.23：在本节第一个程序中，若c.size()为1，则val、val2、val3和val4的值会是什么？
4个变量的值一样，指向唯一的一个元素。
练习9.24：编写程序，分别使用at、下标运算符、front和begin提去一个vector中的第一个元素。在一个空vector上测试你的程序。
#include 
using std::cout;
using std::endl;
#include 
using std::vector;

int main()
{
	vector vec;
	cout<<>

练习9.25：对于第312页中删除一个范围内的元素的程序，如果elem1与elem2相等会发生什么？如果elem2是尾后迭代器，或者elem1和elem2皆为尾后迭代器，又会发生什么？
如果两个迭代器elem1和elem2相等，则什么也不会发生，容器保持不变。哪怕两个迭代器是指向尾后位置也是如此，程序不会出错。
因此elem1和elem2都是尾后迭代器时，容器保持不变。
如果elem2为尾后迭代器，eleme1指向之前的合法位置，则会删除从elem1开始直至容器末尾的所有元素。
练习9.26：使用下面代码定义的ia，将ia拷贝到一个vector和一个list中。使用单迭代器版本的erase从list中删除奇数元素，从vector中删除偶数元素。
int ia[] = {0, 1, 1, 2, 3, 5, 8, 13, 21, 55, 89}
#include 
using std::endl;
using std::cout;
#include 
using std::vector;
using std::begin;
using std::end;
#include 
using std::list;

int main()
{
	int ia[]={0,1,1,2,3,5,8,13,21,55,89};
	vector vec(begin(ia), end(ia));
	list lis(begin(ia), end(ia));
	auto it=vec.begin();
	while(it!=vec.end())
	{
		if(!(*it%2))
			it=vec.erase(it);
		else
			++it;
	}
	auto ir=lis.begin();
	while(ir!=lis.end())
	{
		if(*ir%2)
			ir=lis.erase(ir);
		else
			++ir;
	}
	for(auto i: vec)
		cout<

练习9.27：编写程序，查找并删除forward_list中的奇元素。
#include 
using std::cout;
using std::endl;
#include 
using std::forward_list;

int main()
{
	forward_list 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;
		}
	}
	for(auto i: flst)
		cout<>s1>>s2;
	find_insert(flst,s1,s2);
	cout<<"Now the forward_list is: "<

练习9.29：假定vec包含25个元素，那么vec.resize(100)会做什么？如果接下来调用vec.resize(10)会做什么？
调用vec.resize(100)会向vec末尾添加75个元素，这些元素将进行值初始化。接下来调用vec.size(10)会将vec末尾90个元素删除。
练习9.30：接受单个参数的resize版本对元素类型有什么限制？(如果有的话)
对于元素时类类型，则单参数resize版本要求该类必须提供一个默认构造函数。
练习9.31第316页中删除偶数值元素并复制奇数值元素的程序不能用于list或forward_list。为什么？修改程序，使之也能用于这些类型。
list和forward_list与其他容器的一个不同是，迭代器不支持加减运算，因为链表中元素并非在内存中连续存储，无法通过地址的加减在元素间远距离移动，可以多次调用++来实现与迭代器加法相同的效果。
#include 
using std::cout;
using std::endl;
#include 
using std::list;
#include 
using std::forward_list;

int main()
{
	list lt={0,1,2,3,4,5,6,7,8,9};
	forward_list flst={0,1,2,3,4,5,6,7,8,9};
	cout<<"List is :"<::iterator it=lt.begin();
	while(it!=lt.end())
	{
		if(*it%2)
		{
			it=lt.insert(it, *it);
			++it;
			++it;
		}
		else
		{
			it=lt.erase(it);
		}
	}
	cout<<"Now list is: "<

练习9.32：在第316页的程序中，向下面语句这样调用insert是否合法？如果不合法，为什么？
iter = vi.insert(inter. *iter++);
不合法。编译器在编译代码时，首先对*iter++求值，传递给insert第二个形参，此时iter已指向当前奇数的下一个元素，因此传递给insert的第一个参数是错误位置，程序执行会发生混乱。
练习9.33：在本节最后一个例子中，如果不将insert的结果赋予begin，将会发生什么？编写程序，去掉此赋值语句，验证你的答案。
向vector中插入新元素后，原有迭代器都会失效。因此，不将insert()返回的迭代器赋予begin，会使begin失效。继续使用begin会导致程序崩溃。
 
练习9.34：假定vi是一个保存int的容器，其中有偶数值也有奇数值，分析下面循环的行为，然后编写程序验证你的分析是否正确。
iter = vi.begin();
while (iter !=  vi.end())
    if(*iter % 2)
        iter = vi.insert(iter, *iter);
++iter;


这段代码的第一个错误是忘记使用花括号，使得++iter编程循环后的第一条语句，而非循环所期望的循环体的最后一条语句。除非容器为空，否则陷入死循环。若容器的第一个元素为偶数，布尔表达式为假，if语句真分支不会被执行，iter保持不变。循环继续执行，真分支仍然不会执行，iter继续保持不变，如此陷入死循环。若容器中的第一个元素是奇数，insert语句被调用，将该值插入到首元素之前，并将返回的迭代器赋予iter，因此iter指向新首元素，继续执行循环，会继续将首元素复制到容器首位置，并令iter指向它，如此陷入死循环。

测试程序：
#include 
#include 
#include 
using std::string;
using std::cin;
using std::cout;
using std::endl;
using std::vector;

int main()
{
	vector vi={1, 2, 3, 4, 5, 6, 7, 8, 9};
	auto iter = vi.begin();
	string tmp;
	while(iter != vi.end()) {
		if (*iter % 2)
			iter = vi.insert(iter, *iter);
		for(auto begin = vi.begin(); begin !=vi.end(); ++begin)
			cout<<*begin<<" ";
		cout<>tmp;
	}
	++iter;

	return 0;
}
正确的做法是将++iter移入循环体，再加一个++iter即可。



 
练习9.35：解释一个vector的capacity和size有何区别？
capacity返回已经为vector分配了多大内存空间，而size则返回容器当前已经保存了多少个元素。
 
练习9.36：一个容器的capacity可能小于它的size吗？
不可能小于size。
 
练习9.37：为什么list和array没有capacity成员函数？
list是链表，当有新元素插入时，会从内存空间分配一个新节点保存它；当从链表中删除元素时，该节点占用的内存空间会被立刻释放。因此一个链表占用的内存空间总是与当前保存的元素所需的空间相等。而array是固定大小数组，内存一次性分配，大小不变，不会变化，因此它们均不需要capacity。
 
练习9.39：解释下面的程序片段做了什么：
 
vector svec;
svec.reserve(1024);
string word;
while (cin >> word)
    svec.push_back(word);
svec.resize(svec.resize() + svec.size()/2);
首先，reserve为svec分配了1024个元素的空间。随后，循环不断读入字符，添加到svec末尾，直到遇到文件结束符。这个过程中，如果读入的字符串数量不多于1024，则svec的capacity保持不变，不会分配新的内存空间。否则，会按一定规则分配更大的内存空间，并进行字符串的移动。接下来，resize将向svec末尾添加当前字符串数量一半那么多的新字符串，他们的值都是空串。若空间不够，会分配足够容纳这些字符串的内存空间。
练习9.40：如果上一题中的程序读入的256个词，在resize之后的容器的capacity可能是多少？如果读入了512个、1000个或1048个词呢？
若读入了256个词，则resize之后容器的capacity僵尸384；若读入了512个词，则resize之后的容器capacity僵尸768。若读入了1000个词，则resize之后容器的capacity是2048；若读了1048个词，还是2048。
 
练习9.41：编写程序，从一个vector初始化一个string。
 
#include 
using std::vector;
#include 
using std::cout;
using std::endl;
#include 
using std::string;

int main()
{
	vector cvec={'b','e','a','u','t','i','f','u','l'};
	string s(cvec.data(),cvec.size());
	cout<<>

练习9.42：假定你希望每次读取一个字符存入一个string中，而且知道最少需要读取100个字符，你应该如何提高程序的性能？
 
可以用reserve先为string分配100个字符的空间，然后逐个读取字符，用push_back添加到string末尾。
 
#include 
#include 
#include 
using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;

void inputString(string &s)
{
	s.reserve(100);
	char c;
	while(cin>>c)
		s.push_back(c);
}

int main()
{
	string s;
	inputString(s);
	cout<<>

练习9.43：编写一个函数，接受三个string参数s、oldVal和newVal。使用迭代器及insert和erase函数将s中所有oldVal替换为newVal。测试你的程序，用它替换普通的简写形式，如，将”tho“替换为”though“，将”thru“替换为”through“。
#include 
#include 
#include 
using std::cin;
using std::cout;
using std::cerr;
using std::endl;
using std::vector;
using std::string;

void rePlace(string &s, const string &oldVal, const string &newVal)
{
	auto l = oldVal.size();
	if (!l)
		return;
	auto iter = s.begin();
	while (iter <= s.end()-1) {
		auto iter1 = iter;
		auto iter2 = oldVal.begin();
		while(iter != oldVal.end() && *iter1 == *iter2) {
			++iter1;
			++iter2;
		}
		if(iter2 == oldVal.end()) {
			iter = s.erase(iter, iter1);
			if (newVal.size()) {
				iter2 = newVal.end();
				do {
					--iter2;
					iter = s.insert(iter, *iter2);
				} while(iter2 > newVal.begin());
			}
			iter += newVal.size();
		}
		else ++iter;
	}
}

int main()
{
	string s = "tho thru tho!";
	rePlace(s, "thru", "through");
	cout<<>

练习9.44：重写上一题的函数，这次使用一个下标和replace。
#include 
#include 
#include 
using std::cout;
using std::endl;
using std::vector;
using std::string;

void rePlace(string &s, const string &oldVal, const string &newVal)
{
	int p = 0;
	while((p=s.find(oldVal, p)) !=string::npos) {
		s.replace(p, oldVal.size(), newVal);
		p += newVal.size();
	}
}

int main()
{
	string s = "tho thru tho!";
	rePlace(s, "thru", "through");
	cout<<>

练习9.45：编写一个函数，接受一个表示名字的string参数和两个分别表示前缀（如”Mr.“或”Ms.“）和后缀（如”Jr.“或”III“）的字符串。使用迭代器及insert和append函数将前缀和后缀添加到给定的名字中，将新生成的string返回。
#include 
using std::cout;
using std::endl;
#include 
using std::string;

string combine(string &str,const string &s1, const string &s2)
{
	str.insert(0,s1);
	str.append(s2);
	return str;
}

int main()
{
	string str="Tom",s1="Mr.",s2="Jr.";
	combine(str,s1,s2);
	cout<<>

练习9.46：重写上一题的函数，这次使用位置和长度来管理string，并只使用insert。
#include 
using std::cout;
using std::endl;
#include 
using std::string;
#include 
using std::vector;

void name_string(string &name, const string &prefix, const string &suffix)
{
	name.insert(0, " ");
	name.insert(0, prefix);
	name.insert(name.size(), " ");
	name.insert(name.size(), suffix);
}

int main()
{
	string s = "James Bond";
	name_string (s, "Mr.", "II");
	cout<<>

练习9.47：编写程序，首先查找string ”ab2c3d7R4E6“中每个数字字符，然后查找其中每个字母字符。编写两个版本的程序，第一个要使用find_first_of，第二个要使用find_first_of。
#include 
using std::cout;
using std::endl;
#include 
using std::string;

void use_find_first_of(string str, string find_str)
{
    auto pos = 0;
    while((pos = str.find_first_of(find_str,pos)) != string::npos)
    {
        cout << "char: " << str[pos] << " index: " << pos << endl;
        ++pos; 
    }
    cout << endl;
}

void use_find_first_not_of(string str , string not_find_str)
{
    auto pos = 0;
    while((pos = str.find_first_not_of(not_find_str,pos)) != string::npos)
    {
        cout << "position: " << pos << " char: " << str[pos] << endl;
        ++pos;
    }
    cout << endl;
}

int main()
{
    string str = "abc3d7R4E6";
    string numbers = "0123456789";
    string letters = "abcdRE";

    use_find_first_of(str, numbers);
    use_find_first_of(str, letters);

    use_find_first_not_of(str, letters);
    use_find_first_not_of(str, numbers);
    return 0;
} 
练习9.48：假定name和numbers的定义如325页所示，numbers.find(name)返回什么？
s.find(args)查找s中args第一次出现的位置。因此，对325页给定的name和numbers，在numbers中不存在与name匹配的字符串，find会返回npos。
练习9.49：如果一个字母延伸到中线之上，如d或f，则称其有上出头部分。如果一个字母延伸到中线之下，如p或g，则称其有下出头部分。编写程序，读入一个单词文件，输出最长的既不包含上出头部分，也不不包含下出头部分的单词。
 
#include 
using std::cin;
using std::cout;
using std::cerr;
using std::endl;
#include 
using std::string;
#include 
using std::ifstream;

void find_longest_word(ifstream &in)
{
	string s, longest_word;
	int max_length = 0;

	while (in >> s) {
		if(s.find_first_of("bdfghjklpqty") != string::npos)
			continue;
		cout<