今天我我来进行vector的模拟实现，先简单的实现一下初步功能，使其对内置类型可以适配。（大部分与string很类似）
1 认识vector
开始了解
vector是表示可变大小数组的序列容器。
就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。
vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。
与其它动态序列容器相比（deque, list and forward_list）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起list和forward_list统一的迭代器和引用更好。
使用STL的三个境界：能用，明理，能扩展 ，那么下面学习vector，我们也是按照这个方法去学习
底层实现 我们来了解一下vector的底层实现是如何做到，首先就要了解其类成员是如何定义的，这样我们才能更好的复刻vector（以下是1996年的STL版本，还比较简单）：
protected: typedef simple_alloc<value_type, Alloc> data_allocator; iterator start; iterator finish; iterator end_of_storage //容量结束; 复制 可以看到受保护的内部成员变量是由三个迭代器构成的。 迭代器的底层是：
typedef T value_type; typedef value_type* iterator; 复制 也就是说底层是指针，T是模版类的参数。接下来我们在观察一下构造函数是如何操作的(参考一部分)：
vector() : start(0), finish(0), end_of_storage(0) {} vector(size_type n, const T& value) { fill_initialize(n, value); } vector(int n, const T& value) { fill_initialize(n, value); } vector(long n, const T& value) { fill_initialize(n, value); } 复制 这个fill_initialize又是什么呢？？？是初始化函数，（在工程文件中，经常使用一层又一层的嵌套，由于我还没有丰富的工程经验，我看起来还是很费劲，晕乎乎的）。我们看一部分即可，现在我们开始手搓vector，针对内置类型进行操作。
2 开始实现 我们开始逐步进行实现。
成员变量 根据我们刚才所查看的源码，我们要使用三个迭代器，要使用迭代器，我们可以使用指针进行模拟。
//使用模版 兼容各种类型 template<typename T> class vector { public: //重命名 指针即可模拟迭代器 常量与非常量都要提供哦 typedef T* iterator; typedef const T* const_iterator; private: iterator _start = nullptr; iterator _finish = nullptr; iterator _end = nullptr; }; 复制 写出三个迭代器（指针）后，我们对构造函数应该也有了大致思路：需要初始化三个迭代器，所以我们给与初始值nullptr。让后进行开辟空间。
构造函数 析构函数 这里的构造函数我设置三个接口，一个是空构造，一个是开辟 N 个空间并初始化为val，一个是拷贝构造:
//空构造 vector() {} //开辟 N 个空间并初始化为val vector(size_t n,T val = T()) { iterator tmp = new T[n]; _start = tmp; for (iterator it = begin(); it < _start + n ;it++) { *it= val; } _finish = _start + n; _end = tmp + n ;
} /拷贝构造 vector(vector<T>& v) { //依次尾插即可完成操作 for (auto s : v) { push_back(s); } } 复制 析构函数就是简单的释放空间即可：
1~vector() 2{ 3 delete[] _start; 4 _start = _finish = _end = nullptr; 5}
复制 我们完成了构造函数和析构函数，为了能够进行测试，我们现在来实现尾插操作：
尾插 尾插操作之前，根据我们实现string的经验来说，我们需要做一些准备工作，实现一些常用接口（size(),capacity(),reserve(),resize()）: 注意：如果对象中涉及到资源管理时，千万不能使用memcpy进行对象之间的拷贝，因为memcpy是浅拷贝，否则可能会引起内存泄漏甚至程序崩溃。
1 //注意const 保证不会进行权限的放大 2 size_t size() const{ 3 return _finish - _start; 4 } 5 size_t capacity() const{ 6 return _end - _start; 7 } 8 bool empty(){ 9 return size() == 0; 10 } 11 //扩容 12 void reserve(size_t newcapacity) { 13 //记录位置 14 size_t n = _finish - _start; 15 T* tmp = new T[newcapacity]; 16 //拷贝 17 memcpy(tmp, _start, size() * sizeof(T)); 18 _start = tmp; 19 _finish = _start + n; 20 _end = _start + newcapacity; 21 } 22 //改变大小 23 void resize(size_t n, T val = T()) { 24 //x需要扩容 25 if ( n > size()) 26 { 27 reserve(n); 28 ; 29 while (_finish != _end) { 30 *_finish = val; 31 _finish++; 32 } 33 34 } 35 //不需扩容 36 else 37 { 38 _finish = _start + n; 39 } 40 }
复制 实现了这些接口，就可以顺畅的进行尾插的书写，通过size（）和capacity（）可以判断是否需要扩容，reserve可以进行扩容。然后再_finish位置插入新的数据，再移动_finish即可。
1 //尾插 2 void push_back(T val) 3 { 4 if (size() == capacity()) { 5 //扩容 6 reserve(capacity() == 0 ? 4 : 2 * capacity()); 7 } 8 *_finish = val; 9 _finish++; 10 }
复制 接下来我们在完善一下迭代器。
迭代器 迭代器的实现很简单，对指针进行重命名即可（真正的迭代器没有这么简单）
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; } 复制 完成了begin（） 和end()函数，就可以使用基于范围的for循环了。 我们进行一个简单的测试，来看看我们写的构造，尾插是否正常。
template<class T> void print_vector(const vector<T> v) { for (size_t i = 0; i < v.size(); i++) { cout << v[i] << " "; } cout << endl; } //构造，尾插测试 void vector_test1() { cout << "---------构造 ，尾插测试---------\n"; vector<int> v1; vector<int> v2(4);
1v2.push_back(1); 2v2.push_back(2); 3v2.push_back(3); 4v2.push_back(4); 5 6print_vector(v2); 7 8v1.push_back(5); 9v1.push_back(6); 10print_vector(v1); 11cout << v1.size() << endl; 12cout << v1.capacity() << endl; 13 14vector<int> v3(v1); 15print_vector(v3);
} 复制 看一下效果：
没有问题！！！
插入 删除 寻找操作 这个也很简单，对数据进行挪动就可以完成：
//任意位置插入 void insert(size_t pos = 0,T val = T()) { //保证在数据范围之内 assert(pos >= 0); assert(pos <= size()); //检查 if (size() == capacity()) { //扩容 reserve(capacity() == 0 ? 4 : 2 * capacity()); }
1iterator it = end(); 2//依次后移 然后插入 3while (it >= begin() + pos) { 4 *(it + 1) = *it; 5 it--; 6} 7it++; 8*it = val; 9_finish++;
} void erease(size_t pos) { //保证在数据范围之内 assert(pos >= 0); assert(pos <= size());
1iterator it = begin() + pos; 2//依次前移 3while (it < end()) { 4 *it = *(it + 1); 5 it++; 6} 7_finish--;
} //尾删 void pop_back() { erease(size());
} size_t find(T val = T()) { //依次寻找 for (iterator it = _start; it < _finish;it++) { if (*it == val) return it - _start; } return -1; } 复制 操作符重载 vector容器最重要的操作符应该就是[ ]操作了吧，此外重载一个 = ：
//提供常量与非常量 T& operator[](size_t n) { assert(n >= 0); assert(n < size()); return *(_start + n); } const T& operator[](size_t n) const { assert(n >= 0); assert(n < size()); return *(_start + n); } //类似拷贝 vector<T>& operator=(vector<T>& v){
1T* tmp = new T[v.capacity()]; 2memcpy(tmp, v._start, v.size() * sizeof(T)); 3size_t pos = v.size(); 4size_t n = v.capacity(); 5 6_start = tmp; 7_finish = _start + pos; 8_end = _start + capacity(); 9 10return *this;
} 复制 这样就完成了： 我们进行一个测试来看看是否可行：
void vector_test2() { cout << "---------resize find insert erase测试---------\n";
1vector<int> v1; 2 3v1.push_back(1); 4v1.push_back(2); 5v1.push_back(3); 6v1.push_back(4); 7v1.push_back(5); 8v1.push_back(6); 9print_vector(v1); 10cout << v1.find(2) << endl; 11 12v1.resize(10, 0); 13print_vector(v1); 14v1.insert(0, 0); 15print_vector(v1); 16v1.erease(5); 17print_vector(v1);
} 复制 来看效果：
成功！！！
swap函数 接下来在提供一个swap 函数以供交换，注意一定是深拷贝！！！
1 void swap(vector& v) { 2 3 T* tmp = new T[v.capacity()]; 4 memcpy(tmp, v._start, v.size() * sizeof(T)); 5 size_t pos = v.size(); 6 size_t n = v.capacity(); 7 8 v._start = _start; 9 v._finish = _finish; 10 v._end = _end; 11 12 _start = tmp; 13 _finish = _start + pos; 14 _end = _start + capacity(); 15 16 17 }
复制 来进行一个简单测试：
//交换测试 void vector_test3() { cout << "---------swap 测试---------\n"; vector<int> v1;
1v1.push_back(1); 2v1.push_back(2); 3v1.push_back(3); 4v1.push_back(4); 5v1.push_back(5); 6v1.push_back(6); 7print_vector(v1); 8vector<int> v2(4); 9 10v2.push_back(1); 11v2.push_back(3); 12v2.push_back(1); 13v2.push_back(4); 14print_vector(v2); 15v2.swap(v1); 16 17print_vector(v1); 18print_vector(v2);
}