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

许式伟
2008-4-4

引子

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 的内存。

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 是最合适的人选了。

相关参考

• std::vector
• std::list
• std::TextPool

<!-- google_ad_section_start(weight=ignore) -->