保健品网站模版,网站建设类公司排名,sem和seo都包括什么,营销策划公司挣钱吗Ciallo#xff5e;(∠・ω )⌒☆ ~ 今天#xff0c;我将继续和大家一起学习C进阶篇第四章----map和set ~ ❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️ 澄岚主页#xff1a;椎名澄嵐-CSDN博客 C基础篇专栏#xff1a;★ C基础篇 ★_椎名澄嵐的博客-CSDN博…Ciallo(∠・ω )⌒☆ ~ 今天我将继续和大家一起学习C进阶篇第四章----map和set ~ ❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️ 澄岚主页椎名澄嵐-CSDN博客 C基础篇专栏★ C基础篇 ★_椎名澄嵐的博客-CSDN博客 C进阶篇专栏★ C进阶篇 ★_椎名澄嵐的博客-CSDN博客 ❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️ 目录
一 序列式容器和关联式容器
二 set系列的使用
2.1 set类的介绍
2.2 set的构造和迭代器
2.3 set的增删查
2.4 set的使用
2.5 multiset和set的差异
2.6 两道set经典例题
三 map系列的使用
3.1 map类的介绍
3.2 pair类型介绍
3.3 map的构造
3.4 map的增删查
3.5 构造遍历及增删查使用样例
3.6 insert operator[ ]
3.7 multimap和map的差异 一 序列式容器和关联式容器
序列式容器有string、vector、list、deque、array、forward_list等。逻辑结构为线性序列的数据结构两个位置存储的值之间⼀般没有紧密的关联关系比如交换⼀下他依旧是序列式容器。顺序容器中的元素是按他们在容器中的存储位置来顺序保存和访问的。
关联式容器有map/set系列和unordered_map/unordered_set系列。关联式容器逻辑结构通常是非线性结构 两个位置有紧密的关联关系交换⼀下他的存储结构就被破坏了。顺序容器中的元素是按关键字来保存和访问的。
本次学习的map和set底层是红黑树红⿊树是⼀颗平衡二叉搜索树。set是key搜索场景的结构 map是key/value搜索场景的结构。 二 set系列的使用
2.1 set类的介绍
set - C Reference (cplusplus.com) set的声明如上T就是set底层关键字的类型set默认要求T支持小于比较如果不支持或者想按自己的需求走可以自行实现仿函数传给第二个模版参数set底层存储数据的内存是从空间配置器申请的如果需要可以自己实现内存池传给第三个参数。⼀般情况下我们都不需要传后两个模版参数。set底层是用红黑树实现增删查效率是 迭代器遍历是走的搜索树的中序所以是有序的。 O(logN) 。 2.2 set的构造和迭代器
set的各种构造~( 无参默认构造迭代器区间构造 拷贝构造移动构造 initializer列表构造 ) set的支持正向和反向迭代遍历遍历默认按升序顺序因为底层是⼆叉搜索树迭代器遍历走的中序支持迭代器就意味着支持范围forset的iterator和const_iterator都不支持迭代器修改数据修改关键字数据破坏了底层搜索树的结构。 2.3 set的增删查
set 不支持修改主要有以下接口~
Member types
key_type - T
value_type - T// 单个数据插⼊如果已经存在则插⼊失败
pairiterator, bool insert(const value_type val);
// 列表插⼊已经在容器中存在的值不会插⼊
void insert(initializer_listvalue_type il);
// 迭代器区间插⼊已经在容器中存在的值不会插⼊
template class InputIterator
void insert(InputIterator first, InputIterator last);
// 查找val返回val所在的迭代器没有找到返回end()
iterator find(const value_type val);
// 查找val返回Val的个数
size_type count(const value_type val) const;
// 删除⼀个迭代器位置的值
iterator erase(const_iterator position);
// 删除valval不存在返回0存在返回1
size_type erase(const value_type val);
// 删除⼀段迭代器区间的值
iterator erase(const_iterator first, const_iterator last);
// 返回⼤于等val位置的迭代器
iterator lower_bound(const value_type val) const;
// 返回⼤于val位置的迭代器
iterator upper_bound(const value_type val) const;
2.4 set的使用
迭代器 insert
#includeiostream
#includeset
using namespace std;
int main()
{// 去重升序排序setint s1;// 去重降序排序setint, greaterint s2;s1.insert(5);s1.insert(2);s1.insert(7);s1.insert(5);//setint::iterator it s.begin();auto it s1.begin();while (it ! s1.end()){// error C3892: “it”: 不能给常量赋值// *it 1;cout *it ;it;}cout endl; // 2 5 7// 插入⼀段initializer_list列表值已经存在的值插入失败s1.insert({ 2,8,3,9 });for (auto e : s1){cout e ;}cout endl; // 2 3 5 7 8 9setstring strset { sort, insert, add };// 遍历string比较ascll码大小顺序遍历的for (auto e : strset){cout e ;} cout endl; // add insert sortreturn 0;
} erase find
int main()
{setint s { 4,2,7,2,8,5,9 };for (auto e : s){cout e ;}cout endl;// 删除最小值s.erase(s.begin());for (auto e : s){cout e ;}cout endl;// 直接删除xint x;cin x;int num s.erase(x);if (num 0){cout x 不存在 endl;}for (auto e : s){cout e 删除成功 ;}cout endl;// 直接查找在利⽤迭代器删除xcin x;auto pos s.find(x);if (pos ! s.end()){// pos在erase后失效s.erase(pos);}else{cout x 不存在 endl;}for (auto e : s){cout e 删除成功 ;}cout endl;// 算法库的查找 O(N)auto pos1 find(s.begin(), s.end(), x);// set⾃⾝实现的查找 O(logN)auto pos2 s.find(x);// 利⽤count间接实现快速查找cin x;if (s.count(x)){cout x 在 endl;}else{cout x 不存在 endl;}return 0;
} 注意迭代器失效的问题
int main()
{std::setint myset;for (int i 1; i 10; i)myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90for (auto e : myset){cout e ;}cout endl;// 实现查找到的[itlow,itup)包含[30, 60]区间// 返回 30auto itlow myset.lower_bound(30);// 返回 60auto itup myset.upper_bound(60);// 实现查找到的[itlow,itup)包含[25, 55]区间// 返回 25auto itlow myset.lower_bound(25);// 返回 55auto itup myset.upper_bound(55);// 删除这段区间的值myset.erase(itlow, itup);for (auto e : myset){cout e ;}cout endl;return 0;
} 2.5 multiset和set的差异
multiset和set的使用基本完全类似主要区别点在于multiset⽀持值冗余那么 insert/find/count/erase都围绕着⽀持值冗余有所差异具体参看下面的样例代码理解。
int main()
{// 相比set不同的是multiset是排序但是不去重multisetint s { 4,2,7,2,4,8,4,5,4,9 };auto it s.begin();while (it ! s.end()){cout *it ;it;}cout endl;// 相比set不同的是x可能会存在多个find查找中序的第⼀个int x;cin x;auto pos s.find(x);while (pos ! s.end() *pos x){cout *pos ;pos;}cout endl;// 相比set不同的是count会返回x的实际个数cout s.count(x) endl;// 相比set不同的是erase给值时会删除所有的xs.erase(x);for (auto e : s){cout e ;}cout endl;return 0;
} 2.6 两道set经典例题
1. 两个数组的交集
349. 两个数组的交集 - 力扣LeetCode 首先用两个集合s1和s2来存储nums1和nums2的元素因为集合会自动去重并且排序~ 然后函数用两个迭代器it1和it2来分别遍历s1和s2。在遍历的过程中如果it1指向的元素小于it2指向的元素就让it1向后移动一位如果it1指向的元素大于it2指向的元素就让it2向后移动一位如果它们相等就把这个元素加入到结果向量ret中并且让it1和it2都向后移动一位~
class Solution {
public:vectorint intersection(vectorint nums1, vectorint nums2) {setint s1(nums1.begin(), nums1.end());setint s2(nums2.begin(), nums2.end());// 因为set遍历是有序的有序值依次⽐较// ⼩的相等的就是交集vectorint ret;auto it1 s1.begin();auto it2 s2.begin();while (it1 ! s1.end() it2 ! s2.end()){if (*it1 *it2){it1;}else if (*it1 *it2){it2;}else{ret.push_back(*it1);it1;it2;}}return ret;}
}; 2. 环形链表
142. 环形链表 II - 力扣LeetCode 把每个节点遍历插入set 若插入时发现set中已经有此节点则带环。
class Solution {
public:ListNode *detectCycle(ListNode *head) {setListNode* s;ListNode* cur head;while(cur){if(s.count(cur))return cur;elses.insert(cur);cur cur-next;}return nullptr;}
}; 三 map系列的使用
3.1 map类的介绍 map的声明如上Key就是map底层关键字的类型T是map底层value的类型set默认要求Key⽀持小于比较如果不⽀持或者需要的话可以自行实现仿函数传给第⼆个模版参数map底层存储数据的内存是从空间配置器申请的。⼀般情况下我们都不需要传后两个模版参数。map底层是用红黑树实现增删查改效率是 O(logN) 迭代器遍历是⾛的中序所以是按key有序顺序遍历的。 3.2 pair类型介绍 map 的成员中的 value_type 使用了 pair 类型那什么是 pair 类型呢~ 3.3 map的构造
map的构造我们关注以下⼏个接口即可。 map⽀持正向和反向迭代遍历遍历默认按key的升序顺序因为底层是⼆叉搜索树迭代器遍历⾛的中序⽀持迭代器就意味着⽀持范围formap⽀持修改value数据不⽀持修改key数据修改关键字数据破坏了底层搜索树的结构。 3.4 map的增删查
map增接口插⼊的pair键值对数据跟set所有不同但是查和删的接⼝只⽤关键字key跟set是完全类似的不过find返回iterator不仅仅可以确认key在不在还找到key映射的value同时通过迭代还可以修改value。
Member types
key_type - The first template parameter (Key)
mapped_type - The second template parameter (T)
value_type - pairconst key_type,mapped_type// 单个数据插⼊如果已经key存在则插⼊失败,key存在相等value不相等也会插⼊失败
pairiterator,bool insert (const value_type val);
// 列表插⼊已经在容器中存在的值不会插⼊
void insert (initializer_listvalue_type il);
// 迭代器区间插⼊已经在容器中存在的值不会插⼊
template class InputIterator
void insert (InputIterator first, InputIterator last);// 查找k返回k所在的迭代器没有找到返回end()
iterator find (const key_type k);
// 查找k返回k的个数
size_type count (const key_type k) const;// 删除⼀个迭代器位置的值
iterator erase (const_iterator position);
// 删除kk存在返回0存在返回1
size_type erase (const key_type k);
// 删除⼀段迭代器区间的值
iterator erase (const_iterator first, const_iterator last);// 返回⼤于等k位置的迭代器
iterator lower_bound (const key_type k);
// 返回⼤于k位置的迭代器
const_iterator lower_bound (const key_type k) const; 3.5 构造遍历及增删查使用样例
int main()
{mapstring, string dict;pairstring, string kv1(first, 第一个);dict.insert(kv1); // 有名对象dict.insert(pairstring, string(second, 第二个)); // 匿名对象dict.insert(make_pair(third, 第三个)); // make_pair函数dict.insert({ forth, 第四个 }); // C11// 隐式类型转换构造mapstring, string dict2 { { left, 左边 }, { right, 右边 }, { insert, 插入 }, { erase, 删除 } };auto it dict.begin();while (it ! dict.end()){// cout (*it).first : (*it).second endl;cout it-first : it-second endl;// 存结构可以用箭头// 实际上是cout it.operator-()-first : it.operator-()-second endl;it;}return 0;
} 3.6 insert operator[ ] insert 插⼊⼀个 pair 对象
1 、如果 key 已经在 map 中插⼊失败则返回⼀个 pair 对象返回 pair 对象 first 是 key 所在结点的迭代器 second 是 false。2 、如果 key 不在在 map 中插⼊成功则返回⼀个 pair 对象返回 pair 对象 first 是新插⼊ key 所在结点的迭代器 second 是 true。⽆论插⼊成功还是失败返回 pair 对象的 first 都会指向 key 所在的迭代器。那么也就意味着 insert 插⼊失败时充当了查找的功能正是因为这⼀点insert 可以⽤来实现 operator[]。需要注意的是这⾥有两个 pair 不要混淆了⼀个是 map 底层红⿊树节点中存的 pair 另 ⼀个是 insert 返回值 pair。 operator[ ] 有插入查找修改三个功能 ~
// operator的内部实现
mapped_type operator[] (const key_type k)
{// 1、如果k不在map中insert会插⼊k和mapped_type默认值// 同时[]返回结点中存储mapped_type值的引⽤那么我们可以通过引⽤修改返映射值。所以[]具备了插⼊修改功能// 2、如果k在map中insert会插⼊失败但是insert返回pair对象的first是指向key结点的迭代器// 返回值同时[]返回结点中存储mapped_type值的引⽤所以[]具备了查找修改的功能pairiterator, bool ret insert({ k, mapped_type() });iterator it ret.first;return it-second;
}
operator[ ]的使用
确定key存在才能使用[ ]查找~要不就变成插入了~
int main()
{mapstring, string dict;dict.insert(make_pair(sort, 排序));// key不存在-插入{ insert, string() }dict[insert];// 插入修改dict[left] 左边;// 修改dict[left] 左边、剩余;// key存在-查找cout dict[left] endl;return 0;
} 使用find统计次数
int main()
{// 利⽤find和iterator修改功能统计水果出现的次数string arr[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜, 苹果, 香蕉, 苹果, 香蕉 };mapstring, int countMap;for (const auto str : arr){// 先查找水果在不在map中// 1、不在说明⽔果第⼀次出现则插⼊{⽔果, 1}// 2、在则查找到的节点中⽔果对应的次数auto ret countMap.find(str);if (ret countMap.end()){countMap.insert({ str, 1 });}else{ret-second;}}for (const auto e : countMap){cout e.first : e.second endl;}cout endl;return 0;
}
使用operator[ ] 统计次数
int main()
{string arr[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜, 苹果, 香蕉, 苹果, 香蕉 };mapstring, int countMap;for (const auto str : arr){// []先查找水果在不在map中// 1、不在说明水果第⼀次出现则插⼊{水果, 0}同时返回次数的引⽤⼀下就变成1次了// 2、在则返回水果对应的次数countMap[str];}for (const auto e : countMap){cout e.first : e.second endl;}cout endl;return 0;
} 3.7 multimap和map的差异
multimap和map的使⽤基本完全类似主要区别点在于multimap⽀持关键值key冗余那么 insert/find/count/erase都围绕着⽀持关键值key冗余有所差异这⾥跟set和multiset完全⼀样⽐如find时有多个key返回中序第⼀个。其次就是multimap不⽀持[ ]因为⽀持key冗余[ ]就只能⽀持插⼊了不能⽀持修改。
