可以将关联容器的值设置为容器
程序功能：一通过关键字寻找其对应的多个值，这些值被保存在一个链表中，也可以用vector来保存
int main(){ string s = "aa"; map> mp; string words; while(cin >> words) { if(words=="break") break; int a; cin >> a; mp[words].push_back(a); } cout << "请输入要查找的关键字"; cin >> words; auto i = mp.find(words); for(auto x : i->second){ cout << x << " "; } return 0;}
multimap与multiset
再map与set中关键字是唯一的，对于一个给定的关键字，只能有一个元素的关键字等于他。但是这两个容器没有进行限制
pair
在默认构造的情况下会对两个成员分别进行初始化
一些特备的操作
using Pair = pair;Pair func(string & s){ if(!s.empty()) return {s.front(),s.size()}; //用一个二元列表隐式的返回二元组，挺有意思 else return Pair();}
模板类的嵌套
可将pair嵌套在vector中记录东西
程序功能：记录一个人的名字和身高并用二元组包装保存在vector中
int main(){ vector> vec; string s; int a; while(true){ cout << "请输入姓名，输入break退出"; getline(cin,s); if(s == "break") break; cout << "请输入身高"; cin >> a; cin.get(); vec.emplace_back(s,a); } for_each(vec.begin(), vec.end(),[](pair & p){cout << p.first << " " << p.second << endl;}); return 0;}
一些类型
key_type关键字类型
mapped_type map系列独有，与关键字关联的类型
value_type对于set与key_tyep相同，对于map系列为
历遍关联容器
主题set里数据是只读的，要用const修饰参数
int main(){ set s {"hello","world","I","Love","C++","a","b","c"}; for_each(s.begin(), s.end(),[](const string & s) {cout << s << endl;}); return 0;}
向map中添加元素
使用insert方法向map中插入元素，此方法返回一个pair，第一个类型是迭代器，指向关键字对应的元素，第二个类型是bool表示是否插入成狗，若插入成功为true反则为false，插入失败（插入的元素的关键字在map中已经存在）。
int main(){ set s {"hello","world","I","Love","C++","a","b","c"}; map mp; int a= 0; for(const auto& i : s){ ++a; auto p = mp.insert({i,a}); cout << p.first->first << " " << p.first->second << " " << p.second << endl; } //再插入一个hello auto p = mp.insert({"hello",222}); if(p.second) cout << "插入成功"; else cout << "插入失败"; return 0;}
multiset和set则返回一个迭代器，因为其无需判断原先的关联容器中是否已经存在对应得关键字，其关键字是可重复得
程序功能：统计键入得单词出现得次数
int main(){ map mp; string word; while(cin >> word) { if(word == "break") break; auto p = mp.insert({word,1}); if(!p.second) p.first->second++; } for_each(mp.cbegin(), mp.cend(), [](const pair & p){ cout << p.first << " " << p.second << endl;}); return 0;}
删除操作
接受key_type参数，返回删除元素的数量
int main(){ multimap mp; string word; while(cin >> word) { if(word == "break") break; mp.insert({word,1}); } for_each(mp.cbegin(), mp.cend(), [](const pair & p){ cout << p.first << " " << p.second << endl;}); int erase_num = mp.erase("hello"); cout << "一共删除了" << erase_num << "个hellon"; for_each(mp.cbegin(), mp.cend(), [](const pair & p){ cout << p.first << " " << p.second << endl;}); return 0;}
还有接受范围迭代器和迭代器的两个重载版本,功能大同小异
map的下标访问操作返回类型为mapped_type
map重载了[]，并有一个at()函数不同的是
如果没有对应的关键字[]会插入一个，at()会抛出一个out_of_range异常
程序功能：统计键入的单词出现的次数
int main(){ map mp; string word; while(cin >> word) { if(word == "break") break; ++mp[word]; } for_each(mp.cbegin(), mp.cend(), [](const pair & p){ cout << p.first << " " << p.second << endl;}); return 0;}
干净又卫生奥
注意：[]和at都只对非const的map和unordered_map有用
搜索操作
find()方法，找到第一个相应的关键字对应的pair并返回指向其的迭代器
count()方法，找到相应的关键字对应的pair数量并返回
方法lower_bound(), upperbound(), equal_rang()之前的博客说过
对于非多关联的关联容器很执行操作，对于多关联容器需要一些组合才能达到查找的目的
可以使用lower_bound(), upperbound()组合，如果返回的迭代器相等（有可能是尾后迭代器），则元素不在容器中
可以使用equal_rang()方法
可以使用find(), count()组合
程序功能：通过单词缩写将单词专换为完全形式并输出，将映射规则保存在一个文件中，将转换后的字符串保存在另一个文件中
something.txt
brb be right back
k okay?
y why
r are
u you
pic picture
thk thanks
18r later
bool getmap(ifstream & fin,map & mp){ string key; string value; while(fin >>key &&fin.get()&&getline(fin,value)) { auto p =mp.insert({key,value}); if(!p.second) return false; } return true;}int main(){ ifstream fin("something.txt"); if(!fin.is_open()) { cerr << "文件打开错误" << endl; exit(EXIT_FAILURE); } map words; if(!getmap(fin,words)) { cerr << "源文件存在重复的关键字" << endl; exit(EXIT_FAILURE); } fin.clear(); fin.close(); ofstream fout("out.txt"); if(!fout.is_open()) { cerr << "文件打开错误" << endl; exit(EXIT_FAILURE); } string word; char ch; while(cin >> word&&cin.get(ch)) { if(word == "quit") break; map::const_iterator i; if((i = words.find(word))!=words.end()) { fout << i->second << ch; }else{ fout << word << ch; } } fout.clear(); fout.close(); return 0;}
无序关联容器
这些容器不是通过类型之间定义的严格弱序来组织的，而是使用哈希映射来组织的
理论上哈希映射可以获得更好的平均性能，使用也比有序关联容器见简单
虽然理论上无序关联容器比较快，但是想要达到好的效果还需要一些测试和调优
使用无序容器不会获得排好序的序列
工作原理
将哈希数值相同的关键字保存在一个桶里（一种数据结构），因此，相同的关键字也被保存在桶中
一些桶接口
bucket_count ()桶的数量
max_bucket_count() 能容纳最多桶的数量
bucket_size(n) 第n个桶的大小
bucket(k) 关键字k在哪个桶中
桶迭代
local_iterator 访问桶的迭代器
const_local_iterator 上面的const版本
begin(), end(), cbegin(), cend() 不解释了
哈希策略
load_factor() 平均每个桶中的元素数量，返回float
max_load_factor() 维护桶的平均大小返回float，在需要时添加新的桶，使得load_factor<=max_load_factor
rehash(n) 重新存储，使得load_factor>n， 且bucket_count>size/max_load_factor
reserve(n) 重新存储，使得可以保存n个元素而且不必rehash
对关键字的要求
能进行==的比较
标准库为内置类和一些标准库类型型提供了hash模板能将数据映射为哈希值
但是自定义数据类型不可以，需要我们自己提供哈希映射函数和==判断。
演示
unordered_map> unmp;
再写全点，与上面的方法等价，因为string已经重载了==，就不用自己定义了，再自定义类型中可以像下面这样做
bool func(const string & s1, const string & s2) { return s1 == s2;}int main(){ unordered_map,func> unmp; return 0;}