readme

为了支持快速随机访问，vector将元素连续存储。这意味着，在执行push_back时如果内存不足，不能简单的额外分配一块新内存给新元素。

事实上，当push_back遇到内存不足时，vector会重新分配一块更大的连续内存，然后将当前元素移动到新内存中，然后添加新元素，最后释放旧内存。内存的分配拷贝释放，在效率要求苛刻的场景中十分值得优化。

此外，每次分配的新内存大小并不仅仅比之前空间多一个元素，不然每次push_back都要重新分配内存，重新搬运内存，性能会差到受不了。

reserve函数可以在push_back自动重新分配内存之前，预先保留指定大小的内存空间，如果合理使用，可以有效减少内存分配和内存搬运次数，起到性能优化的目的。

这篇博客讨论了reserve对性能的提升。对于性能优化，可以从不同角度着手。相较于reserve对性能带来的优化，优化架构，更好的算法等等措施一般情况下都可以带来更为明显的性能提升。但作为一只对技术有追求的程序猿，都希望写出最好的代码，所以说，这篇博客你若有时间就读读呗～～

测试程序

//common.h
#ifndef _COMMON_H_
#define _COMMON_H_

#include <string>
#include <stdio.h>
#include <set>
#include <memory>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <iostream>
#include <utility>
#include <algorithm>
#include <map>
#include <numeric>
#include <vector>
#include <iostream>
#include <iterator>
#include <sys/time.h>

using namespace std;
#endif

//Timer.h
#ifndef _TIMER_H
#define _TIMER_H

#include <sys/time.h>
#include "common.h"

class Timer
{
public:
    Timer(string strCallInfo = "Timer")
    {
        _desc = strCallInfo;
        gettimeofday(&_begin,NULL);
        gettimeofday(&_end, NULL);
    };

    ~Timer()
    {
        gettimeofday(&_end,NULL);
        printf("%s, cost %ldms\n", _desc.c_str(), (_end.tv_sec - _begin.tv_sec)*1000 + (_end.tv_usec - _begin.tv_usec)/1000);
    };
private:
    Timer(){};
    string  _desc;

    timeval _begin;
    timeval _end;
};

#endif

//std_reserve.cpp
#include "common.h"
#include "Timer.h"

int main(void){
    int i = 0;
    {
        vector<int> intVector;
        for (i = 0; i < 20; ++i){
            intVector.push_back(i);
            printf("intVector.size(): %ld, intVector.capacity(): %ld\n", intVector.size(), intVector.capacity());
        }
    }
    {
        vector<int> intVector;
        intVector.reserve(20);
        for (i = 0; i < 20; ++i){
            intVector.push_back(i);
            printf("intVector.size(): %ld, intVector.capacity(): %ld\n", intVector.size(), intVector.capacity());
        }
    }
    {
        Timer timer("without reserve");
        vector<int> intVector;
        for (i = 0; i < 10000000; ++i){
            intVector.push_back(i);
        }
    }
    {
        Timer timer("with reserve");
        vector<int> intVector;
        intVector.reserve(10000000);
        for (i = 0; i < 10000000; ++i)
        {
            intVector.push_back(i);
        }
    }
    return 0;

}

编译

g++ -o std_reserve std_reserve.cpp -O2 -g -Wall -std=c++11

执行

[root@***]# ./std_reserve 
intVector.size(): 1, intVector.capacity(): 1
intVector.size(): 2, intVector.capacity(): 2
intVector.size(): 3, intVector.capacity(): 4
intVector.size(): 4, intVector.capacity(): 4
intVector.size(): 5, intVector.capacity(): 8
intVector.size(): 6, intVector.capacity(): 8
intVector.size(): 7, intVector.capacity(): 8
intVector.size(): 8, intVector.capacity(): 8
intVector.size(): 9, intVector.capacity(): 16
intVector.size(): 10, intVector.capacity(): 16
intVector.size(): 11, intVector.capacity(): 16
intVector.size(): 12, intVector.capacity(): 16
intVector.size(): 13, intVector.capacity(): 16
intVector.size(): 14, intVector.capacity(): 16
intVector.size(): 15, intVector.capacity(): 16
intVector.size(): 16, intVector.capacity(): 16
intVector.size(): 17, intVector.capacity(): 32
intVector.size(): 18, intVector.capacity(): 32
intVector.size(): 19, intVector.capacity(): 32
intVector.size(): 20, intVector.capacity(): 32
intVector.size(): 1, intVector.capacity(): 20
intVector.size(): 2, intVector.capacity(): 20
intVector.size(): 3, intVector.capacity(): 20
intVector.size(): 4, intVector.capacity(): 20
intVector.size(): 5, intVector.capacity(): 20
intVector.size(): 6, intVector.capacity(): 20
intVector.size(): 7, intVector.capacity(): 20
intVector.size(): 8, intVector.capacity(): 20
intVector.size(): 9, intVector.capacity(): 20
intVector.size(): 10, intVector.capacity(): 20
intVector.size(): 11, intVector.capacity(): 20
intVector.size(): 12, intVector.capacity(): 20
intVector.size(): 13, intVector.capacity(): 20
intVector.size(): 14, intVector.capacity(): 20
intVector.size(): 15, intVector.capacity(): 20
intVector.size(): 16, intVector.capacity(): 20
intVector.size(): 17, intVector.capacity(): 20
intVector.size(): 18, intVector.capacity(): 20
intVector.size(): 19, intVector.capacity(): 20
intVector.size(): 20, intVector.capacity(): 20
without reserve, cost 259ms
with reserve, cost 204ms

总结

由执行结果可以看出：

• 当vector内存不足时，新分配内存空间大小是当前的2倍。
• reserve更大一块空间之后，capacity将等于预留的空间大小，但size()是实时的当前元素个数。
• 在vector创建时候如果合理预留足够的空间给即将加入的元素，可以避免容量不够的时候重新分配内存，以及在新内存中通过拷贝构造函数实现数据的迁移。
• 本文例程中vector中的数据类型是内置int，在真正使用场景中，vector有可能存放自定义类型的数据，此时重新分配内存伴随的数据拷贝会引入潜在的更大消耗。

reserve的合理使用是很好的习惯，但如果reserve的空间大小小于当前大小，reserve被视为无效；如果reserve的空间过大，会造成内存浪费。所以预留空间大小还需要斟酌才能发挥预期的作用。

此外，这边博客主要针对vecotr进行讨论，其实对于string也有类似的优化效果。