当前位置： 首页 > article >正文

map和set的使用（一）详解

article 2025/1/22 20:29:32

文章目录

  • 序列式容器和关联式容器
  • map和set的介绍
  • set
    • 构造和迭代器遍历和insert
    • find
    • erase
    • swap
    • clear
    • count
    • lower_bound和upper_bound
    • multiset和set的对比
  • set的二个题目
    • 题目解析
    • 算法原理
    • 代码
    • 介绍一个找差集的算法
    • 同步算法
    • 题目解析
    • 算法原理
    • 代码
  • map
    • 构造
    • 遍历
    • initiaizer_list

序列式容器和关联式容器

  • 序列式容器在逻辑上是线性的，在物理上不一定连续，它们的数据之间没有太大的关联，比如交换两个位置的数，依旧是序列式容器，比如vector,list,deque等
  • 关联式容器在逻辑上是非线性的，两个位置的关系是紧密相关的，比如二叉搜索树，随意交换两个位置就破坏了这棵树的结构

map和set的介绍

map和set底层是红黑树，红黑树是平衡二叉搜索树，平衡二叉搜索树接近完全二叉树的结构，但不是完全二叉树，查找效率提高了，等于logN次，set是key的场景，map是key/value的场景。

set

支持增删查，不支持改，修改会改变树的性质

构造和迭代器遍历和insert

在这里插入图片描述

int main()
{
	// 降序排序+去重 Greater > 
	set<int, greater<int>> t;
	// 升序排序+去重 Less <
	// set<int> t;
	t.insert(5);
	t.insert(7);
	t.insert(2);
	t.insert(5);

	// set<int>::iterator it = t.begin();
	auto it = t.begin();
	while(it != t.end())
	{
		// set不管什么迭代器都不支持修改
		// 修改会改变其内部结构
		// 按二叉搜索树的排序,中序，升序排序
		// *it = 10;
		cout << *it << " ";
		++it;
	}
	cout << endl;

	// initializer list 相同的值会插入失败
	t.insert({ 1,2,9,2,7 });
	for (auto e : t)
	{
		cout << e << " ";
	}
	cout << endl;

	// void insert(initializer_list<value_type> ls);
	set<string> strset = { "sort","insert","add" };
	// 语法上隐式类型转换生成临时对象，临时对象拷贝构造strset
	// 编译器直接优化为构造
	// set<string> strset({ "sort","insert","add" });
	// 语法上构造
	for (auto& e : strset)
	{
		cout << e << " ";
	}
	cout << endl;

	return 0;
}

find

在这里插入图片描述

// 算法库的find O(N)
auto pos = find(t.begin(), t.end(), x);
// set的find O(logN)
auto pos = t.find(x);

erase

在这里插入图片描述

  1. 删除某个位置的迭代器
  2. 删除某个值，返回成功删除数据的个数，删除失败返回0，为了兼容multiset(有数据冗余的set),这里面有多个相同的x
  3. 删除迭代器区间
    迭代器失效：
    1.删除的是根节点或只有一个孩子的节点，父亲节点已经链接其他节点了，去访问删除的节点是野指针，节点已经变了，意义变了
    2.删除的节点是有两个孩子的节点，替代法删除，把替代的节点删除，原来要删的节点的位置的迭代器失效，访问会崩溃，节点已经变了，意义变了
    在这里插入图片描述
int main()
{
	// 1.删除某个位置的迭代器
	set<int> t = { 1,2,93,403,43 };
	for (auto e : t)
	{
		cout << e << " ";
	}
	cout << endl;

	// 删除最小值 [first,end),升序排序
	t.erase(t.begin());
	for (auto e : t)
	{
		cout << e << " ";
	}
	cout << endl;

	// 2.删除某个值
	int x;
	/*cin >> x;
	int num = t.erase(x);
	if (num == 0)
	{
		cout << num << "不存在" << endl;
	}
	else
	{
		cout << num << "删除成功" << endl;
	}
	cout << endl;

	for (auto e : t)
	{
		cout << e << " ";
	}
	cout << endl;*/

	// 3.删除一个迭代器区间
	cin >> x;
	auto pos = t.find(x);
	if(pos != t.end())
	{
		// 删除这个节点后,该点迭代器失效
		t.erase(pos);
		// 不要访问,vs强制检查会崩溃
		cout << *pos << endl;
		// 访问Node节点
	}
	else
	{
		cout << "不存在" << endl;
	}

	for (auto e : t)
	{
		cout << e << " ";
	}
	cout << endl;

	return 0;
}

swap

交换两个树的根节点
在这里插入图片描述

clear

清掉数据不清空间
在这里插入图片描述

count

value_type其实是为multiset准备的
功能：这个值在的话返回1，不在返回0
在这里插入图片描述

cin >> x;
if (t.count(x))
{
	cout << x << "在" << endl;
}
else
{
	cout << x << "不在" << endl;
}

lower_bound和upper_bound

lower_bound和upper_bound底层是按照二叉搜索树的逻辑进行查找的，logN
在这里插入图片描述

int main()
{
	std::set<int> myset;
	for (int i = 1; i < 10; i++)
	{
		myset.insert(i * 10);
		// 10 20 30 40 50 60 70 80 90
	}
	
	for (auto e : myset)
	{
		cout << e << " ";
	}
	cout << endl;


	 返回 >= 30
	//auto lowit = myset.lower_bound(30);
	 返回 > 50
	//auto upit = myset.upper_bound(50);
	 30 40 50 


	// 返回 >= 25
	auto lowit = myset.lower_bound(25);
	// 返回 > 55
	auto upit = myset.upper_bound(55);
	// 30 40 50 
	
	// 删除这段区间的值, 迭代器区间的都是[)
	myset.erase(lowit, upit);
	for (auto e : myset)
	{
		cout << e << " ";
	}
	cout << endl;

	return 0;
}

multiset和set的对比

  • multiset和set都在set头文件下，multiset允许键值冗余,insert/find/count/erase都围绕着支持值冗余有所差异
    在这里插入图片描述
int main()
{
	// 排序但是不去重
	multiset<int> t = { 1,2,1,2,342 };
	auto it = t.begin();
	while (it != t.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	 有多个x的话,find查找的是中序的第一个
	int x;
	cin >> x;
	//auto pos = t.find(x);
	//while (pos != t.end() && *pos == x)
	//{
	//	cout << *pos << " ";
	//	++pos;
	//}
	//cout << endl;

	//auto pos = t.find(x);
	//while (pos != t.end() && *pos == x)
	//{
	//	pos = t.erase(pos);
	//	// 删除后返回当前位置的下一个迭代器
	//}
	//cout << endl;

	cout << t.count(x) << endl;

	t.erase(x);
	// erase把所有x都删除

	it = t.begin();
	while (it != t.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	// 返回x的个数
	cout << t.count(x) << endl;

	return 0;
}

set的二个题目

题目链接

题目解析

在这里插入图片描述

算法原理

在这里插入图片描述

代码

class Solution 
{
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) 
    {
        // 用set进行去重+排序
        set<int> s1(nums1.begin(),nums1.end());
        set<int> s2(nums2.begin(),nums2.end());

        vector<int> ret;
        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)
            {
                ++it2;
            }
            else
            {
                ++it1;
            }
        }
        return ret;
    }
};

介绍一个找差集的算法

差集：是一个集合有，另一个集合没有的数据（去除两个集合共同有的数据）
在这里插入图片描述

同步算法

在这里插入图片描述

题目解析

题目链接
在这里插入图片描述

算法原理

让节点一个一个地插入set中，如果set中第一次存在一个重复的节点的话，返回这个重复的节点就是循环的开始
在这里插入图片描述

代码

class Solution 
{
public:
    ListNode *detectCycle(ListNode *head) 
    {
        set<ListNode*> p;
        ListNode* cur = head;
        while(cur)
        {
            if(p.count(cur))
            return cur;
            else
            p.insert(cur);

            cur = cur->next;
        }
        return nullptr;
    }
};

map

map也有map和multimap之分
map支持修改，但是修改的是value的值，迭代器也支持修改value
key->key
T->value
在二叉搜索树那里就是把两个参数分开放
在map这里是把两个参数放在一个pair中，封装了一层
第一个参数是key，第二个参数是value
在这里插入图片描述

构造

在这里插入图片描述

int main()
{
	// 1.构造对象pair插入dict(有名对象)
    map<string, string> dict;
    pair<string, string> kv1("auto", "一");
    dict.insert(kv1);

    // 2.匿名对象
    dict.insert(pair<string, string>("string", "二"));

    // 3.make_pair模版
    dict.insert(make_pair("vector", "三"));

    // 4.C++11
    dict.insert({ "map","三" });

    // 插入时只看key,value不相等时不会更新
    // key相等时插入失败,map是不允许冗余的
    dict.insert({ "map","三二" });
    
	return 0;
}

遍历

结构体指针用->
对象用 .
map不允许冗余，unordered_map允许冗余

map<string, string>::iterator it = dict.begin();
while (it != dict.end())
{
	// 只支持修改value,不支持修改key
	// first不支持修改
	// 底层存的是const first 
	// 这里是const string
	// it->first += 'x';
	it->second += 'x';

	// map不支持*it
	// cout << *it << " ";
	// cout << (*it).first << ":" << (*it).second << endl;
	 cout << it->first << ":" << it->second << endl;
    //cout << it.operator->()->first << ":" << it.operator->()->second << endl;

	 // operator* 返回数据的引用 pair
	 // operator-> 返回数据的指针 pair*

	++it;
}
cout << endl;

initiaizer_list

都用第一种，不会用第二种的

// 1
map<string, string> dict = { {"left", "左边"}, {"right", "右边"}, {"insert", "插入"},{ "string", "字符串" } };
// 2
pair<string, string> kv1("string", "一");
map<string, string> dict = { kv1, pair<string, string>("一", "二") };

用最外层括号给给initiaizer_list，里面的{}隐式类型转换为pair的两个参数
在这里插入图片描述


http://www.kler.cn/a/513954.html

相关文章：

  • 2. CSS 中的单位
  • [HCTF 2018]WarmUp
  • 二十七、资源限制-LimitRange
  • EXCEL的一些用法记录
  • 前端开发Web
  • 【深度学习】利用Java DL4J 训练金融投资组合模型
  • K8s UI工具 Kuboard 安装
  • Mysql视图（学习自用）
  • 记一次 .NET某数字化协同管理系统 内存暴涨分析
  • Day 14 卡玛笔记
  • Java设计模式 十一 外观模式 (Facade Pattern)
  • django使用踩坑经历
  • springboot基于前后端分离的摄影知识网站
  • 新书速览|算法竞赛入门笔记
  • 吴恩达深度学习——建立逻辑回归分类器识别猫
  • html简单项目案例
  • 私有IP、VLAN和VPC，分别适合哪些场景你知道吗？
  • R语言的图形用户界面
  • Android 13 灭屏音乐播放问题解决与优化建议
  • 【MySQL】超详细MySQL常用日期格式转换函数、字符串函数、聚合函数（最新版）
  • 读取配置文件方式
  • Docker网段和服务器ip冲突导致无法访问网络的解决方法
  • 如何使用python技术爬取下载百度文库文档？
  • “深入浅出”系列之算法篇：（2）openCV、openMV、openGL
  • 【vim】vim怎样直接跳转到某行？
  • dl学习笔记：（7）完整神经网络流程