首页 > 读完两遍《STL源码剖析》后,我发现了一些辛秘
头像
拱白菜的阿秀
编辑于 2021-05-14 16:17
+ 关注

读完两遍《STL源码剖析》后,我发现了一些辛秘

前排提醒

  • 本文是阿秀以前给某位号主投稿文章改编而来,当时自己文笔还较弱,现重新改写一下发表出来,希望与大家共同进步!
  • 阅读本文需要具备一些C++基础,不是完全面向小白的文章。
  • 因能力有限,如果总结的不到位,欢迎各位大佬在留言区批评指正。

前言

对于每一位学习 C++ 的小伙伴来说,STL 不可谓不重要,特别是那些为我们造好的底层轮子比如容器、算法等更是一件利器。

比如在一些 OJ 平台,用 STL 下的算法刷题简直不要太爽,谁试谁知道。

不止如此,在一些大厂面试过程中,C++有两个区分度比较高的知识点:虚函数相关和 STL 。

不管是骡子是马,问一下这两个知识点就知道几斤几两了。

今天阿秀就带大家梳理一下 STL 中的常见容器下的一些小知识吧,都是我过去两年在学习C++过程中慢慢总结出来的。

在此过程中去验证一下,那些真理,特别喜欢侯捷老师的一句名言:源码面前,了无秘密

侯捷老师靓照镇楼

好了,发车!

图片说明

STL 下的容器主要分为两类:序列式容器以及关联式容器。

序列式容器顾名思义就是物理上彼此相邻的一种关系,比如数组、栈、队列或者你和你的同桌,这种一个挨着一个的关系;而关联式容器的重点在关联二字上,至少是两个东西之间存在着某种联系才可以叫做关联,否则就不能被称之为关联式容器了,比如 hashtable 中的key和 value,是一对一或者一对多的关系。

序列式容器

vector

不知道在读的小伙伴在刷算法题的时候最喜欢哪个容器,我个人最喜欢的、用的最顺手的容器绝对是vector。

它是一种类似于数组的数据结构,它与数组 array 非常类似,两者的唯一差别就是对于空间运用的灵活性,vector 更加灵活多变,而 array 比较固定,具体来说:

  • array 占用的是静态空间。也就是说一旦配置了它的空间就不可以改变大小,如果遇到空间不足的情况还要自行创建更大的空间,并手动将以前的数据拷贝到新的空间中,再把原来的空间释放才行。

  • vector 则使用更加灵活的动态空间来进行配置。它始终维护一块连续的线性空间,在空间不足时,vector可以自动扩展空间容纳新元素,做到按需供给。其在扩充空间的过程中仍然需要经历:重新配置空间,移动数据,释放原空间等操作。

​ 《STL源码剖析》一书中侯捷老师说 vector 扩容倍数为2倍,如下图所示:

但网上也有说 1.5 倍的,后来我自己动手实践一番后得出结论:动态扩容原则跟操作系统相关,没有一个统一的结论,也就是说在不同环境下 vector 的扩容系数是不一样的,不可盖棺定论为 2 倍。

实践代码如下:

int main()
{
    vector<int> data(2, 1);
    cout << "size: " << data.size() << " capacity " << data.capacity() << endl;
    data.push_back(1);
    cout << "size: " << data.size() << " capacity " << data.capacity() << endl;
    data.push_back(1);
    cout << "size: " << data.size() << " capacity " << data.capacity() << endl;
    data.push_back(1);
    cout << "size: " << data.size() << " capacity " << data.capacity() << endl;
    data.push_back(1);
    cout << "size: " << data.size() << " capacity " << data.capacity() << endl;
    d

全部评论

(2) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

近期精华帖

热门推荐