追根溯源，剖析STL是个享受的过程。
本文主要写std中容器库，打了很久ACM，之前一直没有写写常用的cpp的笔记，现在就来补一下。
用cpp编写算法时，使用stl和不使用stl完全是两种体验，stl中有许多可以提高效率的工具函数和类函数。
我学习和补充自己cpp知识的主要地方为cppreference.com和Concurrency-with-Modern-Cpp，分别对应cpp基础和cpp多线程编程，当然cpp博大精深，需要学习的地方还有许多。
STL的实现有很多的版本，GNU C++标准中使用的是SGI STL，MacOS中的Clion使用的是LLVM，其他的版本还有Clang等，各自的性能和特点都有所不同。
本文分析源码中使用的是SGI STL。
顺序容器(sequence container) 可以实现数据的顺序访问，类似访问数组的形式。
在内存中，vector实例化的对象一般是在连续的内存空间上动态进行分配的（这点和内置的静态空间的array很不同），所以可以通过如a[i]的方式进行访问。
vector的常见操作的复杂度：
vector是属于按需要动态增加空间的容器，在实例化的时候会预分配存储空间，也可以手动进行存储空间的预分配，如果空间不够了就会在堆中新开辟当前空间的两倍的空间，并将当前空间中的值拷贝到新空间，因此如果对vector的操作引起了空间重新配置，那么就会导致指向原来vector的迭代器失效，同时需要一定的运算时间来进行数据迁移。
动态增加步骤：
// 简化版vector类定义
template <class T, class Alloc = alloc>
class vector
{
public:
typedef T value_type;
typedef value_type* iterator; // vector 的迭代器是普通指针
protected:
iterator start; // 表示目前使用空间的头
iterator finish; // 表示目前使用空间的尾
iterator end_of_storage; // 表示目前可用空间的尾
};
通过上述简化版的vector定义，可以看到vecotr对象的内存空间通过三个迭代器（行为类似指针，重载了部分运算符）进行区分，分成了2个空间，分别是已用空间和未使用空间。b表示起来如下：
|-- -- -- used-- -- --|-- -- unused -- --|
^start ^finish ^end_of_storage
deque为双端队列，同时具有栈和队列的属性，是一种双向开口的连续线性空间，头和尾均可以进行元素的插入和删除操作。
list是一个双向链表。
cpp基础类，静态分配存储空间的连续数组。
还有用的不多的，就简单列下，详情看文档。
关联容器(associative container)是可以实现快速查找($O(log_n n)$)的数据结构
set 唯一键的集合，按照键排序。
map 键值对的集合，按照键排序，键是唯一的。
还有许多其他的容器，日后有机会再补充，这里先列着。