C/C++字符串处理惩罚之std::deque与std::TextPool

引子

std::TextPool 基于 std::deque 实现。所以尽量本文接头 std::deque，可是所有的结论对 std::TextPool 同 样有效。

实现提要

顾名思义，这是一个“双向行列（double-ended queue）”。这意味着从行列开始 和竣事处插入（删除）数据的机能很好。为了到达这个目标，std::deque 基于一种分段持续的、介于数组和链表之间的数据结 构，示意如下：

template　<class　_E>
class　deque
{
　　enum　{　BlockSize　=　 512　};

　　typedef　_E　Block[BlockSize];

　　std::vector<Block*>　m_storage;
　　iterator　m_first,　m_last;
};

个中，iterator是deque::iterator类。其详细实现我们这里不展开 接头，只是提示一点：这里m_first, m_last就是容器的begin(), end()。之所以需要它们，是因为m_storage的第一个Block和 最后一个Block的数据大概没有填满，需要有指针去指出界线。设想一下假如 我们只是要实现一个单向的行列，那么可以去掉这 里的m_first成员（因为第一个Block假如它差异时是最后一个Block，则不会不满）。

为什么需要回收这种分段持续的数 据布局呢？谜底是：机能。deque 泛泛很少为C++措施员所利用，但从容器的各方面的机能指标来看，实在不该该如此。可以说 ，deque 是 STL 中基于值的容器（它们包罗：list/slist, vector, deque, basic_string等）中综合机能最优的类。

下面我们仔细阐明一下。

时间机能阐明

push_back/push_front

这两个操纵对 deque 来说并无区别。而 vector 则不支持 push_front（因为机能很差而不提供）。我们比拟各容器 push_back 机能。如下：

vector

vector::push_back 的机能详细要看 vector 的实现，主要关乎vector的内存增长模子。今朝所见典范的 做法是N*2模子，也就是说在申请的内存填满后，申请N*2字节的内存，这里N为当前 vector占用的空间。在此环境下，元素搬移 的时间为 (1/N * N) = 1 为常数（个中1/N为平均搬移的次数，N为每次搬移的数据量），故此 push_back 的巨大度为 O(1)。 但这种做法时间机能是有了，空间存在庞大的挥霍。可是假如增长模子为N+Delta模子（这里Delta为一个常增长系数），那么元 素搬移的时 间为 (1/Delta * N) = O(N)。空间是节省了，但时间机能极差。Erlang语言引入了一个很有意思的增长模子，是基 于 Fibonacci 序列，空间挥霍要好于N*2模子，分身了空间机能和时间机能。

list

list::push_back 的机能为O (1)。主要的时间开销为new Node时间。假如我们利用GC Allocator，list::push_back的速度很是快。

deque

deque::push_back 的机能靠近O(1)。之所以不是O(1)，是因为 m_storage 满了之后，会导致和 vector 一样的内存搬移问题。假设 vector<Block*> 回收了 2*N 增长模子，那么 deque::push_back 机能显然是 O(1)。假如采 用 N+Delta 模子，那么元素搬移时间为 (1/(BlockSize*Delta) * N/BlockSize) = O(N)。固然也是 O(N)，可是一个是 N/Delta，一个是 N/(Delta*BlockSize*BlockSize)，照旧不同很大。由于 m_storage.size() 凡是很小，所以实际环境下哪怕 在海量数据景象下 deque::push_back 仍然表示精采。

operator[]

operator[] 是指通过下标取数据。显然 list 的巨大度为O(N)，很是慢。而 vector、deque 均为 O(1)。让我们想象下 deque::operator[] 的实现：

_E　 deque::operator[](int　i)
{
　　return　m_storage[i/BlockSize][i%BlockSize];
}

可以 看出，deque 只比 vector 多了一次内存会见。

空间机能阐明

push_back

vector

很不幸，假如 vector 回收 N*2 的内存增长模子（凡是如此），那么在最差的环境下，空间巨大度就是 2*N ，最好的环境下为 N（所有的内 存都用上了）。平均来讲，空间巨大度为 1.5*N 。也就是说，凡是差不多有一半的内存是被挥霍的。

list

list 的空间挥霍与 vector 对比不遑多让。它的空间巨大度为 (1 + sizeof(pointer)*2/sizeof(_E))*N。假如我们让 list 存储的 元素为 pointer（即 _E = pointer），那么空间巨大度为 3*N，比 vector 还挥霍。

deque

deque 的最差环境下 的空间巨大度为 N + sizeof(pointer)*2*N/(BlockSize*sizeof(_E))（这里假设vector<Block*>也回收 2*N 增长模子， 平均巨大度则将式中2改为1.5即可）。假如我们生存的元素为 pointer（即 _E = pointer），而且BlockSize取512，那么空间 巨大度为 N + N/256。也就是说最差环境下只挥霍了 N/256 的内存。