《C++ Primer》第11章 11.2节习题答案

《C++ Primer》第11章关联容器

11.2节关联容器概述习题答案

练习11.5：解释map和set的差别。你如何选择使用哪个？

【出题思路】

理解两种关联容器的差别。

【解答】

当需要查找给定值所对应的数据时，应使用map，其中保存的是<关键字, 值>对，按关键字访问值。如果只需判定给定值是否存在时，应使用set，它是简单的值的集合。

练习11.6：解释set和list的差别。你如何选择使用哪个？

【出题思路】

理解关联容器和顺序容器的差别。

【解答】

两者都可以保存元素集合。如果只需要顺序访问这些元素，或是按位置访问元素，那么应使用list。如果需要快速判定是否有元素等于给定值，则应使用set。

练习11.7：定义一个map，关键字是家庭的姓，值是一个vector，保存家中孩子（们）的名。编写代码，实现添加新的家庭以及向已有家庭中添加新的孩子。

【出题思路】

理解map的稍复杂的使用。

【解答】

此map的关键字类型是string，值类型是vector。我们定义函数add_family添加一个家庭，注意，必须先检查是否已有这个家庭，若不做这个检查，则可能将已有家庭的孩子名字清空（如main函数中的王姓家庭的添加顺序）。若确实还没有这个家庭，则创建一个空的vector，表示这个家庭的孩子名字列表。

函数add_child向一个已有家庭添加孩子的名字：首先用[]运算符取出该家庭的vector，然后调用push_back将名字追加到vector末尾。

#include 
#include 
#include 
#include 
#include 

using namespace std;

void add_family(map> &families, const string& family)
{
    if(families.find(family) == families.end())
        families[family] = vector();
}

void add_child(map> &families, const string &family, const string &child)
{
    families[family].push_back(child);
}

int main(int argc, const char * argv[])
{
    map> families;

    add_family(families, "张");
    add_child(families, "张", "强");
    add_child(families, "张", "刚");
    add_child(families, "王", "五");
    add_family(families, "王");

    for(auto f: families)
    {
        cout << f.first << " 家的孩子：";
        for(auto c: f.second)
            cout << c << " ";
        cout << endl;
    }

    return 0;
}

运行结果

练习11.8：编写一个程序，在一个vector而不是一个set中保存不重复的单词。使用set的优点是什么？

【出题思路】

通过实际编程理解set和vector的差别。

【解答】

使用vector保存不重复单词，需要用find查找新读入的单词是否已在vector中，若不在（返回尾后迭代器），才将单词加入vector。而使用set，检查是否重复的工作是由set模板负责的，程序员无须编写对应代码，程序简洁很多。

更深层次的差别，vector是无序线性表，find查找指定值只能采用顺序查找方式，所花费的时间与vector.size()呈线性关系。而set是用红黑树实现的，花费的时间与vector.size()呈对数关系。当单词数量已经非常多时，set的性能优势是巨大的。当然，vector也不是毫无用处。它可以保持单词的输入顺序，而set则不能，遍历set，元素是按值的升序被遍历的。

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

string &trans(string &s)
{
    for(int p = 0; p < s.size(); p++)
    {
        if(s[p] >= 'A' && s[p] <= 'Z')
            s[p] -= ('A' - 'a');
        else if(s[p] == ',' || s[p] == '.')
            s.erase(p, 1);
    }

    return s;
}

int main(int argc, const char * argv[])
{
    ifstream in(argv[1]);
    if(!in)
    {
        cout << "打开输入文件失败！" << endl;
        exit(1);
    }

    vector unique_word;     //不重复的单词
    string word;
    while(in >> word)
    {
        trans(word);
        if(find(unique_word.begin(), unique_word.end(), word) == unique_word.end())
            unique_word.push_back(word);//添加不重复单词
    }

    for(const auto &w: unique_word) //打印不重复单词
    {
        //打茚结果
        cout << w << " ";
    }
    cout << endl;

    return 0;
}

data11_08.txt文件内容为：

the quick red fox jumps over the the slow over red turtle

设置命令行参数：

运行结果：

练习11.9：定义一个map，将单词与一个行号的list关联，list中保存的是单词所出现的行号。

【出题思路】

练习map的使用。

【解答】

map的定义为：

map> word_lineno;

完整程序如下所示。其中用getline读取一行，统计行号。再用字符串流读取这行中所有单词，记录单词行号。参见第8章内容。

#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

string &trans(string &s)
{
    for(int p = 0; p < s.size(); ++p)
    {
        if(s[p] >= 'A' && s[p] <= 'Z')
            s[p] -= ('A' - 'a');
        else if(s[p] == ',' || s[p] == '.')
            s.erase(p, 1);
    }

    return s;
}

int main(int argc, const char * argv[])
{
    ifstream in(argv[1]);
    if(!in)
    {
        cout << "打开输入文件失败！" << endl;
        exit(1);
    }

    map> 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;
}

data11_09.txt文件内容为：

The
quick
Red
fox.
jumps
Over
the,
the
Slow.
over
red.
turtle

设置命令行参数：

运行结果：

练习11.10：可以定义一个vector::iterator到int的map吗？list::iterator到int的map呢？对于两种情况，如果不能，解释为什么。

【出题思路】

理解关联容器对关键字类型的要求。

【解答】

由于有序容器要求关键字类型必须支持比较操作<，因此

map::iterator, int> m1;

是可以的，因为vector的迭代器支持比较操作。而

map::iterator, int> m2;

是不行的，因为list的元素不是连续存储，其迭代器不支持比较操作。

练习11.11：不使用decltype重新定义bookstore。

【出题思路】

本题练习函数指针类型的定义。

【解答】

首先用typedef定义与compareIsbn相容的函数指针类型，然后用此类型声明multiset即可。

typedef bool (*pf)(const Sales_data &, const Sales_data &);
multiset bookstore(compareIsbn);

练习11.12：编写程序，读入string和int的序列，将每个string和int存入一个pair中，pair保存在一个vector中。

【出题思路】

本题练习pair的使用。

【解答】

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

int main(int argc, const char * argv[])
{
    ifstream in(argv[1]);
    if(!in)
    {
        cout << "打开输入文件失败！" << endl;
        exit(1);
    }

    vector> data; //pair的vector
    string s;
    int v;
    while(in >> s && in >> v)       //读取一个字符串和一个整数
    {
        data.push_back(pair(s, v));
    }

    for(const auto &d: data)        //打印单词行号
        cout << d.first << " " << d.second << endl;
    cout << endl;
    return 0;
}

data11_12.txt文件内容为：

The 1
quick 2
Red 3
fox. 4
jumps 5
Over 6
the, 7
the 8
Slow. 9
over 10
red. 11
turtle 12

设置命令行参数：

运行结果：

练习11.13：在上一题的程序中，至少有三种创建pair的方法。编写此程序的三个版本，分别采用不同的方法创建pair。解释你认为哪种形式最易于编写和理解，为什么？

【出题思路】

熟悉pair的不同初始化方式。

【解答】

while(in >> s && in >> v)       //读取一个字符串和一个整数
{
     //data.push_back(pair(s, v));//第一种方式初始化
     //data.push_back({s, v});//列表初始化
     data.push_back(make_pair(s, v));//make_pair初始化
}

显然，列表初始化方式最为简洁易懂。

练习11.14：扩展你在11.2.1节练习（第378页）中编写的孩子姓到名的map，添加一个pair的vector，保存孩子的名字和生日。

【出题思路】

本题练习稍复杂的pair和关联容器的结合使用。

【解答】

在本题中，我们将家庭的姓映射到孩子信息的列表，而不是简单的孩子名字的列表。因此，将在vector中的元素类型声明为pair，两个string分别表示孩子的名字和生日。在添加孩子信息时，用列表初始化创建名字和生日的pair，添加到vector中即可。

#include 
#include 
#include   //pair
#include 
#include 
#include 

using namespace std;

void add_family(map>> &families, const string &family)
{
    families[family];
}

void add_child(map>> &families, const string &family, const string &child, const string &birthday)
{
    families[family].push_back({child, birthday});
}

int main()
{
    map>> families;
    add_family(families, "张");
    add_child(families, "张", "强", "1970-1-1");
    add_child(families, "张", "刚", "1980-1-1");
    add_child(families, "王", "五", "1990-1-1");
    add_family(families, "王");

    for(auto f: families)
    {
        cout << f.first << "家的孩子: ";
        for(auto c: f.second)
            cout << c.first << "(生日" << c.second << "), ";
        cout << endl;
    }

    return 0;
}

运行结果：

练习11.15：对一个int到vector的map，其mapped_type、key_type和value_type分别是什么？

【出题思路】

理解关联容器的类型别名。

【解答】

mapped_type是vector
key_type是int
value_type是pair>

《C++ Primer》第11章 11.2节习题答案

Linux相关栏目本月热门文章