1、关联容器概述
1.1、什么是关联容器？
关联容器描述了对应关系，这种关系可以是一对一、一对多等等。它们和顺序容器不一样的地方在于，顺序容器以“位置”作为元素检索的依据，而关联容器则是以关键字作为元素检索的依据。
1.2、有哪些关联容器？
标准库提供了八种关联容器，分别如下所示：
这八种容器主要有以下三种分类：
（1）要么是无序组织的容器（哈希）、要么是有序组织的容器（红黑树）
（2）要么以键值对为元素（map）、要么以键为元素（set）
（3）要么键只允许出现一次、要么键可以出现多此（multi-）
1.3、相关头文件
2、关联容器的使用方法和设计思想
2.1、什么情况下用map，什么情况用set？
什么情况要用关联容器
先看看大家熟悉的数据结构：数组，数组其实也可以描述成一种键值对结构，因为它是一种： i n d e x → a r r [ i n d e x ] index→arr[index] index→arr[index]的映射结构，只是这种映射收到了很多的限制，比如：
（1）、
i
n
d
e
x
index
index必须是非负整数
（2）、
a
r
r
[
i
n
d
e
x
]
arr[index]
arr[index]的查找不一定很方便
可能有的同学会对（2）有疑惑：“难道随机访问不是 O ( 1 ) O(1) O(1)的吗？”，在数组里当然是 O ( 1 ) O(1) O(1)的！但是，如若 i n d e x index index不是非负整数，而是其他数据类型，此时如果我们还想用顺序容器去存储，是不是该用 v e c t o r vector vector或者 l i s t list list去存储呢？那此时的插入和删除是不是开销较大呢？是不是不方便呢？
什么情况要用map
而
m
a
p
map
map的底层数据结构的红黑树，插入、查找的复杂度都是
O
(
l
o
g
n
)
O(logn)
O(logn)，这是极其方便快捷的！而且
m
a
p
map
map可以轻松描述一些映射关系，比如我需要做一个“姓名-电话”的映射表，则只需要声明一个
m
a
p
<
s
t
r
i
n
g
,
s
t
r
i
n
g
>
n
a
m
e
T
o
P
h
o
n
e
map<string,string> nameToPhone
map<string,string>nameToPhone
的数据结构即可！
什么情况要用set
那么什么时候用
s
e
t
set
set呢？当我们只需要判断某种关键字是否存在于某个集合的时候，就是用
s
e
t
set
set最佳的时候！譬如说我们在交易之前要先判断某个人是否在失信名单里，我们就设一个数据结构：
s
e
t
<
s
t
r
i
n
g
>
b
a
d
C
h
e
c
k
e
r
set<string> badChecker
set<string>badChecker
就可以了！
2.2、map和set的编程实例
程序1：统计各个单词出现的次数（普通版）
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main() {
map<string, int> wordCount;
string word;
while (cin >> word) {
++wordCount[word];
}
for (auto wordCnt : wordCount) {
cout << wordCnt.first << "\t occurs \t" << wordCnt.second
<< (wordCnt.second > 1 ? " times." : " time.") << endl;
}
return 0;
}
运行的效果是：
从程序1可以学到什么？
我们可以发现，关联容器的每个关键字（此处是string）都是按照字典序，顺序排放的！为什么是这样呢？因为红黑树本身是一种平衡搜索树，根据搜索树的中序遍历，键就是顺序存储的，并且是唯一顺序存储的！
如果新进入的字符串 w o r d word word不在 w o r d C o u n t wordCount wordCount中， w o r d C o u n t wordCount wordCount会新建一组键值对，以 w o r d word word为key，以0为value。这告诉我们，如果我们需要在键不存在的时候新建一个键，则 m a p map map重载的 [ ] [] []运算符就很值得使用！但是，如果我们是为了查看键是否存在，就千万别这样用了！因为它会默认地新建一组键值对给你，这将会给你带来意想不到的困扰！
从 m a p map map中提取处来的对象，是 p a i r pair pair数据类型的，它是一种默认以 f i r s t first first为关键字的，重载了 < < <运算符的类，这种类是可以作为 m a p map map的key的！
程序2：忽略停用词，作单词计数
什么是停用词？譬如“and”、“or”、"i"一类的没有什么作用的词，称之为“停用词”！停用词的概念在自然语义分析中有较大的作用，我们来设计程序在忽略停用词的情况下对单词进行计数：
#include <iostream>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
int main() {
const set<string> exclude = {"and", "i", "or", "but", "is", "a", "an", ",", "."};
map<string, int> wordCount;
string word;
while (cin >> word) {
if (exclude.find(word) == exclude.end()) {
++wordCount[word];
}
}
for (auto it : wordCount) {
cout << it.first << "\toccurs\t" << it.second << (it.second > 1 ? " times." : " time.") << endl;
}
return 0;
}
程序运行的效果是：
英语水平不高，请不要见怪~
从程序2我们能学到什么？
关联容器的查找方法，在查找不到的时候返回 e n d ( ) end() end()迭代器，无论是 m a p map map还是 s e t set set都是这样的！
用《C++ primer》书中的原话，就是：
2.3、本小节练习题和参考代码
练习1：描述map和vector的不同
1、map是关联数组，vector是顺序数组。
2、map的关键字可以是任何重载了 < < <运算符的类，对应的值value可以是任意的类。而vector的关键字只能是非负整数，而存储的类型可以是任何类。
3、vector支持随机访问，访问时间开销是 O ( 1 ) O(1) O(1)，插入的开销很大是 O ( n ) O(n) O(n)。但是map的底层数据结构是红黑树，访问时间和插入时间都是 O ( l o g n ) O(logn) O(logn)
练习2：分别给出最适合使用list、vector、deque、map以及set的例子
1、list是循环双向链表的底层结构，如链表那般，适合于插入、删除频繁、查找不频繁的应用场景。比如一个客户流动账本，这个账本一年只在某半个月或一个月进行查账，其他时间只进行记账，这样的情况就适合用链表。
2、vector就是顺序表，和list相反。
3、deque是双端队列，一般的队列是头进尾出，而双端队列是两边都可以进出，适合于“滑动窗口的问题”。
4、map和set我们之前有讨论，就不展开说了。
练习4（练习3同程序1、2）：扩展程序、忽略大小写和标点符号，实现新的单词统计程序
#include <iostream>
#include <map>
#include <cctype>
#include <algorithm>
using namespace std;
void process(string& str) {
for (char& cur : str) {
if (cur >= 'A' && cur <= 'Z') {
cur = cur + 32;
}
}
if (!isalpha(str[str.length() - 1])) {
str.pop_back();
}
}
int main() {
map<string, int> wordCount;
string word;
while (cin >> word) {
process(word);
++wordCount[word];
}
for (auto it : wordCount) {
cout << it.first << "\t\t\toccurs\t\t" << it.second << (it.second > 1 ? " times." : " time.") << endl;
}
return 0;
}
程序运行的效果是：
3、关联容器的简单操作
3.1、map和set的列表初始化
先看代码：
#include <iostream>
#include <map>
#include <set>
using namespace std;
int main() {
set<string> strSet = {
"hello", "world", "love", "function",
"aaaa", "bbbb", "cccc", "dddd", "love"
};
map<string, int> strMap = {
{"hello", 1}, {"world", 2},
{"aaaa", 3}, {"bbbb", 5}, {"bbbb", 4}
};
cout << "----------------set-----------------" << endl;
for (auto it : strSet) {
cout << it << endl;
}
cout << "----------------map-----------------" << endl;
for (auto it : strMap) {
cout << it.first << "\t\t" << it.second << endl;
}
return 0;
}
这份代码运行出来的结果是：
从中我们可以看到两点：
（1）、无论是set还是map，只要是基于红黑树的结构，都不允许有重复的关键字出现
（2）、如果出现了重复的关键字，例如map的初始化有重复的：
{"bbbb", 5}, {"bbbb", 4}
这个时候运行的结果是5而不是4，这也是和红黑树有关的，当我们已经插入了第一个值为5的元素后，再去插入值为4的元素的时候就会检测出"bbbb"这个键已经存在！不允许再插入了！所以就只会保留第一个！
3.2、初始化multimap和multiset
在map和set中，关键字必须是唯一存在的，不允许有多个元素共用一个关键字，但是实际应用真的是这样的吗？
比如在字典中，一个字可能存在多种含义，我们如何记录这样的字典呢？这就需要multimap去解决！
我们下面的程序是对set和multiset进行拷贝初始化：
#include <iostream>
#include <set>
#include <vector>
using namespace std;
int main() {
vector<int> ivec;
for (int i = 0; i < 10; ++i) {
ivec.push_back(i);
ivec.push_back(i);
}
set<int> iset(ivec.cbegin(), ivec.cend());
multiset<int> mitset(ivec.cbegin(), ivec.cend());
cout << "set size = " << iset.size() << endl;
cout << "multiset size = " << mitset.size() << endl;
return 0;
}
程序运行的结果是：
可以直观发现，set进行了去重而multiset不会去重！
3.3、multimap和multiset的一些操作对比
（1）、是否还有序呢？
#include <iostream>
#include <set>
#include <vector>
using namespace std;
int main() {
vector<int> ivec;
for (int i = 0; i < 5; ++i) {
ivec.push_back(i);
ivec.push_back(5 - i - 1);
}
multiset<int> mitset(ivec.cbegin(), ivec.cend());
for (auto it : mitset) {
cout << it << endl;
}
return 0;
}
这份代码的插入顺序是[0, 4, 1, 3, 2, 2, 3, 1, 4, 0]，输出的结果是：
从此可以看出，multiset的键也是字典序排序的！
然后再看看multimap是否也是这样呢？
#include <iostream>
#include <map>
using namespace std;
int main() {
multimap<char, int> mitmap;
for (int i = 0; i < 5; ++i) {
mitmap.insert({'0' + 5 - i - 1, i + 1});
mitmap.insert({'0' + 5 - i - 1, i});
}
for (auto it : mitmap) {
cout << it.first << "\t\t" << it.second << endl;
}
return 0;
}
这个程序运行的效果是：
可以发现也是这样的！无论是一对一映射，还是一对多映射，都是让关键字按照字典序从小到大排序！
（2）如何进行元素的查找？
equal_range(foundVal)进行范围查找
这个equal_range()会返回一个pair对象，这个对象的first代表找到的第一个元素的迭代器，而second表示找到结束符的迭代器！用法如下：
#include <iostream>
#include <map>
using namespace std;
int main() {
multimap<char, int> mitmap;
for (int i = 0; i < 5; ++i) {
mitmap.insert({'0' + 5 - i - 1, i + 1});
mitmap.insert({'0' + 5 - i - 1, i});
}
auto ptr = mitmap.equal_range('1');
if (ptr.first != end(mitmap)) {
for (auto it = ptr.first; ptr.second != it; ++it) {
cout << it->first << "\t\t" << it->second << endl;
}
}
return 0;
}
这个程序是查找关键字为’1’的所有元素，如果找不到将返回multimap对象的结束符迭代器，也就是：end(mitmap)，然后要注意的是，找到的结果不是值而是元素的迭代器指针所以需要用指针的方式去访问对应的值。运行的结果是：
其他也有一些查找方式，比如find()只能查找第一个被找到的元素（或者是尾迭代器），而lower_bound()找到于关键字相同的或者是大于它的第一个元素！而upper_bound()只能找到第一个大于它的元素！这些，尤其是find()感觉在特定场合下可以用，然后lower和upper和二分查找那种相似，感觉应用面不广就不些详细的实验代码了。
4、对关键字类型的要求（核心）
4.1、在C/C++混合编程的时候，以结构体定义的类型作为关键字
以结构体作为关键字的时候，虽然说在结构体里也能写函数，但是秉承这种C风格我们最好是把比较的函数写在外面，会更加契合C风格程序员的编程习惯，我写了一个示例代码：
#include <iostream>
#include <map>
#include <string>
using namespace std;
struct Student {
string name;
string stuId;
int score;
};
bool compWithStudent(const Student& s1, const Student& s2) {
if(s1.score != s2.score) {
return s1.score > s2.score;
}
return s1.stuId < s2.stuId;
}
char getLevelOfStu(int curScore) {
if (curScore >= 80) {
return 'A';
}
else if(curScore >= 60) {
return 'B';
}
else {
return 'C';
}
}
int main() {
map<Student, char, decltype(compWithStudent)* > mpToLevel(compWithStudent);
string name, stuId;
int score;
while (cin >> name >> stuId >> score) {
mpToLevel[{name, stuId, score}] = getLevelOfStu(score);
}
for (auto curStu : mpToLevel) {
cout << curStu.first.name << "\t\t" << curStu.second << endl;
}
return 0;
}
这个程序运行的结果是：
我觉得还是挺好用的，作为一名ACMer，常用比较函数的函数指针去指导排序的规则，所以这种做法我认为会比较收到ACMer的欢迎~
在这个程序中，最核心的就是map实例的声明：
map<Type_Key, Type_Value, decltype(funcName)* > instance(funcName)
这里需要注意的是，在decltype进行类型推导后，只是推出了函数的类型，但是传参需要传递的是函数的指针，所以需要加上指针说明符“ * ”！
4.2、重载<运算符的方法，实现自定义关键字类型
#include <iostream>
#include <map>
#include <string>
using namespace std;
class Student {
private:
string name;
int score;
public:
Student(string name, int score) {
this->name = name;
this->score = score;
}
bool operator<(const Student& s) const {
if (score != s.score) {
return score > s.score;
}
return name < s.name;
}
string getterName() const {
return name;
}
};
char getLevelOfStu(int score) {
if (score >= 90) {
return 'A';
}
else if (score >= 60) {
return 'B';
}
else {
return 'C';
}
}
int main() {
string name;
int score;
map<Student, char> mpToLevel;
while (cin >> name >> score) {
mpToLevel[Student(name, score)] = getLevelOfStu(score);
}
for (auto it : mpToLevel) {
cout << it.first.getterName() << "\t\t" << it.second << endl;
}
return 0;
}
程序运行的结果是：
这里值得注意的是，在重载<运算符的时候，参数是右操作数，而调用这个函数的实例（也就是this指针指向的实例）是左操作数！
4.3、利用仿函数设计自定义关键字类型
#include <iostream>
#include <map>
using namespace std;
struct Student {
string name;
int score;
};
struct Functor {
bool operator() (const Student& s1, const Student& s2) const {
if(s1.score != s2.score) {
return s1.score > s2.score;
}
return s1.name < s2.name;
}
};
char getLevelOfStu(int curScore) {
if (curScore >= 80) {
return 'A';
}
else if(curScore >= 60) {
return 'B';
}
else {
return 'C';
}
}
int main() {
map<Student, char, Functor> mpToLevel;
string name;
int score;
while (cin >> name >> score) {
mpToLevel[{name, score}] = getLevelOfStu(score);
}
for (auto it : mpToLevel) {
cout << it.first.name << "\t\t" << it.second << endl;
}
return 0;
}
程序运行的结果：
这个仿函数比最开始的函数指针更好，我觉得函数指针是仿函数的底层，对仿函数我还不太理解，我再查查资料。
经过我的了解：
仿函数是一种能够行使函数功能的类，作为仿函数的类必须要重载()运算符，因为调用仿函数就是在调用重载的()运算符函数。
################引用#################
如果编程者要将某种“操作”当做算法的参数，一般有两种方法：
（1）一个办法就是先将该“操作”设计为一个函数，再将函数指针当做算法的一个参数。上面的实例就是该做法；
（2）将该“操作”设计为一个仿函数（就语言层面而言是个 class），再以该仿函数产生一个对象，并以此对象作为算法的一个参数。
很明显第二种方法会更优秀，因为第一种方法扩展性较差，当函数参数有所变化，则无法兼容旧的代码。
################引用#################
参考文：C++ 仿函数
5、Pair模板类
5.1、pair的基本操作
从这里可以看到，pair重载了比较运算符，因此pair能够成为map的关键字！在排序的时候也一样，pair的对象以第一个关键字first作为主要排序依据，而second则是副排序依据。
5.2、pair的编程练习
第三题需要改进的代码是下面这个题：
第一题：
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
int main() {
string str;
int i;
vector<pair<string, int> > vec;
while (cin >> str >> i) {
vec.push_back({str, i});
}
for (auto i : vec) {
cout << i.first << '\t' << i.second << endl;
}
return 0;
}
程序运行的结果：
第二题：
我认为，花括号{first, second}的方法创建pair是最好的！
第三题：
用multimap的方法编程：
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
int main() {
multimap<string, pair<string, string> > mpOfSon;
string firstName, secondName, birthday;
while (cin >> firstName >> secondName >> birthday) {
mpOfSon.insert({firstName, {secondName, birthday}});
}
for (auto home : mpOfSon) {
cout << "Home firstname : " << home.first << "\t"
<< " secondname : " << home.second.first << "\t"
<< " birthday : " << home.second.second << endl;
}
return 0;
}
程序运行的效果：
用vector的话也很简单，效果和用multimap是一样的，但是问题就来了，到底是用vector来表示value还是用multimap去处理？这两者哪样会比较好？？
个人觉得，用multimap会好，我觉得这是显然的事情，因为value存vector，在某些时候还需要去vector遍历访问、查找、修改等操作。
6、无序容器
无序容器不是通过比较运算符来组织元素，而是使用哈希函数和关键字类型的==运算符来管理元素。这和Java程序中的HashMap或者HashSet一样，需要重写hashcode和equals方法！
在某些场景下，维护有序的代价也很高，此时是使用无序容器的好时候！
6.1、无序容器对关键字数据类型的要求（核心）
在向无序容器插入元素的时候，需要先计算哈希，如果哈希值不相同则肯定无重复！如果哈希值相同也可能出现哈希冲突，再利用重载的==运算符去判断是否相同，如果不相同则无重复，此时就可以放心插入！
所以在自定义数据类型作为无序容器的key的时候，就需要重写哈希函数和==运算符。
看看模板算法hash函数：
用仿函数写一个支持无序容器的自定义关键字：
#include <iostream>
#include <unordered_map>
using namespace std;
struct Student {
string name;
int score;
bool operator== (const Student& s) const {
return (name == s.name) && (score == s.score);
}
};
struct hashcode {
bool operator() (const Student& s) const {
return hash<string>()(s.name) ^ hash<int>()(s.score);
}
};
char getLevelOfStu(int curScore) {
if (curScore >= 80) {
return 'A';
}
else if(curScore >= 60) {
return 'B';
}
else {
return 'C';
}
}
int main() {
unordered_map<Student, char, hashcode> mpToLevel;
string name;
int score;
while (cin >> name >> score) {
mpToLevel[{name, score}] = getLevelOfStu(score);
}
for (auto it : mpToLevel) {
cout << it.first.name << "\t\t" << it.second << endl;
}
return 0;
}
程序运行的效果如下：
就会发现这样立马就无序了！