devbox
很楠不爱3
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【C++ Primer】第九章 顺序容器 (练习)_49. 对于下面的程序任务,vector、deque 和 list 哪种容器最为合适?解释你 的选择

作者：很楠不爱3 | 2024-03-02 01:33:41

赞

踩

49. 对于下面的程序任务,vector、deque 和 list 哪种容器最为合适?解释你 的选择

C++ Primer 5th 随堂练习

【C++ Primer】第一章 开始 (练习)

【C++ Primer】第二章 变量和基本类型 (练习)

【C++ Primer】第三章 字符串、向量和数组 (练习)

【C++ Primer】第四章 表达式 (练习)

【C++ Primer】第五章 语句 (练习)

【C++ Primer】第六章 函数 (练习)

【C++ Primer】第七章 类 (练习)

【C++ Primer】第八章 IO 库 (练习)

【C++ Primer】第九章 顺序容器 (练习)

【C++ Primer】第十章 泛型算法 (练习)

【C++ Primer】第十一章 关联容器 (练习)

第九章 顺序容器

练习 9.1

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

  • (a) 读取固定数量的单词，将它们按字典序插入到容器中。我们将在下一章中看到，关联容器更适合这个问题。
  • (b) 读取未知数量的单词，总是将单词插入到末尾。删除操作在头部进行。
  • (c) 从一个文件读取未知数量的整数。将这些数排序，然后将它们打印到标准输出。

解答

练习 9.2

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

解答

  1. #include <iostream>
  2. #include <deque>
  3. #include <list>
  4. using namespace std;
  5.  
  6. int main()
  7. {
  8.     list<deque<int>> obj;
  9.     return 0;
  10. }

练习 9.3

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

解答

练习 9.4

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

解答

  1. bool find_val(vector<int>::const_iterator beg, vector<int>::const_iterator end, int val)
  2. {
  3.     while(beg != end) {
  4.         if ((*beg) == val) {
  5.             return true;
  6.         }
  7.         ++beg;
  8.     }
  9.     return false;
  10. }

练习 9.5

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

解答

  1. // 由于需要返回迭代器, 用户可能希望修改元素, 故不再使用常量迭代器
  2. vector<int>::iterator find_val(vector<int>::iterator beg, vector<int>::iterator end, int val)
  3. {
  4.     for( ; beg != end; ++beg) {  // 改用 for 循环亦可
  5.         if ((*beg) == val)
  6.             return beg;
  7.     }
  8.     return end;
  9. }

练习 9.6

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

  1. list<int> lst1;
  2. list<int>::iterator iter1 = lst1.begin(),
  3. 					iter2 = lst1.end();
  4. while (iter1 < iter2) /* ... */

解答

迭代器的循环条件应为：

while (iter1 != iter2) /* ... */

练习 9.7

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

解答

  1. // 既可以
  2. vector<int>::size_type
  3.  
  4. // 也可以
  5. vector<int>::iterator
  6. vector<int>::const_iterator

练习 9.8

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

解答

  1. // 读(2种)
  2. list<string>::const_iterator  // 常量迭代器
  3. list<string>::value_type
  4.  
  5. // 写(2种)
  6. list<string>::iterator  // 迭代器
  7. list<string>::reference

练习 9.9

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

解答

练习 9.10

下面 4 个对象分别是什么类型？

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

解答

it1 是 vector<int>::iterator 类型的，it2、it3、it4 均为 vector<int>::const_iterator 类型的。

练习 9.11

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

解答

  1. vector<int> vec;  // 1 个 0
  2. vector<int> vec(10);  // 10 个 0
  3. vector<int> vec(10, 1);  // 10 个 1
  4. vector<int> vec{ 1, 2, 3 };  // 1, 2, 3
  5. vector<int> vec(vec2);  // 拷贝 vec2 所有的元素
  6. vector<int> vec(vec2.begin(), vec2.end());  // 拷贝 vec2 迭代器范围内所有的元素

练习 9.12

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

解答

  • 接受一个容器创建其拷贝的构造函数，容器类型和元素类型必须都相同。
  • 接受两个迭代器创建拷贝的构造函数，只需要元素的类型能够相互转换，容器类型和元素类型可以不同。

练习 9.13

如何从一个 list<int> 初始化一个 vector<double> ？从一个 vector<int> 又该如何创建？编写代码验证你的答案。

解答

  1. // 由于类型不匹配, 不可以使用拷贝初始化
  2. // 但元素类型可以转换, 故需使用迭代器指定元素范围拷贝
  3. list<int> lst = {0, 1, 2, 3, 4};
  4. vector<double> dvec(lst.begin(), lst.end());  
  5.  
  6. vector<int> ivec = {5, 6, 7, 8, 9};
  7. vector<double> dvec2(ivec.begin(), ivec.end());

练习 9.14

编写程序，将一个 list 中的 char * 指针 (指向 C 风格字符串) 元素赋值给一个 vector 中的 string 。

解答

  1. // 容器类型不同, 不能直接赋值
  2. // 元素类型相容, 可以采用范围辅助
  3. list<const char*> lst = {"hello", "world"};
  4. vector<string> vec;
  5. vec.assign(lst.begin(), lst.end());

练习 9.15

编写程序，判定两个 vector<int> 是否相等。

解答

源程序：

  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. int main()
  6. {   
  7.     vector<int> ivec = {1, 2, 3};
  8.     vector<int> ivec1 = {1, 2, 3};
  9.     vector<int> ivec2 = {1, 2};
  10.     vector<int> ivec3 = {1, 2, 4};
  11.     vector<int> ivec4 = {1, 3, 2};
  12.  
  13.     cout << (ivec == ivec1) << endl;
  14.     cout << (ivec == ivec2) << endl;
  15.     cout << (ivec == ivec3) << endl;
  16.     cout << (ivec == ivec4) << endl;
  17.  
  18.     ivec1.push_back(4);
  19.     ivec1.pop_back();
  20.     cout << ivec1.capacity() << " " << ivec1.size() << endl;
  21.     cout << (ivec == ivec1) << endl;
  22.     
  23.     return 0;
  24. }

输出：

  1. 1
  2. 0
  3. 0
  4. 0
  5. 6 3
  6. 1

练习 9.16

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

解答

源程序：

  1. #include <iostream>
  2. #include <vector>
  3. #include <list>
  4. using namespace std;
  5.  
  6. bool isEqual(vector<int> &ivec, list<int> &ilst)
  7. {
  8.     if(ivec.size() != ilst.size())  // 先比较长度
  9.         return false;
  10.  
  11.     auto vbeg = ivec.cbegin();
  12.     auto vend = ivec.cend();
  13.     auto lbeg = ilst.cbegin();
  14.     auto lend = ilst.cend();
  15.  
  16.     while((vbeg != vend) || (lbeg != lend)) {  // 只写入其一也行
  17.         if((*vbeg) != (*lbeg))
  18.             return false;
  19.         ++vbeg;
  20.         ++lbeg;
  21.     }
  22.     return true;
  23. }
  24.  
  25. int main()
  26. {   
  27.     vector<int> ivec = {1, 2, 3};
  28.     list<int> ilst = {1, 2, 3};
  29.     cout << isEqual(ivec, ilst) << endl;
  30.  
  31.     ivec.push_back(4);
  32.     cout << isEqual(ivec, ilst) << endl;
  33.  
  34.     ivec.pop_back();
  35.     ivec.pop_back();
  36.     cout << isEqual(ivec, ilst) << endl;  
  37.  
  38.     return 0;
  39. }

输出：

  1. 1
  2. 0
  3. 0

练习 9.17

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

if (c1 < c2)

解答

  • c1 和 c2 必须是相同类型的容器，且保存相同类型的元素
  • 元素类型要支持小于关系运算符 <

练习 9.18

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

解答

源程序：

  1. #include <iostream>
  2. #include <string>
  3. #include <deque>
  4. using namespace std;
  5.  
  6. int main()
  7. {       
  8.     // 输入并保存元素
  9.     deque<string> deq;
  10.     string str;
  11.     while(cin >> str) {
  12.         deq.push_back(str);
  13.     }
  14.     // 通过常量迭代器打印元素
  15.     for(auto iter = deq.cbegin(); iter != deq.cend(); ++iter) {
  16.         cout << (*iter) << endl;
  17.     }
  18.     
  19.     system("pause");
  20.     return 0;
  21. }

输出：

  1. hello world my dear
  2. ^Z
  3. hello
  4. world
  5. my
  6. dear

练习 9.19

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

解答

  • 头文件从 #include <deque> 改为 #include <list>
  • 容器类型从 deque<string> 改为 list<string>

练习 9.20

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

解答

源程序：

  1. #include <iostream>
  2. #include <list>
  3. #include <deque>
  4. using namespace std;
  5.  
  6. int main()
  7. {    
  8.     // 初始化容器
  9.     list<int> lst = {0, 1, 2, 3, 4};
  10.     deque<int> odd, even;
  11.  
  12.     // 通过迭代器拷贝
  13.     auto iter = lst.cbegin();
  14.     auto end = lst.cend();
  15.     while(iter != end) {
  16.         int num = *iter;
  17.         if(num % 2 == 1)   // 等价于 if(num & 1) 查看最低位, 1:奇数, 0:偶数
  18.             odd.push_back(num); 
  19.         else
  20.             even.push_back(num);
  21.         ++iter;
  22.     }
  23.     // 等价于
  24.     // for (auto i : lst)
  25.     //    (i & 0x1 ? odd : even).push_back(i);
  26.  
  27.     // 打印结果验证
  28.     for(auto o : odd) { cout << o << " "; }
  29.     cout << endl;
  30.     for(auto e : even) { cout << e << " "; }
  31.     cout << endl;
  32.     
  33.     system("pause");
  34.     return 0;
  35. }

输出：

  1. 1 3
  2. 0 2 4

练习 9.21

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

解答

源程序：

  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. int main()
  6. {    
  7.     vector<string> svec;
  8.     string word;
  9.     auto iter = svec.begin();
  10.     while(cin >> word) {
  11.         iter = svec.insert(iter, word);
  12.     }
  13.  
  14.     for(auto iter = svec.cbegin(); iter != svec.end(); ++iter) {
  15.         cout << *iter << endl;
  16.     }
  17.  
  18.     system("pause");
  19.     return 0;
  20. }

控制台交互：

  1. hello world my dear
  2. ^Z
  3. dear
  4. my
  5. world
  6. hello

练习 9.22

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

  1. vector<int>::iterator iter = iv.begin(),
  2.                        mid = iv.begin() + iv.size() / 2;
  3. while (iter != mid)
  4. 	if (*iter == some_val)
  5. 		iv.insert(iter, 2 * some_val);

解答

源程序 - 方式一：

  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. int main()
  6. {    
  7.     vector<int> iv = {2, 1, 1, 2, 1};
  8.     int some_val = 2;  // 目标值
  9.  
  10.     vector<int>::iterator iter = iv.begin();
  11.     int org_size = iv.size(), new_elem = 0;  // 原始大小, 新元素数
  12.  
  13.     // 每个循环步都重新计算 mid, 保证正确指向 iv 原中央元素
  14.     while(iter != (iv.begin() + org_size / 2 + new_elem)) {
  15.         if(*iter == some_val) {
  16.             iter = iv.insert(iter, 2*some_val);  // iter 指向新元素
  17.             new_elem++;  // 新元素数 +1
  18.             iter++;  // 将 iter 移到新元素的下一个位置
  19.         }
  20.         iter++;  // 将 iter 推进到旧元素的下一个位置
  21.     }
  22.  
  23.     // 用 begin() 获取 vector 首元素迭代器, 遍历 vector 中的所有元素
  24.     for(iter = iv.begin(); iter != iv.end(); iter++)
  25.         cout << *iter << endl;
  26.  
  27.     system("pause");
  28.     return 0;
  29. }

输出：

  1. 4
  2. 2
  3. 1
  4. 1
  5. 2
  6. 1

源程序 - 方式二：

  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. int main()
  6. {    
  7.     vector<int> iv = {2, 1, 1, 2, 1};
  8.     int some_val = 2;  // 目标值
  9.  
  10.     vector<int>::iterator iter = iv.begin();
  11.     int org_size = iv.size(), i = 0;  // 原始大小, 循环次数
  12.  
  13.     // 用循环遍历控制循环次数
  14.     while(i <= org_size / 2) {
  15.         if(*iter == some_val) {
  16.             iter = iv.insert(iter, 2*some_val);  // iter 指向新元素
  17.             iter++;  // 将 iter 移到新元素的下一个位置
  18.         }
  19.         iter++;  // 将 iter 推进到旧元素的下一个位置
  20.         i++;  // 循环次数 +1
  21.     }
  22.  
  23.     // 用 begin() 获取 vector 首元素迭代器, 遍历 vector 中的所有元素
  24.     for(iter = iv.begin(); iter != iv.end(); iter++)
  25.         cout << *iter << endl;
  26.  
  27.     system("pause");
  28.     return 0;
  29. }

输出：

  1. 4
  2. 2
  3. 1
  4. 1
  5. 2
  6. 1

练习 9.23

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

解答

四个变量的值会相同，均为容器中唯一元素的值。

练习 9.24

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

解答

  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. int main()
  6. {    
  7.     vector<int> ivec;
  8.  
  9.     cout << ivec.at(0) << endl;       // terminating with uncaught exception of type std::out_of_range
  10.     cout << ivec[0] << endl;          // Segmentation fault: 11
  11.     cout << ivec.front() << endl;     // Segmentation fault: 11
  12.     cout << *(ivec.begin()) << endl;  // Segmentation fault: 11
  13.  
  14.     system("pause");
  15.     return 0;
  16. }

练习 9.25

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

解答

练习 9.26

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

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

解答

源程序：

  1. #include <iostream>
  2. #include <vector>
  3. #include <list>
  4. using namespace std;
  5.  
  6. int main()
  7. {   
  8.     // 基本数据
  9.     int ia[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 55, 89 };
  10.     vector<int> ivec;
  11.     list<int> ilst;
  12.  
  13.     // 数据拷贝
  14.     ivec.assign(ia, ia+11);
  15.     ilst.assign(ia, ia+11);
  16.  
  17.     // 删除奇数元素
  18.     auto iiter = ivec.begin();  // 等价于 vector<int>::iterator iiter = ivec.begin();
  19.     while(iiter != ivec.end()) {
  20.         if((*iiter) % 2)
  21.             iiter = ivec.erase(iiter);
  22.         else
  23.             ++iiter;
  24.     }
  25.  
  26.     // 删除偶数元素
  27.     for(auto liter = ilst.begin(); liter != ilst.end(); ) {  // 等价于 list<int>::iterator liter = ilst.begin();
  28.         if(!(*liter % 2))
  29.             liter = ilst.erase(liter);
  30.         else
  31.             ++liter;
  32.     }
  33.  
  34.     // 打印结果
  35.     cout << "even vector: ";
  36.     for (auto v : ivec)
  37.         cout << v << " ";
  38.     cout << endl;
  39.     
  40.     cout << "odd list: ";
  41.     for (auto l : ilst)
  42.         cout << l << " ";
  43.     cout << endl;
  44.  
  45.     system("pause");
  46.     return 0;
  47. }

输出：

  1. even vector: 0 2 8
  2. odd list: 1 1 3 5 13 21 55 89

练习 9.27

编写程序，查找并删除 forward_list<int> 中的奇数元素。

解答

源程序：

  1. #include <iostream>
  2. #include <forward_list>
  3. using namespace std;
  4.  
  5. int main()
  6. {   
  7.     // 处理
  8.     forward_list<int> fwlst = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 55, 89 };
  9.     forward_list<int>::iterator prev = fwlst.before_begin();  // 伪头部 - 哨兵节点
  10.     forward_list<int>::iterator curr = fwlst.begin();  // 真头部 - 首节点
  11.     while(curr != fwlst.end()) {
  12.         if(*curr % 2 == 1) {
  13.             curr = fwlst.erase_after(prev);
  14.         }
  15.         else {
  16.             prev = curr;
  17.             ++curr;
  18.         }
  19.     }
  20.  
  21.     // 打印
  22.     cout << "even forward_list: ";
  23.     for(auto f : fwlst)
  24.         cout << f << " ";
  25.     cout << endl;
  26.  
  27.     system("pause");
  28.     return 0;
  29. }

输出：

even forward_list: 0 2 8

练习 9.28

编写函数，接受一个 forward_list<string> 和两个 string 共三个参数。函数应在链表中查找第一个 string，并将第二个 string 插入到紧接着第一个 string 之后的位置。若第一个 string 未在链表中，则将第二个 string 插入到链表末尾。

解答

源程序：

  1. #include <iostream>
  2. #include <forward_list>
  3. #include <string>
  4. using namespace std;
  5.  
  6. int main()
  7. {   
  8.     forward_list<string> f = {"aa", "bb", "cc", "ee"};  // 单链表
  9.     string x = "cc", y = "dd";  // 待寻找元素, 待插入元素
  10.     forward_list<string>::iterator prev = f.before_begin();  // 哨兵节点
  11.     forward_list<string>::iterator curr = f.begin();  // 头节点
  12.     while(curr != f.end()) {
  13.         if(*curr == x) {
  14.             f.insert_after(curr, y);  // 中间位置插入插入并打印
  15.             for(auto n : f) 
  16.                 cout << n << " ";
  17.             cout << endl;
  18.             
  19.             system("pasue");
  20.             return 0;
  21.         }
  22.         prev = curr;  // 双指针后移
  23.         ++curr;
  24.     }
  25.     f.insert_after(prev, y);  // 末尾位置插入元素并打印
  26.     for(auto n : f) 
  27.         cout << n << " ";
  28.     cout << endl;
  29.  
  30.     system("pause");
  31.     return 0;
  32. }

输出：

  1. aa
  2. bb
  3. cc
  4. dd
  5. ee

练习 9.29

假定 vec 包含 25 个元素，那么 vec.resize(100) 会做什么？如果接下来调用 vec.resize(10) 会做什么？

解答

调用 vec.resize(100) 会将 75 个元素 (0 值初始化) 添加到 vec 的末尾；接下来调用 vec.resize(100) 则会将 vec 末尾的 90 个元素删除。

练习 9.30

接受单个参数的 resize 版本对元素类型有什么限制（如果有的话）？

解答

特别地，对类类型的元素而言，调用 resize 时应提供扩增数及各新增元素的初始值；若未提供初始值，则要求该类型必须提供有一个默认构造函数。

练习 9.31

第 316 页中删除偶数值元素并复制奇数值元素的程序不能用于 list 或 forward_list。为什么？修改程序，使之也能用于这些类型。

解答

对复合赋值运算而言，

iter += 1;

复合赋值语句所适用的容器为 string、vector、deque、array，所以要改为：

++iter; ++iter;

以达到相同的效果。

特别地，对 forward_list (基于单链表结构) 而言，还需要增加一个首前 (off-the-beginning) 迭代器 prev 并同时维护一对前驱/后继节点位置的迭代器：

  1. auto prev = flst.before_begin();  // 哨兵节点
  2. auto curr = flst.begin();  // 首节点
  3. //...
  4. curr = flst.insert_after(prev, *curr);
  5. ++curr; ++curr;
  6. ++prev; ++prev;

练习 9.32

在第 316 页的程序中，向下面语句这样调用 insert 是否合法？如果不合法，为什么？

iter = vi.insert(iter, *iter++);

解答

练习 9.33

在本节最后一个例子中，如果不将 insert 的结果赋予 begin，将会发生什么？编写程序，去掉此赋值语句，验证你的答案。

解答

源程序：

  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. int main()
  6. {   
  7.     vector<int> data = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  8.     for(auto iter = data.begin(); iter != data.end(); ++iter) {
  9.         if(*iter % 2) {
  10.             iter = data.insert(iter, *iter);  // 复制奇数元素
  11.             ++iter;
  12.         }
  13.         else {
  14.             iter = data.erase(iter);  // 删除偶数元素
  15.         }
  16.     }
  17.     for (auto i : data)
  18.         cout << i << " ";
  19.     cout << endl;
  20.  
  21.     system("pause");
  22.     return 0;
  23. }

输出：

1 3 5 7 9

练习 9.34

假定 vi 是一个保存 int 的容器，其中有偶数值也有奇数值，分析下面循环的行为，然后编写程序验证你的分析是否正确。

  1. iter = vi.begin();
  2. while (iter != vi.end())
  3.     if (*iter % 2)
  4.         iter = vi.insert(iter, *iter);
  5.     ++iter;

解答

  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. int main()
  6. {   
  7.     vector<int> vi = {1, 2, 3, 4, 5, 6, 7, 8, 9};
  8.     auto iter = vi.begin();
  9.     while(iter != vi.end()) {
  10.         if(*iter % 2) 
  11.             iter = vi.insert(iter, *iter);
  12.  
  13.         for(auto begin = vi.cbegin(); begin != vi.cend(); ++begin)
  14.             cout << *begin << " ";
  15.         cout << endl;
  16.     }
  17.     ++iter;
  18.  
  19.     system("pause");
  20.     return 0;
  21. }
// 无限循环输出 ...

  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. using namespace std;
  5.  
  6. int main()
  7. {   
  8.     vector<int> vi = {1, 2, 3, 4, 5, 6, 7, 8, 9};
  9.     auto iter = vi.begin();
  10.     string tmp;
  11.     while(iter != vi.end()) {
  12.         if(*iter % 2) {
  13.             iter = vi.insert(iter, *iter);
  14.             ++iter; 
  15.         } 
  16.         ++iter;
  17.     }
  18.     for(auto begin = vi.begin(); begin != vi.end(); ++begin)
  19.         cout << *begin << " ";
  20.     cout << endl;
  21.     cin >> tmp;
  22.  
  23.     system("pause");
  24.     return 0;
  25. }
  1. 1 1 2 3 4 5 6 7 8 9
  2. 1 1 2 3 4 5 6 7 8 9
  3. 1 1 2 3 3 4 5 6 7 8 9
  4. 1 1 2 3 3 4 5 6 7 8 9
  5. 1 1 2 3 3 4 5 5 6 7 8 9
  6. 1 1 2 3 3 4 5 5 6 7 8 9
  7. 1 1 2 3 3 4 5 5 6 7 7 8 9
  8. 1 1 2 3 3 4 5 5 6 7 7 8 9
  9. 1 1 2 3 3 4 5 5 6 7 7 8 9 9

练习 9.35

解释一个 vector 的 capacity 和 size 有何区别。

解答

  • capacity 返回已为 vector 分配内存空间大小 (单位：元素个数)，即在不分配新空间的前提下，容器当前最多可以保存多少个元素
  • size 返回容器当前已保存元素个数

练习 9.36

一个容器的 capacity 可能小于它的 size 吗？

解答

由练习 9.35 可知不可能。

练习 9.37

为什么 list 或 array 没有 capacity 成员函数？

解答

练习 9.38

编写程序，探究在你的标准实现中，vector 是如何增长的。

解答

源程序：

  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. int main()
  6. {   
  7.     vector<int> ivec;
  8.     for(int i = 0; i < 100; ++i) {
  9.         cout << "capacity: " << ivec.capacity() << " size: " << ivec.size() << endl;
  10.         ivec.push_back(i);
  11.     }
  12.  
  13.     system("pause");
  14.     return 0;
  15. }

输出：

  1. capacity: 0 size: 0
  2. capacity: 1 size: 1
  3. capacity: 2 size: 2
  4. capacity: 4 size: 3
  5. capacity: 4 size: 4
  6. capacity: 8 size: 5
  7. capacity: 8 size: 6
  8. capacity: 8 size: 7
  9. capacity: 8 size: 8
  10. capacity: 16 size: 9
  11. capacity: 16 size: 10
  12. capacity: 16 size: 11
  13. capacity: 16 size: 12
  14. capacity: 16 size: 13
  15. capacity: 16 size: 14
  16. capacity: 16 size: 15
  17. capacity: 16 size: 16
  18. capacity: 32 size: 17
  19. capacity: 32 size: 18
  20. capacity: 32 size: 19
  21. capacity: 32 size: 20
  22. capacity: 32 size: 21
  23. capacity: 32 size: 22
  24. capacity: 32 size: 23
  25. capacity: 32 size: 24
  26. capacity: 32 size: 25
  27. capacity: 32 size: 26
  28. capacity: 32 size: 27
  29. capacity: 32 size: 28
  30. capacity: 32 size: 29
  31. capacity: 32 size: 30
  32. capacity: 32 size: 31
  33. capacity: 32 size: 32
  34. capacity: 64 size: 33
  35. capacity: 64 size: 34
  36. capacity: 64 size: 35
  37. capacity: 64 size: 36
  38. capacity: 64 size: 37
  39. capacity: 64 size: 38
  40. capacity: 64 size: 39
  41. capacity: 64 size: 40
  42. capacity: 64 size: 41
  43. capacity: 64 size: 42
  44. capacity: 64 size: 43
  45. capacity: 64 size: 44
  46. capacity: 64 size: 45
  47. capacity: 64 size: 46
  48. capacity: 64 size: 47
  49. capacity: 64 size: 48
  50. capacity: 64 size: 49
  51. capacity: 64 size: 50
  52. capacity: 64 size: 51
  53. capacity: 64 size: 52
  54. capacity: 64 size: 53
  55. capacity: 64 size: 54
  56. capacity: 64 size: 55
  57. capacity: 64 size: 56
  58. capacity: 64 size: 57
  59. capacity: 64 size: 58
  60. capacity: 64 size: 59
  61. capacity: 64 size: 60
  62. capacity: 64 size: 61
  63. capacity: 64 size: 62
  64. capacity: 64 size: 63
  65. capacity: 64 size: 64
  66. capacity: 128 size: 65
  67. capacity: 128 size: 66
  68. capacity: 128 size: 67
  69. capacity: 128 size: 68
  70. capacity: 128 size: 69
  71. capacity: 128 size: 70
  72. capacity: 128 size: 71
  73. capacity: 128 size: 72
  74. capacity: 128 size: 73
  75. capacity: 128 size: 74
  76. capacity: 128 size: 75
  77. capacity: 128 size: 76
  78. capacity: 128 size: 77
  79. capacity: 128 size: 78
  80. capacity: 128 size: 79
  81. capacity: 128 size: 80
  82. capacity: 128 size: 81
  83. capacity: 128 size: 82
  84. capacity: 128 size: 83
  85. capacity: 128 size: 84
  86. capacity: 128 size: 85
  87. capacity: 128 size: 86
  88. capacity: 128 size: 87
  89. capacity: 128 size: 88
  90. capacity: 128 size: 89
  91. capacity: 128 size: 90
  92. capacity: 128 size: 91
  93. capacity: 128 size: 92
  94. capacity: 128 size: 93
  95. capacity: 128 size: 94
  96. capacity: 128 size: 95
  97. capacity: 128 size: 96
  98. capacity: 128 size: 97
  99. capacity: 128 size: 98
  100. capacity: 128 size: 99

可见编译器是成倍增长 vector 容量的。

练习 9.39

解释下面程序片段做了什么：

  1. vector<string> svec;
  2. svec.reserve(1024);
  3. string word;
  4. while (cin >> word)
  5.     svec.push_back(word);
  6. svec.resize(svec.size() + svec.size() / 2);

解答

首先，定义一个 vector 并为其分配 1024 个元素的空间。然后，通过一个循环从标准输入中读取字符串并末尾追加到 vector 中。循环结束后，改变 vector 的容器大小 (元素数量) 为原来的 1.5 倍，并使用元素的默认初始化值填充新增元素 (多出的 50%)。若容器大小超过 1024，vector 也会重新分配空间以容纳新增元素。

练习 9.40

如果上一题的程序读入了 256 个词，在 resize 之后容器的 capacity 可能是多少？如果读入了 512 个、1000 个、或1048 个呢？

解答

练习 9.41

编写程序，从一个 vector<char> 初始化一个 string。

解答

源程序：

  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. using namespace std;
  5.  
  6. int main()
  7. {   
  8.     vector<char> cvec = {'h', 'e', 'l', 'l', 'o'};
  9.     string str(cvec.data(), cvec.size());  // 传入首地址及大小
  10.                                            // 给定迭代器范围亦可 string str(cvec.begin(), cvec.end()); 
  11.     cout << str << endl;
  12.  
  13.     system("pause");
  14.     return 0;
  15. }

输出：

hello

练习 9.42

假定你希望每次读取一个字符存入一个 string 中，而且知道最少需要读取 100 个字符，应该如何提高程序的性能？

解答

由于已知至少读取 100 个字符，故可用 reverse 函数预先为 string分配 100 个字符的内存空间，然后再逐个读取字符，并用 push_back 末尾追加到 string 中。

源程序：

  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. using namespace std;
  5.  
  6. void input_string(string s)
  7. {
  8.     s.reserve(100);  // 预分配 100 个元素的空间
  9.     char c;
  10.     while(cin >> c)
  11.         s.push_back(c);
  12. }
  13.  
  14. int main()
  15. {   
  16.     string str;
  17.     input_string(str);
  18.     cout << str << endl;
  19.  
  20.     system("pause");
  21.     return 0;
  22. }

练习 9.43

编写一个函数，接受三个 string 参数 s、oldVal 和 newVal。使用迭代器及 insert 和 erase 函数将 s 中所有 oldVal 替换为 newVal。测试你的程序，用它替换通用的简写形式，如，将 "tho" 替换为 "though"，将 "thru" 替换为 "through" 。

解答

源程序： 

  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. using namespace std;
  5.  
  6. void replace_string(string &s, const string &oldVal, const string &newVal)  // 注意形参类型
  7. {   
  8.     if(oldVal.empty() || (s.size() < oldVal.size()))  // 异常情况
  9.         return;
  10.  
  11.     auto iter = s.begin();  // s 迭代器
  12.     while(iter <= (s.end()-oldVal.size())) {
  13.         auto iter1 = iter;  // 拷贝 s 迭代器
  14.         auto iter2 = oldVal.begin();  // 新建 oldVal 迭代器
  15.         // s 中 iter 开始的子串必须每个字符都与 oldVal 相同
  16.         while(iter2 != oldVal.end() && *iter1 == *iter2) {
  17.             ++iter1;
  18.             ++iter2;
  19.         }
  20.         if(iter2 == oldVal.end()) {  // oldVal 耗尽 —— 字符串相等
  21.             iter = s.erase(iter, iter+oldVal.size());  // 删除 s 中与 oldVal 相等部分 (迭代器范围)
  22.             if(newVal.size()) {
  23.                 auto iter3 = newVal.end();  // 新建newVal 迭代器
  24.                 do {
  25.                     --iter3;
  26.                     iter = s.insert(iter, *iter3);
  27.                 } while(iter3 > newVal.begin());
  28.             }
  29.             iter += newVal.size();  // 迭代器移动到新插入内容之后
  30.         } 
  31.         else 
  32.             ++iter;  // s 迭代器后移一位
  33.     }
  34. }
  35.  
  36. int main()
  37. {   
  38.     string s = "the thru tho!";
  39.     replace_string(s, "thru", "through");
  40.     cout << s << endl;
  41.  
  42.     replace_string(s, "tho", "though");
  43.     cout << s << endl;
  44.  
  45.     replace_string(s, "through", "");
  46.     cout << s << endl;
  47.  
  48.     system("pause");
  49.     return 0;
  50. }

输出： 

  1. the through tho!
  2. the through though!
  3. the  though!

练习 9.44

重写上一题的函数，这次使用一个下标和 replace。

解答

源程序：

  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. using namespace std;
  5.  
  6. void replace_string(string &s, const string &oldVal, const string &newVal)  // 注意形参类型
  7. {   
  8.     if(oldVal.empty() || (s.size() < oldVal.size()))  // 异常情况
  9.         return;
  10.  
  11.     auto index = 0;
  12.     auto range = s.size() - oldVal.size();
  13.     while(index <= range) {
  14.         auto index1 = index;  // 拷贝当前 s 索引
  15.         auto index2 = 0;  // 新建 oldVal 索引
  16.         // 逐个检查相等与否
  17.         while(index2 < oldVal.size() && s[index1] == oldVal[index2]) {
  18.             ++index1;
  19.             ++index2;
  20.         }
  21.         // 相等则替换并后移新增位数, 否则正常后移一位
  22.         if(index2 == oldVal.size()) {
  23.             s.replace(index, oldVal.size(), newVal);
  24.             index += newVal.size();
  25.         } 
  26.         else 
  27.             ++index;
  28.     }
  29. }
  30.  
  31. int main()
  32. {   
  33.     string s = "the thru tho!";
  34.     replace_string(s, "thru", "through");
  35.     cout << s << endl;
  36.  
  37.     replace_string(s, "tho", "though");
  38.     cout << s << endl;
  39.  
  40.     replace_string(s, "through", "");
  41.     cout << s << endl;
  42.  
  43.     system("pause");
  44.     return 0;
  45. }

输出：

  1. the through tho!
  2. the through though!
  3. the  though!

源程序：

  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. using namespace std;
  5.  
  6. void replace_string(string &s, const string &oldVal, const string &newVal)  // 注意形参类型
  7. {   
  8.     int index = 0;
  9.     while((index = s.find(oldVal, index)) != string::npos) {  // 在 s 中使用 find() 查找 oldVal
  10.         s.replace(index, oldVal.size(), newVal);  // 将找到的子串替换为 newVal
  11.         index += newVal.size();  // 下标调整到新插入的内容后
  12.     }
  13. }
  14.  
  15. int main()
  16. {   
  17.     string s = "the thru tho!";
  18.     replace_string(s, "thru", "through");
  19.     cout << s << endl;
  20.  
  21.     replace_string(s, "tho", "though");
  22.     cout << s << endl;
  23.  
  24.     replace_string(s, "through", "");
  25.     cout << s << endl;
  26.  
  27.     system("pause");
  28.     return 0;
  29. }

输出：

  1. the through tho!
  2. the through though!
  3. the  though!

练习 9.45

编写一个函数，接受一个表示名字的 string 参数和两个分别表示前缀（如 "Mr." 或 "Mrs." ）和后缀（如 "Jr." 或 "III" ）的字符串。使用迭代器及 insert 和 append 函数将前缀和后缀添加到给定的名字中，将生成的新 string 返回。

解答

源程序：

  1. #include <iostream>
  2. #include <string>
  3. using namespace std;
  4.  
  5. string fix_prefix_and_suffix(string &name, const string &prefix, const string &suffix)  // 注意形参类型
  6. {   
  7.     // name = prefix + name + suffix;
  8.     name.insert(name.begin(), 1, ' ');  // 注意区别
  9.     name.insert(name.begin(), prefix.begin(), prefix.end());  // 不能只写个 prefix
  10.     name.append(" ");  // 注意区别
  11.     name.append(suffix.begin(), suffix.end());  // 不能只写个 suffix
  12.     return name;
  13. }
  14.  
  15. int main()
  16. {   
  17.     string s = "Wang";
  18.     cout << fix_prefix_and_suffix(s, "Dear", "x") << endl;
  19.  
  20.     system("pause");
  21.     return 0;
  22. }

输出：

Dear Wang x

练习 9.46

重写上一题的函数，这次使用位置和长度来管理string，并只使用insert。

解答

源程序：

  1. #include <iostream>
  2. #include <string>
  3. using namespace std;
  4.  
  5. string fix_prefix_and_suffix(string &name, const string &prefix, const string &suffix)  // 注意形参类型
  6. {   
  7.     name.insert(0, " ");
  8.     name.insert(0, prefix);
  9.     name.insert(name.size(), " ");
  10.     name.insert(name.size(), suffix);
  11.     return name;
  12. }
  13.  
  14. int main()
  15. {   
  16.     string s = "Wang";
  17.     cout << fix_prefix_and_suffix(s, "Dear", "x") << endl;
  18.  
  19.     system("pause");
  20.     return 0;
  21. }

输出：

Dear Wang x

练习 9.47

编写程序，首先查找 string "ab2c3d7R4E6" 中每个数字字符，然后查找其中每个字母字符。编写两个版本的程序，第一个要使用 find_first_of，第二个要使用 find_first_not_of。

解答

稍微修改题求并混合书写，源程序：

  1. #include <iostream>
  2. #include <string>
  3. using namespace std;
  4.  
  5. void find_char(string &s, const string& c)
  6. {
  7.     int pos1 = 0;
  8.     while((pos1 = s.find_first_of(c, pos1)) != string::npos) {
  9.         cout << s[pos1] << " ";
  10.         ++pos1;
  11.     }
  12.     cout << endl;
  13.  
  14.     for(int pos2 = 0; (pos2 = s.find_first_not_of(c, pos2)) != string::npos; ++pos2) {
  15.         cout << s[pos2] << " ";
  16.     }
  17.     cout << endl;
  18. }
  19.  
  20. int main()
  21. {   
  22.     string str = "ab2c3d7R4E6";
  23.     string number = "0123456789";
  24.     string alpha = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
  25.  
  26.     find_char(str, number);
  27.     find_char(str, alpha);
  28.  
  29.     system("pause");
  30.     return 0;
  31. }

输出：

  1. 2 3 7 4 6
  2. a b c d R E
  3. a b c d R E
  4. 2 3 7 4 6

练习 9.48

假定 name 和 numbers 的定义如 325 页所示，numbers.find(name) 返回什么？

解答

练习 9.49

如果一个字母延伸到中线之上，如 d 或 f，则称其有上出头部分（ascender）。如果一个字母延伸到中线之下，如 p 或 g，则称其有下出头部分（descender）。编写程序，读入一个单词文件，输出最长的既不包含上出头部分，也不包含下出头部分的单词。

解答

源程序：

  1. #include <iostream>
  2. #include <fstream>
  3. #include <string>
  4. using namespace std;
  5.  
  6. void find_longest_word(ifstream &in)
  7. {
  8.     string s, longest_word;
  9.     string alpha = "bdfghjklpqty";
  10.     int max_length = 0;
  11.  
  12.     while(in >> s) {
  13.         if(s.find_first_of(alpha) != string::npos)
  14.             continue;
  15.         cout << s << " ";
  16.         if(max_length < s.size()) {
  17.             max_length = s.size();
  18.             longest_word = s;
  19.         }
  20.     }
  21.     cout << "the longest specific string is " << longest_word << endl;
  22. }
  23.  
  24. int main(int argc, char* argv[])
  25. {   
  26.     ifstream in(argv[1]);  // 打开文件
  27.     if(!in) {
  28.         cerr << "can not open the input file" << endl;
  29.         return -1;
  30.     }
  31.     find_longest_word(in);
  32.  
  33.     system("pause");
  34.     return 0;
  35. }

练习 9.50

编写程序处理一个 vector<string>，其元素都表示整型值。计算 vector 中所有元素之和。修改程序，使之计算表示浮点值的 string 之和。

解答

  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. using namespace std;
  5.  
  6. int main()
  7. {
  8.     vector<string> svec = {"123", "+456", "-789"};
  9.     int sum = 0;
  10.     for(auto iter = svec.cbegin(); iter != svec.cend(); ++iter)
  11.         sum += stoi(*iter);
  12.     cout << "sum: " << sum << endl;
  13.  
  14.     system("pause");
  15.     return 0;
  16. }
sum: -210

  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. using namespace std;
  5.  
  6. int main()
  7. {
  8.     vector<string> svec = {"12.3", "-4.56", "+7.8e-2"};
  9.     float sum = 0;
  10.     for(auto iter = svec.cbegin(); iter != svec.cend(); ++iter)
  11.         sum += stof(*iter);
  12.     cout << "sum: " << sum << endl;
  13.  
  14.     system("pause");
  15.     return 0;
  16. }
sum: 7.818

练习 9.51

设计一个类，它有三个 unsigned 成员，分别表示年、月和日。为其编写构造函数，接受一个表示日期的 string 参数。你的构造函数应该能处理不同的数据格式，如 January 1,1900、1/1/1990、Jan 1 1900 等。

解答

练习 9.52

使用 stack 处理括号化的表达式。当你看到一个左括号，将其记录下来。当你在一个左括号之后看到一个右括号，从 stack 中 pop 对象，直至遇到左括号，将左括号也一起弹出栈。然后将一个值（括号内的运算结果）push到栈中，表示一个括号化的（子）表达式已经处理完毕，被其运算结果所替代。

解答

本题可延伸为 逆波兰求值 及 中缀转后缀表达式。

源程序：

  1. #include <iostream>
  2. #include <string>
  3. #include <stack>
  4. using namespace std;
  5.  
  6. int main()
  7. {
  8.     string expression = "hello world (dear)";
  9.     bool bracket_seen = false;
  10.     stack<char> stack;
  11.     for (const auto &s : expression){
  12.         if(s == '(') { 
  13.             bracket_seen = true; 
  14.             continue; 
  15.         }
  16.         else if(s == ')')
  17.             bracket_seen = false;
  18.  
  19.         if(bracket_seen)
  20.             stack.push(s);
  21.     }
  22.     
  23.     string reverse_str;
  24.     while (!stack.empty()){
  25.         reverse_str += stack.top();
  26.         stack.pop();
  27.     }
  28.  
  29.     expression.replace(expression.find("(") + 1, reverse_str.size(), reverse_str);
  30.     cout << expression << endl;
  31.     
  32.     system("pause");
  33.     return 0;
  34. }

输出：

hello world (raed)
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/很楠不爱3/article/detail/178227
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号