Note: This article is available in Chinese only. 本文暂无英文版本。
View original
起因是百度实习二面的时候被问了一道类似这样的题：
给我下面的代码，问有没有什么问题。
1/* ***********************************************
2Author :111qqz
3Created Time :2017年02月28日 星期二 14时49分37秒
4File Name :vector.cpp
5************************************************ */
6#include <cstdio>
7#include <vector>
8#include <ctime>
9using namespace std;
10int func( int x ) //此处函数的条件是不单调...这样才可以触发问题.
11{
12 return (x-50)*(x-50)+1;
13}
14int main()
15{
16
17 vector<int>vec;
18 int *pint = NULL;
19 for ( int i = 0 ; i < 100 ; i++)
20 {
21 int x = func(i);
22 vec.push_back(x);
23 if (x<500)
24 {
25 pint = & vec[0];
26 }
27 }
28 if (pint)
29 *pint = 0 ;
30 int siz = vec.size();
31 for ( int i = 0 ; i < siz ; i++) printf("%d\n",vec[i]);
32 return 0;
33}面试的时候只给了部分代码，func函数没有给出。
当时没有看出问题在哪里…
后来知道了，这道题其实考的是vector的底层实现…
以下内容参考《STL源码解析》4.2章 侯捷著
vector是动态增加空间，但是并不是在原空间后面增加新空间（因为不能保证原空间之后是否还有可以配置的空间），而是以原大小的两倍另外配置一块较大空间，然后将原内容拷贝过来，之后才开始在原内容后面构建新内容，并释放原空间。#
因此，对vector的任何操作，一旦引起对空间重新配置，指向原vector的所有迭代器都失效了！
vector采取的存储方式是连续线性空间，用两个迭代器start和finish分别指向当前配置的空间中已经使用的部分的开始和结尾，用另一个迭代器end_of_storage指向当前配置的整块连续空间（包含备用部分）的尾端。
当我们用push_back()将元素插入vector尾端时，push_back()会先检查是否还有备用空间，如果有就直接在备用空间上构建元素，并调整迭代器finish，使vector变大。如果没有备用空间了，就扩充空间。
可以用以下代码来测试：
1/* ***********************************************
2Author :111qqz
3Created Time :2017年02月28日 星期二 14时33分10秒
4File Name :vector1.cpp
5************************************************ */
6#include <cstdio>
7#include <vector>
8#include <iostream>
9using namespace std;
10int main()
11{
12 vector<int>a;
13 a.push_back(0);
14 int lst = -1;
15 for ( int i = 0 ; i < 200 ; i++)
16 {
17 a.push_back(-1);
18// if (a.capacity()!=lst)
19 printf("i:%d %d ",i,a.capacity());
20 cout<<&a[0]<<endl;
21 lst = a.capacity();
22 }
23 return 0;
24}结果如下：
