首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

为什么std::set容器使用的内存远远超过其数据的大小?

std::set是C++标准库中的一个容器,它是一个有序的集合,其中的元素按照特定的排序规则进行存储。std::set使用红黑树作为底层数据结构来实现,这种数据结构具有自平衡的特性,能够保证插入、删除和查找操作的时间复杂度都是O(log n)。

然而,std::set在实现上需要维护红黑树的结构,包括节点指针、颜色标记等信息,这些额外的信息会占用一定的内存空间。因此,即使std::set中只存储了少量的数据,它所使用的内存空间可能会远远超过数据的实际大小。

这种情况发生的原因是为了保证红黑树的平衡性和高效性能。红黑树需要维护节点之间的关系,包括父节点、左右子节点等指针,以及颜色标记等信息。这些额外的指针和标记信息会占用一定的内存空间,而且随着元素数量的增加,这些额外的信息也会相应增加。

尽管std::set使用的内存可能会超过数据的实际大小,但它仍然具有很多优势和应用场景。首先,std::set能够自动进行元素的排序,这对于需要有序访问元素的场景非常有用。其次,std::set提供了高效的插入、删除和查找操作,这得益于红黑树的自平衡特性。此外,std::set还提供了一系列的操作函数,如交集、并集、差集等,方便进行集合运算。

对于腾讯云的相关产品和产品介绍链接地址,由于要求不能提及具体的云计算品牌商,我无法给出具体的推荐。但腾讯云作为一家知名的云计算服务提供商,也提供了各种云计算相关的产品和服务,包括云服务器、云数据库、云存储等,可以根据具体需求选择适合的产品。

总结:std::set使用的内存可能会超过数据的实际大小,这是因为它需要维护红黑树的结构和额外的指针、标记信息。然而,std::set具有自动排序、高效的插入、删除和查找操作等优势,适用于需要有序访问元素的场景。腾讯云提供了各种云计算相关的产品和服务,可以根据具体需求选择适合的产品。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

STL:调用empty()而不是检查size()是否为0

vector底层是一块连续内存迭代器本质上是指向这块内存首尾位置两个指针。所以empty()函数是在检查这两个指针是否指向同一位置,若是,则说明容器为空,返回true。这当然是常数时间。...std::unordered_set unordered_setemtpy()实现也是判断size()==0。而size()返回是内部维护私有变量M_element_count。...我没有再查看其他容器实现,上述列出容器几乎代表所有stl容器类型。尽管上述各个容器empty()实现和容器底层密切相关,但总体都是耗费常数时间。...那么size()实现就不是常数时间了吗? 上面可以看到,array,set,unordered_set都是内部维护了一个私有成员变量size,各个改变容器成员大小成员函数都会更新这个size。...既然如此,为什么不推荐使用size() == 0呢? 答案是,list一些实现,size耗费线性时间,即list独有的splice操作。不过这取决于各家编译器实现。

1K20

【Example】C++ 标准库常用容器全面概述

这些容器和数组非常类似,都是在逻辑上连续(但内存不一定是连续),与数组不同是,容器可以非常方便动态管理,而不是固定元素大小 std::vector 当你需要容器时,就找vector!...rbegin 返回指向起始逆向迭代器。 rend 返回指向末尾逆向迭代器。 resize 手动改变大小。 shrink_to_fit 释放未使用内存。 size 返回当前长度。...cend 返回一个随机访问常量迭代器,它指向刚超过数组末尾位置。 crbegin 返回一个指向反向数据中第一个元素常量迭代器。 crend 返回一个指向反向数组末尾常量迭代器。...可以将多个不同类型值汇集在一起,但它长度只能是固定。 此外,它还需要配合头文件内几个类外部函数来使用。...元素(盘子)只能从堆栈顶部(基容器末尾最后一个元素)插入、检查或删除。 仅访问顶部元素限制是使用 stack 类原因。 queue 类支持先进先出 (FIFO) 数据结构。

3.2K30

标准关联容器一定比vector查找速度快吗?

delete成对出现 * 2,分配数组时,必须要使用 delet[] * * 而使用 vector或string销毁时,他析构函数会自动销毁容器元素,回收存放那些元素内存 * */ //https...reserve来避免不必要重新分配 /** STL容器可以自动增长到足以容纳你放进去数据,在最大大小范围之内 vector和string利用 realloc等价思想进行空间增长: 1,分配新内存块...,是容器目前容量几倍,每次以 2 为因数增长 2,把所有元素从容器内存拷贝到它内存 3,销毁旧内存对象 4,回收旧内存 首先介绍以下四个让人困惑函数: 1,size() 容器中有多少个元素...//2,保留你可能需要最大空间,然后,一旦你添加完全部数据,修整掉任何多余容量 条款15:使用“交换技巧”减小过剩容量 int main() { //保证减少 vector大小同时...而一旦位置合适了,只要你程序按照 // 阶段方式使用数据结构,它们往往比相应使用真的map设计运行得更快而且使用更少内存

1.8K10

现代C++之容器

1.string string 是模板 basic_string 对于 char 类型特化,可以认为是一个只存放字符 char 类型数据容器。...vector 一个主要缺陷是大小增长时导致元素移动。如果可能,尽早使用 reserve 函数为 vector 保留所需内存,这在 vector 预期会增长很大时能带来很大性能提升。...为什么会需要这么一个阉割版 list 呢? 原因是,在元素大小较小情况下,forward_list 能节约内存是非常可观;在列表不长情况下,不能反向查找也不是个大问题。...正常情况下,向 std 名空间添加声明或定义是禁止,属于未定义行为。 从实际工程角度,无序关联容器主要优点在于性能。...关联容器和priority_queue插入和删除操作,以及关联容器查找操作,复杂度都是 O(log(n)),而无序关联容器实现使用哈希表 ,可以达到平均 O(1)!

1K10

C++从入门到精通——string类

第一个问题是输出 std::string::iterator 类型名,第二个问题是输出 std::string 对象大小,并且说明为什么在不同编译器下结果不同。...容量表示容器已分配内存大小,而不是容器中实际存储元素数量。 对于vector容器来说,capacity()函数可以返回当前容器容量大小。...例如: std::string myString; std::cout << "容量:" << myString.capacity() << std::endl; 当容器元素数量超过容器容量时,容器会重新分配内存空间...+中shrink_to_fit函数是一个vector容器成员函数,用于请求vector缩小容量以适应当前大小。...它语法如下: void shrink_to_fit(); 该函数会释放vector中多余内存空间,使其容量等于大小

14010

资源控制在大数据和云计算平台中应用

同时,大数据作业调度也是基于资源配额进行分配,大数据作业本身就承载了资源配额属性,但是这些作业是否按照配额进行运行和计算,是否超过了指定配额导致overuse,是否达不到指定配额导致资源浪费...设定 cgroup 中任务使用内存限制,包括物理内存和虚拟内存,并自动生成由那些任务使用内存资源报告 net_cls 使用等级识别符(classid)标记网络数据包,可允许 Linux 流量控制程序...对CPU限制不像内存超过配额后再申请的话就会触发OOM kill掉进程,CPU设置配额后进程不会超过该配额使用。...(内存)”,虚拟内存指的是“提交大小”。...YARN支持对现有容器大小调整(cgroup和jobobjects都支持修改资源配额),当用户从YARN申请了一些固定大小容器,想改变容器资源配额大小时候不需要释放掉这些容器重新申请,YARN支持动态改变已经分配容器大小

2K80

《逆袭进大厂》第四弹之C++重头戏STL30问30答

为什么是两倍扩容?释放空间? size()函数返回是已用空间大小,capacity()返回是总空间大小,capacity()-size()则是剩余可用空间大小。...因此,可以使用reserve(n)预先分配一块较大指定大小内存空间,这样当指定大小内存空间未使用完时,是不会重新分配内存空间,这样便提升了效率。...为什么使用红黑树?...当一个元素被插入到一个STL列表(list)中时,列表容器自动为分配内存,保存数据。考虑到要将STL容器放到共享内存中,而容器却自己在堆上分配内存。...206、STL中vector实现 vector是一种序列式容器数据安排以及操作方式与array非常类似,两者唯一差别就是对于空间运用灵活性,众所周知,array占用是静态空间,一旦配置了就不可以改变大小

1.5K20

vector常用操作

简单理解:提供遍历访问一种方式 官方理解:是一个对象,可以循环访问C++标准库容器元素,并提供对各个元素访问 cbeginc代表是返回const,所以他不能修改数据 rbeginr代表反向第一个...< std::endl; // 2 resize(3)执行后,应该元素里面就剩下0,1,2了,为什么v[6]还能访问呢 这和resize和迭代器工作方式有关,当调用v.resize(3);后,v大小...另一方面,当你使用迭代器遍历v时,迭代器只会访问v有效元素,也就是说,只会访问v大小(size)范围内元素。...所以,[]操作符和*it都是读取内存值,但是他们访问范围是不同。[]操作符可以访问到任何位置内存,包括超出v大小范围内存,而*it只能访问到v大小范围内内存。...2.4修改数据 assign会清除容器里以前内容,当输入元素比原来容量空间小时,则原来容量空间不变 emplace替代insert emplace_back替代push_back std::vector

7510

源码分析C++string实现

我们平时使用C++开发过程中或多或少都会使用std::string,但您了解string具体是如何实现吗,这里程序喵给大家从源码角度分析一下。...size: 表示真实数据大小,一般resize函数改变就是这个值。...capacity:表示内部实际已经分配内存大小,capacity一定大于等于size,当size超过这个容量时会触发重新分配机制,一般reserve函数改变就是这个值。..._Alloc>::_M_create( size_type& __capacity, size_type __old_capacity) { /** * max_size()表示标准库容器规定一次性可以分配到最大内存大小..._M_dispose函数: /** * 如果当前指向是本地内存那15个字节,则不需要释放 * 如果不是,则需要使用_M_destroy去释放指向内存 */ void _M_dispose() {

2.2K20

从零开始学C++之STL(一):STL六大组件简介

但由于hash_set/hash_map都是基于hashtable之上,所以不具备自动排序功能。为什么? 因为hashtable没有自动排序功能。...所以说白了,什么样结构决定什么样性质,因为set/map/multiset/multimap都是基于RB-tree之上,所以有自动排序功能,而hash_set/hash_map/hash_multiset...2、比如++操作可以遍历至群集内下一个元素。至于如何做到,取决于容器内部数据组织形式。 3、每种容器都提供了自己迭代器,而这些迭代器能够了解容器内部数据结构。...这个allocator是一个由两级分配器构成内存管理器,当申请内存大小大于128byte时,就启动第一级分配器通过malloc直接向系统堆空间分配,如果申请内存大小小于128byte时,就启动第二级分配器...,从一个预先分配好内存池中取一块内存交付给用户,这个内存池由16个不同大小(8倍数,8~128byte)空闲列表组成,allocator会根据申请内存大小(将这个大小round up成8倍数)

1.3K00

【C++】STL梳理

C++ 标准模板库核心包括以下三个组件: 容器(Containers):用来管理某类对象集合。每一种容器都有优点和缺点,所以为了应付程序中不同需求,STL 准备了七种基本容器类型。...0x61 特点 使用红黑树实现,其内部元素依据值自动排序,每个元素值只能出现一次,不允许重复。 每次插入值时候,都需要调整红黑树,效率有一定影响。...(缺点) map 和 set 插入或删除效率比用其他序列容器高,因为对于关联容器来说,不需要做内存拷贝和内存移动。...另外 string 要使用c_str()转换一下,否则打印出是乱码。 Multiset 和 set 相同,只不过它允许重复元素,也就是说 multiset 可包括多个数值相同元素。...0x7 map map 由红黑树实现,元素都是 “键值/实值” 所形成一个对组(key/value pairs),map 内部自建一颗红黑树,这颗树具有对数据自动排序功能,所以在 map 内部所有的数据都是有序

66721

C++(STL):26 ---关联式容器set用法

set容器都会自行根据键大小对存储键值对进行排序, 只不过 set 容器中各键值对键 key 和值 value 是相等,根据 key 排序,也就等价为根据 value 排序。...因此如果想在程序中使用 set 容器,该程序代码应先包含如下语句: #include using namespace std; 注意,第二行代码不是必需,如果不用,则后续程序中在使用 set...容器存储各个键值对,键和值完全相同,也就意味着它们类型相同,因此 set 容器类模板定义中,仅有第 1 个参数用于设定存储数据类型。...注意,由于 set 容器支持随时向内部添加新元素,因此创建空 set 容器方法是经常使用。 2) 除此之外,set 类模板还支持在创建 set 容器同时,对进行初始化。...另外,C++ 11 标准还为 set 类模板新增了移动构造函数,功能是实现创建新 set 容器同时,利用临时 set 容器初始化。

56110

UE4队列TQueue

TQueue是UE4提供队列容器,完全满足队列先进先出性质,这里主要用于多线程同步数据。...其实std::queue这样容器底层内存管理方式在UE4中也有一个容器TChunkedArray和他非常像,但UE4并不是把他当作队列来用,如果看过UnityECS实现你就会觉得这个结构很眼熟,跟...游戏引擎肯定要优先保证性能,所以这就是为什么UE4没有选择std::deque或TChunkedArray类似数据结构来实现队列原因。 那UE4队列是怎样做?...至于为什么不加,是因为Head只会往Next方向去移动,不会往回移动指向前一个结点,Tail永远不会超过Head,即使追上Head又因为Tail始终指向无效节点,真正数据是Tail->NextNode...这里确实是这个容器唯一缺点了,但是UE4本身在全局重载了new和delete,内存分配和释放其实是来源于内存池,只有在内存内存不够用时UE4才会向系统要新内存,这个频率是远远低于代码中调用new

2.7K30

2019 C++开发工程师面试题大合集

(资源) 2、运行于一个进程中多个线程,它们之间使用相同地址空间,而且线程间彼此切换所需时间也远远小于进程间切换所需要时间。据统计,一个进程开销大约是一个线程开销30倍左右。...(代码易维护) 4、C++11有哪些新特性 1)关键字及新语法:auto、nullptr、for 2)STL容器std::array、std::forward_list、std::unordered_map...、std::unordered_set 3)多线程:std::thread、std::atomic、std::condition_variable 4)智能指针内存管理:std::shared_ptr、...2)调用 malloc()函数时,它沿着连接表寻找一个大到足以满足用户请求所需要内存块。 然后,将该内存块一分为二(一块大小与用户申请大小相等,另一块大小就是剩下来字节)。...4)value大小不同:memcache是一个内存缓存,key长度小于250字符,单个item存储要小于1M,不适合虚拟机使用 5)数据一致性不同:redis使用是单线程模型,保证了数据按顺序提交;

1.3K41

C++(STL):34--- multiset容器详解

回忆一下,set 容器具有以下几个特性: 不再以键值对方式存储数据,因为 set 容器专门用于存储键和值相等键值对,因此该容器中真正存储是各个键值对值(value); set 容器在存储数据时,...会根据各元素值大小对存储元素进行排序(默认做升序排序); 存储到 set 容器元素,虽然类型没有明确用 const 修饰,但正常情况下它们值是无法被修改set 容器存储元素必须互不相等...这意味着,如果想在程序中使用 multiset 容器,该程序代码应包含如下语句: #include using namespace std; 注意,第二行代码不是必需,如果不用,则后续程序中在使用...multiset容器时,需手动注明 std 命名空间(强烈建议初学者使用)。...下面样例中,使用了 STL 标准库提供 std::greater 排序方法,作为 multiset 容器内部排序规则: #include #include using

1.1K20

C++一分钟之-标准模板库(STL)简介

C++标准模板库(STL)是C++编程语言中一组高度灵活且高效通用算法和数据结构集合,它极大简化了常见编程任务,如容器管理、算法应用和迭代器使用。...STL核心组件概览 容器(Container) STL容器负责存储元素,包括向量(vector)、列表(list)、双端队列(deque)、集合(set)、映射(map)等,每种容器都有独特特性和适用场景...内存泄漏 问题:使用动态分配容器(如vector扩容)后未正确释放内存。...迭代器失效 问题:在容器大小变化操作(如插入/删除元素)后继续使用迭代器。 避免:操作后重新获取迭代器,或使用指向容器迭代器(如end())。 3....算法误用 问题:错误理解算法前置条件和后置条件,如对非排序容器使用binary_search。 避免:仔细阅读文档,确保数据结构满足算法要求。

7810

C++系列笔记(九)

标准模版库介绍 STL容器 顺序容器   顺序容器按顺序存储数据,如数组和列表。顺序容器具有插入速度快但查找操作相对较慢特征。...关联容器 关联容器按指定顺序存储数据,就像词典一样。这将降低插入数据速度,但在查询方面有很大优势。...STL提供关联容器包括: std::set——存储各不相同值,在插入时进行排序;容器复杂度为对数; std::unordered_set——存储各不相同值,在插入时进行排序;容器复杂度为常数。...这种容器是C++11新增std::multiset——与set类似,但允许存储多个值相同项,即值不需要是唯一std::unordered_multiset——与 unordered_set...容器适配器 容器适配器(Container Adapter)是顺序容器和关联容器变种,功能有限,用于满足特定需求。主要适配器类如下。

1K20

STL vector用法介绍

如果你想知道vector存放了多少数据,你可以使用empty()。获取vector大小,可以使用size()。...压缩一个臃肿vector 很多时候大量删除数据,或者通过使用reserve(),结果vector空间远远大于实际需要。所有需要压缩vector到它实际大小。...resize()能够增加vector大小。Clear()仅仅能够改变缓存大小,所有的这些对于vector释放内存等九非常重要了。如何来解决这些问题呢,让我们来操作一下。...假定我们已经有一个vector v,它内存大小为1000,当我们调用size()时候,它大小仅为7。我们浪费了大量内存。让我们在它基础上创建一个vector。...我们创建了一个临时变量代替那个命名,然后使用swap(),这样我们就去掉了不必要空间,得到实际大小v。 结论 我希望这个文档可以给那些使用STL vector容器开发者很有价值参考。

21710

C++STL vector详解(杂谈)

如果你想知道vector存放了多少数据,你可以使用empty()。获取vector大小,可以使用size()。...压缩一个臃肿vector 很多时候大量删除数据,或者通过使用reserve(),结果vector空间远远大于实际需要。所有需要压缩vector到它实际大小。...resize()能够增加vector大小。Clear()仅仅能够改变缓存大小,所有的这些对于vector释放内存等九非常重要了。如何来解决这些问题呢,让我们来操作一下。...假定我们已经有一个vector v,它内存大小为1000,当我们调用size()时候,它大小仅为7。我们浪费了大量内存。让我们在它基础上创建一个vector。...我们创建了一个临时变量代替那个命名,然后使用swap(),这样我们就去掉了不必要空间,得到实际大小v。 结论 我希望这个文档可以给那些使用STL vector容器开发者很有价值参考。

1.1K90

C++ STL容器如何解决线程安全问题?

众所周知,STL容器不是线程安全。对于vector,即使写方(生产者)是单线程写入,但是并发读时候,由于潜在内存重新申请和对象复制问题,会导致读方(消费者)迭代器失效。...可能大家平时用reserve()比较多,顾名思义,reserve就是预留内存。为是避免内存重新申请以及容器内对象拷贝。说白了,reserve()是给push_back()准备!...而resize除了预留内存以外,还会调用容器元素构造函数,不仅分配了N个对象内存,还会构造N个对象。从这个层面上来说,resize()在时间效率上是比reserve()低。...vector是顺序容器,STL中还有一类关联容器线程安全问题也不容小觑。比如map、unordered_map。...这时候并行IO本身带来性能提升,远远大于可能伪共享带来损失。 这里为什么说可能呢?因为伪共享触发没你想象这么简单。如何成功模拟出一次伪共享带来性能损失例子?

2.9K20
领券