【C++】—— vector 的模拟实现

0 前言

  前面，我们学习了 $string$，并模拟实现了它，下面我们来学习 $vector$
  $vector$ 的底层即我们前面曾经学过的顺序表，它属于 STL库，为了让我们更加深入理解 $vector$，接下来我们将模拟实现 $vector$
    
  

1 vector 的成员变量

1.1 stl 库中的 vector 成员变量

  我们学习数据结构时，曾经模拟实现过顺序表。当时我们用一个指针 $a$ 管理从堆开辟的空间，$size$ 表示当前有效数据的个数，$capacity$ 表示当前空间的大小。
  
  但是，$stl$库 中的 $vector$ 的成员变量有所差别：它的成员变量是三个迭代器

  
  我们知道，迭代器全部都是 $typedef$ 出来的，那 $vector$ 的迭代器是什么呢？

  可以看到，其迭代器就是 原生指针！

  那start、finish、end_of_storage 变量又是什么意思呢？面对未知的东西，我们应大胆假设，小心求证。

  不管他底层如何，$vector$ 终究逃不过扩容，那我们不难猜想：start 肯定是一个指针指向一个开始，finish指向某个结束，至于end_of_storage，$storage$ 是存储的意思，所以我们大胆猜测end_of_storage与空间相关，可能就是空间结束位置；那这样的话finish 可能表示数据的结束

  那我们怎么取求证呢？我们可以通过一些我们熟悉功能的函数来确认

  
  可以看到，$begin$ 返回的是第一个有效数据位置，这里是start；而 $end$ 返回的是最后一个有效数据的下一个位置，这里返回的是finish；$capacity$ 表示空间的大小，这里返回的是end_of_storage - begin()。
  因此我们的猜测是正确的，那么 $vector$ 的底层结构如下：

注：finish 指向的是有效空间的下一个位置
  
  

1.2 模拟实现 vector 成员变量

  我们模拟实现的 $vector$ 的成员变量，也学习库中的形式

namespace my_vector
{template<class T>class vector{public://···private:iterator _start = nullptr;iterator _finish = nullptr;iterator _end_of_storage = nullptr;};
}

  这里，为了与库中的 $vector$ 区别开，我们使用命名空间

  同时，因为顺序表应满足不同数据类型的存储，我们实现的不是某个具体类型的类，而是类模板。既然是模板，那么函数的声明与定义就不能放在不同的文件中，因此声明和定义全在vector.h文件中，不再需要vector.cpp文件。

  
  

2 迭代器

  因为 $vector$ 的迭代器是一个原生指针，与 $string$ 类似，很简单，我们直接看代码

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;
}

  因为 _$finish$ 本就就是只想最后一个有效数据的下一位，因此我们end()我们直接返回 _finish 即可

  
  

3 size、capacity、empty

  这三个函数都很简单，我们直接看代码

size_t size() const
{return _finish - _start;
}size_t capacity() const
{return _end_of_storage - _start;
}bool empty() const
{return _start == _finish;
}

  
  

4 opreator[ ]

  $vector$ 中的 $opreator$[] 与 $string$ 中的 $operator$[] 类似，都是访问第 $i$ 个数据的元素。同样，$vector$ 的 $operator$[] 也要用 $assert$ 断言来判断下标是否合法

T& operator[](size_t i)
{assert(i < size());return _start[i];
}const T& operator[](size_t i) const
{assert(i < size());return _start[i];
}

  
  这里顺便提一下，$vector$ 还提供了 at 函数 接口。
  $at$ 函数与 $operato$[] 功能相同，但他们检查越界的方式不同
  $at$ 函数是抛异常，而 $operator$[] 是断言
  
  

5 reserve

5.1 初版 reserve

void reserve(size_t n)
{if (n > capacity()){			T* tmp = new T[n];memcpy(tmp, _start, sizeof(T) * size());delete[] _start;_start = tmp;_finish = _start + size();_end_of_storage = _start + n;}
}

  在 $string$ 中，我们已经模拟实现 $reserve$ 了，$vector$ 中也是需要我们手动释放和拷贝的数据的，代码细节就不再细讲了。

  那上面代码有问题吗？
  有的

5.2 _finish 的处理

  首先是对 _$finish$ 的处理上
  这里我们更新_finish的方式是_start + size()，可是 size() 是怎么计算出来的？是通过_finish - _start计算出的，可是此时 _$start$已经更新了，而_$finish$还未更新 ，此时他们相减会出大问题。

  怎么解决呢？也很好办，那就是提前记录 $size$() 的值

void reserve(size_t n)
{if (n > capacity()){//记下size()的值size_t old_size = size();T* tmp = new T[n];memcpy(tmp, _start, sizeof(T) * size());delete[] _start;_start = tmp;_finish = _start + old_size;_end_of_storage = _start + n;}
}

  
  

5.3 深拷贝

  还有一点，上述代码用 $memcpy$ 拷贝是浅拷贝，而我们需要的是深拷贝

  用 $memcpy$ 拷贝有什么问题呢？

void test7()
{vector<string> v1;v1.push_back("11111");v1.push_back("11111");v1.push_back("11111");v1.push_back("11111");print_container(v1);v1.push_back("11111");print_container(v1);
}

运行结果：

  程序崩溃了！
  为什么呢？问题出现在了扩容！

  我们知道 $vector$<$string$> 中，每个 $string$ 都指向一块堆空间。
  虽然 $vector$ 是深拷贝，但是 $vector$ 中的每个 $string$ 都是浅拷贝，而每个string都指向一块资源。这意味着新开辟的 $tmp$ 中，每个 string 都是与对应旧空间的 string 指向同一块空间，$delete$ 后，会调用析构函数，将旧空间指向的资源全部释放掉，此时新空间的每个 $string$ 都是指向一块已经被释放的空间，自然会出现问题。

  
  那如何解决呢？那就是对vector中的每个成员都进行深拷贝。我们不能再使用 $memcpy$，而是要自己赋值

void reserve(size_t n)
{if (n > capacity()){		size_t old_size = size();T* tmp = new T[n];for (size_t i = 0; i < old_size; ++i){_tmp[i] = _start[i];}delete[] _start;_start = tmp;_finish = _start + old_size;_end_of_storage = _start + n;}
}

  _tmp[i] = _start[i];是赋值，本质是调用自定义类型的赋值重载函数，实现了每个成员的深拷贝，而[ ]，则是前面实现的operator[]重载函数

  
  

5.4 终版

void reserve(size_t n)
{if (n > capacity()){		size_t old_size = size();T* tmp = new T[n];for (size_t i = 0; i < old_size; ++i){_tmp[i] = _start[i];}delete[] _start;_start = tmp;_finish = _start + old_size;_end_of_storage = _start + n;}
}

  
  

6 push_back 与 pop_back

  $push$_$back$ 直接往尾部放数据即可，但要注意空间不够要扩容

void push_back(const T& x)
{if (_finish == _end_of_storage){size_t n = size() == 0 ? 4 : 2 * size();reserve(n);}*_finish = x;++_finish;
}

  
  $pop$_$back$ 也很简单，但要注意判断是否为空。

void pop_back()
{assert(!empty());--_finish;
}

  
  

7 打印函数

  STL库 中，$vector$ 是没有重载 $operator$<< 的。
  为什么呢？因为库事先并不知道你要以什么形式打印：是连续打印，还是每打印一个数据就空格还是每打印一个就换行？而且自己实现一个打印函数并不困难。因此库就交给程序员自己实现。
  

7.1 初写打印

  那么我们就自己实现一个打印函数吧。
  打印函数是一个全局函数

template<class T>
void print_vector(const vector<T>& v)
{vector<T>::const_iterator it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;
}

  但上述函数写的是有问题的

  

7.2 typename 关键字

  为什么呢？
  问题出现在vector<T>::const_iterator it;中

  可以直接突破类域，用类名::方式去类中取东西，能取到两种：一种是 静态成员变量，另一种是在 类中 $typedef$ 的类型。
  
  C++规定：类模板没有被实例化之前，编译器是不会往里面去取东西的。
  编译器走到 $print$_$vector$ 时，$vector$ 模板还没被实例化出来。而因为不敢去模板中取，编译器不知道 $const$_$iterator$ 是 类型 还是 静态成员变量，如果取到静态成员变量，后面还跟着变量 it 就会出大问题。因此编译器报错。

  要解决上述问题，需在前面加上 $typename$ 关键字。加上 $typename$，即明确告诉编译器 $const$_$iterator$ 是类型。（可以看做编译器的甩锅。编译器：你说了是类型的啦，我给你过了，如果他是成员变量的话那也是你的问题，不怪我）
  但如果是取静态成员变量，前面什么都不用加，因为如果真是静态成员变量，你不会像vector<T>::const_iterator it这样用的，直接就vector<T>::const_iterator;这样
  

template<class T>
void print_vector(const vector<T>& v)
{//没有实例化的类模板里面取东西，编译器不能区分const_iterator是类型还是静态成员变量typename vector<T>::const_iterator it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;
}

  这样就可以啦
  
  当然，这还有一种更简单的方式，用 $auto$ 就没有那么麻烦，因为 $auto$ 直接是由v.begin()推导而来

template<class T>
void print_vector(const vector<T>& v)
{	auto it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;
}

  
  

7.3 打印函数进阶

  但上述打印函数，稍稍改进一下，就可以变成所有类型容器的打印函数，而不仅仅是 $vector$ 类型的

template<class Container>
void print_container(const Container& v)
{auto it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;
}

  需要注意的是判断条件while (it != v.end())只能是 !=，有些小伙伴可能会写while (it < v.end())。对于 $string$ 与 $vecto$r 来说是没问题，因为他们本来就是原生指针；但对其他容器就不行了，比例 $list$ 链表，它的 $iterator$ 是一个类，不存在比较大小的概念。
  
  

8 insert

8.1 insert 初版

void insert(iterator pos, const T& x)
{assert(pos >= begin() && pos <= end());if (_finish == _end_of_storage){size_t n = size() == 0 ? 4 : 2 * size();reserve(n);}iterator i = end();while (pos != i){*i = *(i - 1);--i;}*pos = x;++_finish;
}

  上述代码其实是有问题的
  我们一起来看看
  

8.2 迭代器失效

8.2.1 情况一：类似野指针

  上述代码其实是有问题的
  我们先来测试一个不需要扩容的

void test1()
{vector<int> v1;v1.reserve(10);v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.insert(v1.begin() + 1, 10);print_vector(v1);
}

运行结果：

  没有问题
  

  那再来一个需要扩容的

void test1()
{vector<int> v1;v1.reserve(4);v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.insert(v1.begin() + 1, 10);print_vector(v1);
}

运行结果：

  可以看到，报错了

  为什么呢？这是因为 $pos$ 迭代器失效了

  我们结合图来看就很容易看懂了。扩容后，pos 依然指向旧空间，此时旧空间已经被释放了，$pos$ 迭代器就是一个野指针，同时while (pos != i)判断语句永远也不会成立，造成死循环。

  怎么办呢？我们应记录 pos 迭代器与 _start 的相对位置，再将 pos 映射到新空间中

void insert(iterator pos, const T& x)
{assert(pos >= begin() && pos <= end());if (_finish == _end_of_storage){size_t len = pos - _start;size_t n = size() == 0 ? 4 : 2 * size();reserve(n);pos = _start + len;}iterator i = end();while (pos != i){*i = *(i - 1);--i;}*pos = x;++_finish;
}

  

8.2.2 algorithm 库中的查找函数

  这里，介绍 $algorithm$ 库中的查找函数，$find$ 函数模板适用于所有的容器，只需要传一个迭代器区间给它，就能帮你查找

  库中的 $find$函数 是一个模板：

  需要注意的是，传值要传左闭右开区间

  
  

8.2.3 情况二：insert 后再对 pos 进行访问

8.2.3.1 不扩容的情况

  我们知道，$insert$ 函数的 $pos$ 形参是一个迭代器，如果我们想在指定数据之前插入数据，就可以用 find 模板找到相应数据的迭代器

  现在，我用 $find$函数 找到 $p$ 为 5 的位置，在之前插入数据 100，并将 5 $\ast$ 10

void test2()
{vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);v1.push_back(6);int x = 5;auto p = std::find(v1.begin(), v1.end(), x);if (p != v1.end()){v1.insert(p, 40);*(p) *= 10;}print_container(v1);
}

运行结果：

  为什么是100 * 10 呢？
  这是因为迭代器失效了，在 $insert$ 以后，我们可以认为迭代器 p 就已经失效了。我们结合图来理解

  用 $insert$ 插入数据后，$p$ 指向的位置已经变了。你以为它指向的还是 5，但实际上他已经变了
  

8.2.3.1 扩容的情况

  上述情况还不是最恐怖的，最恐怖的是扩容的情况

void test3()
{vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);int x = 2;auto p = std::find(v1.begin(), v1.end(), x);if (p != v1.end()){v1.insert(p, 100);*(p) *= 10;}print_container(v1);
}

运行结果：

  现在连100 都不乘10了，为什么呢？还是迭代器失效的问题，我们来看图

  $pos$ 的位置还是指向旧空间，这时再对 $pos$ 访问，就是类似于野指针的访问。
  

8.2.4、解决方法

8.2.4.1、想法一

  那应该怎么解决上述问题呢？
  在解决完第一种情况的代码中，我们在函数内是对 $pos$ 进行了更新的

  
   但是形参的改变并不影响实参，那我们可不可以用引用呢？

void insert(iterator& pos, const T& x)

  这样，$pos$ 是引用，就能改变函数外的 $p$ 了。
  
  但这样是不行的，因为会影响传参

vector<int> v;
v1.insert(v1.begin(), 10);

  像这样，我们传递第一个迭代器，但这样传参，v1.begin()的返回值中间会产生一个临时变量，实际传递的就是这个临时变量。临时变量是常性，必须用 $const$ 引用，普通的引用是传不进去的。
  
  那如果我加 $const$ 呢？

void insert(const iterator& pos, const T& x)

  加了 $const$，里面的 $pos$ 就无法改变了，所以还是不行
  
  

8.2.4.2、想法二

  我们来看一下库中的 $insert$ 是怎么处理的

  库中给了一个返回值，返回的是更新之后的 $pos$。

iterator insert(iterator pos, const T& x)
{assert(pos >= begin() && pos <= end());if (_finish == _end_of_storage){size_t len = pos - _start;size_t n = size() == 0 ? 4 : 2 * size();reserve(n);pos = _start + len;}iterator i = end();while (pos != i){*i = *(i - 1);--i;}*pos = x;++_finish;return pos;
}

  所以如果真要 $insert$ 后继续访问 $p$，一定要更新 $p$ 再访问

void test4()
{vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);int x = 2;auto p = std::find(v1.begin(), v1.end(), x);if (p != v1.end()){p = v1.insert(p, 100);*(p + 1) *= 10;}print_container(v1);
}

运行结果：

  

8.3 总结

  用 $insert$ 后，迭代器 p 就失效了，最好的办法就是不再用 $p$ 去访问。如果非要访问，一定要更新一下迭代器 $p$ 再去访问

  
  

9 erase

iterator erase(iterator pos)
{assert(pos < end() && pos >= begin());iterator i = pos;while (i != end() - 1){*(i) = *(i + 1);++i;}--_finish;return pos;
}

  同样，$erase$ 也存在迭代器失效的问题。我们使用的时候一定要注意！$erase$之后就不要再访问迭代器，一定要访问也要先更新再访问，更新后的迭代器指向要删除数据的下一个位置
  
  

10 resize

void resize(size_t n, const T& val = T())
{if (n < size()){_finish = _start + n;}else{reserve(n);while (_finish < _start + n){*_finish = val;++_finish;}}
}

  $resize$ 的功能与实现这里就不再过多解释，这里大家直接看代码即可。

  这里我们重点讲一下 const T& val = T()的写法
  这是自定义类型给缺省值的方法。因为 $vector$ 是模板，给缺省值时不能再像 const T& val = 0 这样给，因为是模板，你不知道 T 是什么类型，像前面给 0 就表示 T 一定是 0 了，肯定是不合适的。T 可能是 $int$，可能是 $double$、也可能是自定义类型。

  如果是自定义类型的对象，我们就调用它的默认构造。上述给缺省值的方法就是给 T 的一个匿名对象并调用它的默认构造。

  那如果 T 是内置类型：$int$、$double$怎么办？他们没有默认构造这一概念啊
  在此之前，我们确实是认为默认函数是没有构造函数这一概念的，但是为了兼容像模板这样的场景，内置类型也有了构造函数的概念(还有析构函数的概念)。

void test5()
{int i = int();int j(1);cout << i << endl;cout << j << endl;cout << int(2) << endl;
}

运行结果：

  
  

11 构造函数系列

11.1 默认构造

vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr)
{}

  但实际上，并不需要这么麻烦，因为我们在成员变量声明时，结了缺省值，我们这样就可以了

vector() {}

  学习类与对象时，我们知道：所有成员都会走初始化列表。如果我们没有显式写在初始化列表，对于内置类型：没有缺省值不做任何处理，但现在我们在成员变量声明时，结了缺省值，则用缺省值初始化。
  
  在C++11中，给了一个方式可以 强制生成默认构造：

vector() = default;

  因为编译器只有在程序员没有自己实现任何构造函数（拷贝构造也是构造）时才会生成默认构造，如果我们自己实现了带参的构造，又想编译器生成默认构造，就可以用上述语法
  
  

11.2 拷贝构造

vector(const vector<T>& v)
{reserve(v.capacity());for (auto& e : v){push_back(e);}
}

  拷贝构造，就是遍历 对象$v$，将 $v$ 的值全部 $push$_$back$ 进 $this$ 中。这里范围for用了引用，是为了减少拷贝，而为了避免频繁的扩容，使用 $reserve$ 提前开辟空间。

  
  

11.3 迭代器区间构造 与 n 个 value 构造

11.3.1 迭代器区间构造

  在stl库中，还提供了一个构造方法：迭代器区间构造

  这里讲一个新的知识点：类模板里面的成员函数可以是函数模板

为什么要用模板呢？这样不行吗？

vector(iterator first, iterator last)

  如果是这样的话，那么迭代器构造只能用 $vector$ 迭代器构造，如果是函数模板的话可以用任意的迭代器进行构造
  
代码如下：

template<class InputIterator>
vector(InputIterator first, InputIterator last)
{while (first != last){push_back(*first);++first;}
}

测试：

void test6()
{list<int> l1;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);l1.push_back(5);l1.push_back(6);vector<int> v1(++l1.begin(), --l1.end());print_vector(v1);
}

运行结果：

  可见，迭代器区间可以用任意容器迭代器进行初始化，但它要求类型是匹配的
  
  

11.3.2 n 个value构造

  $n$ 个 $value$ 的构造很简单，不断 $push$_$back$ 就行

vector(size_t n, const T& val = T())
{reserve(n);while (n--){push_back(val);}
}

  

11.3.3 注意事项

  调用 $n$ 个 $value$ 的构造函数时，会出现一个很奇怪的报错

void test7()
{vector<int> v(10, 1);print_vector(v);
}

  
  为什么我调用的时 $n$ 个 $value$ 的构造，结果报错报到迭代器区间的构造了呢？
  这是因为编译器把vector<int> v(10, 1);中的 10 和 1 识别成两个迭代器了。
  为什么会这样呢？编译器有一个原则，那就是匹配最匹配的

  我们先来看 $n$ 个 $value$ 的构造
  vector(size_t n, const T& val = T())对 10 和 1 来说，T 是 $int$ 是确定的
  但是 $n$ 是 $size$_$t$，$int$ 要进行类型转换

  再看迭代器区间构造
  vector(InputIterator first, InputIterator last)，它实例化出来是两个 $int$，不用类型转换，所以编译器选择迭代器区间构造

  那怎么解决呢？
  stl库中选择重载多个 $n$ 个 $value$ 的构造函数，让你永远有更好的选择

 vector(size_t n, const T& value = T()){reserve(n);while (n--){push_back(value);}}vector(int n, const T& value = T()){reserve(n);while (n--){push_back(value);}}vector(long long n, const T& value = T()){reserve(n);while (n--){push_back(value);}}

  
  

12 赋值运算符重载

  赋值运算符重载分为现代写法与传统写法，这在 $string$ 的模拟实现中讲过类似的，这里就不再细讲了，我们直接看代码
  

12.1 传统写法

void clear()
{_finish = _start;
}vector<T>& operator=(const vector<T>& v)
{clear();if (this != &v){reserve(v.capacity());const_iterator it = v.begin();while (it != v.end()){push_back(*it);++it;}}return *this;
}

  

12.2 现代写法

void swap(vector<T>& v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);
}
vector<T>& operator=(vector<T> tmp)
{swap(tmp);return *this;
}

  
注：类里面可以用类名替代类型，类外面不行

  比如这样：用 类名vector 替代 类型vector<int>

void swap(vector& v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);
}
vector<T>& operator=(vector tmp)
{swap(tmp);return *this;
}

  不过并不推荐这种写法，因为对新手来说不友好。
  
  

13 源码

//vector.h#pragma once
#include<iostream>
#include<assert.h>
#include<vector>namespace my_vector
{template<class T>class vector{public:// Vector的迭代器是一个原生指针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;}size_t size() const{return _finish - _start;}size_t capacity() const{return _end_of_storage - _start;}bool empty(){return _start == _finish;}void clear(){_finish = _start;}vector():_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){}// C++11 前置生成默认构造vector() = default;vector(size_t n, const T& value = T()){reserve(n);while (n--){push_back(value);}}vector(int n, const T& value = T()){reserve(n);while (n--){push_back(value);}}vector(long long n, const T& value = T()){reserve(n);while (n--){push_back(value);}}vector(const vector<T>& v){reserve(v.capacity());const_iterator it = v.begin();while (it != v.end()){              push_back(*it);it++;}}template<class InputIterator>vector(InputIterator first, InputIterator last){InputIterator tmp = first;//不能是< , list那些就不行while (tmp != last){push_back(*tmp);tmp++;}}void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}vector<T>& operator=(vector<T> tmp){swap(tmp);return *this;}~vector(){if(_start){delete[] _start;_start = _finish = _end_of_storage;}}T& operator[](size_t n){assert(n < size());return *(_start + n);}const T& operator[](size_t n) const{assert(n < size());return *(_start + n);}void reserve(size_t n);void push_back(const T& x);void resize(size_t n, const T& value = T());void pop_back();iterator insert(iterator pos, const T& x);        iterator erase(iterator pos);private:iterator _start = nullptr; // 指向数据块的开始iterator _finish = nullptr; // 指向有效数据的尾iterator _end_of_storage = nullptr; // 指向存储容量的尾};template<class T>void vector<T>::push_back(const T& x){if (size() == capacity()){size_t new_capacity = capacity() ? 2 * capacity() : 4;reserve(new_capacity);}*_finish = x;_finish++;}template<class T>void vector<T>::reserve(size_t n){if (n > capacity()){   iterator tmp = new T[n];size_t preserve_size = size();int m = 0;iterator it = begin();while (it != end()){            *(tmp + m) = *it;++m;++it;}//memcpy(tmp, _start, sizeof(T) * size());delete[] _start;_start = tmp;_finish = _start + preserve_size;_end_of_storage = _start + n;}}template<class T>void vector<T>::resize(size_t n, const T& value){if (n <= size()){_finish = _start + n;}else{reserve(n);int m = n - size();while (m--){*_finish = value;++_finish;}}}template<class T>void vector<T>::pop_back(){assert(!empty());_finish;}/template<class T>typename vector<T>::iterator vector<T>::insert(typename vector<T>::iterator pos, const T& x){assert(pos <= _finish && pos >= _start);/*if (size() == capacity()){size_t new_capacity = capacity() ? 2 * capacity() : 4;reserve(new_capacity);}*///相对位置if (size() == capacity()){size_t len = pos - _start;reserve(capacity() ? 2 * capacity() : 4);pos = _start + len;}iterator it = end();while (it > pos){*it = *(it - 1);it--;}*pos = x;++_finish;return pos;}template<class T>typename vector<T>::iterator vector<T>::erase(typename vector<T>::iterator pos){assert(pos < end() && pos >= begin());iterator it = pos + 1;while (it != end()){*(it - 1) = *it;++it;}--_finish;return pos;}template<class T>void print_vector(const vector<T>& v){typename vector<T>::const_iterator it = v.begin();while (it != v.end()){std::cout << *it << " ";++it;}std::cout << std::endl;}template<class Container>void print_container(const Container& v){auto it = v.begin();while (it != v.end()){std::cout << *it << " ";++it;}std::cout << std::endl;}
}