1、不要使用vector<bool>

vector<bool>是一个假的容器,它并不储存真的bool值,而是储存紧凑表示的“bool”,储存在“vector”中的每个“bool”仅占一个二进制位,一个字节可容纳8个“bool”。不能对其中的元素取地址,因为vector<bool>只是假装存储了这些bool。

    vector<bool> v;
    v.push_back(1);
    bool *pb = &v[0];       //报错,你可以创建一个指向bool的指针,而指向单个位的指针则是不允许的。
    cout << &v[0] << endl;  //同样报错,因为vector<bool>中的元素不能取地址

建议使用deque<bool>bitset来代替它,这两个数据结构几乎能做vector<bool>所能做的一切事情。

2、调用empty()而不是检查size()是否为0

当我们在判断一个数据结构是否非空时,经常会用

    if (s.size())

来代替

    if (!s.empty())

其实这里最好使用后者,因为我们知道一般size()的调用是 的时间复杂度,但是对于一些 list 实现,size()会耗费线性时间,而empty()则总是花费常数时间。

3、在循环中尽量使用 ++ i 来代替 i ++

两者的不同点:

  • ++ i : increment and fetch(累加然后取出),返回一个reference;
  • i ++ : fetch and increment(取出然后累加),返回一个const对象。

因为 i ++ 会创建一个临时对象并返回,比++ i多了一个创建和销毁临时对象的开销,效率比 ++ i 要低。这也是为什么可以使用++++ i而不能使用i ++++的原因。

4、使用reserve来避免不必要的重新分配

在vector的大多数实现中,每当需要更多空间时,就会重新分配两倍的新内存(VS中是1.5倍),把容器中所有元素从旧内存复制到新内存中,再释放旧内存。

    vector<int> v;
    for (int i = 0; i < 1000; ++ i) v.push_back(i);

考虑以上代码,该循环在进行过程中将导致2到10次重新分配(1000大致等于2的10次方)。每当一个元素需要插入而容器的容量不够时,就会发生重新分配过程(包括原始内存的分配和释放,对象的拷贝和析构,迭代器、指针和引用的失效),避免重新分配的关键在于尽早地使用reserve,把容器的容量设为足够大的值。

    vector<int> v;
    v.reserve(1000);    //这样处理后,下面的循环中将不会再发生重新分配。
    for (int i = 0; i < 1000; ++ i) v.push_back(i);

reserveresize的区别:

reserve只增加capacity的大小,但它的size没有变(没有真正创建元素对象),而resize同时增加capacity和size的大小(真正创建了元素对象),通过默认构造函数创建新元素并添加到容器末尾。