第十一章关联容器

11.1

map：存储关键字-值（key-value）对的容器，关键字起到索引的作用，值则表示与索引相关联的数据；关键字是唯一、有序存储的

vector：存储单一类型元素的容器；元素是按添加顺序存储的

11.2

list：频繁在任意处插入/删除元素但不要求有随机访问能力时

vector：在尾部插入/删除元素且要求具有随机访问能力时

deque：在首尾插入/删除元素且要求具有随机访问能力时

map：统计每个单词在输入中出现的次数

set：查找集合中是否包含某个数

11.3

 1 #include <iostream>
 2 #include <fstream>
 3 #include <iterator>
 4 #include <vector> 
 5 #include <string>
 6 #include <deque>
 7 #include <list> 
 8 #include <forward_list>
 9 #include <stack>
10 #include <queue>
11 #include <algorithm> 
12 #include <functional>
13 #include <map>
14 #include <set> 
15  
16 using namespace std;
17 using namespace std::placeholders;
18 
19 int main()
20 {
21        map<string, int> jzd;
22        string word;
23        while (cin >> word) {
24            ++jzd[word];
25        }
26        for (auto &i : jzd) {
27            cout << i.first << " occurs about " << i.second << (i.second > 1 ? "times.
" : "time
"); 
28        }
29     return 0;
30 }

View Code

11.4

 1 #include <iostream>
 2 #include <fstream>
 3 #include <iterator>
 4 #include <vector> 
 5 #include <string>
 6 #include <deque>
 7 #include <list> 
 8 #include <forward_list>
 9 #include <stack>
10 #include <queue>
11 #include <algorithm> 
12 #include <functional>
13 #include <map>
14 #include <set> 
15 #include <cctype>
16  
17 using namespace std;
18 using namespace std::placeholders;
19 
20 int main()
21 {
22        map<string, int> jzd;
23        string word;
24        while (cin >> word) {
25            for (auto &i : word)
26             if (i <= 'Z' && i >= 'A')    i = tolower(i);
27         for (auto it = word.begin(); it != word.end(); ++it) {
28             if (ispunct(*it)) {
29                 it = word.erase(it);
30                 --it;
31             }
32         }
33            ++jzd[word];
34        }
35        for (auto &i : jzd) {
36            cout << i.first << " occurs about " << i.second << (i.second > 1 ? "times.
" : "time
"); 
37        }
38     return 0;
39 }

View Code

11.5

map：每个元素都是一个关键字-值对，初始化时必须提供关键字类型和值类型

set：每个元素只是一个关键字，没有值，元素类型就是关键字类型

11.6

set：元素都是唯一有序的

list：插入/删除元素很方便

11.7

 1 #include <iostream>
 2 #include <fstream>
 3 #include <iterator>
 4 #include <vector> 
 5 #include <string>
 6 #include <deque>
 7 #include <list> 
 8 #include <forward_list>
 9 #include <stack>
10 #include <queue>
11 #include <algorithm> 
12 #include <functional>
13 #include <map>
14 #include <set> 
15 #include <cctype>
16  
17 using namespace std;
18 using namespace std::placeholders;
19 
20 int main()
21 {
22        map<string, vector<string>> imap;
23        string name1, name2;
24        while (cin >> name1) {
25            cin >> name2;
26            imap[name1].push_back(name2);
27        }
28        for (auto &i : imap) {
29            for (auto &j : i.second) {
30                cout << i.first << " " << j << endl;
31            }
32            cout << endl;
33        }
34     return 0;
35 }

View Code

11.8

 1 #include <iostream>
 2 #include <fstream>
 3 #include <iterator>
 4 #include <vector> 
 5 #include <string>
 6 #include <deque>
 7 #include <list> 
 8 #include <forward_list>
 9 #include <stack>
10 #include <queue>
11 #include <algorithm> 
12 #include <functional>
13 #include <map>
14 #include <set> 
15 #include <cctype>
16  
17 using namespace std;
18 using namespace std::placeholders;
19 
20 void use_set(const vector<string> &vec)
21 {
22     set<string> iset(vec.begin(), vec.end());
23     for (auto &i : iset)    cout << i << " ";
24     cout << endl;
25 }
26 
27 void use_vector(const vector<string> &vec)
28 {
29     vector<string> ivec(vec.begin(), vec.end());
30     //unique必须要先sort过 
31     sort(ivec.begin(), ivec.end());
32     vector<string>::iterator it = unique(ivec.begin(), ivec.end());
33     ivec.erase(it, ivec.end());
34     for (auto &i : ivec)    cout << i << " ";
35     cout << endl;
36 }
37 
38 int main()
39 {
40     vector<string> vec = {"scout", "peanut", "jack", "peanut", "amazon", "jack", "demo"};
41        use_set(vec);
42        use_vector(vec);
43     return 0;
44 }

View Code

11.9

 1 #include <iostream>
 2 #include <fstream>
 3 #include <iterator>
 4 #include <vector> 
 5 #include <string>
 6 #include <deque>
 7 #include <list> 
 8 #include <forward_list>
 9 #include <stack>
10 #include <queue>
11 #include <algorithm> 
12 #include <functional>
13 #include <map>
14 #include <set> 
15 #include <cctype>
16  
17 using namespace std;
18 using namespace std::placeholders;
19 
20 int main()
21 {
22     map<string, list<int>> imap;
23     imap = {{"kzw", {2, 3, 5}}, {"ly", {1, 4, 6}}};
24     for (auto &i : imap) {
25         for (auto &j : i.second) {
26             cout << i.first << " occurs at line " << j << endl; 
27         }
28     }
29     return 0;
30 }

View Code

11.10

可以定义一个 vector<int>::iterator 到 int 的map，因为容器vector的迭代器定义了行为正常的<运算符。

而list的迭代器则没有定义大小比较的操作。

11.11

	bool (*pf)(const Sales_data &, const Sales_data &) = compareIsbn;
	multiset<Sales_data, pf> bookstore(compareIsbn);

11.12

 1 #include <iostream>
 2 #include <fstream>
 3 #include <iterator>
 4 #include <vector> 
 5 #include <string>
 6 #include <deque>
 7 #include <list> 
 8 #include <forward_list>
 9 #include <stack>
10 #include <queue>
11 #include <algorithm> 
12 #include <functional>
13 #include <map>
14 #include <set> 
15 #include <cctype>
16  
17 using namespace std;
18 using namespace std::placeholders;
19 
20 int main()
21 {
22     vector<pair<string, int>> vec;
23     pair<string, int> pa;
24     string ss;
25     int i;
26     while (cin >> ss >> i) {
27         pa.first = ss;
28         pa.second = i;
29         vec.push_back(pa);
30     }
31     for (auto &i : vec) {
32         cout << i.first << " " << i.second << endl;
33     }
34     return 0;
35 }

View Code

11.13

 1 #include <iostream>
 2 #include <fstream>
 3 #include <iterator>
 4 #include <vector> 
 5 #include <string>
 6 #include <deque>
 7 #include <list> 
 8 #include <forward_list>
 9 #include <stack>
10 #include <queue>
11 #include <algorithm> 
12 #include <functional>
13 #include <map>
14 #include <set> 
15 #include <cctype>
16  
17 using namespace std;
18 using namespace std::placeholders;
19 
20 void func1()
21 {
22     vector<pair<string, int>> vec;
23     pair<string, int> pa;
24     string ss;
25     int i;
26     while (cin >> ss >> i) {
27         pa.first = ss;
28         pa.second = i;
29         vec.push_back(pa);
30     }    
31 }
32 
33 void func2()
34 {
35     vector<pair<string, int>> vec;
36     string ss;
37     int i;
38     while (cin >> ss >> i) {
39         pair<string, int> pa(ss, i);
40         vec.push_back(pa);
41     }
42 }
43 
44 void func3()
45 {
46     vector<pair<string, int>> vec;
47     string ss;
48     int i;
49     while (cin >> ss >> i) {
50         pair<string, int> pa = {ss, i};
51         vec.push_back(pa);
52     }
53 }
54 
55 void func4()
56 {
57     vector<pair<string, int>> vec;
58     string ss;
59     int i;
60     while (cin >> ss >> i) {
61         pair<string, int> pa{ss, i};
62         vec.push_back(pa);
63     }
64 }
65 
66 int main()
67 {
68     func1();
69     func2();
70     func3();
71     func4();
72     return 0;
73 }

View Code

11.14

 1 #include <iostream>
 2 #include <fstream>
 3 #include <iterator>
 4 #include <vector> 
 5 #include <string>
 6 #include <deque>
 7 #include <list> 
 8 #include <forward_list>
 9 #include <stack>
10 #include <queue>
11 #include <algorithm> 
12 #include <functional>
13 #include <map>
14 #include <set> 
15 #include <cctype>
16  
17 using namespace std;
18 using namespace std::placeholders;
19 
20 int main()
21 {
22        map<string, vector<pair<string, string>>> imap;
23        string name1, name2, birthday;
24        while (cin >> name1) {
25            cin >> name2 >> birthday;
26            pair<string, string> pa(name2, birthday);
27            imap[name1].push_back(pa);
28        }
29        for (auto &i : imap) {
30            for (auto &j : i.second) {
31                cout << i.first << " " << j.first << " " << j.second << endl;
32            }
33            cout << endl;
34        }
35     return 0;
36 }

View Code

11.15

mapped_type：vector<int>

key_type：int

value_type：pair<int, vector<int>>

11.16

    map<string, int> imap = {{"cat", 2}, {"demo", 3}};
	map<string, int>::iterator map_it = imap.begin();
	int a = map_it->second; 
	cout << a << endl;

11.17

第二个错误，因为关联容器不支持push_back()

11.18

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

11.19

多个方法：

	//way1
	bool (*pf)(const Sales_data &, const Sales_data &) = compareIsbn;
	multiset<Sales_data, pf> bookstore(compareIsbn); 
	multiset<Sales_data, pf>::iterator it = bookstore.begin();
	//way2
	multiset<Sales_data, bool(*)(const Sales_data &, const Sales_data &)> bookstore(compareIsbn);  
	multiset<Sales_data, bool(*)(const Sales_data &, const Sales_data &)>::iterator it = bookstore.begin(); 
    //way3
    using compareType = bool (*)(const Sales_data &lhs, const Sales_data &rhs);  
	multiset<Sales_data, compareType> bookstore(compareIsbn);  
	multiset<Sales_data, compareType>::iterator it = bookstore.begin();

11.20

 1 #include <iostream>
 2 #include <fstream>
 3 #include <iterator>
 4 #include <vector> 
 5 #include <string>
 6 #include <deque>
 7 #include <list> 
 8 #include <forward_list>
 9 #include <array>
10 #include <stack>
11 #include <queue>
12 #include <algorithm> 
13 #include <functional>
14 #include <map>
15 #include <set> 
16 #include <cctype>
17  
18 using namespace std;
19 using namespace std::placeholders;
20 
21 int main()
22 {
23     map<string, size_t> imap;
24     string word;
25     while (cin >> word) {
26         //retPair的类型为pair<map<string, size_t>::iterator, bool>
27         //如果imap中存在关键字为word的元素，则insert什么也不做 
28         auto retPair = imap.insert(make_pair(word, 1));
29         if (retPair.second == false)
30             ++retPair.first->second;
31     }
32     return 0;
33 }

View Code

显然下标运算符那个版本更容易编写，因为map的下标运算符可以：①若map中无对应元素，下标运算符可以插入该元素到map中；②若map中有对应元素，则由于下标运算符返回一个左值，故可以将map的mapped_type对象自加。

11.21

word_count.insert({word, 0})：返回一个pair<map<string, size_t>::iterator, bool>，即向word_count中插入一个pair<word, 0>（含有该关键字的元素已存在的话就不做任何事情）；
然后解引用该元素（即map<string, size_t>::iterator->），得到word_count中的pair<word, 0>或pair<word, n>（对应已存在的情况），再将第二成员的值自加。

　　综上：作用是单词计数（尚未存在于map中的单词记录其中且其计数器初始化为1，已存在的仅仅将其计数器加一）

11.22

	map<string, vector<int>> imap;
	string word;
	vector<int> vec;
	//参数类型以及返回类型 
	pair<map<string, vector<int>>::iterator, bool> retPair = imap.insert(make_pair(word, vec));

参数类型：make_pair(word, vec)

返回类型：pair<map<string, vector<int>>::iterator, bool>

11.23

 1 #include <iostream>
 2 #include <fstream>
 3 #include <iterator>
 4 #include <vector> 
 5 #include <string>
 6 #include <deque>
 7 #include <list> 
 8 #include <forward_list>
 9 #include <array>
10 #include <stack>
11 #include <queue>
12 #include <algorithm> 
13 #include <functional>
14 #include <map>
15 #include <set> 
16 #include <cctype>
17  
18 using namespace std;
19 using namespace std::placeholders;
20 
21 int main()
22 {
23     multimap<string, string> mimap;
24     string name1, name2;
25     while (cin >> name1 >> name2)
26         mimap.insert(make_pair(name1, name2));
27     for (auto &i : mimap)
28         cout << i.first << " " << i.second << endl;
29     return 0;
30 }

View Code

11.24

插入元素pair<0, 1>到 m 中

11.25

v是一个空容器，vector的下标运算符不可以插入元素，故本题是对一个未知的内存空间赋值，会导致运行时错误；

而map的下标运算符支持插入元素，故上题是可行的。

11.26

用什么类型来对一个 map 进行下标操作：key_type

下标运算符返回的类型：mapped_type

	map<string, vector<int>> imap;
	vector<int> vec = {65, 66, 67, 68, 69};
	string s = "A-E's ASCII";
	imap[s] = vec;		//第一个类型的实例是s，第二个类型的实例是vec

11.27

使用count：统计容器中关键字等于 k 的元素的数量，大多用于multimap或multiset

使用find：查找某个元素是否在容器中

11.28

	map<string, vector<int>> imap;
	string s;
	map<string, vector<int>>::iterator it = imap.find(s);

11.29

如果给定的关键字不在容器中，

upper_bound：返回一个迭代器，该迭代器指向一个不影响容器中元素顺序的关键字插入位置（但不插入）

lower_bound：返回一个迭代器，该迭代器指向一个不影响排序的关键字插入位置（但不插入）

equal_range：返回一个迭代器pair，该pair中的两个迭代器都指向关键字可以插入的位置（但不插入）

11.30

pos.first：pos为一个pair<multimap<string, string>::iterator, multimap<string, string>::iterator>，故得到pair的第一个成员，是一个multimap迭代器，指向第一个匹配的元素；

pos.first->：解引用此迭代器，提取multimap中的元素，该元素是一个pair<string, string>；

pos.first->second：multimap中元素的题目部分

11.31

 1 #include <iostream>
 2 #include <fstream>
 3 #include <iterator>
 4 #include <vector> 
 5 #include <string>
 6 #include <deque>
 7 #include <list> 
 8 #include <forward_list>
 9 #include <array>
10 #include <stack>
11 #include <queue>
12 #include <algorithm> 
13 #include <functional>
14 #include <map>
15 #include <set> 
16 #include <cctype>
17  
18 using namespace std;
19 using namespace std::placeholders;
20 
21 int main()
22 {
23     multimap<string, string> mimap;
24     string name1, name2;
25     while (cin >> name1) {
26         if (name1 == "eof") 
27             break;
28         cin >> name2;
29         mimap.insert(make_pair(name1, name2));
30     }
31     cout << "请输入要删除作品的作者：";
32     cin >> name1;
33     auto it = mimap.find(name1);
34     if (it != mimap.end()) {
35         cout << "请输入要删除的作品名：";
36         cin >> name2;
37         auto mit = mimap.upper_bound(name1);
38         while (it != mit) {
39             if (it->second == name2) {
40                 mimap.erase(it);
41                 --it;
42                 break;
43             }
44             ++it;
45         } 
46         if (it == mit)    cout << "该作者没有此书！
";
47         else {
48             for (auto &i : mimap) {
49                 cout << "作者：" << i.first << " 书名：" <<  i.second << endl; 
50             }
51         }
52     }
53     else {
54         cout << "查无此作者！
";
55     }
56     return 0;
57 }

View Code

11.32

 1 #include <iostream>
 2 #include <fstream>
 3 #include <iterator>
 4 #include <vector> 
 5 #include <string>
 6 #include <deque>
 7 #include <list> 
 8 #include <forward_list>
 9 #include <array>
10 #include <stack>
11 #include <queue>
12 #include <algorithm> 
13 #include <functional>
14 #include <map>
15 #include <set> 
16 #include <cctype>
17  
18 using namespace std;
19 using namespace std::placeholders;
20 
21 int main()
22 {
23     multimap<string, string> mimap;
24     string name1, name2;
25     while (cin >> name1) {
26         if (name1 == "eof") 
27             break;
28         cin >> name2;
29         mimap.insert(make_pair(name1, name2));
30     }
31     for (auto &i : mimap)
32         cout << "作者：" << i.first << " 书名：" <<  i.second << endl; 
33     return 0;
34 }

View Code

11.33

 1 #include <iostream>
 2 #include <fstream>
 3 #include <sstream>
 4 #include <iterator>
 5 #include <vector> 
 6 #include <string>
 7 #include <deque>
 8 #include <list> 
 9 #include <forward_list>
10 #include <array>
11 #include <stack>
12 #include <queue>
13 #include <algorithm> 
14 #include <functional>
15 #include <map>
16 #include <set> 
17 #include <cctype>
18  
19 using namespace std;
20 using namespace std::placeholders;
21 
22 const string &transform(const string &s, const map<string, string> &imap)
23 {
24     auto it = imap.find(s);
25     if (it != imap.end()) {
26         return it->second;
27     }
28     else
29         return s;
30 }
31 
32 void word_transform(ifstream &rin, ifstream &tin)
33 {
34     map<string, string> imap;
35     string s1, s2;
36     while (rin >> s1 && getline(rin, s2)) {
37         s2 = s2.substr(1);
38         imap.insert(make_pair(s1, s2));
39     }
40     string word, line;
41     while (getline(tin, line)) {
42         istringstream in(line);
43         bool space = false;
44         while (in >> word) {
45             if (!space)
46                 space = true;
47             else 
48                 cout << " ";
49             cout << transform(word, imap);
50         }
51         cout << endl;
52     }
53 }
54 
55 int main()
56 {
57     ifstream rin("map_file.txt"), tin("data.txt");
58     word_transform(rin, tin);  
59     return 0;
60 }

View Code

11.34

传递的map对象是const的，而下标运算可能会在map中插入新元素，这与形参相悖；此外，用下标运算或者返回指定关键字对应的值（即mapped_type），或者添加一个指定关键字的元素（并对其进行值初始化），那么如果是添加元素的话，结果是返回空串，这与目的相悖。

const string &transform(const string &s, map<string, string> &imap)
{	
	//下标返回一个mapped_type对象 
	string transAfter = imap[s];
	//若插入元素的话，会返回空串 
	return imap[s];
}

11.35

给map对象添加元素时，如果其中已存在与欲添加元素具有相同关键字的元素，那么编译器将忽略此次添加操作。

11.36

当只有一个关键字和空格时：key会读取关键字，这一行只剩下空格可以读取到value中；因此value只有一个空格，即size为1，从而 if 条件不成立，转交给 else，所以会触发异常：throw runtime_error("no rule for "+key);

11.37

与有序容器相比的优势：关键字类型不必要有明显的排序关系，而且省去了维护元素的序代价；

有序容器的优势：元素有序排放

11.38

单词计数：

int main()
{
    unordered_map<string, int> umap;
    string word;
    while (cin >> word) {
    	++umap[word];
    }
	return 0;
}

单词转换：

#include <iostream>
#include <fstream>
#include <sstream>
#include <iterator>
#include <vector> 
#include <string>
#include <deque>
#include <list> 
#include <forward_list>
#include <array>
#include <stack>
#include <queue>
#include <algorithm> 
#include <functional>
#include <map>
#include <set> 
#include <cctype>
#include <unordered_map>
#include <unordered_set>
 
using namespace std;
using namespace std::placeholders;

const string &transform(const string &s, const unordered_map<string, string> &imap)	//修改处2 
{
	auto it = imap.find(s);
	if (it != imap.end()) {
		return it->second;
	}
	else
		return s;
}

void word_transform(ifstream &rin, ifstream &tin)
{
	unordered_map<string, string> imap;	//修改处1 
	string s1, s2;
	while (rin >> s1 && getline(rin, s2)) {
		s2 = s2.substr(1);
		imap.insert(make_pair(s1, s2));
	}
	string word, line;
	while (getline(tin, line)) {
		istringstream in(line);
		bool space = false;
		while (in >> word) {
			if (!space)
				space = true;
			else 
				cout << " ";
			cout << transform(word, imap);
		}
		cout << endl;
	}
}

int main()
{
	ifstream rin("map_file.txt"), tin("data.txt");
	word_transform(rin, tin);  
	return 0;
}

第十一章 关联容器

第十一章关联容器