第十一章 关联容器

练习11.1

描述map和vector的不同。

解：

    顺序容器中的元素是“顺序”存储的，对于vector，元素在其中按顺序存储，每个元素都有唯一对应
的位置编号，所有操作都是按编号进行的。例如，获取元素（头、尾、下标）、插入删除元素（头、尾、
任意位置）、遍历元素（按元素位置顺序逐一访问）。底层数据结构是数组，链表，简单但能保证上诉操
作的高效。而对于按值的元素访问，例如查找（搜索）给定值（find），在这种数据结构上的实现都是要
通过遍历来完成的，因而效率不佳
    而map这种关联容器，就是为了高效实现“按值访问元素”这类操作而设计的。为了达到这一目的，
容器中的元素都是按照关键字存储的，关键字值与元素数据建立起对应关系，这就是“关联”的含义。底
层数据结构是红黑树、hash表等

练习11.2

分别给出最适合使用list、vector、deque、map以及set的例子。

解：

• list：双向链表，适合频繁插入删除元素的场景。
• vector：适合频繁访问元素或者尾部增加和删除元素的场景。
• deque：双端队列，适合频繁在头尾插入删除元素的场景。
• map：需要按某个特征进行访问的场景
• set：适合需要知道在某个集合内某些元素满不满足某个条件的场景。

练习11.3

编写你自己的单词计数程序。

解：

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ifstream inpt;
    inpt.open("mnt.txt", ios::in);
    if (!inpt.is_open())
    {
        cout << "文件打开失败" << endl;
        return -1;
    }

    map<string, size_t> cnt;
    string word;
    while (inpt >> word)
        ++ cnt[word];
    
    for (auto item : cnt)
        cout << item.first << "出现了" << item.second << "次" << endl;

    inpt.close();
    
    cout << endl;
    return 0;
}

练习11.4

扩展你的程序，忽略大小写和标点。例如，“example.”、"example,"和"Example"应该递增相同的计数器。

解：

//增加一个对字符串处理的函数即可 
#include <bits/stdc++.h>

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()
{
    ifstream inpt;
    inpt.open("mnt.txt", ios::in);
    if (!inpt.is_open())
    {
        cout << "文件打开失败" << endl;
        return -1;
    }

    map<string, size_t> cnt;
    string word;
    while (inpt >> word)
        ++ cnt[trans(word)];
    
    for (auto item : cnt)
        cout << item.first << "出现了" << item.second << "次" << endl;

    inpt.close();

    cout << endl;
    return 0;
}

练习11.5

解释map和set的区别。你如何选择使用哪个？

解：

当需要按关键字访问时，应使用map
如果只需要判定给定值是否存在时，应使用set

练习11.6

解释set和list的区别。你如何选择使用哪个？

set 是有序不重复集合，底层实现是红黑树，而 list 是无序可重复集合，底层实现是链表

练习11.7

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

解：

map<string, vector<string>> m;
for (string ln; cout << "Last name:\n", cin >> ln && ln != "@q";)
	for (string cn; cout << "|-Children's names:\n", cin >> cn && cn != "@q";)
		m[ln].push_back(cn);

练习11.8

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

解：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

int main()
{
	std::vector<std::string> exclude = { "aa", "bb", "cc", "dd", "ee", "ff" };
	for (std::string word; std::cout << "Enter plz:\n", std::cin >> word;)
	{
		auto is_excluded = std::binary_search(exclude.cbegin(), exclude.cend(), word);
		auto reply = is_excluded ? "excluded" : "not excluded";
		std::cout << reply << std::endl;
	}
	return 0;
}

set的优点是集合本身的元素就是不重复。

练习11.9

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

解：

std::map<std::string, std::list<std::size_t>> m;

练习11.10

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

解：
关联容器要求关键字类型必须支持<操作，因此：
可以定义 vector<int>::iterator 到 int 的map，但是不能定义 list<int>::iterator 到 int 的map。因为map的键必须实现 < 操作，list 的迭代器不支持比较运算。

练习11.11

不使用decltype 重新定义 bookstore。

解：

using Less = bool (*)(Sales_data const&, Sales_data const&);
std::multiset<Sales_data, Less> bookstore(less);

练习11.12

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

解：

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ifstream inpt;
    inpt.open("mnt.txt", ios::in);
    if (!inpt.is_open())
    {
        cout << "文件打开失败" << endl;
        return -1;
    }

    vector<pair<string, int>> data;
    string s;
    int v;
    while (inpt >> s && inpt >> v)
        data.push_back(pair<string, int>(s, v));
    for (auto item : data)
        cout << item.first << " " << item.second << endl;

    inpt.close();

    cout << endl;
    return 0;
}

练习11.13

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

解：

vec.push_back(std::make_pair(str, i));
vec.push_back({ str, i });
vec.push_back(std::pair<string, int>(str, i)); 

使用花括号的初始化器最易于理解和编写。

练习11.14

扩展你在11.2.1节练习中编写的孩子姓达到名的map，添加一个pair的vector，保存孩子的名和生日。

解：

#include <iostream>
#include <map>
#include <string>
#include <vector>

using std::ostream;
using std::cout;
using std::cin;
using std::endl;
using std::string;
using std::make_pair;
using std::pair;
using std::vector;
using std::map;

class Families
{
public:
	using Child = pair<string, string>;
	using Children = vector<Child>;
	using Data = map<string, Children>;

	void add(string const& last_name, string const& first_name, string birthday)
	{
		auto child = make_pair(first_name, birthday);
		_data[last_name].push_back(child);
	}

	void print() const
	{
		for (auto const& pair : _data)
		{
			cout << pair.first << ":\n";
			for (auto const& child : pair.second)
				cout << child.first << " " << child.second << endl;
			cout << endl;
		}
	}

private:
	Data _data;
};

int main()
{
	Families families;
	auto msg = "Please enter last name, first name and birthday:\n";
	for (string l, f, b; cout << msg, cin >> l >> f >> b; families.add(l, f, b));
	families.print();

	return 0;
}

练习11.15

对一个int到vector<int>的map，其mapped_type、key_type和 value_type分别是什么？

解：

• mapped_type : vector<int>
• key_type : int
• value_type : std::pair<const int,vector >

练习11.16

使用一个map迭代器编写一个表达式，将一个值赋予一个元素。

解：

map<int, int> m;
auto it = m.begin();
it->second = 12;

练习11.17(*)

假定c是一个string的multiset，v 是一个string 的vector，解释下面的调用。指出每个调用是否合法：

copy(v.begin(), v.end(), inserter(c, c.end()));
copy(v.begin(), v.end(), back_inserter(c));
copy(c.begin(), c.end(), inserter(v, v.end()));
copy(c.begin(), c.end(), back_inserter(v));

解：
本题考查关联容器迭代器的特点
set迭代器是cons的，因此只允许访问set中的元素，而不能改变set。
set和map的关键字都是const的，因此也不能通过迭代器来改变set中的元素的值
综上所述，前两个是非法的，后两个是合法的

练习11.18

写出第382页循环中map_it 的类型，不要使用auto 或 decltype。

解：

map<string, size_t>::const_iterator map_it = word_count.cbegin();

练习11.19

定义一个变量，通过对11.2.2节中的名为 bookstore 的multiset 调用begin()来初始化这个变量。写出变量的类型，不要使用auto 或 decltype。

解：

using compareType = bool (*)(const Sales_data &lhs, const Sales_data &rhs);
std::multiset<Sales_data, compareType> bookstore(compareIsbn);
std::multiset<Sales_data, compareType>::iterator c_it = bookstore.begin();

练习11.20

重写11.1节练习的单词计数程序，使用insert代替下标操作。你认为哪个程序更容易编写和阅读？解释原因。

解：

#include <iostream>
#include <map>
#include <string>

using std::string;
using std::map;
using std::cin;
using std::cout;

int main()
{
	map<string, size_t> counts;
	for (string word; cin >> word;)
	{
		auto result = counts.insert({ word, 1 });
		if (!result.second)
			++result.first->second;
	}
	for (auto const& count : counts)
		cout << count.first << " " << count.second << ((count.second > 1) ? " times\n" : " time\n");

	return 0;
}

使用insert更容易阅读和编写。insert有返回值，可以明确的体现出插入操作的结果。

练习11.21

假定word_count是一个string到size_t的map，word是一个string，解释下面循环的作用：

while (cin >> word)
	++word_count.insert({word, 0}).first->second;

解：

这条语句等价于：

while (cin >> word)
{
	auto result = word_count.insert({word, 0});
	++(result.first->second);
}

    ~~~    循环不断读入单词，直到文件结束或者错误，每读入一个单词就构造一个pair，通过insert操作插入到word_count中。
    ~~~    若insert成功：先添加一个元素，然后返回一个 pair，pair 的 first元素是一个迭代器。若关键字已存在，则它指向已存在的元素，否则指向新插入的元素。因此，这个first迭代器指向刚刚添加的元素，继续使用->second则可获得元素值的引用，即单词的计数。若单词是新的，则值为0，若已存在，则值为之前出现的次数，然后对其进行递增操作

练习11.22

给定一个map<string, vector<int>>，对此容器的插入一个元素的insert版本，写出其参数类型和返回类型。

首先map的元素肯定是pair，所以要考虑first和second
从map类型可以看出，first是string
second是vector<int>

map的insert返回的也是一个pair，所以也要考虑first和second
由21题可知，first应该是一个迭代器
综上所述，结果如下：

std::pair<std::string, std::vector<int>>    // 参数类型
std::pair<std::map<std::string, std::vector<int>>::iterator, bool> // 返回类型

练习11.23

11.2.1节练习中的map 以孩子的姓为关键字，保存他们的名的vector，用multimap 重写此map。

解：

#include <map>
#include <string>
#include <iostream>

using std::string;
using std::multimap;
using std::cin;
using std::endl;

int main()
{
    multimap<string, string> families;
    for (string lname, cname; cin >> cname >> lname; families.emplace(lname, cname));
    for (auto const& family : families)
        std::cout << family.second << " " << family.first << endl;
}

练习11.24

下面的程序完成什么功能？

map<int, int> m;
m[0] = 1;

解：

添加一个元素到map中，如果该键存在，则重新赋值。

练习11.25

对比下面的程序与上一题程序

vector<int> v;
v[0] = 1;

解：

未定义行为，vector 的下标越界访问。

练习11.26

可以用什么类型来对一个map进行下标操作？下标运算符返回的类型是什么？请给出一个具体例子——即，定义一个map，然后写出一个可以用来对map进行下标操作的类型以及下标运算符将会返会的类型。

解：

对map进行下标操作，应该使用key_type，即关键字的类型
而对下标操作返回的类型是mapped_type，即关键字关联的值的类型
实例：

map<string, int>
进行下标操作的类型：string
下标操作放回的类型：int

练习11.27

对于什么问题你会使用count来解决？什么时候你又会选择find呢？

解：

对于允许重复关键字的容器，应该用 count ; 对于不允许重复关键字的容器，应该用 find 。

练习11.28

对一个string到int的vector的map。定义并初始化一个变量来保存在其上调用find所返回的结果。

解：

map<string, vector<int>> m;
map<string, vector<int>>::iterator it = m.find("key");

练习11.29(-)

如果给定的关键字不在容器中，upper_bound、lower_bound 和 equal_range 分别会返回什么？

解：

     ~~~~     lower_bound返回第一个具有给定关键字的元素，upper_bound则返回最后一个具有给定关键字的元素之后的位置。即，这两个迭代器构成包含所有具有给定关键字的元素的范围。
     ~~~~     若给定关键字不在容器中，两个操作应该构成一个空范围，它们返回相当的迭代器，指出关键字的正确插入位置——不影响关键字的排序。如果给定关键字比所有关键字都大，则此位置是容器的尾后位置end
     ~~~~     equal_range返回一个pair，其first成员等价于lower_bound返回的迭代器，second成员等价于upper_bound返回的迭代器。因此，若给定关键字不在容器中，first和second都指向关键字的正确插入位置，两个迭代器构成一个空范围

练习11.30

对于本节最后一个程序中的输出表达式，解释运算对象pos.first->second的含义。

解：

pos 是equal_range返回的，是一个pair，pos.first 和lower_bound的返回结果相同，即指向容器中第一个具有给定关键字的元素。因此，对其解引用会得到一个value_type的对象，即一个pair，这个pair的first为元素的关键字，即给定的关键字，而second为关键字关联的值。

练习11.31

编写程序，定义一个作者及其作品的multimap。使用find在multimap中查找一个元素并用erase删除它。确保你的程序在元素不在map 中时也能正常运行。

解：

//将数据插入到multimap中，需要使用insert操作
//在multimap中查找给定关键字的元素，有几种方法
1.使用find只能查找第一个具有给定关键字的元素，要找到所有具有给定关键字的元素，需要编写
循环
2.lower_bound和upper_bound配合使用，可找到具有给定关键字的元素的范围
lower_bound是大于等于，upper_bound是大于，因此可以找到等于的范围
3.equal_range最为简单，一次即可获得要查找的元素的范围
综上，只要将找到的范围传递给erase，即可删除指定作者的所有著作
当然，为了解决元素不在multimap中的情况，首先检查equal_range返回的两个迭代器，若相等(空
范围)，则什么也不做。只有当范围不为空的时候，才将迭代器传递给erase，删除所有元素
#include <bits/stdc++.h>

using namespace std;

void remove_author(multimap<string, string> &books, const string &author)
{
    auto pos = books.equal_range(author);
    if (pos.first == pos.second)
        cout << "没有" << author << "这个作者" << endl;
    else 
        books.erase(pos.first, pos.second);
}

void print_books(multimap<string, string> &books)
{
    cout << "当前书目包括：" << endl;
    for (auto book : books)
        cout << book.first << ", 《" << book.second << "》" << endl;
    cout << endl;
    
}

int main()
{
    multimap<string, string> books;
    books.insert({"金庸", "天龙八部"});
    books.insert({"金庸", "射雕英雄传"});
    books.insert({"耳根", "求魔"});
    books.insert({"耳根", "仙逆"});
    books.insert({"耳根", "我欲封天"});

    print_books(books);
    remove_author(books, "金庸");
    remove_author(books, "太冤枉");
    print_books(books);

    
    cout << endl;
    return 0;
}

练习11.32

使用上一题定义的multimap编写一个程序，按字典序打印作者列表和他们的作品。

解：

equal_range

练习11.33

实现你自己版本的单词转换程序。

解：

#include <map>
#include <string>
#include <fstream> 
#include <iostream>
#include <sstream>

using std::string; using std::ifstream;

std::map<string, string> buildMap(ifstream &map_file)
{
    std::map<string, string> trans_map;
    for (string key, value; map_file >> key && getline(map_file, value); )
        if (value.size() > 1) trans_map[key] = value.substr(1).substr(0, value.find_last_not_of(' '));
    return trans_map;
}

const string & transform(const string &s, const std::map<string, string> &m)
{
    auto map_it = m.find(s);
    return map_it == m.cend() ? s : map_it->second;
}

void word_transform(ifstream &map, ifstream &input)
{
    auto trans_map = buildMap(map);
    for (string text; getline(input, text); ) {
        std::istringstream iss(text);
        for (string word; iss >> word; )
            std::cout << transform(word, trans_map) << " ";
        std::cout << std::endl;
    }
}

int main()
{
    ifstream ifs_map("../data/word_transformation_bad.txt"), ifs_content("../data/given_to_transform.txt");
    if (ifs_map && ifs_content) word_transform(ifs_map, ifs_content);
    else std::cerr << "can't find the documents." << std::endl;
}

练习11.34

如果你将transform 函数中的find替换为下标运算符，会发生什么情况？

解：

find仅查找给定关键字是否在容器中出现，若容器中不存在给定关键字，则它返回尾后迭代器。
当关键字存在时，下标运算符的行为和find类似，但是不存在的时候，它会构造一个pair(先进行值初始化)，然后将其插入到容器中。

练习11.35

在buildMap中，如果进行如下改写，会有什么效果？

trans_map[key] = value.substr(1);
//改为
trans_map.insert({key, value.substr(1)});

解：

当一个转换规则的关键字多次出现的时候，使用下标运算符会保留为最后一次添加的值，而用insert则保留第一次添加的值。

练习11.36

我们的程序并没检查输入文件的合法性。特别是，它假定转换规则文件中的规则都是有意义的。如果文件中的某一行包含一个关键字、一个空格，然后就结束了，会发生什么？预测程序的行为并进行验证，再与你的程序进行比较。

解：

如果关键字没有对应的规则，那么程序会抛出一个 runtime_error。

练习11.37

一个无序容器与其有序版本相比有何优势？有序版本有何优势？

无序容器拥有更好的性能，有序容器使得元素始终有序。

练习11.38

用 unordered_map 重写单词计数程序和单词转换程序。

解：

#include <unordered_map>
#include <set>
#include <string>
#include <iostream>
#include <fstream>
#include <sstream>

using std::string;

void wordCounting()
{
    std::unordered_map<string, size_t> word_count;
    for (string word; std::cin >> word; ++word_count[word]);
    for (const auto &w : word_count)
        std::cout << w.first << " occurs " << w.second << (w.second > 1 ? "times" : "time") << std::endl;
}

void wordTransformation()
{
    std::ifstream ifs_map("../data/word_transformation.txt"), ifs_content("../data/given_to_transform.txt");
    if (!ifs_map || !ifs_content) {
        std::cerr << "can't find the documents." << std::endl;
        return;
    }
    
    std::unordered_map<string, string> trans_map;
    for (string key, value; ifs_map >> key && getline(ifs_map, value); )
        if (value.size() > 1) trans_map[key] = value.substr(1).substr(0, value.find_last_not_of(' '));
    
    for (string text, word; getline(ifs_content, text); std::cout << std::endl)
        for (std::istringstream iss(text); iss >> word; ) {
            auto map_it = trans_map.find(word);
            std::cout << (map_it == trans_map.cend() ? word : map_it->second) << " ";
        }
}

int main()
{
    //wordCounting();
    wordTransformation();
}