vector使用的简单优化技巧

背景

在大部分C++项目中,一般都会大量使用到vector,毕竟数组是最常用的结构。 vector也是stl里面最高效的实现之一,在g++编译器下,开启-O3优化选项的时候,vector的随机访问效率基本上和原生的数组效率一样高,当然前提是使用恰当。

滥用push_back是可怕的性能杀手。

【代码1】

vector<int> vec;
for(size_t i = 0; i < 130; i ++)
{
    vec.push_back(i);
}

【代码2】

vector<int> vec(130);
for(size_t i = 0; i < 130; i++)
{
    vec[i] = i;
}

在【代码1】中,刚初始化的时候vec的容量是0,随着 push_back 依次重新分配内存。 容量大小的变化如下:

0 -> 1 -> 2 -> 4 -> 8 -> 16 -> 32 -> 64 -> 128 -> 256

而且忧伤的是,每次重新分配,比如 4 -> 8的这个过程中(在此不考虑内存池优化的影响):

  1. 先申请一个8的空间
  2. 将大小为4的这段内存复制到8的空间
  3. 将大小为4的这段空间释放掉

而【代码2】中,在 vector<int> vec(130); 这行初始化代码中直接就就内存一次性分配好(大小为130)。

所以在工程中,如果我们可以预知vector的大小为多少,尽量在初始化的时候就直接指定大小。 这样既能做到节约内存,比如【代码1】会导致vec的实际容量大小是256,而【代码2】实际容量大小只有130。

善用reserve最大限度的减少push_back时的内存重新分配

很多情况下很难知道准确的所需容量大小,所以可以使用 vector::reserve 先预留一个较大的容量。 这样在push_back 的时候就无需频繁的内存重新分配,直到预留的容量已经使用完了(只要预留的容量大小适当,遇上用完的概率很小)。

值得一提的是,在今天的CppJieba性能优化中,在性能瓶颈的地方,简单的加了一行 reserve 语句,性能测试结果就提高了10%

而且建议需要reserve的话, 最好是在 vector 初始化的时候紧接着就reserve,这样代码显得规整一些,毕竟内存预留也算是初始化的一部分。

总结

其实上面说的都是很简单通用的手段,比如在unordered_map中也可以用类似的方法优化。 但是遗憾的是在c++11之前,unordered_map没有reserve这个函数。

C++制定标准的那些所谓委员们,标准的出台效率低得简直和国企有的一拼,C++语言都被这群猪不知道耽误了多少。

记得有句话说: 大部分C++程序犯过的错误就是过早的优化STL

如果连STL常用容器的性能都没有榨干利用到极致,就去大谈特谈放弃STL的,基本上不是无知就是装逼。

转载请注明出处: vector使用的简单优化技巧