存档

‘STL源码剖析’ 分类的存档

STL笔记之二叉查找树

2014年9月7日 没有评论

SGI STL的关联容器(map、set、multimap、multiset)底层都是基于红黑树(Red Black Tree,RBT)来实现的,红黑树是一种被广泛使用的二叉查找树(Binary Search Tree,BST),有比较良好的操作效率。
1. 二叉查找树
二叉查找树可提供对数时间的元素插入和访问,其遵循以下规则:任何节点的键值一定大于其左子树中每一个节点的键值,并小于其右子树中每一个节点的键值。不过在极端情况下,当所有节点位于一条链上时,二叉查找树的操作时间为O(N)。二叉查找树[......]

继续阅读

STL笔记之hashtable

2014年8月24日 5 条评论

之前对hash一直存在恐惧感,毕竟没用过……最近在一个组件里面自己实现了一个hashtable,感觉也就这么回事;回头看看书上对hashtable的分析,发现是极其的相似。不过,旧版本的C++标准里面并没有hashtable这个东西,而C++11中引入了相关的容器(std::unordered_set, std::unordered_multiset, std::unordered_map, std::unordered_multimap),所以可以直接使用C++11里面的容器了。
1. has[......]

继续阅读

STL笔记之slist

2014年7月26日 没有评论

slist是SGI STL里面的一个单向链表,不过这个不属于标准定义,所以,G++下面不能用,另外看了下VS2008里面也没有。不过看到书上这一部分讲解,还是配合SGI的代码做一个了解。一般情况下使用标准的list就可以满足要求了,而且会更加方便,list的分析可以参考STL笔记之list一文。因为slist是单向链表,所以它的迭代器类型为forward_iterator。
1. slist节点设计
链表最基本的结构就是指针域和数据域,对单向链表的节点而言,其拥有一个next指针,指向下一个节点[......]

继续阅读

STL笔记之deque

2014年7月12日 没有评论

deque是双端队列,在队列头部和尾部可以快速的进行元素的插入和删除操作,相比vector而言有一定的优势,同时由于内部构造的设计,不存在vector那样扩充时带来的“配置新空间 / 移动旧数据 / 释放旧空间”问题。deque还提供Random Access Iterator,可以随机访问容器内的元素。deque同时还是STL中queue和stack的底层依赖组件。
1. deque结构设计
如果只是平时使用deque的话,可能就想不到其内部实现细节了。下面的图片展示deque的内部结构设计:[......]

继续阅读

STL笔记之优先队列

2014年7月5日 2 条评论

在STL中队列queue是基于deque实现的,优先队列priority_queue则是基于堆实现的。所谓优先队列即元素具有优先级的队列,在最大优先级队列中,队列最前面的元素具有最高的优先级,最大优先级队列基于最大堆(max-heap)实现。
1. 堆的基本性质
二叉堆是一颗完全二叉树,可以分为最小堆和最大堆,以最大堆为例来说,对于堆中的每一个节点p,都满足条件key[p] >= key[p->left] && key[p] >= key[p->right],即以p为根的子树中,根节[......]

继续阅读

STL笔记之list

2014年6月30日 没有评论

STL提供的list是一个双向链表容器,对应的迭代器类型为Bidirectional Iterators. 对于双向链表我们可以方便的在任意位置进行插入和删除操作,list每个节点的内存位置之间没有必然联系。
1. list 迭代器
链表由许多节点链接在一起构成,list中的节点的定义如下:

// ListNodeBase定义
struct _List_node_base {
_List_node_base* _M_next;
_List_node_base* _M_prev[......]

继续阅读

STL笔记之vector

2014年6月20日 没有评论

vector是初次了解STL接触最多的一个容器,是一种很方便的数组替代品,不需要显示指定容量大小,其内部可以根据需要进行自动扩容操作。也正因为这个特性,每次扩容的时候都会伴随着“配置新空间 / 移动旧数据 / 释放旧空间”的操作,因此是有一定的时间成本的,当然vector提供了reserve接口,如果能够对元素个数有一个大概的了解,那么可以一开始就分配合适的空间。vector的内存空间是连续的,因此对插入元素的操作而言,在vector尾部插入才是合适的选择。
1. _Vector_base 基类[......]

继续阅读

STL笔记之迭代器

2014年6月14日 2 条评论

迭代器(iterator)是STL里面很基础也很重要的一个东西,迭代器的traits技术设计的很棒(在上一篇文章《STL笔记之空间配置器》中提到destroy函数使用了traits技术来判断对象是否具有trivial destructor,然后通过重载自动选择合适的实现版本)。
迭代器是一种行为类似指针的对象,因为指针最常用的是->和*两个操作符,因此迭代器最重要的编程工作也是对这两个操作符的重载的实现。
1. 初探traits技术
假设现在定义了这样一个迭代器MyIter,当我们拿到一个MyIt[......]

继续阅读

STL笔记之空间配置器

2014年6月10日 2 条评论

最近看了看侯捷的《STL源码剖析》,打算看完之后写写笔记,毕竟很多东西看起来看懂了,却并不一定能够将其描述清楚,说到底还是没有彻底弄明白,最近博客也基本不怎么写了,所以还是决定写一写,这也算是写博客的乐趣之一吧。这一系列笔记,更主要是写给自己看的:)
1. 初探allocator
其实像我这样的一般人几乎接触不到allocator这种东西,因为这个模板参数是有默认值的,普通用户完全不需要和他打交道。但观察一下allocator这个东西的设计思路,还是可以学到不少东西。先从一个简单的allocat[......]

继续阅读