STL——vector
STL历史
STL 的主要实现版本
HP STL：由 Alexander Stepanov 和 Meng Lee 在惠普 Palo Alto 实验室工作时完成，是 C++ STL 的第一个实现版本。
SGI STL：由 Silicon Graphics Computer Systems 公司参照 HP STL 实现，被 Linux 的 C++ 编译器 GCC 所采用。
STLport：由 Boris Fomitchev 开发的跨平台版本，基于 SGI STL。
P.J.Plauger STL：由 P.J.Plauger 实现，被 Visual C++ 编译器所采用。
Rouge Wave STL：由 Rouge Wave 公司开发，用于 Borland C++ 编译器。
STL六大组件
容器（Containers）：如 vector, list, deque, set, map，用于存放数据。
算法（Algorithms）：如 sort, search, copy, erase。
迭代器（Iterators）：用于连接容器和算法。
仿函数（Functors）：行为类似函数，可作为算法的策略。
配接器（Adapters）：用于修饰容器、仿函数或迭代器接口。
配置器（Allocators）：负责空间配置与管理。
Vector
1、vector 是表示可变大小数组的容器，一般是异地扩容（需要拷贝操作）
2、vector 采用连续空间存储，可采用下标随机访问
3、vector 的尾插尾删相对高效，但在其他位置的增删操作需要挪动元素，效率较低
模拟实现
构造函数
vector 以迭代器作为成员变量，且此处迭代器的实现为 原生指针
template<class T>
class myVector
{
public:typedef T* iterator;typedef const T* const_iterator;iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}myVector():_start(nullptr),_finish(nullptr),_end_of_storge(nullptr){}private:iterator _start;iterator _finish;iterator _end_of_storge;
};增 -- insert
void insert (iterator position, size_type n, const T& val);
向 position 位置插入 n 个 val
首先判断 position 的合法性（注意 assert 在 release 版本代码中不起作用，后面需要使用捕获异常），其次检查空间是否足够，如果不够就按照 2 倍来开足够的空间，最后挪动元素，并插入 n 个 val
size_t capacity(){return _end_of_storge - _start;}size_t size(){return _finish - _start;}void insert(iterator position, size_t n, const T& val){assert(position >= _start && position <= _finish);if (_finish + n > _end_of_storge){size_t new_capacity = capacity() == 0 ? 6 : capacity * 2;reserve(new_capacity);}}如果空间不够，扩容至 new_capacity，实现扩容函数 reserve
reserve
reserve 中在开好空间后，需要实现深拷贝，那么使用 T 类型的赋值重载 解决两个已经存在的对象间的深拷贝问题；至于 T 类型的赋值重载怎么实现的，那是 T 类的事情，不关我 myVector 的事（当然此处默认 T 类有默认构造、赋值重载）
实际上，如果 T 没有实现深拷贝的赋值重载就 g 了；
iterator src = _finish;
while (src != position) {--src;new (src + n) T(*src); // 拷贝构造到目标地址(src)->~T(); // 析构原位置对象（可选）
}所以其实使用 placement new 定位 new 来拷贝构造未初始化的内存是更完美的方法
void reserve(size_t n){if (n > capacity()) // 需要扩容的容量 大于 实际容量时才执行扩容{size_t old_size = size();T* tmp_start = new T[n];if (size() > 0) // 有内容才需拷贝，且需要实现深拷贝{for (size_t i = 0; i < size(); i++) // 循环次数即元素个数{*(tmp_start + i) = *(_start + i); // 调 T 类型的赋值重载处理深拷贝}}delete[] _start;_start = tmp_start;_finish = _start + old_size;_end_of_storge = _start + n;}}回到 insert，扩完空间后，从 position 向后挪动 n 个位置，并插入 n 个 val
void insert(iterator position, size_t n, const T& val){assert(position >= _start && position <= _finish);if (_finish + n > _end_of_storge) // 扩容{size_t new_capacity = capacity() == 0 ? 6 : capacity() * 2;reserve(new_capacity);}iterator begin = _finish; // 从后向前挪动while (begin > position){begin--;*(begin + n) = *begin;}for (size_t i = 0; i < n; i++) // 插入 n 个 val{*(position + i) = val;}_finish += n;}bug 出现：异地扩容后迭代器的失效
在经过下面这段代码之前，position 指向原空间的某位置；如果发生了异地扩容，但是 position 没有跟着改变，那么就变成了悬空迭代器 or 野指针
if (_finish + n > _end_of_storge) // 扩容{size_t new_capacity = capacity() == 0 ? 6 : capacity * 2;reserve(new_capacity);}
所以我们需要在扩容前，记录下 position 的偏移量，在扩容后更新
void insert(iterator position, size_t n, const T& val){assert(position >= _start && position <= _finish);if (_finish + n > _end_of_storge) // 扩容{size_t pos_offset = position - _start; // 记录 position 偏移量size_t new_capacity = capacity() == 0 ? 6 : capacity() * 2;reserve(new_capacity);position = _start + pos_offset; // 更新 position}iterator begin = _finish; // 从后向前挪动while (begin > position){begin--;*(begin + n) = *begin;}for (size_t i = 0; i < n; i++) // 插入 n 个 val{*(position + i) = val; // T 类的赋值重载}_finish += n;}包一丝，下面这段 定位 new 的 代码应该是 挪动数据时，对 _finish 后未初始化的内存，拷贝时用的
iterator src = _finish;
while (src != position) {--src;new (src + n) T(*src); // 拷贝构造到目标地址(src)->~T(); // 析构原位置对象（可选）
}增 -- push_back
void push_back (const T& val);
复用 insert
void push_back(const T& val){insert(_finish, 1, val);}删 -- erase
iterator erase (iterator position);
删掉 position 位置的元素，返回被删掉元素后那个元素的迭代器
这里是实现删掉一个元素，标准库还提供了重载是删除迭代器区间的元素；整体从前向后挪动元素覆盖掉要删除的元素即可
iterator erase(iterator position){assert(position >= _start && position <= _finish);iterator begin = position + 1;while (begin < _finish){*(begin - 1) = *begin;begin++;}_finish--;return position;}删 -- pop_back
void pop_back();
复用 erase
void pop_back(){erase(_finish - 1);}operator[ ]
重载 [ ] 运算符
T& operator[](size_t i){return *(_start + i);}拷贝构造
拷贝构造也是构造，也走一遍初始化列表
这里在 拷贝 数据时，可以复用 push_back，因为 push_back 中实现了深拷贝逻辑；
但是如果不复用，可以直接使用 定位 new 来对申请好未初始化的内存 拷贝构造，最后处理 _finish 和 _end_of_storge，也是比较完美的方法；vector 里装 内置类型 和 自定义类型都可以解决
myVector(const myVector<T>& v):_start(nullptr),_finish(nullptr),_end_of_storge(nullptr){this->reserve(v.capacity()); // 为 this 分配 和 v 一样大的原始内存for (size_t i = 0; i < v.size(); i++){//push_back(v[i]);new (_start + i) T(v[i]); // 使用定位 new 来拷贝构造}_finish = _start + v.size();_end_of_storge = _start + v.capacity();}析构函数
~myVector(){delete[] _start;_start = _finish = _end_of_storge = nullptr;}resize
void resize (size_t n, T val = T());
resize 的功能分段考虑，如果 n <= this->size( ) ，那么将 size( ) 减小至 n；如果 n > this->size( )，那就将 size( ) 扩大到 n，被扩充的元素值设置为 val
void resize(size_t n, T val = T()){if (n <= size()) // 删掉 size() - n 个元素{_finish = _start + n;}else{reserve(n); // 如果 n < capacity() reserve 什么也不会做while (size() < n){// *_finish = val;new (_finish) T(val);_finish++;}}}考虑一个问题：如果 T 类型中申请了资源，而我们在 n <= this->size( ) 又没有释放，不就内存泄露了？所以在删掉元素时，应当显式调用析构函数清理；那么如果 T 是内置类型，调用析构函数的操作会被编译器优化成 空操作的
void resize(size_t n, T val = T()){if (n <= size()) // 删掉 size() - n 个元素{// _finish = _start + n;while (_start + n != size()){_finish--;_finish->~T(); // 显式调用 T 析构函数，适配资源清理情况}}else{reserve(n); // 如果 n < capacity() reserve 什么也不会做while (size() < n){// *_finish = val;new (_finish) T(val);_finish++;}}}小结
容器中存储的可能是 内置类型 或 自定义类型 或 有申请内存资源的自定义类型，在实现 容器内元素 的拷贝逻辑时，用 placement new 是比较标准的做法，它会调用该类型的 拷贝构造 完成对所申请原始内存的初始化。
不过没有使用 try catch 来捕获可能的异常。