STL源码剖析（一）

新开了个坑，侯捷的STL源码剖析。

其实最开始想看源码是因为用string用的不熟悉，不知道里面有哪些函数，也不知道用了函数里面存储层会变成什么样。比如对string用+=会发生什么，重新分配内存还是用指针指向新开的内存，strlen的复杂度到底是不是O(n)等等，然后就买了侯捷的这本书，结果到手后发现没有string，这就比较坑，想着好歹是买了书，就先看看别的STL的实现吧。就这样。

先看第一遍，只分析STL里面函数/容器的实现思路，不涉及具体代码的分析，所以写的很简略。

不过听说STL代码有很多奇淫技巧，有时间还是需要读第二遍的。

第一遍可能有些地方看的不是很透彻，欢迎探讨。

第二章空间配置据说新版STL更改了分配器，所以就没看，直接跳过去了。

第三章

文章目录 vector 不定长数组list 列表deque 双向队列stack 栈queue 队列

vector 不定长数组

用法和数组一样，特点是不需要提前知道数组大小，可以自动增长空间，但是需要手动缩小。

也不能说是震惊吧，就是之前没想过，erase函数需要进行内存的拷贝

由于和数组过于接近，迭代器也变成了普通指针的模样

每次分配内存空间的时候，都比要求的空间要大一点。每次塞满的时候都会比之前的空间大一倍。这里需要注意的是，vector会新分配空间，并将元空间的数据拷贝到新空间上来。这就造成了，一旦引起空间重新配置，指向源vector的所有迭代器就失效了。

list 列表

没啥好说的，双向链表。

deque 双向队列

我一直以为双向队列是和vector一样，满了之后进行空间的重分配，结果好像不是这样。它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并