学习了这么久的vector,想必读者对vector的底层原理一定充满好奇,为了满足读者的求知欲,本节将带领读者深入vector的学习,探寻其底层实现的奥秘。
vector被称为动态数组,普通数组的promax版,得益于动态扩展这一特性使得它与普通数组走上了截然不同的命运。下面我将提供其底层源码的一部分,有理有据地深入了解vector。
template<typename _Tp, typename _Alloc>struct _Vector_base { struct _Vector_impl : public _Alloc { pointer _M_start; //指向第一个元素 pointer _M_finish; //指向最后一个元素的下一个位置 pointer _M_end_of_storage; //指向内存块最后一个位置的下一个位置 _Vector_impl() : _M_start(0), _M_finish(0), _M_end_of_storage(0) { } _Vector_impl(_Alloc const& __a) : _Alloc(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0) { } };public: _Vector_impl _M_impl;
源码比较复杂,我们只需要关心单行注释这三个变量就好了,他们是vector的核心变量。
有色部分(A-G)表示一个vector容器,可见该容器预存共7个单位空间,已经有5个单位空间被使用了(深绿色部分),还有2个单位空间没有被使用(浅绿色部分)。
此时注意三个指针的位置,大多数情况下,_M_start负责查找,比如从头开始遍历元素;_M_finish负责元素增删,比如push_back()、pop_back();_M_end_of_storage管内存尾,负责统计容器容量。
当然,你也可以写一个模板去实现diy的vector,通过这三个指针的千变万化来满足个性化需求。
那么vector是如何“动态”的呢?
当元素总量超过当前容量时,vector会申请一个更大内存,然后将原数据复制到新数组,然后销毁旧数组,是不是有点像冒泡排序的swap算法,我愿称其为移花接木。一次动态扩展的行为,由于地址发生变化,所以会影响其他成员变量,比如维护的指针或迭代器,所以我们需要及时更新这类变量,避免未定义行为。
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程