C/C++字符串处理(5):std::deque与TextPool

引子

TextPool 基于 std::deque 实现。所以尽管本文讨论 std::deque,但是所有的结论对 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 的内存。

deque的其他特性

元素地址不变

由于 deque 并不进行数据搬移,带来一个有意思的特性,就是 deque 的元素地址在只有 push_back/push_front,没有 insert/erase 时,可保持元素地址不变。

需要注意的是,vector 并不具备这样的特性。如下的代码是不合法的:

std::vector<int> vec;
...
int& elem = vec[i];
vec.push_back(100);
elem = 99; // error: can't access elem since vec was changed!

由于取得 elem 之后存在 push_back 操作,所获得的元素地址(&elem)可能会由于内存搬移而失效。但是如果我们将容器换为 std::deque<int>,则这个代码不会有任何问题。

std::deque<int> dq;
...
int& elem = dq[i];
dq.push_back(100);
elem = 99; // ok!

另外需要注意的是,元素地址不变,并不代表 iterator 不变,如下的代码 deque 并不支持:

std::deque<int> dq;
...
std::deque<int>::iterator it = dq.begin() + i;
dq.push_back(100);
*it = 99; // error: can't access iterator since deque was changed!

结论

通过 vector, list, deque 的时间、空间性能对比,我们可以看出,应该提倡尽可能使用 deque 这个容器。特别是,如果要承受海量数据,deque 是最合适的人选了。

相关参考

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License

Subscription expired — please renew

Pro account upgrade has expired for this site and the site is now locked. If you are the master administrator for this site, please renew your subscription or delete your outstanding sites or stored files, so that your account fits in the free plan.