0.前言 本文简单地总结了STL的顺序容器的知识点。文中并不涉及具体的实现技巧,对于细节的东西也没有提及。一来不同的标准库有着不同的实现,二来关于具体实现《STL源码剖析》已经展示得全面细致。所以本文仅仅是对容器基础知识的归纳。至于容器提供的接口与使用实例,建议查取官方文档。文章难免有错漏,希望指出。 1.容器概论 容器,置物之所也。像桶可装水,碗可盛汤,C++的容器,可以存储对象。容器有多种,用来处理不同的元素操作诉求。按照元素存储到容器中以及访问方式的差异,容器分为顺序容器与关联容器。顺序容器也称为序列
在vector中,我们经常会使用迭代器iterator对vector中的元素进行索引,也经常需要将迭代器作为参数传递到vector的成员函数中,迭代器使用非常方便,但使用不当也会给我们带来巨大的麻烦,下面就深入分析vector迭代器失效的场景
vector是一个表示可变大小数组的序列容器,与我们平常定义的数组类似,区别在于vector在进行插入操作时,如果空间不足,会自动扩容。由于vector采用连续空间来进行存储数据,所以我们可以采用下标,来访问元素。
不同容器的迭代器,其功能强弱有所不同。容器的迭代器的功能强弱,决定了该容器是否支持 STL 中的某种算法。 例如,排序算法需要通过随机访问迭代器来访问容器中的元素,因此有的容器就不支持排序算法。
上期说过C++这块面试问的东西也蛮多,简历上只要出现C++这几个字,那么STL库就是必问。
对于STL,我们不仅学会使用STL,还要了解其底层原理,这样一来,我们就能知道什么时候用string好,什么时候用vector,什么时候用list,哪种方法效率高等等。其次了解了STL的底层原理,也助于我们的C++功力大增!
最近在看STL容器失效的例子,涉及到vector数组迭代器失效的问题,如果不注意使用,很容易出现问题,我们先来看一下一个简单的示例程序,在数组nums中删除大于50的元素,代码如下:
vector 是我们学习的第一个真正的 STL 容器,它接口的使用方式和 string 有一点点的不同,但大部分都是一样的,所以这里我们就只演示其中一些接口的使用,大家如果有疑惑的地方直接在 cplusplus 是上面查看对应的文档即可。
有了前面模拟实现string的经验,vector对大家来说也不会算很难。vector本质也就是一个空间可以动态变化的数组,所以这里就挑一些些容易踩坑的地方讲解一下,在最后会附上我的完整代码。
最近在开发过程中,定位一个问题的时候,发现多线程场景下大量创建和销毁某个C:\Windows\System32\reg.exe时出现了383个进程创建消息处理的接口,和384个进程销毁处理消息的接口都在等待锁,另外一个线程也在等锁,后面看了一下在处理进程创建和进程销毁的IPC消息处理所在类中有三把锁,执行流程都锁住了,猜测应该是某个线程持有锁没释放,导致其他并发线程锁住了,结合转储的dump和log日志,以及使用VS2017加载对应的dump,对并行堆栈中的线程进行分析,找了很久没发现问题。最后想了一下,是不是某个地方线程做了耗时或者同步阻塞操作导致的,或者线程中执行了死循环,排查后发现是因为一个同事在对map做循环遍历时,erase操作不当,导致某个地方迭代器失效,线程崩溃了,持有两把锁,其他所有线程都拿不到锁,导致IPC消息一直无法发送,最后程序无法升级。
2. 关联式容器 元素是排序的;插入任何元素,都按相应的排序规则来确定其位置;在查找时具有非常好的性能;通常以平衡二叉树的方式实现,包含set、map。
上次我们讲了string,其经本框架是由一个char的指针和两个分别代表含量和容量的整形构成。但是严格意义上string出现的时间很早并不属于stl,而在stl这个需要大量迭代器操作的地方,使用上面那种框架,似乎并不合适。所以我们使用如下操作。
其实大家可以认为vector就是我们之前数据结构学的顺序表,那说到顺序表,相信就不用给大家过多解释了。
// 测试vector的默认扩容机制 void TestVectorExpand() { size_t sz; vector<int> v; sz = v.capacity(); cout << "making v grow:\n"; for (int i = 0; i < 100; ++i) { v.push_back(i); if (sz != v.capacity()) { sz = v.capacity(); cout << "capacity changed: " << sz << '\n'; } } } //vs:运行结果:vs下使用的STL基本是按照1.5倍方式扩容 making foo grow: capacity changed: 1 capacity changed: 2 capacity changed: 3 capacity changed: 4 capacity changed: 6 capacity changed: 9 capacity changed: 13 capacity changed: 19 capacity changed: 28 capacity changed: 42 capacity changed: 63 capacity changed: 94 capacity changed: 141 //g++运行结果:linux下使用的STL基本是按照2倍方式扩容 making foo grow: capacity changed: 1 capacity changed: 2 capacity changed: 4 capacity changed: 8 capacity changed: 16 capacity changed: 32 capacity changed: 64 capacity changed: 128 // 如果已经确定vector中要存储元素大概个数,可以提前将空间设置足够 // 就可以避免边插入边扩容导致效率低下的问题了 void TestVectorExpandOP() { vector<int> v; size_t sz = v.capacity(); v.reserve(100); // 提前将容量设置好,可以避免一遍插入一遍扩容 cout << "making bar grow:\n"; for (int i = 0; i < 100; ++i) { v.push_back(i); if (sz != v.capacity()) { sz = v.capacity(); cout << "capacity changed: " << sz << '\n'; } } }
vector 是 STL 中的容器之一,其使用方法类似于数据结构中的 顺序表,得益于范型编程和 C++ 特性的加持,vector 更强大、更全能;在模拟实现 vector 时,还需要注意许多细枝末节,否则就很容易造成重复析构及越界访问
在学习完list和vector这两个运用最广泛的容器后我们发现这两个容器有许多相似的用法,甚至在大多时候(有时候不行,后文会提到)这2个容器能直接相互替换,此时我们可能会有些疑问,这么多重复的内容为啥不能把这2个容器相互借鉴一下,直接把搞成一个容器呢?
其实我刚开始也没想到会写这么快,明显后面几篇的数据跟不上第一篇啦。可能是有一部分朋友对CSDN还不是很了解吧。 在文中的蓝字是可以点击的超链接,在文章标题下面有文章所属专栏,也是可以点击的,我这一系列的文章都在一个专栏下: 开发成长之路 你们可以慢慢看,不懂的随时私信我,我在CSDN上还是比较活跃的,一般一个小时内都能回复。
使用STL的三个境界:能用,明理,能扩展 ,那么下面学习vector,我们也是按照这个方法去学习
为了规范STL中不同容器的统一的 访问方式,这里大佬们设计了 迭代器 来去替代C语言中指针的地位(在部分容器和部分平台上甚至直接就是指针的重命名中),所以迭代器的行为和指针的行为十分相似,但更加强大。
假设有个map容器,用于存储大学班级中各个家乡省份对应的学生数,key为省份中文全拼,value为学生数。现需要删除人数为0的记录,删除代码如下:
list也是最经常使用的一个容器,尤其是在对容器中的元素进行频繁的插入和删除时,通过指针操作使得list的插入和删除在常数时间内即可完成。
1. 下面是vector的框架,其中成员变量分别为指向当前使用空间首部分的_start指针和最后一个元素的下一个位置的_finish指针,以及指向可用空间末尾的下一个位置的_end_of_storage指针,并且对于vector来说,由于它的底层是由顺序表实现的,所以它的迭代器就是原生态指针T*,我们定义了const和非const的迭代器,便于const和非const对象的迭代器的调用。
假设有个 map 容器,用于存储大学班级中各个家乡省份对应的学生数,key为省份中文全拼,value为学生数。现需要删除人数为0的记录,删除代码如下:
C++ STL极大的方便了用户编写程序,但是同时一不小心也会犯一些错误,如erase()造成迭代器失效经常会引起错误。 错误示例: std::list< int> List; std::list< int>::iterator it; for( it = List.begin(); it != List.end(); it++) { if( it符合删除条件 ) { List.era
2. 就像数组一样,vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问,和数组一样高效。但是又不像数组,它的大小是可以动态改变的,而且它的大小会被容器自动处理。
其中后四个类主要为前两个类服务。 其中使用频率最高的就是容器库,迭代器库,算法库。容器库为我们提供了存储数据的数据结构,算法库则是我们操作数据结构的算法,迭代器库作为容器库和算法库的黏合剂。
list本身与list节点,这两个是完全不同的结构,是需要分开来设计的,对于一个list节点来说,由于list是双向环状链表(双向带头循环链表),所以需要提供两个指针,一个指向前一个元素,一个指向另一个元素,同时还需要一个val,用来存储数据。如下所示为SGI版本的list底层(稍作修改,便于学习):
vector(size_type n, const value_type& val = value_type())
一、迭代器 迭代器是泛型指针 普通指针可以指向内存中的一个地址 迭代器可以指向容器中的一个位置 STL的每一个容器类模版中,都定义了一组对应的迭代器类。使用迭代器,算法函数可以访问容器中指
本文的目的主要是介绍list的常用接口,从构造函数,访问数据,修改数据等接口函数介绍.帮助大家初步掌握list的使用,后续会分享list的模拟实现,从底层理解list更加深刻的理解list.
C++vector的使用及模拟 零、前言 一、什么是vector 二、vector的常用接口说明 1、vector对象常用构造 2、vector对象容量操作 3、vector对象访问及遍历操作 4、vector对象修改操作 5、vector迭代器失效问题 三、vector剖析及模拟实现 1、vector框架及常用接口展示 2、vector模拟常用接口具体细节 3、使用memcpy拷贝问题 4、动态二维数组理解 零、前言 本章将学习C++中的vector类,掌握其使用以及模拟实现 一、什么是vector
前言:学习C++的STL,我们不仅仅要求自己能够熟练地使用各种接口,我们还必须要求自己了解一下其底层的实现方法,这样可以帮助我们写出比较高效的代码程序!
1. LRUCache是一种缓存的替换技术,在CPU和main memory之间根据计算机的局部性原理,往往会采用SRAM技术来构建CPU和主存之间的高速缓存,DRAM(dynamic random access memory)用于构建主存,LRUCache这种缓存替换技术常被应用于高速缓存中缓存行的替换,我们接下来就要模拟实现LRUCache这种数据结构。
也是我们熟悉的这几个,默认构造、n个val的构造、迭代器区间的构造以及拷贝构造。 然后看一下它的迭代器:
本节将会讲述list的使用,以及list的底层实现,对于底层实现,list的底层就是我们之前学过数据结构中的链表,因此这就与vector的结构相差很大,迭代器的部分也与vector有很大差别,迭代器的相关内容极为重要,也是本节的难点;此外也会有vector与list两者之间进行对比,下面开始正文。
1. 从迭代器的上层角度来看,vector和list的迭代器的使用没有差别,迭代器的begin和end返回的是左闭右开的区间位置[ begin(),end() )。
1.vector的介绍和使用 1.vector的介绍 vector是表示可变大小数组的序列容器。 就像数组一样,vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问,和数组一样高效。但是又不像数组,它的大小是可以动态改变的,而且它的大小会被容器自动处理。 本质讲,vector使用动态分配数组来存储它的元素。当新元素插入时候,这个数组需要被重新分配大小为了增加存储空间。其做法是,分配一个新的数组,然后将全部元素移到这个数组。就时间而言,这是一个相对代价高的任务,因为
STL(Standard Template Library),即标准模板库,是一个高效的C++程序库。包含了诸多在计算机科学领域里常用的基本数据结构和基本算法。为广大C++程序员们提供了一个可扩展的应用框架,高度体现了软件的可复用性。其核心思想就是泛化编程(generic programming),在这种思想里,大部分基本算法被抽象,被泛化,独立于与之对应的数据结构,用于以相同或相近的方式处理各种不同情形。
文章首发于本人CSDN账号:https://blog.csdn.net/tefuirnever
vector 是表示可变大小数组的序列 容器,其使用的是一块 连续 的空间,因为是动态增长的数组,所以 vector 在空间不够时会扩容;vector 优点之一是支持 下标的随机访问,缺点也很明显,头插或中部插入效率很低,这和我们之前学过的 顺序表 性质很像,不过在结构设计上,两者是截然不同的
list 是可以在常数范围内在任意位置进行插入和删除的序列式容器,其底层是带头双向循环链表;list 常用接口的使用和 string、vector 系列容器的接口使用一样,这里我就不再详细介绍,具体使用细节可以查看 list 使用文档 – cplusplus.com。
list是STL中的一个容器,底层结构是一个带头双向循环链表。即每一个节点都有两个指针分别指向这个节点的前驱和后继节点,且这个容器一旦被创建出来即使不插入任何数据也应该有一个哨兵位(并且指针都是指向本身)。
C++在操作容器时更加推荐使用迭代器进行操作,C++标准库为每一种标准容器都定义了一种迭代器类型同时也支持了对部分容器使用下标进行访问。
为了建立数据结构和算法的一套标准,并且降低他们之间的耦合关系,以提升各自的独立性、弹性、交互操作性(相互合作性,interoperability),诞生了STL。
vector 学习时一定要学会查看文档:vector文档介绍,vector 在实际中非常的重要,在实际中我们熟悉常见的接口就可以,下面我们直接开始模拟实现,在模拟实现中我们实现的是常见的接口,并且会在实现中讲解它们的使用以及注意事项。
Chromium是一个伟大的、庞大的开源工程,很多值得我们学习的地方。 今天与大家分享的就是Chromium下base中的stl_util,是对stl的补充,封装,更有利于我们的使用,完全可以移植到自己的C++工程项目中来。 1 释放STL内存 Clears internal memory of an STL object. 我们知道,vector的clear()方法式清除了vector中的内容,但是vector object所占的内存不会清除。 因此,std_util中有个这个方法: template<
上次讲了常用的接口:C++初阶:容器(Containers)vector常用接口详解 今天就来进行模拟实现啦
本篇根据各个公司的面试问的常见问题进行总结。 来源:公众号(c语言与cpp编程) 公众号回复“面试”,获取pdf答案 1 变量的声明和定义有什么区别 2 简述 #ifdef、#else、#endif和
这是《逆袭进大厂》系列的第四期,本期是 C++ 重头戏,也就是标准模板库 STL 的内容,本期是 24098 个字。
📷 本篇根据各个公司的面试问的常见问题进行总结。 1 变量的声明和定义有什么区别 2 简述#ifdef、#else、#endif和#ifndef的作用 3 写出int 、bool、 float、指针变量与 “零值”比较的if语句 4 结构体可以直接赋值吗 5sizeof和strlen的区别 6 C 语言的关键字static和 C++ 的关键字static有什么区别 7 C 语言的malloc和 C++ 中的new有什么区别 8 写一个 “标准”宏MIN 9 ++i和i++的区别 10 volatile有什
领取专属 10元无门槛券
手把手带您无忧上云