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

    引子

    std：：TextPool 基于 std：：deque 实现。所以尽管本文讨论 std：：deque，但是所有的结论对 std：：TextPool 同样有效。

    实现概要

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

    其中，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 性能。如下：