当前位置: 首页 > news >正文

C++之multimap:关键字分类的利器

目录

1.引言

2.主要特点

3.成员函数

4.使用实例

 5.注意事项


1.引言

        在C++中,multimap是标准模板库(STL)中的一个关联容器,它存储键值对(key-value pairs),并且允许键的重复。multimap内部通常通过红黑树(或其他平衡二叉搜索树)实现,这保证了元素按照键的顺序进行存储和检索。

2.主要特点

        1.有序性: std::multimap 是一个有序集合容器,它根据元素的键值自动进行排序。这种有序性使得元素可以按照特定的顺序进行存储和检索,从而方便了对元素的排序和查找操作。

        2.插入与删除的对数级复杂度: 由于 std::multimap 内部采用红黑树作为数据结构,因此其插入和删除操作的时间复杂度都是对数级的,即 O(log n),其中 n 是容器中元素的数量。这意味着,无论容器中有多少元素,插入和删除操作的效率都能保持相对稳定,不会随着元素数量的增加而显著下降。

        3.高效的查找性能: 同样得益于红黑树的特性,std::multimap 的查找操作也具有对数级的时间复杂度。这使得在大量元素中快速定位到特定元素成为可能,提高了程序的执行效率。

        4.允许重复元素: 与 std::map 不同,std::multimap 允许存储重复的元素。这意味着在同一个 multimap 容器中,可以有多个具有相同键值的元素存在。这一特性使得 multimap 在某些需要处理重复元素的场景中非常有用。

        5.空间消耗: 由于 std::multimap 使用红黑树作为内部数据结构,而红黑树在维护平衡的过程中可能需要额外的空间来存储节点的颜色和进行旋转操作。因此,相对于其他简单的数据结构(如数组或链表),multimap 的空间消耗可能会稍高一些。但需要注意的是,这种空间消耗是为了换取更高的操作效率而付出的代价。

        需要注意的是,虽然 std::multimap 具有上述性能特点,但在某些特定场景下可能并不是最优选择。例如,如果需要进行频繁的插入和删除操作,并且不关心元素的顺序,那么使用其他数据结构(如哈希表)可能会更加高效。

      在很多场合都要用到,比如:

      1.在电话簿中相同的人可以有两个以上电话号码
      2.文件系统中可以将多个符号链接映射到相同的物理文件
      3.DNS服务器可以将几个URL映射到相同的IP地址

3.成员函数

函数作用

begin()

返回指向第一个元素的迭代器

clear()

删除所有元素

count()

返回一个元素出现的次数

empty()

如果multimap为空则返回真

end()

返回一个指向multimap末尾的迭代器

equal_range(k)

该函数查找所有与 k 关联的值。返回迭代指针的 pair,它标记开始和结束范围

erase()

删除元素

find()

查找元素

get_allocator()

返回multimap的配置器

insert()

插入元素

key_comp()

返回比较key的函数

lower_bound()

返回键值>=给定元素的第一个位置

max_size()

返回可以容纳的最大元素个数

rbegin()

返回一个指向mulitmap尾部的逆向迭代器

rend()

返回一个指向multimap头部的逆向迭代器

size()

返回multimap中元素的个数

swap()

交换两个multimaps

upper_bound()

返回键值>给定元素的第一个位置

value_comp()

返回比较元素value的函数

4.使用实例

 使用multimap根据关键字分类的应用举例:

#include<iostream>
#include<map>
using namespace std;int main()
{multimap<int, int> m;m.insert(pair<int,int>(1, 10));m.insert(pair<int, int>(1, 20));m.insert(pair<int, int>(1, 30));m.insert(pair<int, int>(2, 21));m.insert(pair<int, int>(2, 22));m.insert(pair<int, int>(3, 31));m.insert(pair<int, int>(3, 32));multimap<int, int>::iterator  it;pair<multimap<int, int>::iterator, multimap<int, int>::iterator> ret;for (it = m.begin(); it != m.end(); ){cout << it->first << "==>";ret = m.equal_range(it->first);for (it = ret.first; it != ret.second; ++it){cout << " " << (*it).second;}cout << endl;}cout << m.count(1) << endl;//与键1关联的值的数量return 0;
}

 5.注意事项

  • 由于multimap允许键的重复,所以在进行查找和删除操作时,需要注意可能会有多个元素匹配同一个键。
  • 遍历multimap时,元素的顺序是按照键的升序排列的。
  • 如果需要控制元素的排序方式,可以在创建multimap时提供一个自定义的比较函数。
  • multimap::insert() 和 map::insert() 的返回值不同
  • multimap::insert():返回指向新插入元素的迭代器(multimap::insert()总是能执行成功)
  • map::insert() :返回 pair<iterator, bool>,此处 bool 值表示插入操作是否成功。

   multimap在需要存储键值对且允许键重复的场景下非常有用,例如记录某个单词在文本中出现的所有位置或统计投票结果等。


http://www.mrgr.cn/news/46492.html

相关文章:

  • CSS的小知识
  • JAVA:在IDEA引入本地jar包的方法(不读取maven目录jar包)
  • 【SH】Xiaomi9刷Windows10系统研发记录 、手机刷Windows系统教程、小米9重装win10系统
  • 技术管理专题学习笔记-技术管理能力对比--卓越和拙劣
  • lobechat搭建本地知识库
  • 记一次学习skynet中的C/Lua接口编程解析protobuf过程
  • (Linux和数据库)1.Linux操作系统和常用命令
  • NLP: SBERT介绍及sentence-transformers库的使用
  • 基于SpringBoot的校园新闻管理系统 计算机毕业设计选题 Java毕业设计 SpringBoot+Vue 前后端分离 [附源码+安装调试]
  • MAX模型转为las点云模型
  • 响应速度相关知识
  • 汽车胶黏剂市场研究:预计2030年全球市场规模将达到67.4亿美元
  • Apache Flink 配合 Debezium 连接器来捕获 Oracle 数据库变更日志的应用
  • 图像平滑处理
  • 基于vue框架的大学生在线教育jp6jw(程序+源码+数据库+调试部署+开发环境)系统界面在最后面。
  • IDEA 输入英文字体变了的问题
  • 【宽搜】6. leetcode 513 找树左下角的值
  • patch函数前两个参数位
  • c++输出保留n位小数
  • 默认情况下,`QTableView`中的单元格内容是不支持自动换行的,而是将文本截断或者显示省略号。要实现内容自动换行。要用Delegate
  • 鹧鸪云光伏软件全面解析
  • Web3与人工智能的交叉应用探索
  • 【深度学习总结】热力图-Grad-CAM使用
  • whistle使用实践
  • Linux内核 -- 使用 `proc_create_seq` 和 `seq_operations` 快速创建 /proc 文件
  • VAE(与GAN)