C/C++字符串处理之std::vector与std::StringBuilder

引子
std::StringBuilder 基于 std::vector 实现。所以尽管本文讨论 std::vector，但是所有的结论对 std::StringBuilder 同样有效。
实现概要
简单来讲，std::vector 是一个动态数组，管理的是一块线性的、可 动态增长的内存。
如何加速 std::vector？
使用 vector::reserve
在大致可预估 vector 大小时，在插 入数据前，应该先调用 reserve(size) 进行内存的预分配（这里 size 是预估的vector元素个数）。
避免在vector开始 (begin)插入/删除数据
也就是说，应该尽量用 vector::insert(end(), …) 或者 vector::push_back/pop_back 添加/删除数据。而不要用 vector::insert(begin(), …) 操作。vector 没有提供 push_front 操作，原因只有一个： 从 vector 开始处插入/删除数据是低效的做法。
如果你需要大量的在容器开始(begin)处 insert 数据，那么可以选择 std::deque（有 vector 随机访问的优点，也有 list 高效插入的优点）或者 std::list。
std::vector 的缺陷
什么时候不能用 std::vector ？
在容器需要容纳海量数据，并且元素个数不可预知时，坚决不能用 std::vector。所有 基于线性内存的数据结构（如 std::vector，std::string）在海量数据时，遭遇性能瓶颈。
内存碎片
基于线性 内存的数据结构（如 std::vector，std::string），还有一个典型的问题，就是容易产生内存碎片。在大量操作 std::vector 或 std::string 后，内存碎片就会比较严重。
std::vector 与 allocator
我们知道，std::vector 的原型 是:
template  >
class vector;
那么是否需要像我们针对 Map/MultiMap、Set/MultiSet、List/Slist、HashMap/HashMultiMap 、HashSet/HashMultiSet、Deque 做的那样，将 AllocT 改用 GC Allocator呢？
答案是：不需要。GC Allocator 对于 改善小内存分配是有益的。但是在动态的线性内存的数据结构无效。这样的数据结构除了 std::vector 外，典型的还有 std::string（std::basic_string）。
推荐阅读
std::deque(http://cpp.winxgui.com/cn:std-deque) - 介于 std::vector 与 std::list 之间的一个数据结构，既可以随 机定位，海量数据是性能仍然非常稳健（事实上其 push_back/push_front 的性能几乎为常数：O(1)，而不像 std::vector 那 样，随着元素的增加，插入速度急剧下降）。
std::list(http://cpp.winxgui.com/cn:std-list) - 双向链表。