map和set的使用

ops/2024/10/9 2:08:43/

引言

序列式容器和关联式容器

序列式容器：逻辑结构为线性序列的数据结构，两个位置存储的值之间⼀般没有紧密的关联关系，例如：string、vector、list、deque、array.

关联式容器：关联式容器也是用来存储数据的，但它通常是非线性结构，两个位置之间有紧密的关联，交换会导致结构被破坏。例如：map/set系列和unordered_map/unordered_set系列.

map和set底层是红⿊树，红⿊树是⼀颗平衡⼆叉搜索树。set是key搜索场景的结构，
map是key/value搜索场景的结构。

Set类

概念

• set的声明如下，T就是set底层关键字的类型

template < class T, // set::key_type/value_typeclass Compare = less<T>, // set::key_compare/value_compareclass Alloc = allocator<T> // set::allocator_type
> class set;


• set默认要求T⽀持⼩于⽐较，如果不⽀持或者想按⾃⼰的需求⾛可以⾃⾏实现仿函数传给第⼆个模版参数
• set底层存储数据的内存是从空间配置器申请的，如果需要可以⾃⼰实现内存池，传给第三个参
数。
• ⼀般情况下，我们都不需要传后两个模版参数。
• set底层是⽤红⿊树实现，增删查效率是O(logN) ，迭代器遍历是⾛的搜索树的中序，所以是有序
的。

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 & = allocator_type());// copy (3) 拷⻉构造
set(const set& x);// initializer list (5) initializer 列表构造
set(initializer_list<value_type> il,const key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type());// 迭代器是⼀个双向迭代器
iterator->a bidirectional iterator to const value_type// 正向迭代器
iterator begin();
iterator end();// 反向迭代器
reverse_iterator rbegin();
reverse_iterator rend();

Set的增删查

//Member types
//key_type->The first template parameter(T)
//value_type->The first template parameter(T)// 单个数据插⼊，如果已经存在则插⼊失败
pair<iterator, bool> insert(const value_type& val);
// 列表插⼊，已经在容器中存在的值不会插⼊
void insert(initializer_list<value_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);
// 删除val，val不存在返回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;

insert和迭代器的使用

#include<iostream>
#include<set>
using namespace std;
int main()
{// 去重+升序排序set<int> s;// 去重+降序排序（给⼀个⼤于的仿函数）//set<int, greater<int>> s;s.insert(5);s.insert(2);s.insert(7);s.insert(5);//set<int>::iterator it = s.begin();auto it = s.begin();//简便写法用autowhile (it != s.end()){// error C3892: “it”: 不能给常量赋值// *it = 1;cout << *it << " ";++it;}cout << endl;// 插⼊⼀段initializer_list列表值，已经存在的值插⼊失败s.insert({ 2,8,3,9 });for (auto e : s){cout << e << " ";}cout << endl;//此处对字符串进行排序set<string> strset = { "sort", "insert", "add" };// 遍历string⽐较ascll码⼤⼩顺序遍历的for (auto& e : strset){cout << e << " ";}cout << endl;
}

测试结果如下：

find和erase的使用

int main()
{set<int> 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;int x = 0;cin >> x;auto pos = s.find(x);if (pos != s.end()){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;
}

测试结果如下：

multiset和set的差异

        multiset和set的使⽤基本完全类似，主要区别点在于multiset⽀持值冗余，那么insert/find/count/erase都围绕着⽀持值冗余有所差异，具体参看下⾯的样例代码理解。

#include<iostream>
#include<set>
using namespace std;
int main()
{// 相⽐set不同的是，multiset是排序，但是不去重multiset<int> 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;
}

不同点：

即mutiset排序不会像set一样去重，而是会将相同值保留下来.

find在遇到相同值时，寻找中序顺序的第一个.

count会返回x的实际个数.

erase给值时会删除所有相同的值.

map类

概念

        map的声明如下，Key就是map底层关键字的类型，T是map底层value的类型，set默认要求Key⽀持⼩于⽐较，如果不⽀持或者需要的话可以⾃⾏实现仿函数传给第⼆个模版参数，map底层存储数据的内存是从空间配置器申请的。⼀般情况下，我们都不需要传后两个模版参数。map底层是⽤红⿊树实现，增删查改效率是 O(logN) ，迭代器遍历是⾛的中序，所以是按key有序顺序遍历的。map的声明如下：

template < class Key, // map::key_typeclass T, // map::mapped_typeclass Compare = less<Key>, // map::key_compareclass Alloc = allocator<pair<const Key, T> > //map::allocator_type
> class map;

pair类型的概念

map底层的红⿊树节点中的数据，使⽤pair<Key, T>存储键值对数据。

typedef pair<const Key, T> value_type;
template <class T1, class T2>
struct pair
{typedef T1 first_type;typedef T2 second_type;T1 first;T2 second;pair() : first(T1()), second(T2()){}pair(const T1& a, const T2& b) : first(a), second(b){}template<class U, class V>pair(const pair<U, V>& pr) : first(pr.first), second(pr.second){}
};template <class T1, class T2>
inline pair<T1, T2> make_pair(T1 x, T2 y)
{return (pair<T1, T2>(x, y));
}

可以理解为将Key和Value两个值合为一个值的作用，并且由于是用结构体写的，故可以直接访问里面的成员变量.

Map的构造和迭代器

        map的⽀持正向和反向迭代遍历，遍历默认按key的升序顺序，因为底层是⼆叉搜索树，迭代器遍历⾛的中序；⽀持迭代器就意味着⽀持范围for，map⽀持修改value数据，不⽀持修改key数据，修改关键字数据，破坏了底层搜索树的结构。

        我们关注几个常用的接口：

// 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 & = allocator_type());// copy (3) 拷⻉构造
map(const map& x);// initializer list (5) initializer 列表构造
map(initializer_list<value_type> il,const key_compare & comp = key_compare(),const allocator_type & alloc = allocator_type());// 迭代器是⼀个双向迭代器
iterator->a bidirectional iterator to const value_type
// 正向迭代器
iterator begin();
iterator end();
// 反向迭代器
reverse_iterator rbegin();
reverse_iterator rend();

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->pair<const key_type, mapped_type>增
// 单个数据插⼊，如果已经key存在则插⼊失败,key存在相等value不相等也会插⼊失败
pair<iterator, bool> insert(const value_type& val);
// 列表插⼊，已经在容器中存在的值不会插⼊
void insert(initializer_list<value_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);
// 删除k，k存在返回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;

Map的数据修改 

map支持修改map_type数据，不支持修改key数据.

map第⼀个⽀持修改的⽅式时通过迭代器，迭代器遍历时或者find返回key所在的iterator修改，map还有⼀个⾮常重要的修改接⼝operator[]，但是operator[]不仅仅⽀持修改，还⽀持插⼊数据和查找数据，所以他是⼀个多功能复合接⼝.
需要注意从内部实现⻆度，map这⾥把我们传统说的value值，给的是T类型，typedef为
mapped_type。

⽽value_type是红⿊树结点中存储的pair键值对值。⽇常使⽤我们还是习惯将这⾥的T映射值叫做value。

mapped_type& operator[] (const key_type& k)
{pair<iterator, bool> ret = insert({ k, mapped_type() });iterator it = ret.first;return it->second;
}

1、如果k不在map中，insert会插⼊k和mapped_type默认值，同时[]返回结点中存储
mapped_type值的引⽤，那么我们可以通过引⽤修改返映射值。所以[]具备了插⼊+修改功能
2、如果k在map中，insert会插⼊失败，但是insert返回pair对象的first是指向key结点的
迭代器，返回值同时[]返回结点中存储mapped_type值的引⽤，所以[]具备了查找+修改的功能

构造及增删查的测试

#include<iostream>
#include<map>
using namespace std;
int main()
{//构造及迭代遍历map<string, string> dict = { {"left", "左边"}, {"right", "右边"},{"insert", "插⼊"},{ "string", "字符串" } };//map<string, string>::iterator it = dict.begin();auto it = dict.begin();while (it != dict.end()){//cout << (*it).first <<":"<<(*it).second << endl;// map的迭代基本都使⽤operator->,这⾥省略了⼀个->// 第⼀个->是迭代器运算符重载，返回pair*，第⼆个箭头是结构指针解引⽤取pair数据//cout << it.operator->()->first << ":" << it.operator->()-> second << endl;cout << it->first << ":" << it->second << endl;++it;}cout << endl;// insert插⼊pair对象的4种⽅式，对⽐之下，最后⼀种最⽅便pair<string, string> kv1("first", "第⼀个");dict.insert(kv1);dict.insert(pair<string, string>("second", "第⼆个"));dict.insert(make_pair("sort", "排序"));dict.insert({ "auto", "⾃动的" });// "left"已经存在，插⼊失败dict.insert({ "left", "左边，剩余" });// 范围for遍历for (const auto& e : dict){cout << e.first << ":" << e.second << endl;}cout << endl;string str;while (cin >> str){auto ret = dict.find(str);if (ret != dict.end()){cout << "->" << ret->second << endl;}else{cout << "⽆此单词，请重新输⼊" << endl;}}return 0;
}

map的[]功能测试

利用find和iterator的功能实现统计水果出现次数.

#include<iostream>
#include<map>
#include<string>
using namespace std;int main()
{// 利⽤find和iterator修改功能，统计⽔果出现的次数string arr[] = { "苹果", "西⽠", "苹果", "西⽠", "苹果", "苹果", "西⽠","苹果", "⾹蕉", "苹果", "⾹蕉" };map<string, 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;
}

测试结果：

multimap和map的差异

        multimap和map的使⽤基本完全类似，主要区别点在于multimap⽀持关键值key冗余，那么
insert/find/count/erase都围绕着⽀持关键值key冗余有所差异，这⾥跟set和multiset完全⼀样，⽐如find时，有多个key，返回中序第⼀个。其次就是multimap不⽀持[]，因为⽀持key冗余，[]就只能⽀持插⼊了，不能⽀持修改。

总结

        我们需要熟悉set/multiset和map/multiset并且能够运用得当：主要弄清楚容器中的迭代器的使用和注意事项；新名词如"pair"的意义；能够利用容器常见的接口，能对其进行增删查;能够了解multiset、multimap与set、map的区别，能能够分辨清楚multi的冗余在其中起到什么不同作用.


http://www.ppmy.cn/ops/122923.html

相关文章

如何让70B参数的大型语言模型在资源有限的边缘设备上高效运行？

如何让70B参数的大型语言模型在资源有限的边缘设备上高效运行？

你有没有想过，像我们平时使用的智能手机、家里的智能音箱这样的小设备，也能运行那些参数量高达数十亿的大型语言模型（LLM）呢？这听起来像是天方夜谭，毕竟这些模型动辄需要巨大的算力和存储资源，但实际上，随着技术的发展，这个梦想正在变成现实。那么，问题来了，怎么在资…
阅读更多...
Streamlit：用Python快速构建交互式Web应用

Streamlit：用Python快速构建交互式Web应用

在传统的Web开发中&#xff0c;开发者常常需要编写大量的前端和后端代码&#xff0c;才能实现一个简单的交互式Web应用。Streamlit 通过简化这一过程&#xff0c;使得你只需要用Python编写代码&#xff0c;就能快速创建具有丰富交互功能的Web应用。本文将介绍如何使用Streamlit…
阅读更多...
Echarts实现订单数据统计，前端+后端 代码

Echarts实现订单数据统计，前端+后端 代码

以下是静态统计图可以直接看到统计图&#xff0c;复制粘贴即可看到效果&#xff0c;但是数据是死的。下面我会介绍一种动态的方法 &#xff0c;后端动态返回&#xff0c;基于订单页面的数据&#xff0c;来渲染统计图。 Vue 安装 Echarts npm i echarts -S 静态 &#xff1a; …
阅读更多...
【STM32单片机_(HAL库)】4-2-1【定时器TIM】定时器输出PWM实现呼吸灯实验

【STM32单片机_(HAL库)】4-2-1【定时器TIM】定时器输出PWM实现呼吸灯实验

1.硬件 STM32单片机最小系统LED灯模块 2.软件 pwm驱动文件添加定时器HAL驱动层文件添加GPIO常用函数定时器输出PWM配置步骤main.c程序 #include "sys.h" #include "delay.h" #include "led.h" #include "pwm.h"int main(void) {HA…
阅读更多...
Thinkphp/Laravel基于vue.js的社区健康服务管理系统Vscode毕业设计成品源码_0i0k4

Thinkphp/Laravel基于vue.js的社区健康服务管理系统Vscode毕业设计成品源码_0i0k4

目录 技术栈和环境说明具体实现截图设计思路关键技术课题的重点和难点&#xff1a;框架介绍数据访问方式PHP核心代码部分展示代码目录结构解析系统测试详细视频演示源码获取 技术栈和环境说明 采用PHP语言开发&#xff0c;开发环境为phpstudy 开发工具notepad并使用MYSQL数据库…
阅读更多...
免费 Oracle 各版本 离线帮助使用和介绍

免费 Oracle 各版本 离线帮助使用和介绍

文章目录 Oracle 各版本 离线帮助使用和介绍概要在线帮助下载离线文档包&#xff1a;解压离线文档&#xff1a;访问离线文档&#xff1a;导航使用&#xff1a;目录介绍Install and Upgrade&#xff08;安装和升级&#xff09;&#xff1a;Administration&#xff08;管理&#…
阅读更多...
留存率的定义与SQL实现

留存率的定义与SQL实现

1.什么是留存率 留存率是指在特定时间段内&#xff0c;仍然继续使用某项产品或服务的用户占用户总数的百分比。 通常&#xff0c;留存率会以日&#xff0c;周&#xff0c;或月为单位进行统计和分析。 2.SQL留存率常见问题 1.计算新用户登录的日期的次日留存率以及3日留存率 …
阅读更多...
【堆排】为何使用向下调整法建堆比向上调整法建堆更好呢？

【堆排】为何使用向下调整法建堆比向上调整法建堆更好呢？

文章目录 前言一、堆排代码一、计算使用向上调整法建堆的时间复杂度二、计算使用向下调整法插入的时间复杂度总结 前言 在博主的上一篇博客堆排(链接在这里点击即可)的总结中提出啦使用向下调整法建堆比使用向上调整法建堆更好&#xff0c;是因为使用向上调整法建堆的时间复杂…
阅读更多...
最新文章

Copyright @ 2022~2023