目录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 Reference2.2 set 的初始化函数template class T, // set::key_type/value_type 类型 class Compare lessT, // set::key_compare/value_compare 比较器默认小于号 class Alloc allocatorT // 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) // 单个插入 pairiterator,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_tn 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 返回最大下限和最小上限 两个的结合 pairiterator,iterator equal_range (const value_type val) const;lower_bound 和 upper_bound 针对的是不同_ket 之间查找有效区间的equal_range 针对的是相同_ket 的有效区间 例如12223 就会把以一个2和最后一个3有效区间 [2,3) 一起打包到pairiterator,iterator这个类中void test_set1() { int arr[] { 9,3,7,4,2,85,42,13,34 }; setint 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允许重复元素可以存放多个相同的值插入重复值成功。setint s; s.insert(1); s.insert(1); // 无效s 里只有一个1 multisetint 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 Reference3.2 map 的初始化函数template class Key, // map::key_type class T, // map::mapped_type class Compare lessKey, // map::key_compare class Alloc allocatorpairconst Key,T // map::allocator_type class map; typedef pairconst 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) // 单个插入 pairiterator,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 返回最大下限和最小上限 两个的结合 pairiterator,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 Referencetemplateclass T1, class T2 struct pair { T1 first; // 第一个成员 T2 second; // 第二个成员 };pair 是一个拥有两个自定义类型模板结构体在 map 常被用来当做 typedef pairconst Key, T value_type; 头文件#include utilitypair 类型还有内置的运算符重载优先比较 first 其次比较 secondtemplate class T1, class T2 bool operator (const pairT1,T2 lhs, const pairT1,T2 rhs) { return lhs.firstrhs.first lhs.secondrhs.second; } template class T1, class T2 bool operator! (const pairT1,T2 lhs, const pairT1,T2 rhs) { return !(lhsrhs); } template class T1, class T2 bool operator (const pairT1,T2 lhs, const pairT1,T2 rhs) { return lhs.firstrhs.first || (!(rhs.firstlhs.first) lhs.secondrhs.second); } template class T1, class T2 bool operator (const pairT1,T2 lhs, const pairT1,T2 rhs) { return !(rhslhs); } template class T1, class T2 bool operator (const pairT1,T2 lhs, const pairT1,T2 rhs) { return rhslhs; } template class T1, class T2 bool operator (const pairT1,T2 lhs, const pairT1,T2 rhs) { return !(lhsrhs); }pair 的使用#include iostream #include map #include utility #include string using namespace std; int main() { mapint, 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 重复。
