通读《STL源码剖析》之后的一点读书笔记

时间:2022-09-14 20:48:01

直接逼入正题。 Standard Template Library简称STL。STL可分为容器(containers)迭代器(iterators)、空间配置器(allocator)、配接器(adaptors)、算法(algorithms)、仿函数(functors)六个部分。

迭代器和泛型编程的思想在这里几乎用到了极致。模板或者泛型编程其实就是算法实现时不指定具体类型,而由调用的时候指定类型,进行特化。在STL中,迭代器保证了STL中算法的连续性和紧密型,使得各算法不需要考虑具体的数据结构。

 仿函数实质就是在结构体中重载operator ()、<、>等操作符。仿函数实际上更多的是一种概念和思想性的东西,而非一种物质上的实际提升。

容器和算法是STL中最为核心的部件,一切工作的铺垫(例如迭代器、空间配置器等)都是根据他们而展开的。下面概要的讲一下容器和算法的主要内容。

   容器:

   1、vector

vector其实是一种顺序性的容器,当然这里的顺序不是说排好序,而是说操作的时候按照一定的次序关系。另外,vector和数组array是非常相似的,最大的不同是array是静态的,而vector是动态,这就是为什么大部分时候使用vector的原因了,因为我们往往不知道数组开多大比较合适,开大了浪费,开小了保存不下来,选择vector是一个比较优的选择。其实vector本质上就是一个array,只不过它是一个变化的array,那么一个固定大小的array怎么变成vector的呢?我们看一下它的数据结构或许会更加明白一些。

 template<class T,class Alloc=alloc>
class vector{
public:
typedef T value_type;
typedef value_type* point;
typedef value_type* iterator;
typedef value_type& reference;
typedef size_t size_type;
...
protected:
iterator start;//目前使用空间的头部
iterator finish;//目前使用空间的尾
iterator end_of_storage;//能够使用空间的尾
...
};

我们注意到vector中的start,finish,end_of_storage。

好了,有了这三个变量,一切就有了答案。比如我们初始化vector的大小为10,那么end_of_storage=start+10了。我们可以通过维护finish这个变量来使得它看起来是动态的,比如我们插入5个值,那么通过计算finish与start的差值就能得到size()为5了。我们还可以继续插入,只不过此时需要finish向后移动一位就OK。但是,随之而来的问题又来了,当finish等于end_of_storage之后怎么办呢?显然,如果要继续插入的话,不能进行操作啊。

莫慌,请别怀疑程序猿是智商最高的那一类,我们新建一个array,这次申请的空间比上一个大那不就OK了吗?同时把旧的array复制到newarray中去,同时delete掉old array。这样就保证了还可以继续添加。但是有时候申请资源会不成功哦,所以插入操作并不总是OK的啦。程序猿的世界,bug总是无处不在。这个时候需要重回old array,同时delete 掉新申请的array.

我们已经解决掉了怎么使一个固定大小的array变成一个动态vector的问题,就是建一个更大的array。那么更大到底是多大呢?STL中把这个更大定义为两倍的当前SIZE.这个可能是根据经验得到的数据,两倍会是一个比较优的解。

vector中提供了insert,erase,pushback还有重载操作符等方法。其实insert就是在后面添加一个值,vector容量不够了先扩容再insert.

erase也就是擦掉某个值的操作其实就是删除某个值,然后后面的值前移,vector中erase效率极其低下,如果需要频繁的erase操作,建议还是换一个数据结构会比较好。

还有例如begin(),end(),size().这些其实都是通过维护start,finish,end_of_storage得到的。

  2、list

在STL中list表示的是一种环状的双向链表(带头),相比vector需要维护start finish end_of_storage,list只需要维护一个node指针结点(头结点)就可以了。

双向环状链表的初始过程如下:

     node=getNode();//新建一个结点
node->next=node;//后一结点是node
node->pre=node;//前一结点是node

其他插入、删除、取值等操作只需要了解链表的操作都是非常easy了。

3、deque(双端队列,两边都可进可出)

deque在这里其实也是一个array,只不过是分段而已,所谓分段在这里的意思就是。deque可能连续第一组有连续十个空间存放值,第二组也有十个空间存放值,但是这两组空间不是连续的,也就是说第一组空间的尾+1,不等于第二组空间的头。这两组空间的组织和管理是通过链表(在STL中称为map,(这个map翻译成地图更合适,而非数据结构中的map))的方式形成的。

4、stack(先进后出的数据结构),queue(先进先出的数据结构)

他们的底层实现都是list,只是根据List做一些量身定制而已。就比如都是一件衣服,不同人穿的时候,稍微在外表上做点修饰,本质不改变。

上面说的都是顺序性的容器,当然顺序性容器中海油优先队列,slist等,它们其实都是大同小异,不具体阐述了。

  5、set、map、multiset、multimap

set和map的最大不同就是set是单值,而map是键值对,当然set也可以理解成键值对相等的特殊键值对。这样讲的话,我们大概就知道了,它们的底层实现就是一个东西。那么multiset和set有什么区别呢?主要值能不能重复的问题,如果可以保存多个相同值的话就使用multiset否则就使用set。因为插入的时候,它们分别调用的是insert和unique_insert;同理,map和multimap也是这个意思。

map有排序的功能,并且能够快速的插入和查找,甚至删除。它是怎么做到的呢?

这就要看的底层实现了。它们的底层都是基于红黑树,请看博主这篇文章:map,set的底层实现:红黑树[多图,手机慎入]

博文已经讲得非常清楚了,这里不再累述。

  6、hashtable、hashset、hashmap、hash_multiset,hash_multimap

其实这里面主要是讲了一个东西,就是hashtable,同样hashset和hashmap的问题是是否是键值对的问题。而mullti..是是否是多值的问题。

hash的最重要的功能就是插入和查找相当迅速,我们使用hash更多的是看中他查找的时间复杂度几乎是O(1).那么hash是怎么实现如此高效的查找呢?

我们需要看他的数据结构,其实hash是一个array,通过某个合理的方式把值映射到array某个array[i]中。这就是hash的最核心思想了。说的简单,我们这里有几个问题需要解决:

  a、如何才是高效的映射?  

    b、如果两个不同的元素映射到同一个array[i]中又怎么办?

     c、数据量太小,array太大,会造成浪费;如果数据量太大,array太小,查找效率会非常低下,怎么解决?

我们一个一个来看。首先会到a.这里映射关系需要用到某个合适哈希函数,实验说明质数是一个非常好的选择,比如(value)mod(某个质数)。

b,提到的其实就是冲突处理的问题,冲突一般有以下方式,线性探测:冲突之后把元素放到下一个位置,下一个也有元素继续后面。二次探测:即一个哈希函数冲突了之后,用下一个哈希函数;开链法:就是在该array[i]下用一个链表表示。冲突了就放到链表中。STL中选择的是开链法。

对于问题c,STL中的解决方法是,选择某个质数K作为N,当K小于hash中的元素个数之后,用更大的质数代替N,同时对之前的每一个元素重构hash.

 其他算法

其他例如find,accumulate...等算法,其实就是维护迭代器,一般都是fistIterator,lastIterator,operatorValue.这种架构。

从始至终,迭代器和泛型在几乎每一个STL容器或算法中都有出现、这才是精髓!

  

空间配置器

     这里在STL中说的空间配置器更多的是指内存的申请和释放。在STL中,一般拥有两级空间配置器,其中第一级配置器更像我们传统意义上的申请;而第二级配置器是一个池,一般称为内存池。

这里对空间配置器进行一个简短的综述,空间配置器管理存储资源的申请和释放的策略是当申请的资源较大时,这里说的较大时大于126BYTES时,调用第一级配置器,采用malloc和free的方式申请和释放;当小于126BYTES时,调用第二级配置器,第一级配置器实际上是由一个链表进行维护,但freeList中找到了合适大小的内存,直接给申请者使用,如果实在不够的话,就只能用部分,甚至再用堆申请一部分,即用malloc申请。释放的时候加入到freeList中。

采用二级配置器的一个利好就是,能够较大程度上减少碎片化,提高内存内部的使用率,减少资源浪费。

参考文献:STL源码剖析

版权所有,欢迎转载,但是转载请注明出处:潇一

通读《STL源码剖析》之后的一点读书笔记的更多相关文章

  1. STL&quot&semi;源码&quot&semi;剖析-重点知识总结

    STL是C++重要的组件之一,大学时看过<STL源码剖析>这本书,这几天复习了一下,总结出以下LZ认为比较重要的知识点,内容有点略多 :) 1.STL概述 STL提供六大组件,彼此可以组合 ...

  2. 【转载】STL&quot&semi;源码&quot&semi;剖析-重点知识总结

    原文:STL"源码"剖析-重点知识总结 STL是C++重要的组件之一,大学时看过<STL源码剖析>这本书,这几天复习了一下,总结出以下LZ认为比较重要的知识点,内容有点 ...

  3. STL源码剖析读书笔记之vector

    STL源码剖析读书笔记之vector 1.vector概述 vector是一种序列式容器,我的理解是vector就像数组.但是数组有一个很大的问题就是当我们分配 一个一定大小的数组的时候,起初也许我们 ...

  4. STL&quot&semi;源码&quot&semi;剖析

    STL"源码"剖析-重点知识总结   STL是C++重要的组件之一,大学时看过<STL源码剖析>这本书,这几天复习了一下,总结出以下LZ认为比较重要的知识点,内容有点略 ...

  5. 《STL源码剖析》相关面试题总结

    原文链接:http://www.cnblogs.com/raichen/p/5817158.html 一.STL简介 STL提供六大组件,彼此可以组合套用: 容器容器就是各种数据结构,我就不多说,看看 ...

  6. STL源码剖析之空间配置器

    本文大致对STL中的空间配置器进行一个简单的讲解,由于只是一篇博客类型的文章,无法将源码表现到面面俱到,所以真正感兴趣的码农们可以从源码中或者<STL源码剖析>仔细了解一下. 1,为什么S ...

  7. 面试题总结(三)、《STL源码剖析》相关面试题总结

    声明:本文主要探讨与STL实现相关的面试题,主要参考侯捷的<STL源码剖析>,每一个知识点讨论力求简洁,便于记忆,但讨论深度有限,如要深入研究可点击参考链接,希望对正在找工作的同学有点帮助 ...

  8. 【STL 源码剖析】浅谈 STL 迭代器与 traits 编程技法

    大家好,我是小贺. 点赞再看,养成习惯 文章每周持续更新,可以微信搜索「herongwei」第一时间阅读和催更,本文 GitHub : https://github.com/rongweihe/Mor ...

  9. &lpar;原创滴~&rpar;STL源码剖析读书总结1——GP和内存管理

    读完侯捷先生的<STL源码剖析>,感觉真如他本人所说的"庖丁解牛,恢恢乎游刃有余",STL底层的实现一览无余,给人一种自己的C++水平又提升了一个level的幻觉,呵呵 ...

随机推荐

  1. android开发读书笔记

    第九章心得: HAL ( Hardware Abstraction Layer,硬件抽象腔,〉是建立在Linux驱动之上的一套翻字库.这套程序 j率并不属于 Linux 内核, 而是属于 Linux ...

  2. OAF&lowbar;开发系列24&lowbar;实现OAF更新记录显示Record History(案例)

    20150716 Created By BaoXinjian

  3. Java Io 流(输入输出流)

    IO流,也就是输入和输出流,可分为字节流和字符流. 1. 字节流 (1). InputStream 输入流,用于读取文件 输入流常用API: inputStream.read()  读取一个字节 in ...

  4. PYTHON FABRIC实现远程操作和部署

    转载至:http://wklken.me/posts/2013/03/25/python-tool-fabric.html fabric title是开发,但是同时要干开发测试还有运维的活 (o(╯□ ...

  5. php命名空间及和autoload结合使用问题。

    在讨论如何使用命名空间之前,必须了解 PHP 是如何知道要使用哪一个命名空间中的元素的.可以将 PHP 命名空间与文件系统作一个简单的类比.在文件系统中访问一个文件有三种方式: 相对文件名形式如foo ...

  6. 梳理下Cordova的热更新

    公司的大部分都是Hybrid 产品,也就是混合开发,所以比较重要的一个核心功能就是热更新了. 做这个功能的时候中间碰到不少坑,记录一下,比较简单,大致思想就是从服务器拉取JS文件替换掉本地对应文件 之 ...

  7. 【译】巧用CSS变量实现自动前缀

    转:https://www.h5jun.com/post/autoprefixing-with-css-variables-lea-verou.html 最近,当我在制作 markapp.io 这个小 ...

  8. Django 【认证系统】auth

    本篇内容 介绍Django框架提供的auth 认证系统 方法: 方法名 备注 create_user 创建用户 authenticate 登录验证 login 记录登录状态 logout 退出用户登录 ...

  9. js截取固定长度字符串,多余字符显示&period;&period;&period;

    function cutstr(str, len) { var str_length = 0; var str_len = 0; str_cut = new String(); str_len = s ...

  10. Linux与Windows比较出的20个优势

    Linux相信大家并不会陌生,Android(安卓或安致)就是基于Linux平台的开源手机操作系统,在电脑方面有ubuntu(中文名:乌班图)等等也是基于linux. Windows与Linux Li ...