文档建议反馈控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

C++中map和set的使用

（图片来源于网络） 一、set 1.1 set特点介绍 set的介绍 C++中的set是一个STL容器，它是一个自动排序的集合（即将数据存入set，我们通过迭代器顺序访问出来时，数据是有序的），内部使用红黑树...数据唯一（可以用于去重）：每个value必须是唯一的。set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。 set在底层是用二叉搜索树(红黑树)实现的。...它是按照键（key）进行排序和存储的，键必须是唯一的，而值（value）可以重复。map通常使用红黑树实现，所以它的查找、插入和删除操作的时间复杂度都是O(log n)。 那么何为键值对？...键值对是一种常用的数据存储结构，由“键”和“值”两部分组成。其中，“键”是唯一的，用于标识数据，而“值”则是与键相关联的数据。...banana香蕉 orange橘子 map3: 2 monkey3 panda1 空格对应的值:2 [ ]的作用 在 C++ 中，map 中的 [] 运算符可以用于访问和修改

18910

【C++】map和set在OJ中的应用

前言 上一篇文章我们学习了map和set的使用，那这篇文章我们来做几道题，练习一下。 1....其实就建立了原链表结点与拷贝链表每个结点的一种映射关系，方便我们设置拷贝结点的random域。 那我们现在C++有了map，搞这个是不是很简单啊： 怎么做呢？...首先我们定义一个map，然后遍历原链表，依次拷贝结点，在map中建立源节点与拷贝结点的映射，并链接拷贝链表 然后，再遍历原链表设置拷贝结点的random域： 如果源节点的random指向空，那么拷贝结点...random也指向空；如果源节点不指向空，那拷贝结点就指向map中对应源节点的random指向的结点对应的拷贝结点 1.2 AC代码 来写一下代码 class Solution { public...那我们的map不是会“自动排序”（当然本质是因为中序遍历使得有序）嘛，是的，但是它是按照key的大小进行排（插入的时候比较的是key的大小）的，而我们统计出来的次数是不是放到value里面了。

13110
您找到你想要的搜索结果了吗？
是的
没有找到

【C++】 使用红黑树模拟实现STL中的map与set

前言 前面的文章我们学习了红黑树，也提到了C++STL中的map和set的底层其实就是用的红黑树来实现的（而map和set的使用我们前面也学过了）。...STL源码中map和set的实现 那在正式实现之前，我们先一起来看一下STL（SGI版本）中map和set的源码，大致了解一下库里面是怎么实现的。...3.2 map、set的结构定义 那然后我们来创建一个头文件，先把map的结构简单定义一下 因为map里面pair的键key不能修改，所以我们加一个const，库里面也是这样搞的。...3.8 map的[]重载 那map与set不同的是不是他还重载了[]啊，这个我们之前在map和set的使用那篇文章也讲过。...： 当插入成功的时候，pair的first为指向新插入元素的迭代器，second为true，当插入失败的时候（其实就是插入的键已经存在了），那它的first为容器中已存在的那个相同的等效键元素的迭代器

13710

【C++】使用哈希表模拟实现STL中的unordered_set和unordered_map

前言 前面的文章我们学习了unordered_set和unordered_map的使用以及哈希表，并且我们提到了unordered_set和unordered_map的底层结构其实就是哈希表。...所以这里有些地方我们就不会特别清楚的去说明了，如果某些地方大家看的不能太明白，建议先搞懂这篇文章——使用红黑树模拟实现STL中的map与set 这里面我们是讲的比较清楚的。...增加一个模板参数 2. unordered_set和unordered_map增加KeyOfT仿函数 然后我们把unordered_set/map能写的先写一写： 3. insert封装及测试 那我们先把...然后end用空构造就行了 6. unordered_set和unordered_map的迭代器封装 那哈希表的迭代器实现好，我们就可以封装unordered_set和unordered_map的迭代器了...当插入成功的时候，pair的first为指向新插入元素的迭代器，second为true，当插入失败的时候（其实就是插入的键已经存在了），那它的first为容器中已存在的那个相同的等效键元素的迭代器，second

11710

【C++100问】深度总结STL基本容器的使用

《C++ Primer》学习笔记/习题答案 总目录 ---- 《C++ Primer》学习笔记（三）：字符串、向量和数组 《C++ Primer》习题参考答案：第3章 - 字符串、向量和数组 《C++...在关键字类型的元素没有明显的序关系的情况下，无序容器是非常有用的。在某些应用中，维护元素的序代价非常高昂， 此时无序容器也很有用。使用无序容器通常更为简单(通常也会有更好的性能) 。...multimap（多重映射）：唯一的区别是插入的元素（值）可以相同，即同一个键可以对应多个值。 优缺点： 优点：关键字查询高效，且元素唯一，以及能自动排序。把一个值映射成另一个值，可以创建字典。...在某些应用中，维护元素的序代价非常高昂， 此时无序容器也很有用。事实上使用无序容器通常更为简单(通常也会有更好的性能) 。...《C++ Primer》学习笔记（九）：顺序容器 《C++ Primer》习题参考答案：第9章 - 顺序容器 《C++ Primer》学习笔记（三）：字符串、向量和数组 https://en.cppreference.com

1.1K31

Clojure 学习入门（18）—— 数据类型

从这一点来看，相比于列表，向量更像是数组。总的来说，对于很多应用来讲向量更好，因为跟列表相比向量毫无劣势而且更快。 向量在Clojure程序中的字面表示是使用方括号。...关键字、字符串和数字都经常被用作映射的键。 与向量类似，映射是它们的键的函数（不过如果给定的键不存在，它们不会抛出异常）。要得到一个特定键对应的值，只要使用该映射最为函数，并将键作为参数传递给它。...默认地，sorted-map非常自然地对键进行比较：根据数字或者字母表里可用的那一种。 Struct Maps 使用映射时，很多时候有这种情况：我们需要产生一组有相同键组合的映射。...结构映射允许你首先定一个键组成的结构，然后用它来实例化多个映射，并通过共享键和查找的信息来节省内存。它们在语义上跟普通映射相同：唯一不同的是实现方式。...但是他们依然是映射，因此从各方面来说，你都可以使用相同的方法来取得一个值甚至是添加新的键。当然，新添加的键不会像在结构里定义的键一样有节省内存的优势。

2.2K10

【C++】STL的基本用法

vector myVector; ⭐2.3 向vector 中添加元素 在使用 cin >> myVector[i]; 时，由于 myVector 是一个空的向量，尝试访问 myVector...因为在 for 循环中，你试图直接通过下标将输入的值存储到 myVector 中，但是 myVector 的大小为零，因此没有有效的索引。这可能导致程序崩溃或产生不可预测的结果。...STL容器之map ✨3.1 map 在C++的STL（标准模板库）中，map 是一种关联式容器，用于存储键-值对。它按照键的顺序进行排序，并且具有快速查找功能。...STL容器之set ✨4.1 set set是C++标准模板库[STL]中的一个关联容器，它提供了一种有序的、不重复的集合。set使用红黑树实现，这使得它的插入、删除和查找操作都具有较好的性能。...唯一性： set中不允许重复的元素，每个元素在集合中只能出现一次。 动态操作： set支持插入和删除操作，可以在运行时动态地改变集合的大小。

11810

C++ STL 详解

双端队列deque 基本上与向量相同，唯一的不同是，其在序列头部插入和删除操作也具有常量时间复杂度 表list 对任意元素的访问与对两端的距离成正比，但对某个位置上插入和删除一个项的花费为常数时间...但是它是以牺牲插入删除操作的效率为代价的 多重集合multiset 和集合基本相同，但可以支持重复元素具有快速查找能力 映射map 由{键，值}对组成的集合，以某种作用于键对上的谓词排列...,array,string C++ STL中最基本以及最常用的类或容器无非就是以下几个： string vector set list map 下面就依次介绍它们，并给出一些最常见的最实用的使用方法，...首先给出map最好用也最最常用的用法例子，就是用字符串作为key去查询操作对应的value。 要使用map得先加个头文件map。...交互作用产生第三个序列 unique() 将重复的元素摺叠缩编，使成唯一 unique_copy() 将重复的元素摺叠缩编，使成唯一，并复制到他处 upper_bound() 上限

1.1K40

STL容器分类「建议收藏」

容器里面的对象必须是同一类型，该类型必须是可拷贝构造和可赋值的，包括内置的基本数据类型和带有公用拷贝构造函数和赋值操作符的类。典型的容器有队列、链表和向量等。 在标准C++中，容器一般用模版类来表示。...STL中的关联容器有4种： n set（集合）—— 支持唯一键值，并提供对键本身的快速检索；例如set：{学号}（对应于set类，定义在头文件中）； n...multiset（多重集合）—— 支持可重复键值，并提供对键本身的快速检索；例如set：{姓名}（可能有同名的）（对应于multiset类，也定义在头文件中）； n...map（映射/映像）—— 支持唯一Key类型的键值，并提供对另一个基于键的类型T的快速检索；例如map：{(学号, 姓名)}、{(电话号码, 姓名)}等（对应于...map类，定义在头文件中）； n multimap（多重映射）—— 支持可重复Key类型的键值，并提供对另一个基于键的类型T的快速检索；例如map<string

69610

【技术创作101训练营】不学STL 怎么做算法题？

为何要学习 C++ STL 讲两句 在座的可能都是 大一大二的 学弟学妹，可能对于算法的学习还比较陌生 还停留在 C语言学习的初期 或是学习了数据结构，也经过了一番练习， 对学习有了一些自己的看法， 今天我作为训练营的负责人...，想向到场的同学，解释一下 为什么 咱们要学习使用 C++ 并且 要学会 STL 的使用。...为何要用C++ 首先是为何要使用C++ ，因为 竞赛不是做工程 不会用到很多c++面向对象的特性 基本的语法会写能做题就够了 主要学下STL标准模板库 边做OJ上的题边学 不用特意去学c++ C++ 的运行速度...set set是集合，set不存在重复的元素，会按照从小到大进行排序 set集合中没有重复的元素 set中的元素都是排好序的 头文件引入 #include 增加元素 insert()--在集合中插入元素...中第一个元素的引用 获取最后一个元素 back()：返回 queue 中最后一个元素的引用 C++ 引用 & 与传值的区别 c++ & 被称为引用符号(函数参数列表使用) c语言 & 被称为取地址运算符

1K00

STL库基础学习

4）set和map 3.几种STL 的时间复杂度比较 ---- 1.什么是STL库 ◦ STL 又称为标准模板库，是一套功能强大的 C++ 模板类，提供了通用的模板类和函数，这些模板类和函数可以实现多种流行和常用的算法和数据结构...◦ 也就是说，有了 STL ，数据结构中很多东西不要再需要自己去手写，而是可以自己去调用 STL 去帮你完成相关的功能 ◦ 无论是在算法竞赛中还是往后工作写项目中，都会大量使用 STL...功能与我们在数据结构中所学的栈相似，是一个只能从顶部插入和弹出的模板. （4）set和map ◦ set 和 map 中没有顺序的概念，因为在底层实现上是红黑树，而非顺序结构 ◦ set...和 map 中去找到我们所要找到的值相当快速，时间复杂度为 O( logn ) ◦ set 和 map 中不会出现重复的元素，如果插入已经存在的元素则不会发生任何改变 ◦ set...和 map 拥有自己迭代器，因为底层实现的特性，访问得到的元素序列是已经排好序的 ◦ set 和 map 唯一的区别是 set 是集合囊括所有插入的元素， map 不仅囊括所有插入的元素

83140

建议收藏 哭着喊着 从C语言转向C++刷算法

set set是集合，set不存在重复的元素，会按照从小到大进行排序 set集合中没有重复的元素 set中的元素都是排好序的 头文件引入 #include 增加元素 insert()--在集合中插入元素...-查找值对应的位置 **同set的find，如果找不到则返回最后一个元素的下一个位置** 删除函数 erase()---根据键删除元素 clear()--清处所有的元素 stack 称为栈(或者堆栈...中第一个元素的引用 获取最后一个元素 back()：返回 queue 中最后一个元素的引用 C++ 引用 & 与传值的区别 c++ & 被称为引用符号(函数参数列表使用) c语言 & 被称为取地址运算符...func(n);// 并不会改变n的值，n还是0 } C++ struct c++ 和 c 语言一样，但是 c++ 可以 可以省略 struct 关键字 直接使用 代码样例 struct stu {... c++ 的默认计算相关的类集合 sort swap max min sort使用时 一般使用在结构体 容器向量排序 #include #include <

1.3K20

【C++】STL 标准模板库 ① ( STL 简介 | STL 基本概念 | STL 主要内容 )

; 向量 vector , 双端队列 deque , 表 list , 队列 queue , 堆栈 stack , 集合 set , 多重集合 multiset , 映射 map 和 多重映射 multimap..., 不同之处是 双端队列可以 在序列头部 插入和删除 操作 , 具有常量时间复杂度 ; 表 list : 对任意元素的访问与对两端的距离成正比，但对某个位置上插入和删除一个项的花费为常数时间 集合 set...: 元素不能重复的集合 ; 多重集合 multiset : 元素可以重复的集合 ; 映射 map : 存放键值对 , 一个键对应一个值 ; 多重映射 multimap : 存放键值对 , 一个键对应多个值..., 可以顺序访问容器中的每个元素 , 而不改变容器中元素的位置 ; 常量时间复杂度 指的是在执行某个操作时 , 所花费的时间与输入规模无关 , 通常为 O(1) ; 二、STL 代码示例 在下面的代码中..., 使用了 STL 容器中的 vector 向量容器 , 使用 sort 排序算法 对 vector 向量中的元素进行了排序 ; 使用 STL 容器中的 vector 向量容器需要导入 vector

17930

Android开发笔记（二十六）Java的容器类

容器的分类 集合(Set/HashSet) 集合中的元素是没有顺序的，而且不可以重复。这意味着，集合只能遍历而无法通过索引访问指定元素，并且如果重复添加相同值将不会增大集合。...remove : 删除元素 size : 获取容器大小 队列(ArrayList) 队列与集合恰恰相反，队列中的元素是有顺序的，而且允许重复，所以队列可以使用索引来访问指定元素（类似数组的下标...除了删除元素之外，还可以删除指定位置的元素 set : 替换指定位置的元素 subList : 截取从开始位置到结束位置之间的子队列 链表(LinkedList) 链表又称双端队列（类似C...具体的说，当一个向量的指针Iterator正在使用时，另一个线程改变了向量的状态（比如添加或删除了一些元素），这时调用指针的方法将抛出异常(ConcurrentModificationException...即先获取容器中的键集合，然后对键集合进行指针遍历分别取出该键对应的值，具体代码如下： Set key_set = map.keySet(); for (String item_key

59440

Java每日十题——日积月累更能事半功倍

参考答案：缓存穿透是指用户查询数据，在数据库没有，自然在缓存中也不会有。这样就导致用户查询的时候，在缓存中找不到，每次都要去数据库再查询一遍，然后返回空（相当于进行了两次无用的查询）。...一种是挂链式，也叫拉链法，在产生冲突的hash地址指向一个链表，将具有相同的key值的数据存放到链表中。。 7、HashSet和HashMap的区别是什么？JDK是如何实现HashSet的呢？...参考答案：HashMap实现了Map接口 HashSet实现了Set接口 HashMap储存键值对 HashSet仅仅存储对象 使用put()方法将元素放入map中 使用add()方法将元素放入set中...而索引包括聚集索引（clustered index ）和非聚簇索引（secondary index），聚集索引使用表的主键作为索引键，叶子节点包含表的所有字段。...创建索引的时候尽量使用唯一性大的列来创建索引，由于使用b+tree做为索引，以innodb为例，一个树节点的大小由“innodb_page_size”，为了减少树的高度，同时让一个节点能存放更多的值，索引列尽量在整数类型上创建

52520

STL小结

但是它是以牺牲插入删除操作的效率为代价的 多重集合multiset 和集合基本相同，但可以支持重复元素具有快速查找能力 映射map 由{键，值}对组成的集合，以某种作用于键对上的谓词排列...当数据元素增多时（10000和20000个比较），map和set的插入和搜索速度变化如何？ 如果你知道log2的关系你应该就彻底了解这个答案。...在map和set中查找是使用二分查找，也就是说，如果有16个元素，最多需要比较4次就能找到结果，有32个元素，最多比较5次。那么有10000个呢？...交互作用产生第三个序列 unique() 将重复的元素摺叠缩编，使成唯一 unique_copy() 将重复的元素摺叠缩编，使成唯一，并复制到他处 upper_bound() 上限 四、注意细节： 1、...remove从一个容器中remove元素不会改变容器中元素的个数，erase是真正删除东西。 13、提防在指针的容器上使用类似remove的算法，在调用类似remove的算法前手动删除和废弃指针。

82210

java集合详解完整版（超详细）「建议收藏」

，不会产生不确定的结果。...HashMap：适用于Map中插入、删除和定位元素。 Treemap：适用于按自然顺序或自定义顺序遍历键(key)。 四、重点问题 （一）说说List,Set,Map三者的区别？...List(对付顺序的好帮手)： List接口存储一组不唯一（可以有多个元素引用相同的对象），有序的对象 Set(注重独一无二的性质): 不允许重复的集合。不会有多个元素引用相同的对象。...另外，HashTable 基本被淘汰，不要在代码中使用它； 对Null key 和Null value的支持： HashMap 中，null 可以作为键，这样的键只有一个，可以有一个或多个键所对应的值为...不冲突，就不会产生并发，效率又提升N倍。

80120
点击加载更多

扫码

添加站长 进交流群

领取专属 10元无门槛券

手把手带您无忧上云

扫码加入开发者社群

相关资讯

热门标签

更多标签

活动推荐

    运营活动

    活动名称
    广告关闭

    腾讯云开发者

    扫码关注腾讯云开发者

    扫码关注腾讯云开发者

    领取腾讯云代金券

    热门产品

    热门推荐

    更多推荐

    Copyright © 2013 - 2024 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有

    深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 深公网安备号 44030502008569

    腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号 | 京公网安备号11010802020287

    领券