目录
1. set 和 map 的与其他类型的介绍对比
2. set 的系列介绍
2.1 set 和 multiset 的相关文献
2.2 set 的初始化函数
2.3 set 的增删改函数
2.4 set 的其他函数
2.5 set 和 multiset 的对比
3. map 的系列介绍
3.1 map 和 multimap 的相关文献
3.2 map 的初始化函数
3.3 map 的增删改函数
3.4 map 的其他函数
3.5 map 的 operator[] 运算符重载
3.6 pair 类的介绍
3.7 map 和 multimap 的对比
1. set 和 map 的与其他类型的介绍对比
与之前的类型的对比 string vector list stack queue deque priority_queue 等的类型的，set 和 map 的类型与二叉搜索树关系更加相似，但他们的底层是以红黑树构成的，如果你现在还没有了解红黑树的话，那就先以比二叉搜索树更加牛逼的理解就可以。
在二叉搜索树章节中我们有稍微熟悉了二叉搜索树的底层，其中二叉搜索树中的结构有两个类型有关是 class K 和 class V , K 对应的是 _key 全部二叉搜索树的比较基准都是以 _key 为标准，V对应的是 _value 是附加的类型，set 就是两类型中有 _key 一个，map 就是有两个。
2. set 的系列介绍
2.1 set 和 multiset 的相关文献
set - C++ Reference multiset - C++ Reference
2.2 set 的初始化函数
template < class T, // set::key_type/value_type 类型 class Compare = less<T>, // set::key_compare/value_compare 比较器（默认小于号） class Alloc = allocator<T> // set::allocator_type 内存池 > class set; // 默认 set 左子树小 右子树大empty (1) // 默认构造 explicit set (const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type()); range (2) // 一段区间构造 template <class InputIterator> set (InputIterator first, InputIterator last, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type()); copy (3) // 拷贝构造 set (const set& x); copy (1) // 等号运算算符重载 set& operator= (const set& x);2.3 set 的增删改函数
// insert single element (1) // 单个插入 pair<iterator,bool> insert (const value_type& val); with hint (2) // iterator insert (iterator position, const value_type& val); range (3) // 区间插入 template <class InputIterator> void insert (InputIterator first, InputIterator last); // erase (1) // 指定区间删除 void erase (iterator position); (2) // 指定内容删除 // 看完 multiset 的话： 指定内容删除并且返回（size_t）n size_type erase (const value_type& val); (3) // 指定区间删除（要配合迭代器使用） void erase (iterator first, iterator last); // swap 交换 void swap (set& x); // 清空 void clear();2.4 set 的其他函数
// begin end rbegin rend // begin 返回最小值的迭代器 iterator begin(); const_iterator begin() const; // end 返回最大值的迭代器 iterator end(); const_iterator end() const; // rbegin 返回最大值的迭代器 iterator rbegin(); const_iterator rbegin() const; // rend 返回最小值的迭代器 iterator rend(); const_iterator rend() const; // empty 判断是否为空 bool empty() const; // size 返回已经节点有多少个 size_type size() const; // count 检查是否有这个数，有就返回1，没有返回0 size_type count (const value_type& val) const; // find 查找 给 val 返回地址 iterator find (const value_type& val) const; // lower_bound 输入的数值返回地址，如果数值没有，查找比这个大的数值 iterator lower_bound (const value_type& val) const; // upper_bound 输入的数值返回地址，如果数值没有，查找比这个小的数值 iterator upper_bound (const value_type& val) const; // 两个对比 lower_bound 查找最大下限 upper_bound 查找最小上限 // equal_range 返回最大下限和最小上限 两个的结合 pair<iterator,iterator> equal_range (const value_type& val) const;lower_bound 和 upper_bound 针对的是不同_ket 之间查找有效区间的；
equal_range 针对的是相同_ket 的有效区间 例如：1，2，2，2，3 就会把以一个2和最后一个3，有效区间 [2,3) 一起打包到pair<iterator,iterator>这个类中
void test_set1() { int arr[] = { 9,3,7,4,2,85,42,13,34 }; set<int> s(arr, arr + 9); s.insert(10); for (auto ch : s) { cout << ch << " "; } cout << endl; s.erase(10); for (auto ch : s) { cout << ch << " "; } cout << endl; s.erase(s.begin()); for (auto ch : s) { cout << ch << " "; } cout << endl; s.erase(s.begin(),s.end()); s.insert(10); for (auto ch : s) { cout << ch << " "; } cout << endl; return; }2.5 set 和 multiset 的对比
- 元素是否允许重复
set：不允许重复键值，容器内元素唯一；插入重复值会直接失败，不会新增元素。multiset：允许重复元素，可以存放多个相同的值，插入重复值成功。
set<int> s; s.insert(1); s.insert(1); // 无效，s 里只有一个1 multiset<int> ms; ms.insert(1); ms.insert(1); // 有效，ms 里有两个1- 查找删除接口行为差异（高频考点）
find(val)：返回第一个等于 val 的元素迭代器，两者行为一致。count(val)set：返回只能是 0 或 1multiset：返回有多少个等于 val 的元素
erase(val)（传值，不是迭代器！）set.erase(val)：删除值为 val 的那一个元素multiset.erase(val)：删除所有值等于 val 的元素
- 如果只想删掉 multiset 里其中一个：
auto it = ms.find(val); if (it != ms.end()) ms.erase(it);3. map 的系列介绍
3.1 map 和 multimap 的相关文献
map - C++ Reference multimap - C++ Reference
3.2 map 的初始化函数
template < class Key, // map::key_type class T, // map::mapped_type class Compare = less<Key>, // map::key_compare class Alloc = allocator<pair<const Key,T> > // map::allocator_type > class map; typedef pair<const Key, T> value_type;// 构造函数 empty (1) explicit map (const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type()); range (2) template <class InputIterator> map (InputIterator first, InputIterator last, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type()); copy (3) map (const map& x); // 赋值运算符重载 copy (1) map& operator= (const map& x);3.3 map 的增删改函数
// insert 插入 single element (1) // 单个插入 pair<iterator,bool> insert (const value_type& val); with hint (2) // iterator insert (iterator position, const value_type& val); range (3) // 指定区间插入 template <class InputIterator> void insert (InputIterator first, InputIterator last); // erase 删除 (1) // 指定地址删除 void erase (iterator position); (2) // 指定内容删除 size_type erase (const key_type& k); (3) // 指定区间删除 void erase (iterator first, iterator last); // swap 交换 void swap (map& x); // clear 清空 void clear();3.4 map 的其他函数
// begin end rbegin rend // begin 返回最小值的迭代器 iterator begin(); const_iterator begin() const; // end 返回最大值的迭代器 iterator end(); const_iterator end() const; // rbegin 返回最大值的迭代器 iterator rbegin(); const_iterator rbegin() const; // rend 返回最小值的迭代器 iterator rend(); const_iterator rend() const; // empty 判断是否为空 bool empty() const; // size 返回已经节点有多少个 size_type size() const; // count 检查是否有这个数，有就返回1，没有返回0 size_type count (const key_type& val) const; // find 查找 给 val 返回地址 iterator find (const key_type& val) const; // lower_bound 输入的数值返回地址，如果数值没有，查找比这个大的数值 iterator lower_bound (const key_type& val) const; // upper_bound 输入的数值返回地址，如果数值没有，查找比这个小的数值 iterator upper_bound (const key_type& val) const; // 两个对比 lower_bound 查找最大下限 upper_bound 查找最小上限 // equal_range 返回最大下限和最小上限 两个的结合 pair<iterator,iterator> equal_range (const key_type& val) const;3.5 map 的 operator[] 运算符重载
mapped_type& operator[] (const key_type& k);map 的operator[] 运算符重相对于 vector 等的不一样（注意 multimap 没有这个运算符重载），相当于如果 k 在 map 中存在就返回对应地址，并且可以进行修改 map 中的 value 的（不是 ket），如果没有就会就会在这个区域进行插入新_key 空间，后面与前者的功能一致。
3.6 pair 类的介绍
pair - C++ Reference
template<class T1, class T2> struct pair { T1 first; // 第一个成员 T2 second; // 第二个成员 };pair 是一个拥有两个自定义类型模板结构体，在 map 常被用来当做 typedef pair<const Key, T> value_type; 头文件：#include <utility>
pair 类型还有内置的运算符重载
优先比较 first ，其次比较 second
template <class T1, class T2> bool operator== (const pair<T1,T2>& lhs, const pair<T1,T2>& rhs) { return lhs.first==rhs.first && lhs.second==rhs.second; } template <class T1, class T2> bool operator!= (const pair<T1,T2>& lhs, const pair<T1,T2>& rhs) { return !(lhs==rhs); } template <class T1, class T2> bool operator< (const pair<T1,T2>& lhs, const pair<T1,T2>& rhs) { return lhs.first<rhs.first || (!(rhs.first<lhs.first) && lhs.second<rhs.second); } template <class T1, class T2> bool operator<= (const pair<T1,T2>& lhs, const pair<T1,T2>& rhs) { return !(rhs<lhs); } template <class T1, class T2> bool operator> (const pair<T1,T2>& lhs, const pair<T1,T2>& rhs) { return rhs<lhs; } template <class T1, class T2> bool operator>= (const pair<T1,T2>& lhs, const pair<T1,T2>& rhs) { return !(lhs<rhs); }pair 的使用
#include <iostream> #include <map> #include <utility> #include <string> using namespace std; int main() { map<int, string> mp; mp.insert(make_pair(1, "C++")); mp.insert({2, "Java"}); mp[3] = "Python"; for(auto &p : mp) { cout << p.first << " : " << p.second << endl; } auto it = mp.find(2); if(it != mp.end()) { it->second = "GO"; } return 0; }3.7 map 和 multimap 的对比
同理 map和multimap都属于关联容器，底层都是红黑树（平衡二叉搜索树），元素按键key有序排列，迭代器遍历是升序；核心差别：map 键不允许重复，multimap 允许 key 重复。
