C++进阶：map与set容器的使用

目录

  • 1. 关联式容器map与set
  • 2. set与multiset的接口与使用
    • 2.1 set的接口与使用
      • 2.1.1 成员函数
      • 2.1.2 迭代器
      • 2.1.3 容量相关
      • 2.1.4 修改相关
    • 2.1.5 查找，计数与补充
    • 2.2 multiset的接口与使用
  • 3. map与multimap的接口与使用
    • 3.1 map的接口与使用
      • 3.1.1 map的使用补充
      • 3.1.2 插入与operator[]
    • 3.2 multimap接口与使用
  • 4. map与set相关练习
    • 4.1 随机链表的复制（map实现）
    • 4.2 前K个高频单词
    • 4.3 两个数组的交集

1. 关联式容器map与set

  1. 我们在之前的学习中，已经学习了解了许多的STL库中的容器，诸如vector（顺序表），list（链表）,deque（双端队列），这类容器的底层数据结构都为线性序列。
  2. 而今天我们所学习的map与set，则是一种区别于此前线性数据结构，叫做关联式数据结构的新容器。
  3. map与set的底层数据结构为红黑树，这一种平衡二叉树，此类关联式数据结构其中存储的数据为<key , value>模型。
  4. 这类数据结构，其可以通过键值迅速找到对应的数据，之所以其支持此种数据存储方式，是因为它的搜索效率相较于线性数据结构具有更高。

2. set与multiset的接口与使用

2.1 set的接口与使用

2.1.1 成员函数

  1. <1> set容器其的底层为一颗红黑树
    <2> 其数据存储节点所存的值为单参数数据，即key模型
    <3> set中不允许存在值相同的数据结点。
  1. 构造函数
//迭代器区间构造
template<class InputIterator>
set(InputIterator first, InputIterator last);

//拷贝构造
set(const set& x);
  1. 赋值运算符重载
set& operator=(const set& x);

2.1.2 迭代器

  1. <1> set支持迭代器遍历与范围for
    <2> 对其进行正向遍历会得到升序的数据序列，逆向遍历会得到降序的数据序列
    <3> 将数据插入至set中，并获取遍历得到的数据序列，等于对一组数据进行去重与排序
    <4> C++算法库中存在有去重算法unique，向其传递一段迭代器区间，其会这段区间内的数据进行去重，前提为区间内的数据有序。
#include <iostream>
using namespace std;
#include <set>
int main()
{
	int arr[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	set<int> s;
	 
	for (auto e : arr)
	{
	    s.insert(e);
	}
	
	//正向遍历，升序
	for (auto it = s.begin(); it != s.end(); it++)
	{
	    cout << *it << " ";
	}
	cout << endl;
	
	//逆向遍历，降序
	for (auto rit = s.rbegin(); rit != s.rend(); rit++)
	{
	    cout << *rit << " ";
	}
	cout << endl;
	
	return 0;
}

在这里插入图片描述

//非const迭代器
//正向迭代器
iterator begin();
iterator end();

//反向迭代器
reverse_iterator rbegin();
reverse_iterator rend();

//const迭代器
const_iterator cbegin();
const_iterator cend();

const_reverse_iterator crbegin();
const_reverse_iterator crend();

2.1.3 容量相关

//判空
bool empty() const;

//数据长度
size_t size();

//最大存储数据个数
size_t max_size();

2.1.4 修改相关

  1. 插入
//插入一个值
pair<iterator, bool> insert(const value_type& val);

//在指定迭代器位置插入一个值，返回新插入元素的迭代器
iterator insert(iterator pos, const value_type& val);

//插入一段迭代器区间
void insert(iterator first, iterator last);
  1. inset的值插入方式，会返回一个pair类型的值。
  2. pair为C++库中定义的一个类，这个类是将两个指定的不同数据类型的值进行了封装
  3. 存储到的两个数据在pair类型中分别是名为first与second的成员变量，第一个insert函数的返回值pair
    <1> 当新插入元素在set中没有值重复结点时，pair返回值中的second为true，first为返回新插入元素结点的迭代器
    <2> 当set存在相同值得结点时，pair返回值中得second为false，first为set中相同值结点得迭代器
  4. set中数据存储结点的key值不可以被改变，会破坏红黑树的结构
  1. 删除
//删除一个指定迭代器位置的数据
void erase(iterator pos);

//从set中删除一个为指定值的结点
size_t erase(const value_type& val);

//删除一段指定的迭代器区间
void erase(iterator first, iterator last);
  1. 删除指定迭代器位置的数据时，若迭代器不存在，会发生报错
  2. 删除set中key值为指定值的结点时，若结点不存在，不会发生报错

2.1.5 查找，计数与补充

  1. 查找
iterator find(const value_type& val) const;
  1. 查找set中key值为指定值的结点，若找到，返回此结点的迭代器，若未找到，返回end()。
  1. 计数
size_t count(const value_type& val) const;
  1. 统计set中key值为指定值结点的个数并返回，set中此接口是为了与multiset做统一。
  1. lower_bound与upper_bound
//指定一段区间，获得set中标识此段区间内的迭代器
//左边界
iterator lower_bound(const value_type& val) const;

//右边界
iterator upper_bound(const value_type& val) const;
  1. lower_bound获取区间左边界迭代器，会返回值大于等于val的迭代器
  2. upper_bound获取区间右边界迭代器，会返回值大于val的迭代器
  3. 区间边界需要左闭右开[left，right)，这与迭代器的遍历方式相关

2.2 multiset的接口与使用

  1. multiset的接口与使用方式都和set相同 ，只是multiset支持key值冗余，即相同值结点的插入
  2. 在查找时，若multiset中存在着多个key值相同的结点，其会优先返回第一个查找到的key值结点

3. map与multimap的接口与使用

3.1 map的接口与使用

3.1.1 map的使用补充

  1. <1> map的接口与set大体相同，两者之间的区别为其中数据存储结点，其存储的数据有所不同，set中存储key类型的结点，而map中存储<key，value>类型的结点。
    <2> 并因此，map一些接口的使用方式也set有所区别。
    <3> 因为存储数据模型的原因，其的查找，数据结构排列都是以key值为依照
  1. <1> map中存储数据结点都为pair类型的变量，first做key值，second做value
    <2> key值不可改变，而value可以修改
    <3> map容器其数据结点的value_type为pair<const key, value>
  1. map的迭代器，重载了operator->运算符，因此，可以使用it->first，it->second的方式访问数据结点内部存储的值。

3.1.2 插入与operator[]

  1. 插入
//插入一个值
pair<iterator, bool> insert(const value_type& val);

//在指定迭代器位置插入一个值
iterator insert(iterator pos, const value_type& val);

//插入一段迭代器区间内的值
template<class InputIterator>
void insert (InputIterator first, InputIterator last);
  1. pair类型对象的构造，可以采用传递有名对象与匿名对象的方式，除此之外，C++库中还存在着一个函数make_pair可以帮助我们构造一个指定pair类型的对象，方便我们的使用
  2. C++11中，支持了多参数构造函数的隐式类型转换
//make_pair的内部实现，根据传递参数推导类型构造pair对象
template <class T1,class T2>
pair<T1,T2> make_pair (T1 x, T2 y)
{
	return ( pair<T1,T2>(x,y) );
}

//方式1：
insert(make_pair(10, 10));

//方式2：多参数构造函数隐式类型转换方式
inset({10, 10});
  1. operator[] 运算符重载
  1. 我们传递key值，会返回map中key值所对应结点的value，且为引用类型，可修改。
value_type& operator[](const key& k);

//内部实现等同于
*((this->insert(make_pair(k, map_value_type())).first)).second

//简单模拟实现
V& operator[](const key& k)
{
	pair<const key, V> ret = insert(make_pair(k, V()));
	
	return ret.first->second;
}
  1. insert值插入的返回值为pair<iterator，bool>，取用此pair的first，即插入元素的iterator，并以此迭代器访问其对应结点的second
//使用operator[]可以直接插入统计修改，对应key值的value
int main()
{
	vector<string> v = {"苹果", "西瓜", "菠萝", "菠萝", "西瓜" ,"苹果" ,"苹果" };
    map<string, int> m;

    for (auto e : v)
    {
        m[e]++;
    }
	
	//等同于
	for(auto : v)
	{	
		//插入
		pair<iterator, bool> ret = m.insert(e).first;
		
		//存在，次数++
		if(ret.second == false)
		{
			(ret.first)->second++;
		}
	}

    for (auto e : m)
    {
        cout << e.first << " : " << e.second << endl;
    }
	
	return 0;
}

在这里插入图片描述

3.2 multimap接口与使用

  1. multimap与map的关系与multiset与set的关系类似，multimap也支持key冗余，在其他接口的使用上，与map相同。
  2. multimap不支持operator[]。

4. map与set相关练习

4.1 随机链表的复制（map实现）

  1. 题目链接：
    随机链表的复制
  2. 思路：映射关系的建立，前提：随机指针指向的是链表中的结点
class Solution 
{
public:
    Node* copyRandomList(Node* head) 
    {
        //记录映射关系，原链表与拷贝链表
        //随机指针都指向链表本身的结点
        //以原链表的随机指针指向结点，找到对应的拷贝结点
        
        //创建拷贝链表，并建立映射关系
        Node* cur = head;
        Node* newhead = nullptr;
        Node* newtail = nullptr;
        map<Node*, Node*> m;
        while(cur)
        {
            Node* newnode = new Node(cur->val);
            if(newhead == nullptr)
            {
                newhead = newnode;
                newtail = newhead;
            }
            else
            {
                newtail->next = newnode;
                newtail = newtail->next;
            }
            m[cur] = newnode;

            cur = cur->next;
        }

        //根据映射关系，调整随机链表
        cur = head;
        while(cur)
        {
            //当前拷贝结点的随机指针，指向原链表随机指针指向结点的映射结点
            m[cur]->random = m[cur->random];
            cur = cur->next;
        }

        return newhead;
    }
};

4.2 前K个高频单词

  1. 题目信息：
    在这里插入图片描述
  2. 题目链接：
    前K个高频单词
  3. 思路：数据小于32为插入排序，大于32为归并排序
class Solution 
{
public:
    struct comp1
    {
        bool operator()(const pair<string, int>& left, const pair<string, int>& right)
        {
            return (left.second > right.second) || (left.second == right.second && left.first < right.first);
        }
    };

    struct comp2
    {
        bool operator()(const pair<string, int>& left, const pair<string, int>& right)
        {   
            //归并排序，稳定，不会打乱map中的字典序
            //11归，22归，44归，...
            return left.second > right.second;
        }
    };

    vector<string> topKFrequent(vector<string>& words, int k) 
    {
        vector<string> ret;
        //向map中插入计数
        map<string, int> m;
        for(auto e : words)
        {
            m[e]++;
        }
        //向vector中插入结点数据并排序
        vector<pair<string, int>> v(m.begin(), m.end());
        //进行排序，快排（不稳定排序），归并（稳定排序）
        //pair的默认排序方式
        //构建的匿名对象comp()
        //sort(v.begin(), v.end(), comp1());
        stable_sort(v.begin(), v.end(), comp2());

        //map排序为字典序的升序
        //根据value排降序
        for(auto it = v.begin(); it != v.begin() + k; it++)
        {
            ret.push_back(it->first);
        }

        return ret;
    }
};

4.3 两个数组的交集

  1. 题目信息：
    在这里插入图片描述
  2. 题目链接：
    两个数组的交集
  3. 思路：
    <1> set去重查找
    <2> 同步算法
  4. 同步算法：（应用：云存储同步）
    <1> 将两方数据分别插入至一个set去重排序，可以同时找到数据的交集与差集
    <2> 从开始比对，小的为差集，相等的为交集，因为二者都有序，那么小的一定是差集
    <3> 若为差集，小的++，若为交集，二者同时++
//方法1：
class Solution 
{
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) 
    {
        vector<int> ret;
        //插入去重，不能重复
        set<int> s1;
        set<int> s2;
        for(auto e : nums1)
        {
            s1.insert(e);
        }

        for(auto e : nums2)
        {
            s2.insert(e);
        }

        for(auto e : s1)
        {
            if(s2.count(e))
            {
                ret.push_back(e);
            }
        }

        return ret;
    }
};

//方法2：
class Solution 
{
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) 
    {
        vector<int> ret;
        set<int> s1(nums1.begin(), nums1.end());
        set<int> s2(nums2.begin(), nums2.end());

        //同步算法
        auto it1 = s1.begin();
        auto it2 = s2.begin();
        while(it1 != s1.end() && it2 != s2.end())
        {
            if(*it1 == *it2)
            {
                ret.push_back(*it1);
                it1++;
                it2++;
            }
            else if(*it1 < *it2)
            {
                it1++;
            }
            else
            {
                it2++;
            }
        }

        return ret;
    }
};

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/571003.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

小孩子不懂事，写着玩的

小孩子不懂事，写着玩的

目录 Web攻防 特有漏洞 ASP安全 ASPX&#xff08;.NET&#xff09;安全 PHP安全 JavaWeb安全 JS&#xff0c;Node.js安全 Java安全 Python安全 通用漏洞 SQL注入 MySQL-root高权限读写注入 PostgreSQL-高权限读写注入 MSSQL-sa高权限读写执行注入 SQL注入体系 o…
阅读更多...
QWidget 类

QWidget 类

QWidget 类中包括框架的属性 QWidget 类中不包括框架的属性 总结：可使用以下两种方法设置部件的位置和大小 ①、通常使用 move()设置部件的位置，使用 resize()设置部件的大小。 ②、使用 setGeometry()函数同时设置部件的位置和大小。 ③、无法为部件指定包含边框在内的大…
阅读更多...
C语言操作符和关键字

C语言操作符和关键字

文章目录 操作符单目操作符sizeof&#xff08;类型&#xff09;强制类型转换 关系操作符、逻辑操作符、条件操作符逗号表达式 常见关键字typedefstaticstatic修饰局部变量static修饰全局变量static修饰函数 register寄存器关键词define定义常量和宏 操作符 单目操作符 C语言中…
阅读更多...
echarts bar图表实现多个label显示

echarts bar图表实现多个label显示

2024.0.23今天我学习了使用bar组件&#xff0c;可以渲染多个label显示的效果&#xff0c;如&#xff1a; 当我们有一个这样的图表时&#xff0c;根据需求需要在 这上面的顶部再显示一个空置床位数占用床位数的合计总值&#xff0c;如果直接添加一个label肯定是不行&#xff0c;…
阅读更多...
深度学习-线性代数

深度学习-线性代数

目录 标量向量矩阵特殊矩阵特征向量和特征值 标量由只有一个元素的张量表示将向量视为标量值组成的列表通过张量的索引来访问任一元素访问张量的长度只有一个轴的张量&#xff0c;形状只有一个元素通过指定两个分量m和n来创建一个形状为mn的矩阵矩阵的转置对称矩阵的转置逻辑运…
阅读更多...
[MYSQL索引优化] 分页查询优化

[MYSQL索引优化] 分页查询优化

这里一共介绍两种常见的分页索引优化技巧,let go! 示例表: CREATE TABLE t_product (id int(0) NOT NULL,pname varchar(200) CHARACTER SET utf8mb4 COLLATE utf8mb4_0900_ai_ci NULL DEFAULT NULL,price double(7, 2) NULL DEFAULT 0.00,promoteSales varchar(200) CHARA…
阅读更多...
Linux进程详解三：进程状态

Linux进程详解三：进程状态

文章目录 进程状态Linux下的进程状态运行态-R阻塞态浅度休眠-S深度睡眠-D暂停状态-T暂停状态-t 终止态僵尸-Z死亡-X 孤儿进程 进程状态 进程的状态&#xff0c;本质上就是一个整型变量&#xff0c;在task_struct中的一个整型变量。 状态的存在决定了你的后续行为动作。 Linu…
阅读更多...
DRF： 序列化器、View、APIView、GenericAPIView、Mixin、ViewSet、ModelViewSet的源码解析

DRF： 序列化器、View、APIView、GenericAPIView、Mixin、ViewSet、ModelViewSet的源码解析

前言&#xff1a;还没有整理&#xff0c;后续有时间再整理&#xff0c;目前只是个人思路&#xff0c;文章较乱。 注意路径匹配的“/” 我们的url里面加了“/”&#xff0c;但是用apifox等非浏览器的工具发起请求时没有加“/”&#xff0c;而且还不是get请求&#xff0c;那么这…
阅读更多...
C++字符串中单词的提取以及按符号分隔

C++字符串中单词的提取以及按符号分隔

句子中的单词提取利用stringstream即可 如果要分割需配合getline使用 两者前提都是要先转化为字符串流。
阅读更多...
Linux套接字编程详解

Linux套接字编程详解

Linux套接字编程 预备知识IP地址和MAC地址套接字结构网络字节序 UDP套接字编程服务端代码客服端代码 TCP 套接字守护进程 计算器模块1 日志头文件序列化和反序列化 预备知识 IP地址和MAC地址 MAC地址用来在局域网中标识唯一主机 Ip地址用于在广域网中标识唯一主机 &#xff0…
阅读更多...
李廉洋：4.24-4.25现货黄金，WTI原油区间震荡，走势分析。

李廉洋：4.24-4.25现货黄金，WTI原油区间震荡，走势分析。

黄金消息面分析&#xff1a;金银近日回调。随着伊朗方面淡化以色列最新反击&#xff0c;中东地区局势没有进一步发酵下&#xff0c;风险溢价下降金银出现较大幅度调整。由于近期高于预期的通胀数据&#xff0c;降息预期持续降温。昨日疲软的美国PMI以及以色列在加沙攻击的加剧支…
阅读更多...
【Unity】AssetBundle加载与卸载

【Unity】AssetBundle加载与卸载

unity官方apiAssetBundle-LoadFromFileAsync - Unity 脚本 API 异步加载AB包 using UnityEngine; using System.Collections; using System.IO;public class LoadFromFileAsyncExample : MonoBehaviour {IEnumerator Start(){var bundleLoadRequest AssetBundle.LoadFromFil…
阅读更多...
消息服务应用1——java项目使用websocket

消息服务应用1——java项目使用websocket

在当前微服务项目中&#xff0c;由于业务模块众多&#xff0c;消息服务的使用场景变得异常活跃。而WebSocket由于其自身的可靠性强&#xff0c;实时性好&#xff0c;带宽占用更小的优势&#xff0c;在实时通讯应用场景中独占鳌头&#xff0c;加上HTML5标准的普及流行&#xff0…
阅读更多...
OpenCompass 大模型评测实战——笔记

OpenCompass 大模型评测实战——笔记

OpenCompass 大模型评测实战——笔记 一、评测1.1、为什么要做评测1.2、如何通过能力评测促进模型发展1.2.1、面向未来拓展能力维度1.2.2、扎根通用能力1.2.3、高质量1.2.4、性能评测 1.3、评测的挑战1.3.1、全面性1.3.2、评测成本1.3.3、数据污染1.3.4、鲁棒性 二、OpenCompas…
阅读更多...
java-junit单元测试

java-junit单元测试

问题 Junit框架 代码 工具类 // 工具类 public class StringUtils {// 获取字符串的最大下标public static int getMaxIndex(String str){// 这个地方是有问题的&#xff0c;应该是str.length() - 1 也没有进行str是否为空的判断return str.length() ;} }测试类 测试类类名&…
阅读更多...
vcontact2：病毒聚类（失败）

vcontact2：病毒聚类（失败）

Bitbucket 安装 mamba create --name vContact2 biopython1.78 mamba install -c bioconda vcontact20.11.3vim ~/envs/vContact2/lib/python3.9/site-packages/vcontact2/exports/summaries.py 把 np.warnings.filterwarnings(ignore) 改成 import warnings warnings.filte…
阅读更多...
递归、搜索与回溯算法：FloodFill 算法

递归、搜索与回溯算法：FloodFill 算法

例题一 算法思路&#xff1a; 可以利⽤「深搜」或者「宽搜」&#xff0c;遍历到与该点相连的所有「像素相同的点」&#xff0c;然后将其修改成指定的像素即可。 全局变量&#xff1a; int dx[4] { 0,0,1,-1 }, dy[4] { 1,-1,0,0 }; int m, n; int precolor;//记录原先的颜色…
阅读更多...
【Linux】日志分析与管理

【Linux】日志分析与管理

作为一个运维&#xff0c;如果不会看日志&#xff0c;就好比是冬天刚刚用热水泡完了脚&#xff0c;接着就立马让人把水喝掉。 目录 一、Inode介绍 1.1 什么是inode 1.2 inode表内容 1.3 查看inode号的方式 二、日志分析 2.1 日志的用途 2.2 日志的分类 2.3 日志级别 2…
阅读更多...
Flink学习（七）-单词统计

Flink学习（七）-单词统计

前言 Flink是流批一体的框架。因此既可以处理以流的方式处理&#xff0c;也可以按批次处理。 一、代码基础格式 //1st 设置执行环境 xxxEnvironment env xxxEnvironment.getEnvironment;//2nd 设置流 DataSource xxxDSenv.xxxx();//3rd 设置转换 Xxx transformation xxxDS.…
阅读更多...
简述MASM宏汇编

简述MASM宏汇编

Hello , 我是小恒不会java。今天写写x86相关底层的东西 寄存器 8086由BIU和EU组成 8088/8086寄存器有14个。8通用&#xff0c;4段&#xff0c;1指针&#xff0c;1标志 8个通用寄存器&#xff1a;这些寄存器可以用来存储任意类型的数据&#xff0c;包括整数、地址等。8086有8个…
阅读更多...
最新文章

Copyright @ 2022~2023