C++Primer 5th：第十一章 关联容器

本文最后更新于：2020年7月12日 上午

第十一章 关联容器

  • 类型map和multimap定义在头文件map中
  • set和multiset定义在头文件set中
  • 无序容器定义在头文件unorderd_map和unorderd_set中

11.1 使用关联容器

  1. 使用map
    • 关键字-值对的集合
    • 关联数组（associative array）
1
2
3
4
5
6
7
8
//统计每个单词在输入中出现的次数
map<string, size_t> word_count;
string word;
while (cin >> word)
	++word_count[word];
for (const auto &w : word_count)
	cout << w.first << " occures " << w.second
		<< ((w.second > 1) ? " times" : " time") << endl;
  1. 使用set
    • 使用set保存想忽略的单词，只对不在集合中的单词统计出现次数
1
2
3
4
5
6
7
map<string, size_t> word_count;
set<string> exclude = {"The", "But", "And", "Or", "An", "A",
                      "the", "but", "and", "or", "an", "a"};
string word;
while(cin >> word)
    if(exclude.find(word) == exclude.end())
        ++word_count[word];

11.2 关联容器概述

11.2.1 定义关联容器

  1. 初始化multimap或multiset
    • 允许多个元素具有相同的关键字
1
2
3
4
5
6
7
8
9
10
vector<int> ivec;
for (vector<int>::size_type i = 0; i != 10; ++i) {
	ivec.push_back(i);
	ivec.push_back(i);
}
set<int> iset(ivec.cbegin(), ivec.cend());
multiset<int> miset(ivec.cbegin(), ivec.cend());
cout << ivec.size() << endl;	//20
cout << iset.size() << endl;	//10
cout << miset.size() << endl;	//20

11.2.2 关键字类型的要求

  • 对于有序容器map, multimap, set以及multiset，关键字类型必须定义元素比较的方法。

11.2.3 pair类型

  • 头文件：utility
  • pair的数据成员是：public的
  • 两个成员分别命名为first和second
1
pair<string, string> author{"James", "Joyce"};
  1. 创建pair对象的函数
1
2
3
4
5
6
7
8
pair<string, int> process(vector<string> &v){
    if(!v.empty())
        return {v.back(), v.back().size()};
    	//或者使用如下形式
    	//return make_pair(v.back(), v.back().size());
    else
        return pair<string, int>();
}

11.3 关联容器操作

key_type

  • 此容器类型的关键字类型

mapped_type

  • 每个关键字关联的类型；只适用于map

value_type

  • 对于set，与key_type相同
  • 对于map，为pair<const key_type, mapped_type>

11.3.1 关联容器迭代器

  1. map
1
2
3
4
5
6
7
8
map<string, size_t> word_count;
auto map_it = word_count.begin();
// *map_it 是指向一个pair<const string, size_t>对象的引用
cout << map_it->first;			//打印此元素的关键字
cout << " " << map_it->second;	//打印此元素的值
//错误：关键字是const的
//map_it->first = "new key";
++map_it->second;
  1. set 的迭代器是 const 的
1
2
3
4
5
6
set<int> iset = { 0,1,2,3,4,5,6,7,8,9 };
set<int>::iterator set_it = iset.begin();
if (set_it != iset.end()) {
	//*set_it = 42;	//错误：set 中的关键字是只读的
	cout << *set_it << endl;
}
  1. 遍历关联容器
1
2
3
4
5
6
7
map<string, size_t> word_count;
auto map_it = word_count.cbegin();
while (map_it != word_count.cend()){
	cout << map_it->first << " occurs "
		<< map_it->second << " times" << endl;
	++map_it;
}
  1. 在实际编程中，如果真要对一个关联容器使用算法，要么将它当作一个源序列，要么当作一个目的位置。

11.3.2 添加元素

  1. 向map添加元素
1
2
3
4
5
map<string, size_t> word_count;
word_count.insert({ "word", 1 });
word_count.insert(make_pair("word", 1));
word_count.insert(pair<string, int>("word", 1));
word_count.insert(map<string, int>::value_type("word", 1));
  1. 检测insert的返回值
  • 对于不包含重复关键字的容器，添加单一元素的insert返回一个pair
  • pair的first成员是一个迭代器，指向具有给定关键字的元素
  • second成员是一个bool值
  1. 向multiset或multimap添加元素
1
2
3
multimap<string, string> authors;
authors.insert({"Barth, John", "Sot-weed Factor"});
authors.insert({"Barth, John","Lost in the Funhouse"});

11.3.3 删除元素

1
2
3
4
5
6
7
// 从c中删除每个关键字为K的元素
//返回一个size_type值，指出删除的元素的数量
c.earse(k);
//删除迭代器p指定的元素
c.earse(p);
//删除迭代器对b和e所表示的范围中的元素
c.earse(b,e);

11.3.4 map的下标操作

  1. 使用一个不在map容器中的关键字作为下标，会添加一个具有此关键字的元素到map中
1
2
map<string, size_t> word_count;
word_count["Anna"] = 1;
  1. 使用下标操作的返回值
  • map的下标运算符返回的类型与解引用map迭代器得到的类型不同
1
2
3
count << word_count["Anna"];
++word_count["Anna"];
cout << word_count["Anna"];

11.3.5 访问元素

  • 如果不需要计数，最好使用find
1
2
3
4
5
set<int> iset = { 0,1,2,3,4,5,6,7,8,9 };
iset.find(1);	//返回指向key==1的元素的迭代器
iset.find(11);	//返回值等于iset.end()的迭代器
iset.count(1);	//返回1
iset.count(11);	//返回0
  1. 对map使用find代替下标操作
  2. 在multimap或multiset中查找元素
1
2
3
4
5
6
7
8
string search_item("Alain de Botton");		//要查找的作者
auto entries = author.count(search_item);	//元素的数量
auto iter = authors.find(search_item);		//此作者的第一本书
while (entries){
	cout << iter->second << endl;
	++iter;
	--entries;
}
  1. 一种不同的，面向迭代器的解决方案

lower_bound和upper_bound

  • 如果两者返回相同的迭代器，则给定的关键字不在容器中
1
2
3
4
for(auto beg = authors.lower_bound(search_item), end = authors.upper_bound(search_item); 
beg != end; ++beg){
	cout << beg->second << endl;
}
  1. equal_range函数
1
2
3
for(auto pos = authors.equal_range(search_item); pos.first != pos.second; ++pos.first){
	cout << pos->first->second << endl;
}

11.3.6 一个单词转换的 map

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<iostream>
#include<string>

#include<map>

#include<fstream>
#include<sstream>

using namespace std;

map<string, string> buildMap(ifstream& map_file)
{
	map<string, string> 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 map<string, string>& 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)
{
	auto trans_map = buildMap(map_file);	//保存转换规则
	string text;							//保存输入中的每一行
	while (getline(input, 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()
{
	ifstream ifs1, ifs2;
	ifs1.open("map_file.txt");
	ifs2.open("input.txt");

	word_transform(ifs1, ifs2);

	ifs1.close();
	ifs2.close();

	system("pause");
	return 0;
}
  • map_file.txt
1
2
3
4
5
6
7
k okay?
y why
r are
u you
pic picture
thk thanks!
18r later
  • input.txt
1
2
3
where r u
y dont u sent me a pic
k thk 18r

11.4 无序容器

  • 如果关键字类型固有就是无序的，或者性能测试发现问题可以用哈希技术解决，就可以使用无序容器
  1. 使用无序容器
1
2
3
4
5
6
7
8
9
#include<unordered_map>
//统计出现的次数，但单词不会按字典序排列
unordered_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;
  1. 管理桶
  • 无序容器在存储组织上为一组桶，每个桶保存零个或多个元素
  • 无序容器使用一个哈希函数将元素映射到桶
  1. 无序容器对关键字类型的要求
  • 默认情况下，无序容器使用关键字类型的==运算符比较元素
  • 使用一个hash类型的对象来生成每个元素的哈希值
1
2
3
4
5
6
7
8
9
10
11
size_t hasher(const Sales_data &sd)
{
	return hash<string>()(sd.isbn());
}
bool eqOp(const Sales_data &lhs, const Sales_data &rhs)
{
    return lhs.isbn() == rhs.isbn();
}

using SD_multiset = unordered_multiset<Sales_data, decltype(hasher)*, decltype(eqOp)*>;
SD_multiset bookstore(42, hasher, eqOp);