β

STL源码分析: deque

Rayn新天地 219 阅读

在造(chao) STL的过程中,也会学习到一些比较厉害的新奇的设计,比如说deque,内存结构上有点巧妙。写一篇博客来记录一下。

deque概述

对于C++ STL中的deque是一种双向开口的顺序容器,可以支持头尾两端的插入删除操作。类似的还有大家熟知的vector,由于vector的动态分配特性所致,虽然可以头尾两端操作,但是效率极差,达到了O(n)。再来看在deque中,这个操作却是常数级别的,为什么呢?接下来我要说到的就是这个。

deque的内存结构

deque从表面上看起来是一段连续空间,但是内部实则不然,deque内部其实是由一段一段的定量连续空间接起来的,每当空间不足,就新开辟一段定量连续空间,然后把它接过去就OK了,这就是它和vector最大不同,当然代价就是特别设计的迭代器有那么点复杂。

deque采用了一块map作为主控中心,它是一小段连续空间,每个节点指向另一段定量连续空间(称为缓冲区,这里才是deque数据的真正存储地带),deque的实际定义如下,BufSize就是一段缓冲区的大小。

template <class T, class Alloc = alloc, size_t BufSize>
class deuqe {...}

deque的迭代器

在造(chao) STL的过程中,也会学习到一些比较厉害的新奇的设计,比如说deque,内存结构上有点巧妙。写一篇博客来记录一下。

作者:Rayn新天地
Rayn的个人博客
原文地址:STL源码分析: deque, 感谢原作者分享。

发表评论