【C++第十四课-map和set】set的用法、multiset、map的用法、multimap

之前学的都只是存储数据
在初阶阶段，我们已经接触过STL中的部分容器，比如：vector、list、deque、forward_list(C++11)等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。那什么是关联式容器？它与序列式容器有什么区别

关联式容器
关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是<key, value>结构的键值对，在数据检索时比序列式容器效率更高

set – k模型
map – kv模型

set

key不允许修改

set的用法

底层是红黑树 – 平衡搜索二叉树

#include<set>

set功能：排序+去重

算法unique()也可以去重，但前提需要有序。因此一般去重用set

反向迭代器

	set<int>::reverse_iterator it = s.rbegin();while (it != s.rend()){cout << *it << " ";++it;}cout << endl;

find

找到了返回这个值的迭代器，如果没有找到返回end() – 是开区间位置

erase

（1）迭代器必须在，不在就会报错
（2）给的值可以不在树里面

count

返回某个值有几个

lower_bound、upper_bound

当要删除一段区间的时候用

方法一：使用find找到要删除的2和9，再用erase的迭代器区间删除
问题：（1）2和9不一定存在（2）给erase的迭代器区间必须是左闭右开的，如果2和9在，find找到的也是左闭右闭的
方法二：使用lower_bound、upper_bound

lower_bound：返回的是>=val的迭代器
upper_bound：返回的是>val的迭代器

void func2()
{set<int> s;s.insert(5);s.insert(9);s.insert(4);s.insert(6);s.insert(3);s.insert(8);s.insert(1);s.insert(1);// 删除[2, 9]set<int>::iterator start = s.lower_bound(2);set<int>::iterator finish = s.upper_bound(9);s.erase(start, finish);for (auto e : s){cout << e << " ";}cout << endl;}

multiset

允许插入重复的值
排序
重复的值怎么放？
放左边和右边都可以，因为有旋转，都会变的。

erase

这里返回删除了几个其实是为了multiset准备的，色图set也有是为了统一

count

实际上也是为multiset设计的，set有是为了统一

find

当find的值有多个的时候返回**中序的第一个 **

map

key不允许修改，value允许修改

Key和T不是分开的，封到了pair的一个结构里面

map的构造

void test_map1()
{map<string, string> m;m.insert(pair<string, string>("string", "字符串"));pair<string, string> kv("char", "字符");m.insert(kv);//C++11支持m.insert({ "sort", "排序" });//C++98提出的m.insert(make_pair("sort", "排序"));auto it = m.begin();while (it != m.end()){cout << (*it).first << ":" << (*it).second << endl;++it;}cout << endl;}

1、m.insert(pair<string, string>("string", "字符串"));是匿名对象
2、m.insert({ "sort", "排序" });可以这么写是因为隐式类型转换，对于只有一个参数的构造函数支持隐式类型转换
3、（*it）这个解引用之后得到的是pair的数据

find

如果找的返回对应节点的迭代器，如果找不到返回end

multimap

允许key的冗余

计算出现的次数

普通方法

void test_map2()
{map<string, int> countmap;string arr[] = { "芒果", "苹果", "西瓜", "芒果", "芒果", "西瓜", "猕猴桃" };for (auto& e : arr){map<string, int>::iterator it = countmap.find(e);if (it == countmap.end()){countmap.insert(make_pair(e, 1));}else{it->second++;}}for (auto& e : countmap){cout << e.first << ":" << e.second << endl;}
}

[ ]

基于insert实现的

[ ] : 给我一个key，返回value的引用
如果key不存在，插入key
底层是借助insert实现的

插入的key如果存在就返回当前节点的value
插入的key如果不存在就进行插入，返回新插入节点的value（value是类型的）

void test_map3()
{map<string, int> countmap;string arr[] = { "芒果", "苹果", "西瓜", "芒果", "芒果", "西瓜", "猕猴桃" };for (auto& e : arr){countmap[e]++;}for (auto& e : countmap){cout << e.first << ":" << e.second << endl;}
}

如果e存在返回的是对应节点的value，value++
如果e不存在插入新节点，新节点的value是类型的默认值，对value进行++就是0
底层实现大概如下图

[ ]的功能
（1）插入
（2）查找
（3）修改
（4）插入+修改

void test_map5()
{map<string, string> map;map.insert({ "sort", "排序" });map.insert({ "left", "左边" });//插入map["right"];//查找cout << map["sort"] << endl;//修改map["sort"] = "xxx";//插入+修改map["string"] = "字符串";
}

insert

除了有插入的功能，也有查找的功能。

对于（1）版本，返回值是一个pair，pair的first是返回key对应的迭代器。pair的second返回的是bool，如果key在map里面不存在、插入key返回true，如果key在map里面存在返回false。

void test_map4()
{map<string, int> countmap;string arr[] = { "芒果", "苹果", "西瓜", "芒果", "芒果", "西瓜", "猕猴桃" };for (auto& e : arr){//insert,如果存在就返回iterator，如果不存在就插入pair<map<string, int>::iterator, bool> ret = countmap.insert(make_pair(e, 1));if (ret.second == false)//节点存在，不用插入{ret.first->second++;}}for (auto& e : countmap){cout << e.first << ":" << e.second << endl;}
}

题目

随即链表的复制
两个数组的交集

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {map<int, int> m;vector<int> v;//统计完了for(auto e: nums1){m.insert(make_pair(e,1));}//有就value++，没有就不插入for(auto e: nums2){auto ret = m.find(e);if(ret != m.end())ret->second++;}for(auto& e:m){if(e.second >= 2)v.push_back(e.first);}return v;}
};