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

C/C++字符串处理之std::vector与std::StringBuilder2013-02-05 csdn 许式伟引子

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 DataT, class AllocT = std::allocator<DataT> >
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）。