C++Primer第五版第十一章关联容器

11.1 使用关联容器

知识点1：关联容器与顺序容器有着本质的区别，关联容器中的元素是按关键字来保持和访问的。

知识点2：与之相反，顺序容器中的元素是按它们在容器中的位置来顺序保持和访问的。

知识点3：关键词在关联容器中起到重要的作用，map中的元素是（关键字—值）对，关键词是索引左右，值是与索引相关联的数据。set每个元素只包含一个关键字，支持高效的关键词查找。

练习11.1

对于vector这样的顺序容器，元素在其中按照顺序存储，每个元素有唯一对应的位置编号，所有操作都是按编号（位置）进行的。例如，获取元素（头，尾，用下标获取任意位置），插入删除元素（头，尾，任意位置），遍历元素（按元素位置顺序逐一访问）。底层的数据结构是数组，链表，简单但已能保证上述操作的高效。而对于依赖值的元素访问，例如查找（搜索）给定值（find），在这种数据结构上的实现是要通过遍历完成，效率不佳。

而map这种关联容器，就是为了高效实现“按值访问元素”，这类操作而设计的。为了达到这一目的，容器中的元素是按照关键字值储存的，关键字值与元素数据建立起对应关系，这就是“关联”的含义。底层数据结构是红黑树，哈希表等，可高效实现按关键字值查找，添加，删除元素等操作。

练习11.2

map：存储字典型数据

set：坏值检验，只有关键字的好处

list：任意位置任意删除添加数据

deque：信息处理，只在头部

vector：相关联数据，顺序处理

练习11.3

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <sstream>
#include <list>
#include <deque>
#include <forward_list>
#include <algorithm>
#include<numeric>
#include<map>
#include<set>
using namespace std;

int main(int argc,char **argv) {

	
	map<string, size_t> word_count;
	string word;
	while (cin >> word){
		++word_count[word];
	}
	for (const auto &w : word_count){
		cout << w.first << "occurs" << w.second << ((w.second > 1) ? "times" : "time") << endl;
	}
	system("pause");
	return 0;
}

练习11.4

知识点1：头文件：#inlude <cctype.h>，ispunct() 函数用来检测一个字符是否为标点符号或特殊字符，其原型为：int ispunct(int c);

知识点2：目前在头文件iostream中也可以使用，C++ 5.11已证明。把字符转换成小写字母,非字母字符不做出处理用法: int tolower(int c);

#include<iostream>
#include<string>
#include<map>
#include<cctype>  /ctype无法打开，包含tolower()函数和ispunct函数
using namespace std;

void process(string &s) {
	for (auto i = 0;i < s.size(); ++i) {
		if (isupper(s[i])) s[i] = tolower(s[i]);
		else if (ispunct(s[i])) {
			s.erase(i,1);
		}
	}
}

int main() {
	string s;
	map<string, size_t> num;
	cout << "输入单词表：" << endl;
	while (cin >> s) {
		process(s);
		++num[s];
	}
	for (const auto &i : num) {
		cout << i.first << " occurs " << i.second << ((i.second > 1) ? " times" : " time") << endl;
	}

	system("pause");
	return 0;
}

11.2 关联容器的概述

知识点1：关联容器不支持顺序容器的位置相关操作，如push_back等等。

知识点2：关联容器的迭代器都是双向的，还有一些关于哈希性能的操作

知识点3：multimap和multiset允许多个元素具有相同的关键字，所以给multiset和multimap中传入相同的元素，是可行的，而set、map会忽略相同关键字的元素

练习11.5

map和set都是stl中的关联容器，map以键值对的形式存储，key=value组成pair，是一组映射关系。

set只有值，可以认为只有一个数据，并且set中元素不可以重复且自动排序，如果需要重复则使用multiset。

练习11.6

set不可以重复，且自动排序。

练习11.7

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

using namespace std;

int main() {
	map<string, vector<string>> mp;
	string last_name, first_name;
	cout << "输入姓：" << endl;
	cin >> last_name;
	cout << "输入该姓的成员名字：" << endl;
	while (cin >> first_name) {
		mp[last_name].push_back(first_name);
	}
	for (const auto i : mp) {
		cout << "姓：" << i.first << " 有以下成员：" << endl;
		for (const auto j : i.second) {
			cout << j << " ";
		}
		cout << endl;
	}

	system("pause");
	return 0;
}

练习11.8

set会自动忽略重复的关键字

#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;

int main() {
	vector<int> v = { 1,1,2,3,4,4,5,6 };
	auto iter = unique(v.begin(), v.end());
	v.erase(iter, v.end());
	for (auto i : v) {
		cout << i << " ";
	}
	cout << endl;
	system("pause");
	return 0;
}

以后补剩下的。

C++Primer第五版 第十一章 关联容器

C++Primer第五版第十一章关联容器