本文答案,部分参考于C++ Primer 习题集
前面章节的习题答案
配套的学习资料
https://www.jianguoyun.com/p/DTK5uJgQldv8CBjKv80D
11.1
一个是顺序容器,一个是关联容器.这个是本质上的区别.
顺序容器中的元素是顺序存储的.关联容器中的元素是按关键字值来存储的.
底层数据结构是红黑树,哈希表等.
11.2
如果元素很小.例如int,大致数量预先可知.在程序运行过程中不会剧烈变化.大部分情况下只在末尾添加或删除需要频繁访问任意位置的元素.则vector可带来最高的效率.如果需要频繁的在头部和尾部添加或删除元素,则deque是最好的选择.
如果元素较大,数量预先不知道,或是程序运行过程中频繁变换,对元素的访问更多是顺序访问全部或很多元素.则list很适合.
map很适合对一些对象按它们的某个特性进行访问的的情形.典型的例如按学生的名字来查询学生信息.即可将学生名字作为关键字,将学生信息作为元素值,保存在map中.
set,就是集合.但需要保存特定的值的集合.
11.3
书上给的例子,蛮好的,不用改.
11.4
#include<iostream>
#include<map>
#include<algorithm>
#include<set>
using namespace std;
int main(void) {
map<string, size_t> word_count;
string word;
while (cin >> word) {
if (isupper(word[0])) word[0] = tolower(word[0]);
++word_count[word];
}
for (const auto& w : word_count) cout << w.first << " occurs " << w.second << ((w.second > 1) ? "times" : "time") << endl;
return 0;
}
输入输出结果如下:
the The Link link Zelda zelda
^Z
link occurs 2times
the occurs 2times
zelda occurs 2times
11.5
当需要查找给定值所对应的数据时,应使用map,其中保存的是<关键字,值> 对,按关键字访问值
如果只需要判定给定值是否存在时,应使用set,它是简单的值的集合.
11.6
两者都可以保存元素集合.
如果只需要顺序访问这些元素,或是按位置访问元素,那么应该使用list。
如果需要快速判定是否有元素等于给定值,则应使用set
11.7
#include<iostream>
#include<map>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;
int main(void) {
map<string, vector<int>> old_f, new_f;
old_f["Huang"] = { 1,2,3,4,5,6 };
old_f["Huang"].push_back(8);
for (auto i : old_f["Huang"]) cout << i << " ";
cout << endl;
string name;
cin >> name;
vector<int> child_id;
int t;
while (cin >> t) child_id.push_back(t);
new_f[name] = child_id;
for (auto i : new_f[name]) cout << i << " ";
return 0;
}
输入输出如下:
1 2 3 4 5 6 8
Link 1 2 3 4 5 6 7 ^Z
1 2 3 4 5 6 7
11.8
set的优点就是有一个好用的自动去重.
vector则需要我们手动去重.
代码如下:
#include<iostream>
#include<map>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;
int main(void) {
string t;
vector<string> test;
while (cin >> t) {
if(test.cend()==find(test.cbegin(),test.cend(),t))
test.push_back(t);
}
for (auto i : test) cout << i << " ";
cout << endl;
return 0;
}
输入输出结果如下:
Link love Zelda
HPY love Money
love love love love
^Z
Link love Zelda HPY Money
11.9
代码如下,因为我的标点符号太多的原因,有些地方有乱码.
#include<iostream>
#include<fstream>
#include<sstream>
#include<map>
#include<list>
#include<string>
#include<algorithm>
using namespace std;
string& trans(string& s) {
for (int p = 0; p < s.size(); ++p) {
if (s[p] >= 'A' && s[p] <= 'Z') s[p] = tolower(s[p]);
else if (s[p] == ',' || s[p] == '.') s.erase(p, 1);
return s;
}
}
int main(void) {
ifstream in("E:\\File\\HPY\\Zelda.txt");
if (!in) {
cout << "打开输入文件失败!" << endl;
exit(1);
}
map<string, list<int>> word_lineno; //
string line;
string word;
int lineno = 0;
while (getline(in, line)) {
++lineno;
istringstream l_in(line);
while (l_in >> word) {
trans(word);
word_lineno[word].push_back(lineno);
}
}
for (const auto& w : word_lineno) {
cout << w.first << "所在行:";
for (const auto& i : w.second) cout << i << " ";
cout << endl;
}
return 0;
}
输入输出如下:
a所在行:4 4 4 4
all所在行:1
along所在行:3
always所在行:2 4
and所在行:1 1 4 4 5 5
another,to所在行:6
appreciate所在行:3 6
are所在行:1 6
around所在行:5 5
bad所在行:6
based所在行:4
be所在行:4
be,because所在行:1
begins所在行:4
best所在行:3
born,you所在行:5
brighten所在行:6
brighter所在行:6
brightest所在行:4
can所在行:3
can鈥檛所在行:4
chance所在行:1
comes所在行:3
cry,those所在行:3
crying所在行:5
crying.所在行:5
day所在行:6
die,you're所在行:5
do所在行:1
do.所在行:1
don鈥檛所在行:3 6
don鈥檛,所在行:6
down,to所在行:6
dream所在行:1
dream;go所在行:1
dreams所在行:1
ends所在行:4
enough所在行:2
everyone所在行:5 5
everything所在行:3
everything;they所在行:3
failures所在行:4
feel所在行:2
for所在行:1 3
forgotten所在行:4
friendship.And所在行:6
from所在行:1
future所在行:4
go所在行:4 4
go;be所在行:1
happen所在行:6
happiest所在行:3
happiness所在行:2
happy?所在行:2
have所在行:1 2 3 3 3 4 6
heartaches所在行:4
hope所在行:2
hug所在行:1
human,enough所在行:2
hurt,所在行:3
hurts所在行:2 2
if所在行:6
importance所在行:3
in所在行:1 2 4 6
is所在行:5 5
it所在行:2
it,to所在行:6
just所在行:1 3 6
keep所在行:2
kiss所在行:4
know所在行:6
let所在行:4 6
lies所在行:3
life所在行:1 1 5 6
lifeuntil所在行:4
lives.Love所在行:4
make所在行:2 2 2 3 6 6
may所在行:2
mean所在行:6
message所在行:6
message.所在行:6
miss所在行:1 6
moments所在行:1
most所在行:3
much所在行:1
necessarily所在行:3
need所在行:6
of所在行:3 3 3 3 4 6
on所在行:4 4 6
one所在行:1 1 5 6
only所在行:1 3
opportunity所在行:6
or所在行:6
other所在行:2
others鈥檚hoes.If所在行:2
out所在行:6
past所在行:4
past,所在行:4
people所在行:3 3 6
person,所在行:2
pick所在行:1
please所在行:6
probably所在行:2
put所在行:2
real!所在行:1
really所在行:6 6
searched,and所在行:3
see所在行:6
send所在行:6
side所在行:6
smile所在行:6
smile,grows所在行:4
smiling所在行:5
smiling.Live所在行:5
so所在行:1 5
someone所在行:1
someone鈥檚所在行:6
something所在行:6
sorrow所在行:2
strong,enough所在行:2
sweet,enough所在行:2
tear.The所在行:4
that所在行:1 2 3 5 6 6
the所在行:1 2 3 3 3 3 5 6 6
their所在行:3 4 6
them所在行:1 1 6
there所在行:1
they所在行:3
things所在行:1 6
this所在行:6 6
those所在行:3 3 3 6 6 6 6 6
to所在行:1 1 1 1 1 1 2 2 2 2 6 6 6 6 6
too.所在行:2
touched所在行:4 6
trials所在行:2
tried,for所在行:3
want所在行:1 1 1 1 1 6
was所在行:5
way所在行:6
way.Happiness所在行:3
well所在行:4
were所在行:5 5
what所在行:1 1
when所在行:1 5 5 6 6
where所在行:1
who所在行:3 3 3 3 4 5 6 6 6 6
will所在行:4 6 6
with所在行:4 4 4 6
worry,nothing所在行:6
you所在行:1 1 1 1 1 1 1 2 2 2 2 2 2 4 4 5 5 5 5 6 6 6 6 6 6 6
you,it所在行:2
you,to所在行:6
you,you所在行:6
your所在行:1 4 5 6
yourself所在行:2
11.10
由于有序容器要求关键字类型必须支持比较操作<,因此
map<vector<int>::iterator, int> m1; //是可以的,因为vector的迭代器支持比较操作
map<list<int>::iterator, int> m2; //是不行的,因为list的元素不是连续存储,其迭代器不支持比较操作
11.11
代码如下:
typedef bool (*pf)(const Sales_data&, const Sales_data&);
multiset<Sales_data, pf> bookstore(compareIsbn);
11.12
#include<iostream>
#include<fstream>
#include<sstream>
#include<map>
#include<list>
#include<vector>
#include<string>
#include<algorithm>
#include <set>
#include<utility>
using namespace std;
int main(void) {
vector<string> string_test;
vector<int> int_test;
string t_string;
int t_int;
for (int i = 0; i < 5; ++i) {
cin >> t_string;
string_test.push_back(t_string);
}
for (int i = 0; i < 5; ++i) {
cin >> t_int;
int_test.push_back(t_int);
}
vector<pair<string, int>> data;
for (int i = 0; i < 5; ++i) data.push_back(pair<string, int>(string_test[i], int_test[i]));
for (const auto& d : data) cout << d.first << " " << d.second << endl;
return 0;
}
输入输出如下:
one two three four five
1 2 3 4 5
one 1
two 2
three 3
four 4
five 5
11.13
data.push_back({ s,v });
data.push_back(make_pair(s, v));
11.14
#include<iostream>
#include<fstream>
#include<sstream>
#include<map>
#include<list>
#include<vector>
#include<string>
#include<algorithm>
#include <set>
#include<utility>
using namespace std;
int main(void) {
map<string, vector<pair<string, string>>> families;
string name1, name2, bri;
for (int i = 0; i < 5; ++i) {
cin >> name1 >> name2 >> bri;
families[name1].push_back(make_pair(name2, bri));
}
return 0;
}
输入输出代码如下:
Link Zelda 18
H P 20
Z Q 18
U T 19
W B 20
11.15
mapped_type 是 vector<int>
key_type 是 int
value_type 是 pair<const int,vector<int>>
11.16
map<int,int> m
auto it=m.begin();
it->second=0;
11.17
前面两个是无序的插入到有序的. 不对
后面两个是有序的插入到无序的.对.
11.18
pair <const string,size_t> :: iterator
11.19
typedef_bool (*pf) (const Sales_data &,const Sales_data &);
multiset<Sales_data,pf> bookstore(compareIsbn);
pair<const Sales_data,pf>::iterator it=bookstore.begin();
11.20
肯定是原来的啊,用insert一环套一环,和套娃一样.不熟练的话,很容器出错的好吧.
代码就是P385的那个.
11.21
循环不断从标准输入读入单词(字符串),直至遇到文件结束或错误.
每读入一个单词,构造pair{word,0},通过insert 操作插入到word_count中.insert返回一个pair.其first成员是一个迭代器,若单词(关键字) 已存在与容器中,它指向新插入的元素.
因此,first会得到这个迭代器,指向word对应的元素.继续使用->second可获得元素的值的引用.即单词的计数.若单词是新的.则其值为0,若已存在.则值为之前出现的次数.对其进行递增操作,即完成将出现次数加1
11.22
参数类型 是一个pair,first 的成员的类型是map的关键字类型 string,second 成员的类型是map的值的类型vector:pair<string,vector>
返回类型也是一个pair,first成员的类型是map的迭代器,second成员的类型是布尔型
pair<map<string, vector<int>> ::iterator, bool>;
11.23
#include<iostream>
#include<fstream>
#include<sstream>
#include<map>
#include<list>
#include<vector>
#include<string>
#include<algorithm>
#include <set>
#include<utility>
using namespace std;
int main(void) {
multimap<string, string> families;
families.insert({ "张","强" });
families.insert({ "张","北" });
families.insert({ "Link","Zelda" });
for (auto f : families) cout << f.first << "家的孩子" << f.second << endl;
return 0;
}
11.24
如果m中已有了关键字0,下标操作提取出其值.赋值语句将其置为1
否则,下标操作会创建一个pair(0,0),即关键字为0,值为0(值初始化) ,将其插入到m中,然后提取其值.然后提取其值.赋值语句将值置为1
11.25
0就是位置0
如果v不是空的,那么就是输出这个值.
如果没有,会报错.
11.26
对map进行下标操作,应使用其key_type ,即关键字的类型
而下标操作返回的类型是 mapped_type .即关键字关联的值的类型
例子如下:
map<string,int>
//用来进行下标操作的类型 string
//下标操作返回的类型 int
11.27
只想知道在不在用find
想知道出现了几次 用count
11.28
find返回的一定是一个迭代器,能找到的话,返回第一个找到的元素的地址.不能找到的话,返回尾后迭代器
map<string,vector<int>> m;
map<string,vector<int>> ::iterator iter;// 这个就是类型的迭代器
11.29
它们都指向插入的正确位置.
lower_bound和upper_bound一定指向同一个位置.而且那个关键字在这个位置插入,一定是有序的.
equal_range返回一个pair 这个pair的first和second也一定指向同一个位置.那个关键字在这个位置插入,一定是有序的.
11.30
pos.first 就是找到的第一个给定作者的第一部著作的位置.
对应的因为是一个map
所以,我们用
pos.first->second
就是给定作者的第一步著作的位置.
->second 就是这个位置迭代器下的 值.
11.31
#include<iostream>
#include<fstream>
#include<sstream>
#include<map>
#include<list>
#include<vector>
#include<string>
#include<algorithm>
#include <set>
#include<utility>
using namespace std;
int main(void) {
multimap<string, string> test = { {"HPY","Link"},{"HPY","Zelda"},{"HPY","1024"},{"Faker","God"} };
test.erase(test.equal_range("HPY").first, test.equal_range("HPY").second);
for (auto i : test) cout << i.first << ":" << i.second << endl;
return 0;
}
11.32
#include<iostream>
#include<fstream>
#include<sstream>
#include<map>
#include<list>
#include<vector>
#include<string>
#include<algorithm>
#include <set>
#include<utility>
using namespace std;
int main(void) {
multimap<string, string> test = { {"HPY","Link"},{"HPY","Zelda"},{"HPY","1024"},{"Faker","God"} };
test.erase(test.equal_range("HPY").first, test.equal_range("HPY").second);
for (auto i : test) cout << i.first << ":" << i.second << endl;
return 0;
}
11.33
在配套的程序中有.这里不贴了.
11.34
不行的
下标还有一个功能就是插入.这样会导致程序错误.
11.35
下标可以实现覆盖操作,但是insert不行。
11.36
程序自己已经有处理失败的异常了.虽然还不是很完善.
11.37
无序版本通常性能更好,使用也更为简单,有序版本的优势是维护了关键字的徐.
当元素的关键字类型没有明显的序关系,或是维护元素的序代价非常高时,无序容器非常好用.
但当应用要求必须维护元素的序时,有序版本就是唯一的选择.
11.38
代码如下: