C/C++字符串处理(4):std::vector与StringBuilder

引子

StringBuilder 基于 std::vector 实现。所以尽管本文讨论 std::vector,但是所有的结论对 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/MultiMapSet/MultiSetList/SlistHashMap/HashMultiMapHashSet/HashMultiSetDeque 做的那样,将 AllocT 改用 GC Allocator呢?

答案是:不需要。GC Allocator 对于改善小内存分配是有益的。但是在动态的线性内存的数据结构无效。这样的数据结构除了 std::vector 外,典型的还有 std::string(std::basic_string)

推荐阅读

  • std::deque - 介于 std::vector 与 std::list 之间的一个数据结构,既可以随机定位,海量数据是性能仍然非常稳健(事实上其 push_back/push_front 的性能几乎为常数:O(1),而不像 std::vector 那样,随着元素的增加,插入速度急剧下降)。
  • std::list - 双向链表。
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.