git仓库地址：https://gitee.com/tgwTTT/c-lreant.git

一.vector的定义：在 C++ 中，vector 是标准模板库（STL）提供的一个动态数组容器，位于头文件 中。它可以自动管理内存，支持动态扩容，是 C++ 中最常用的容器之一。

(constructor)构造函数声明接口说明
vector()无参构造
vector（size_type n, const value_type& val = value_type()）构造并初始化n个val
vector (const vector& x); 拷贝构造
vector (InputIterator first, InputIterator last);使用迭代器进行初始化构造

二.vector iterator 的使用

iterator的使用接口说明
begin + end（重点）获取第一个数据位置的iterator/const_iterator， 获取最后一个数据的下一个位置的iterator/const_iterator
rbegin + rend获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置的reverse_iterator

vector接口说明：

容量空间接口说明
size获取数据个数
capacity获取容量大小
empty判断是否为空
resize（重点）改变vector的size
reserve （重点）改变vector的capacity
push_back（重点）尾插
pop_back （重点）尾删
find查找。（注意这个是算法模块实现，不是vector的成员接口）
insert在position之前插入val
erase删除position位置的数据
swap交换两个vector的数据空间
operator[] （重点）像数组一样访问

三.vector简单实现

vector的底层是一个简单的线性表，它是一个在堆上连续存储、支持动态扩容的类模板，内部只保存 3 个裸指针（或等价信息）来管理这块内存。

iterator _start = nullptr;//首地址
iterator _end_of_storage = nullptr;//最大容量地址
iterator _finish = nullptr;//最后一个元素的下一个地址
1.动态扩容策略
当 size() == capacity() 时：
申请新内存：
分配 new_capacity = max(old_capacity * k, 1)，其中 k 通常是 2（GCC/Clang）或 1.5（MSVC）。
移动/复制元素：
如果 T 有 noexcept 的移动构造，则 std::move；否则拷贝。
销毁旧元素并释放旧块：
更新 3 个指针：
指向新的更大块。
因此 push_back 的摊还时间复杂度是 O(1)。
下面是push_back的实现：
void push_back(const T& x) {
	if (_finish == _end_of_storage) {//满了就扩容
		reserve(capacity() == 0 ? 4 : capacity() * 2);
	}
	*_finish = x;
	++_finish;
}
void reserve(size_t n) {
	if (n > capacity()) {
		size_t old_size = size();
		cout << "扩容" << n << endl;
		T* tmp = new T[n];
		memcpy(tmp, _start, sizeof(T) * size());
		delete[]_start;
		_start = tmp;
		_finish = _start + old_size;
		_end_of_storage = _start + n;
	}
}
size_t size() {
	return _finish - _start;
}
size_t capacity() {
	return _end_of_storage - _start;
}
二.erase()的实现
1.计算移动距离
2.如果 len > 0,直接交换
3.析构尾部多余元素
4.调整 finish_ 指针
下面是代码演示：
oid Erase(iterator pos)
		{
			assert(pos >= _start);
			assert(pos < _finish);

			iterator it = pos + 1;
			while (it != end())
			{
				*(it - 1) = *it;
				++it;
			}

			--_finish;
		}
常见误区：
删除后迭代器失效：返回值是唯一仍有效的迭代器，其余全部失效。
capacity 不变：erase 只改 size。
对 bool vector 的特殊实现：std::vector 是 bit 压缩，erase 需要位操作，与普通 vector 实现完全不同。

其余完整代码在git仓库。今天的更新就到这，如有错误欢迎评论区指出