【C++】关联式容器——mapset的使用

文章目录

  • 1.关联式容器和键值对
    • 1. 关联式容器
    • 2. 键值对
  • 2. 树形结构的关联式容器——set
    • 1. 模版参数列表
    • 2. 默认成员函数
    • 3. 迭代器
    • 4.容量相关操作
    • 5.modify
    • 6.其他操作接口
  • 3. 树形结构的关联式容器——map
    • 1. 默认成员函数
    • 2. 迭代器
    • 3. 容量与数据访问
    • 4.数据修改
    • 5. 其他操作接口

1.关联式容器和键值对

1. 关联式容器

在之前的学习中，我们学习了vector，list，deque等容器，这些容器被统称为序列式容器，因为其底层是线性的数据结构，内部存放的是元素本身，那么关联式容器是什么呢？关联式容器也是用来存放数据的，只是关联式容器中存放数据是以<key,value>键值对的方式存储的，在数据检索的时候效率更高。

其实也可以理解成使用了更高级的数据结构，除了单纯的存储数据外，加上了一些特殊的存储逻辑。比如map和set就使用了二叉搜索树这种高级的数据结构。

STL中一共实现了两种不同类型的关联式容器：树形结构和哈希结构。

其中树形结构的容器有：map、multimap、set、multiset四个。其底层都是使用了**平衡搜索树（红黑树）**实现的，容器中的元素是一个有序的序列。

2. 键值对

用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息。

现在要建立一个英汉互译的字典，那该字典中必然有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该应该单词，在词典中就可以找到与其对应的中文含义。

在SGI- STL中对于键值对pair的定义如下

template <class T1, class T2>
struct pair
{
	typedef T1 first_type;
	typedef T2 second_type;
	T1 first;   //key
	T2 second;  //value
	pair() : first(T1()), second(T2())  //默认构造
	{}
	pair(const T1& a, const T2& b) : first(a), second(b) //构造函数
	{}
};

其中一般使用first表示key，second表示value。

make_pair

按照一般的调用方式，如果我们想创建一个pair的匿对象，需要使用以下代码

pair<string,string>("apple","苹果");

写了这么长一串就是为了创建一个匿名的pair对象多少是有点麻烦的，所以干脆就封装出一个函数模版make_pair,用于快速创建出一个pair对象，使用方式

make_pair("apple","苹果");//调用此函数就返回一个pair对象

在底层，这个函数是这样实现的

template<class T1, class T2>
pair<T1,T2> make_pair(T1 first, T2 second)
{
  	return (pair<T1,T2>(first,second));//本质上还是调用了pair的构造函数
}

2. 树形结构的关联式容器——set

首先还是老样子，挂一下set的使用文档

image-20230512185722599

上述的英文看起来可能对某些同学很吃力，所以我们总结一下

  1. set是按照特定顺序存储唯一元素的容器，里面不会出现重复的内容（可以用来去重）
  2. set虽然是采用了键值对的方式存储数据，但是在set中，key==value，可以对照二叉搜索树中的K模型来看。所以在插入数据时只需要插入value即可，不需要构造键值对。
  3. set中的元素一般是const修饰的，不能被修改，但是可以插入或者删除元素
  4. set中的数据的排序方式是可以自己传入的，默认使用的是仿函数less<T>。
  5. set通常比unordered_set更慢，通过其key访问单个元素，但允许根据其顺序对子集进行直接迭代。
  6. set中查找某个元素的时间复杂度为log2n

1. 模版参数列表

接下来我们来看看set的模版参数列表

image-20230513093220748

第一个参数是其内部存放元素类型，实际在其内部存放的是<value,value>键值对；第二个参数看到是Compare就知道是仿函数啦，这是用来决定set中数据的排序方式的，默认按照小于来排序；Alloc是set中元素空间的管理方式，默认使用STL提供的空间配置器。

2. 默认成员函数

1. 构造函数

image-20230513095109454

set的构造方式就非常简洁，一个默认构造，一个迭代器区间构造，还有一个拷贝构造

void Test1()
{
    set<int> s1;//默认构造
    vector<int> v = {1,3,5,2,6,3,5,1};
    set<int> s2(v.begin(), v.end());//迭代器区间构造
    set<int> s3(s2);//拷贝构造
    cout << "s1:";
    for(auto e : s1)
    {
        cout << e << " ";
    }
    cout << endl;
    cout << "s2:";
    for(auto e : s2)
    {
        cout << e << " ";
    }
    cout << endl;
    cout << "s3:";
    for(auto e : s3)
    {
        cout << e << " ";
    }
    cout << endl;
}

image-20230513100128756

2. 析构函数和赋值重载

很显然，在构造set对象的时候有资源申请，所以在析构函数的时候，需要进行资源释放。

析构函数和赋值重载的使用与其他容器非常相似，这里就不赘述了。

3. 迭代器

image-20230513100951008

set迭代器的使用与其他容器的迭代器一样

void Test2()
{
    vector<int> v = {1,3,5,2,6,3,5,1};
    set<int> s(v.begin(), v.end());//使用set存放之后可以去重
    set<int>::iterator it1 = s.begin();
    cout << "正向迭代器：";
    while(it1 != s.end())
    {
        cout <<*it1 << " ";
        ++it1;
    }
    cout << endl;
    set<int>::reverse_iterator it2 = s.rbegin();
    cout << "反向迭代器：";
    while (it2 != s.rend())
    {
        cout << *it2 << " ";
        ++it2;
    }
    cout << endl;
}

image-20230513101908799

4.容量相关操作

函数原型说明
bool empty() const;判断set是否为空，如果为空返回true，否则返回flase
size_t size() const;返回容器的数据个数，类型为size_t(unsigned int)
size_t max_size() const;返回容器中最多能够存放的数据个数

5.modify

1.insert

向set中插入一个对象，并且能够保持结构不变，依然符合平衡搜索树

image-20230513121025994

这里注意一下：第一个插入返回的是一个pair类型的对象，其中pair的第一个成员是一个迭代器，其指向的是插入的元素在set中的位置，第二个成员是bool类型，如果成功插入了数据就返回true，若set中已经存在这个数据，就会插入失败，其中的值就是false。

所以这里insert能够做到两个功能：查找和插入。

2.erase

在set中删除一个数据，并且结构保持不变

image-20230513121113366

void Test3()
{
    vector<int> v = {1,3,5,2,6,3,5,1};
    set<int> s(v.begin(), v.end());//使用set存放之后可以去重
    cout << "before insert:";
    auto it1 = s.begin();
    while(it1 != s.end())
    {
        cout <<*it1 << " ";
        ++it1;
    }
    cout << endl;
    //insert
    auto a1 = s.insert(4);
    auto a2 = s.insert(4);
    cout << "after insert:";
    it1 = s.begin();
    while(it1 != s.end())
    {
        cout <<*it1 << " ";
        ++it1;
    }
    cout << endl;
    cout << "a1:" << *(a1.first) << ":" << a1.second << endl;
    cout << "a2:" << *(a2.first) << ":" << a2.second << endl;
    cout << "---------------------------" << endl;
    s.erase(4);
    cout << "after erase";
    it1 = s.begin();
    while(it1 != s.end())
    {
        cout <<*it1 << " ";
        ++it1;
    }
    cout << endl;
}
image-20230513123204561

3.swap

交换两个set对象，效率比算法库里实现的高

image-20230513121419860

4.clear

清除set对象中所有数据，但是不删除set对象

image-20230513121444821

6.其他操作接口

1.find

查找set中某个元素，并返回迭代器，如果不存在，就返回end()。

image-20230513123541264

2.lower_bound

以传入的值为下限，返回一个迭代器

image-20230513123800339

3.upper_bound

以传入的值为上限，返回一个迭代器

image-20230513123917369

void Test4()
{
    set<int> s;
    for(int i = 1; i < 10; ++i)
        s.insert(10 * i);
    auto it = s.find(30);
    if(it != s.end())
        s.erase(it);
    for(const auto& e : s)
    {
        cout << e << " ";
    }
    cout << endl;
    auto it1 = s.lower_bound(40);
    auto it2 = s.upper_bound(70);//注意，这里返回的是70的下一个位置
    s.erase(it1,it2);//这里的删除的迭代器区间是前闭后开的
    for(const auto& e : s)
    {
        cout << e << " ";
    }
    cout << endl;
}
image-20230513124615330

除了set之外，在set头文件中还包含了一个容器：multisetmultiset使用文档

multiset与set极其相似，唯一的不同点就是multiset支持在内部插入重复的数据。

void Test5()
{
    vector<int> v = {1,3,5,2,6,3,5,1};
    set<int> s(v.begin(), v.end());
    multiset<int> ms(v.begin(), v.end());
    cout << "     set:";
    for(const auto& e : s)
    {
        cout << e << " ";
    }
    cout << endl;
    cout << "multiset:";
    for(const auto& e : ms)
    {
        cout << e << " ";
    }
    cout << endl;
}
image-20230513133733679

这里补充一个在set里面没有介绍的接口:count：计算val在multiset中的个数，也可以用来判断set中是否存在该元素。

image-20230513134156562

3. 树形结构的关联式容器——map

map使用文档

image-20230513134546858

  1. map是关联式容器它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素
  2. 在map中key是排序和唯一标识的元素，value中存放的是与key相关的内容，key和value的类型不需要相同；在map中存放的类型不是key也不是value，而是一个pair对象，pair对象中的内容是key和value，在实现上是一个typedef，typedef pair<const key,value> value_type.
  3. 在map内部的元素存放位置严格按照key的强弱顺序排列，强弱顺序的比较规则又仿函数Compare控制，默认的仿函数是less
  4. map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)
  5. map支持下表访问符[]，即通过key访问到value
  6. map的底层是一个平衡搜索树(红黑树)

1. 默认成员函数

image-20230513141202305

image-20230513141248409

image-20230513141316566

默认成员函数和set的用法非常相似，这里就不过多介绍了

2. 迭代器

image-20230513143742429

迭代器的使用方式也是极其相似的，也就不多介绍了，有需要的朋友直接看文档即可

3. 容量与数据访问

函数原型解释
bool empty() const判断map是否为空，如果为空，返回true，否则返回false
size_type size() const返回map中的元素个数，数据类型是size_type(unsigned int)
mapped_type& operator[] (const key_type& k);返回key对应的value，这个value可以被修改

在map中有一个独特的数据访问方式：map中重载了operator[]操作符，可以通过key作为类似下标的方式访问到对应的value

对于这个特性，这里还有一种很新奇的的用法

/统计单词出现次数
vector<string> vs = {"apple", "banana", "apple","orange", "watermelon", "orange", "apple", "watermelon", "watermelon", "apple", "orange", "apple"};
map<string,int> m1;
for(const auto& e : vs)
{
  m1[e]++;
}

🙋当key不在map中时，通过operator获取对应value时会发生什么问题?

image-20230513153214546

通过查看文档可知，如果使用的key不在map里面的时候，会自动调用insert函数插入一个key，然后使用value的默认构造创建一个值，构造一个pair对象，然后插入到map中。与其不同的是，at接口遇到这种情况的时候就会抛出异常。

这个原因也就是上面的新奇用法的原理。

void Test6()
{
    vector<string> vs = {"apple", "banana", "apple","orange", "watermelon", "orange", "apple", "watermelon", "watermelon", "apple", "orange", "apple"};
    map<string,int> m1;//默认构造
    for(const auto& e : vs)//统计次数的方式
    {
        m1[e]++;
    }
    map<string,int> m2(m1.begin(), m1.end());//迭代器区间
    map<string,int> m3(m1);//拷贝构造
    m1 = m3;//赋值重载
    cout << "---------------m1---------------" << endl;
    for(const auto& e : m1)
    {
        cout << e.first << ":" << e.second << endl;
    }
    cout << "---------------m2---------------" << endl;
    for(const auto& e : m2)
    {
        cout << e.first << ":" << e.second << endl;
    }
    cout << "---------------m3---------------" << endl;
    for(const auto& e : m3)
    {
        cout << e.first << ":" << e.second << endl;
    }
}
image-20230513154028887

4.数据修改

image-20230513153537623

数据的修改部分，只看接口的话，发现和set基本一致，用法之类的也都是一致的，没有什么特殊情况，所以也就不多说了。直接上示例：

void Test7()
{
    map<string, string> dict;
    dict.insert(make_pair("left", "左边"));
    dict.insert(make_pair("right", "右边"));
    dict.insert(make_pair("string", "字符串"));
    dict.insert(make_pair("sort", "排序"));
    for(const auto& e : dict)
    {
        cout << e.first << ":" << e.second << endl;
    }
    cout << "------after erase------" << endl;
    dict.erase("insert");
    for(const auto& e : dict)
    {
        cout << e.first << ":" << e.second << endl;
    }
    cout << "------after swap------" << endl;
    map<string, string> dict_swap;
    dict_swap.insert(make_pair("swap", "交换"));
    dict.swap(dict_swap);
    cout << "dict:" << endl;
    for(const auto& e : dict)
    {
        cout << e.first << ":" << e.second << endl;
    }
    cout << "dict_swap:" << endl;
    for(const auto& e : dict_swap)
    {
        cout << e.first << ":" << e.second << endl;
    }
    cout << "------after clear------" << endl;
    dict.clear();
    for(const auto& e : dict)
    {
        cout << e.first << ":" << e.second << endl;
    }
}
image-20230513155359566

5. 其他操作接口

image-20230513155509165

这里的操作接口与set的接口完全一样，就不过多赘述了。

<map>头文件中还包含了multimap这个容器，同样的multimap和map的用法完全基本相同，唯一的区别就是multimap允许重复的key值存在。和set与miltiset的关系一样，有需要的可以去对照上文的set和multiset。

本节完。。。

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

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

相关文章

初识C语言

初识C语言

1. 初识C语言 C语言是一门通用计算机编程语言&#xff0c;广泛应用于底层开发。 C语言是一门面向过程的计算机编程语言&#xff0c;它与C,Java等面向对象的编程语言有所不同。 第一个C语言程序&#xff1a; #include<stdio.h>int main(void) {printf("hello worl…
阅读更多...
MyBatis基础知识点总结

MyBatis基础知识点总结

MyBatis了解 MyBatis 是什么&#xff1f; MyBatis 是支持定制化 SQL、存储过程以及高级映射的优秀的持久层框架 MyBatis 避免了几乎所有的 JDBC 代码和手动设置参数以及获取结果集 MyBatis 可以使用简单的XML或注解用于配置和原始映射&#xff0c;将接口和Java的 POJO&#x…
阅读更多...
JVM-内存结构

JVM-内存结构

✅作者简介&#xff1a;热爱Java后端开发的一名学习者&#xff0c;大家可以跟我一起讨论各种问题喔。 &#x1f34e;个人主页&#xff1a;Hhzzy99 &#x1f34a;个人信条&#xff1a;坚持就是胜利&#xff01; &#x1f49e;当前专栏&#xff1a;JVM &#x1f96d;本文内容&…
阅读更多...
Mybatis一级缓存详解

Mybatis一级缓存详解

目录 一级缓存 一级缓存的组织 一级缓存的生命周期 一级缓存的工作流程 Cache接口的设计以及CacheKey的定义 一级缓存的性能分析 一级缓存与Spring 事务一级缓存存在的弊端 官方文档分析 Spring通过Mybatis调用数据库的过程 一级缓存 对于会话&#xff08;Session&am…
阅读更多...
chanmama响应数据解析

chanmama响应数据解析

0x00目标url aHR0cHM6Ly93d3cuY2hhbm1hbWEuY29tL2F1dGhvckRldGFpbC85OTI0MjExODcxOC9wcm9tb3Rpb24 0x01接口分析 简单的get 但是返回数据被加密了 这里我们就来想想怎么解密这些数据。首先后端发来的数据是加密的&#xff0c;但是我们在前端看到的可不是加密后的数据。前端…
阅读更多...
什么是零拷贝？

什么是零拷贝？

零拷贝 什么是零拷贝 零拷贝指的是&#xff0c;从一个存储区域到另一个存储区域的copy任务无需CPU参与就可完成。零拷贝的底层是 通过DMA总线技术实现的。零拷贝与具体的编程语言无关&#xff0c;完全依赖于OS&#xff0c;OS支持就可使用&#xff0c;不支持 设置了也不起作用…
阅读更多...
大厂视频面试，因为截屏作废

大厂视频面试，因为截屏作废

大厂视频面试现在这么严格了么&#xff1f;无意间按到截屏直接显示面试作废&#xff0c;好在最后和HR解释了下&#xff0c;再约时间重新面。 作为一个面试过3、4家大厂&#xff0c;现在在鹅厂工作的过来人来说&#xff0c;上面遇到的这个问题是AI面&#xff0c;不用太担心&…
阅读更多...
笔记本电脑开机黑屏没反应怎么办？

笔记本电脑开机黑屏没反应怎么办？

笔记本电脑开机黑屏没反应怎么办&#xff1f;有用户电脑开机之后&#xff0c;桌面会变成黑屏显示。而且是常常都会出现这样的问题&#xff0c;非常影响自己的电脑使用体验。那么遇到这个问题要怎么去进行问题的解决呢&#xff1f;来看看以下的解决方法吧。 准备工作&#xff1a…
阅读更多...
玩游戏时突然弹出”显示器驱动程序已停止响应并且已恢复”怎么办

玩游戏时突然弹出”显示器驱动程序已停止响应并且已恢复”怎么办

随着3A游戏大作不断面市&#xff0c;用户也不断地提升着自己的硬件设备。但是硬件更上了&#xff0c;却还会出现一些突如其来的情况&#xff0c;比如正准备开启某款游戏时&#xff0c;电脑右下角突然出现“显示器驱动程序已停止响应并且已恢复”。遇事不慌&#xff0c;驱动人生…
阅读更多...
java lambda表达式详解

java lambda表达式详解

一、Lambda初识 我们知道&#xff0c;在Java中&#xff0c;接口是不能实例化的&#xff0c;但是接口对象可以指向它的实现类对象。如果接口连实现对象都没有呢&#xff1f;那还可以使用匿名类的方式&#xff0c;如下: public class JavaTest { public static void main(Strin…
阅读更多...
某程序员哀叹：二本计算机，4年开发，年包才40多万。二本真的不如985/211吗？

某程序员哀叹：二本计算机，4年开发，年包才40多万。二本真的不如985/211吗？

前段时间&#xff0c;某职场论坛上有人发了一个帖子&#xff0c;发帖人问&#xff1a;为什么大家工资那么高&#xff0c;三五年都六七十万了&#xff1f;我二本计算机专业&#xff0c;四年前端开发&#xff0c;找个年包40万多点就顶头了。 原贴如下&#xff1a; 有网友表示楼主…
阅读更多...
2022年平均工资出炉，IT行业又是第一

2022年平均工资出炉，IT行业又是第一

根据5月9日国家统计局最新资料显示&#xff0c;2022年&#xff0c;全国城镇非私营单位就业人员年平均工资为114029元&#xff0c;比上年增长6.7%&#xff0c;扣除通胀后实际增长4.6%。其中&#xff0c;行业间的差距相当明显。根据资料显示&#xff0c;2022年无论是在私营单位还…
阅读更多...
Android---bitmap优化

Android---bitmap优化

目录 Bitmap 占用内存大小计算 Bitmap | Drawable | InputStream | Byte[] 之间进行转换 Bitmap 相关方法 BitmapFactory 工厂类 Bitmap 占用内存大小计算 Bitmap 作为位图&#xff0c;需要读入一张图片中每一个像素点的数据&#xff0c;其主要占用内存的地方也正是这些像…
阅读更多...
python进阶--月考二

python进阶--月考二

python进阶--月考二 &#xff08;一&#xff09;装饰器&#xff08;二&#xff09;创建名为express.py文件&#xff0c;编写以下推导式&#xff08;25分&#xff09;&#xff08;三&#xff09;创建名为process_test.py的文件&#xff0c;计算1-3000之间的水仙花数&#xff08;…
阅读更多...
QT MD4 MD5 Sha1等几种加密方式

QT MD4 MD5 Sha1等几种加密方式

QT MD4 MD5 Sha1等几种加密方式 [1] QT MD4 MD5 Sha1等几种加密方式[2] qt MD5 和AES 加密一 、MD5 加密二、AES 加密和解密 [3] QT中sqlite数据库数据加密/混淆---MD5/SHA1/SHA2/SHA3&#xff08;1&#xff09;创建一个加密对象&#xff08;2&#xff09;放入要加密的数据&…
阅读更多...
目前可用的ChatGPT网站

目前可用的ChatGPT网站

本文意在整理可用gpt-3.5、gpt-4.0等网站。 本文主要是方便自己翻阅&#xff0c;如对您也有所帮助&#xff0c;不胜荣幸~ 文章目录 chatgpt.qdymys.cngpttalkchatgpt-cn.cobing.comchat机器人wuguokai.cn总结 chatgpt.qdymys.cn 网址&#xff1a;https://chatgpt.qdymys.cn/限…
阅读更多...
SpringCloud —— eureka

SpringCloud —— eureka

目录 1.认识微服务 1.0.学习目标 1.1.单体架构 1.2.分布式架构 1.3.微服务 1.4.SpringCloud 1.5.总结 2.服务拆分和远程调用 2.1.服务拆分原则 2.2.服务拆分示例 2.2.1.导入Sql语句 2.2.2.导入demo工程 2.3.实现远程调用案例 2.3.1.案例需求&#xff1a; 2.3.2.注…
阅读更多...
mysql进阶-查询优化-慢查询日志

mysql进阶-查询优化-慢查询日志

文章目录 一、什么是慢查询日志二、慢查询日志能干什么2.1 性能分析和优化2.2 诊断和排查问题2.3 数据分析和探索 三、慢查询日志实战3.1 永久开启开启慢查询日志3.2 临时开启慢查询日志3.4 常用命令 四、如何分析慢查询日志五、优化慢查询语句五、总结 一、什么是慢查询日志 …
阅读更多...
观察者设计模式（Observer Design Pattern）[论点:概念、组成角色、相关图示、示例代码、框架中的运用、适用场景]

观察者设计模式（Observer Design Pattern）[论点:概念、组成角色、相关图示、示例代码、框架中的运用、适用场景]

文章目录 概念组成角色相关图示示例代码框架中的运用适用场景 概念 观察者设计模式&#xff08;Observer Design Pattern&#xff09;是一种行为型设计模式&#xff0c;它定义了一种对象间的一对多的依赖关系&#xff0c;让多个观察者对象同时监听某一个主题对象&#xff0c;当…
阅读更多...
SpringBoot 配置文件

SpringBoot 配置文件

前言&#xff1a; 本篇主要介绍两种配置文件格式&#xff0c;分别为properties与yml(yaml)。 需要注意的是&#xff1a; 两个配置文件从功能上来讲是可以同时存在的&#xff0c;但是企业中通常会规定使用某一种格式的配置文件。如果同一个配置出现在两种格式的配置文件中的话&a…
阅读更多...
最新文章

Copyright @ 2022~2023