C++ primer 第十一章 关联容器

C++ primer 第十一章 关联容器 11.1节练习

练习11.1：描述map和vector的不同。
map中保存的是对值（key:value），其中的key和value都可以是任意类型。vector其实也可以看成是保存的对值，只不过他的key是固定的0，1，2，…

练习11.2：分别给出最适合使用list、vector、deque、map以及set的例子。
若元素很小（例如 int），大致数量预先可知，在程序运行过程中不会剧烈变化，
大部分情况下只在末尾添加或删除需要频繁访问任意位置的元素，则 vector 可带来最高的效率。
若需要频繁在头部和尾部添加或删除元素，则 deque 是最好的选择。
如果元素较大（如大的类对象），数量预先不知道，或是程序运行过程中频繁变化，对元素的访问更多是顺序访问全部或很多元素，则 list 很适合。
map 很适合对一些对象按它们的某个特征进行访问的情形。典型的例如按学生的名字来查询学生信息，即可将学生名字作为关键字，将学生信息作为元素值，保存在 map 中。
set，顾名思义，就是集合类型。当需要保存特定的值集合——通常是满足/不满足某种要求的值集合，用 set 最为方便。
本题答案来源：CSDN博主「我是管小亮」
原文链接：https://blog.csdn.net/TeFuirnever/article/details/103731753

练习11.3：编写你自己的单词计数程序。

#include 
#include 
#include 
# include 

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

#include 
#include 
#include 
# include 

11.2.1节练习

练习11.5：解释map和set的区别。你如何选择使用哪个？
当需要查找给定关键字所对应的数据时，应使用 map，按关键字访问值。
如果只需判定给定值是否存在时，应使用 set，它是简单的值的集合。

练习11.6：解释set和list的区别。你如何选择使用哪个？
如果只需要顺序访问这些元素，或是按位置访问元素，那么应使用 list。
如果需要快速判定是否有元素等于给定值，则应使用 set。

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

#include 
#include 
#include 
# include 

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

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

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

本题答案来源：CSDN博主「我是管小亮」
原文链接：https://blog.csdn.net/TeFuirnever/article/details/103731753

11.2.2节练习

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

map>

**练习11.10：**可以定义一个vector::iterator到int的map吗？list::iterator到int的map呢？对于两种情况，如果不能，解释为什么？
由于有序容器要求关键字类型必须支持比较 *** 作 <，
因此 mapml; 是可以的，因为 vector 的迭代器支持比较 *** 作。
而 mapm2; 是不行的，因为 list 的元素不是连续存储，其迭代器不支持比较 *** 作。

本题答案来源：CSDN博主「我是管小亮」
原文链接：https://blog.csdn.net/TeFuirnever/article/details/103731753

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

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

11.2.3节练习

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

#include 
#include 
#include 
# include 

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

vec.push_back(make_pair(s, n));
vec.push_back({s, n});

我觉得用花括号最方便，而且看上去就是一对。

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

#include 
#include 
#include 
# include 

11.3.1节练习

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

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

map m;
auto it=m.begin();
it->second = 0;        //it->first是不可以修改的

练习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 的迭代器是 const 的，因此只允许访问 set 中的元素，而不能改变 set。与 map 一样，set 的关键字也是 const，因此也不能通过迭代器来改变 set 中元素的值。

因此，前两个调用试图将 vector 中的元素复制到 set 中，是非法的。

而后两个调用将 set 中的元素复制到 vector 中，是合法的。

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

pair::iterator

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

typedef bool (*pf)(const Sales_data &, const Sales_data &); 
multiset bookstore(compareIsbn); 
......
pair::iterator it = bookstore.begin();

11.3.2节练习

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

#include 
#include 
#include 
# include 

下标更容易理解和编写。因为下标的形式不用判断关键字是否存在。

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

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

向map中插入pair，{word, 0} ，如果单词存在，插入不起作用，返回的first是指向那个单词pair的迭代器，迭代器指向的元素的second成员是单词数目，给这个数目加1就可以啦。如果单词不存在，插入起作用，返回first的是指向这个新插入的pair的迭代器，同样给second加1就可以啦。

练习11.22：给定一个map>，对此容器的插入一个元素的insert版本，写出其参数类型和返回类型。
参数类型：pair>
返回类型：pair>::iterator, bool>

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

#include 
#include 
#include 
# include 

11.3.4节练习

练习11.24：下面的程序完成什么功能？

map m;
m[0] = 1;

如果关键字0存在，把他的值变成1；
如果不存在，添加{0， 1}对。

练习11.25：对比下面的程序与上一题程序

vector v;
v[0] = 1;

对于 m，"0”表示“关键字0”。而对于 v，“0”表示“位置0”。

若 v 中已有不少于一个元素，即，存在“位置0”元素，则下标 *** 作提取出此位置的元素（左值），赋值 *** 作将其置为1。而 map 的元素是 pair 类型，下标提取的不是元素，而是元素的第二个成员，即元素的值。

如 v 尚为空，则下标提取出的是一个非法左值（下标 *** 作不做范围检查），向其赋值可能导致系统崩溃等严重后果。

练习11.26：可以用什么类型来对一个map进行下标 *** 作？下标运算返回的类型是什么？请给出一个具体例子——即，定义一个map，然后写出一个可以用来对map进行下标 *** 作的类型以及下标运算符将会返回的类型。
用map的关键字类型（key_type）进行下标 *** 作；
下标运算返回的是map的值的类型（mapped_type）；

map
//下标 *** 作类型
string
//下标运算符返回的类型
int

11.3.5节练习

练习11.27：对于什么问题你会使用count来解决？什么时候你又会选择find呢？
对于不允许重复关键字的容器，count和find没有什么区别。
对于允许重复关键字的容器，find会返回容器中是否有某个关键字。如果存在，count会返回有几个相同的关键字，如果不存在，返回0。
总结来说，对于不循序重复关键字的容器，用find，对于允许重复关键字的容器，需要计数用count()，只需要知道是否存在用find。

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

map>::iterator iter;

练习11.29：如果给定的关键字不住在容器中，upper_bound、lower_bound、equal_range分别会返回什么？
upper_bound和lower_bound会返回容器的尾后迭代器；
equal_range会返回一个pair，其中的两个元素都是容器的尾后迭代器。

练习11.30：对于本节最后一个程序中的输出表达式，解释运算对象pos.first->second的含义。
equal_range返回一对由迭代器组成的pair，first成员指向关键字和给定元素相同的第一个map元素，这个元素也是一个pair，他的second成员是书名。

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

#include 
#include 
#include 
# include 

练习11.32：使用上一题定义的multimap编写一个程序，按字典序打印作者列表和他们的作品。
在上一题的程序中已经体现了。

11.3.6节练习

练习11.33：实现你自己版本的单词转换程序。

#include 
#include 
#include 
# include 

练习11.34：如果你将transform函数中的find替换为下标运算符，会发生什么情况？
当关键字存在时，下标运算符的行为与 find 类似，但当关键字不存在时，它会构造一个 pair（进行值初始化），将其插入到容器中。对于单词转换程序，这会将不存在的内容插入到输出文本中，这显然不是我们所期望的。

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

trans_map[key] = value.substr(1)

改为trans_map.insert({key, value.substr(1)})

当规则文件中存在多条规则转换相同单词时，下标+赋值 的版本最终会用最后一条规则进行文本转换，而 insert 版本则会用第一条规则进行文本转换。

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

会跑出异常，程序中已经处理了

if(value.size() > 1){
			trans_map[key] = value.substr(1);
		}
		else{
			throw runtime_error("no rule for" + key);
		}

11.4节练习

练习11.37：一个无序容器与其有序容器相比有何优势？有序版本有何优势？
无序容器不用维护元素的序，当关键字没有明显的序关系或者维护序的代价非常高昂时，用无序容器。当需要元素按一定的顺序排列时，只能用有序容器。

练习11.38：用unordered_map重写单词计数程序（参见11.1节，第375页）和单词转换程序（参见11.3.6节，第391页）。

#include 
#include 
#include 
# include 
# include 
using namespace std;
 
int main()
{

    unordered_map word_count;
	fstream file;
	file.open("article.txt");
	string word;
	while(file >> word){
		auto i = word.begin();
		while( i != word.end()){
			if(ispunct(*i)){
				word.erase(i);
			}
			else{
				*i = tolower(*i);
				++i;
			}
		}
		++word_count[word];
	}

	for(const auto &w : word_count){
		cout << w.first << " occurs " << w.second << endl;
	}
    return 0;
}

单词计数程序用无序容器，输出和之前不同，单词顺序不再按字典序排列。

#include 
#include 
#include 
# include 
# include 
# include 
using namespace std;

unordered_map buildMap(ifstream &map_file){
	unordered_map trans_map;
	string key;
	string value;
	while(map_file >> key && getline(map_file, value)){
		if(value.size() > 1){
			trans_map[key] = value.substr(1);
		}
		else{
			throw runtime_error("no rule for" + key);
		}
	}
	return trans_map;
}

const string &transform(const string &s, const unordered_map &m){
	auto map_it = m.find(s);
	if(map_it != m.cend()){
		return map_it->second;
	}
	else{
		return s;
	}

}

void word_transform(ifstream &map_file, ifstream &input_file){
	auto trans_map = buildMap(map_file);
	string text;
	while(getline(input_file, text)){
		istringstream stream(text);
		string word;
		bool firstword = true;
		while(stream >> word){
			if(firstword)
				firstword = false;
			else
				cout << " ";
			cout << transform(word, trans_map);
		}
		cout << endl;
	}
}
int main()
{
    string map_path = "map_file.txt";
	string input_path = "input_file.txt";
	ifstream map_file, input_file;
	map_file.open(map_path);
	input_file.open(input_path);
	word_transform(map_file, input_file);
    return 0;
}

单词转换程序中，最终的输出和转换字典的顺序没有关系，所以输出不会发生变化。