ios网站开发视频教程,商城类网站备案,苏州网站建设找思创,wordpress游客怎么发表文章【C】—— vector 的模拟实现 0 前言1 vector 的成员变量1.1 stl 库中的 vector 成员变量1.2 模拟实现 vector 成员变量 2 迭代器3 size、capacity、empty4 opreator[ ]5 reserve5.1 初版 reserve5.2 _finish 的处理5.3 深拷贝5.4 终版 6 push_back 与 pop_back7 打印函数7.1 初… 【C】—— vector 的模拟实现 0 前言1 vector 的成员变量1.1 stl 库中的 vector 成员变量1.2 模拟实现 vector 成员变量 2 迭代器3 size、capacity、empty4 opreator[ ]5 reserve5.1 初版 reserve5.2 _finish 的处理5.3 深拷贝5.4 终版 6 push_back 与 pop_back7 打印函数7.1 初写打印7.2 typename 关键字7.3 打印函数进阶 8 insert8.1 insert 初版8.2 迭代器失效8.2.1 情况一类似野指针8.2.2 algorithm 库中的查找函数8.2.3 情况二insert 后再对 pos 进行访问8.2.3.1 不扩容的情况8.2.3.1 扩容的情况 8.2.4、解决方法8.2.4.1、想法一8.2.4.2、想法二 8.3 总结 9 erase10 resize11 构造函数系列11.1 默认构造11.2 拷贝构造11.3 迭代器区间构造 与 n 个 value 构造11.3.1 迭代器区间构造11.3.2 n 个value构造11.3.3 注意事项 12 赋值运算符重载12.1 传统写法12.2 现代写法 13 源码 0 前言 前面我们学习了 s t r i n g string string并模拟实现了它下面我们来学习 v e c t o r vector vector v e c t o r vector vector 的底层即我们前面曾经学过的顺序表它属于 STL库为了让我们更加深入理解 v e c t o r vector vector接下来我们将模拟实现 v e c t o r vector vector
1 vector 的成员变量
1.1 stl 库中的 vector 成员变量 我们学习数据结构时曾经模拟实现过顺序表。当时我们用一个指针 a a a 管理从堆开辟的空间 s i z e size size 表示当前有效数据的个数 c a p a c i t y capacity capacity 表示当前空间的大小。 但是 s t l stl stl库 中的 v e c t o r vector vector 的成员变量有所差别它的成员变量是三个迭代器 我们知道迭代器全部都是 t y p e d e f typedef typedef 出来的那 v e c t o r vector vector 的迭代器是什么呢 可以看到其迭代器就是 原生指针 那start、finish、end_of_storage 变量又是什么意思呢面对未知的东西我们应大胆假设小心求证。 不管他底层如何 v e c t o r vector vector 终究逃不过扩容那我们不难猜想start 肯定是一个指针指向一个开始finish指向某个结束至于end_of_storage s t o r a g e storage storage 是存储的意思所以我们大胆猜测end_of_storage与空间相关可能就是空间结束位置那这样的话finish 可能表示数据的结束 那我们怎么取求证呢我们可以通过一些我们熟悉功能的函数来确认 可以看到 b e g i n begin begin 返回的是第一个有效数据位置这里是start而 e n d end end 返回的是最后一个有效数据的下一个位置这里返回的是finish c a p a c i t y capacity capacity 表示空间的大小这里返回的是end_of_storage - begin()。 因此我们的猜测是正确的那么 v e c t o r vector vector 的底层结构如下 注finish 指向的是有效空间的下一个位置
1.2 模拟实现 vector 成员变量 我们模拟实现的 v e c t o r vector vector 的成员变量也学习库中的形式
namespace my_vector
{templateclass Tclass vector{public://···private:iterator _start nullptr;iterator _finish nullptr;iterator _end_of_storage nullptr;};
}这里为了与库中的 v e c t o r vector vector 区别开我们使用命名空间 同时因为顺序表应满足不同数据类型的存储我们实现的不是某个具体类型的类而是类模板。既然是模板那么函数的声明与定义就不能放在不同的文件中因此声明和定义全在vector.h文件中不再需要vector.cpp文件。 2 迭代器 因为 v e c t o r vector vector 的迭代器是一个原生指针与 s t r i n g string 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;
}因为 _ f i n i s h 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[ ] v e c t o r vector vector 中的 o p r e a t o r opreator opreator[] 与 s t r i n g string string 中的 o p e r a t o r operator operator[] 类似都是访问第 i i i 个数据的元素。同样 v e c t o r vector vector 的 o p e r a t o r operator operator[] 也要用 a s s e r t assert 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];
}这里顺便提一下 v e c t o r vector vector 还提供了 at 函数 接口。 a t at at 函数与 o p e r a t o operato operato[] 功能相同但他们检查越界的方式不同 a t at at 函数是抛异常而 o p e r a t o r operator 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;}
}在 s t r i n g string string 中我们已经模拟实现 r e s e r v e reserve reserve 了 v e c t o r vector vector 中也是需要我们手动释放和拷贝的数据的代码细节就不再细讲了。 那上面代码有问题吗 有的
5.2 _finish 的处理 首先是对 _ f i n i s h finish finish 的处理上 这里我们更新_finish的方式是_start size()可是 size() 是怎么计算出来的是通过_finish - _start计算出的可是此时 _ s t a r t start start已经更新了而_ f i n i s h finish finish还未更新 此时他们相减会出大问题。 怎么解决呢也很好办那就是提前记录 s i z e size 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 深拷贝 还有一点上述代码用 m e m c p y memcpy memcpy 拷贝是浅拷贝而我们需要的是深拷贝 用 m e m c p y memcpy memcpy 拷贝有什么问题呢
void test7()
{vectorstring 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);
}运行结果 程序崩溃了 为什么呢问题出现在了扩容 我们知道 v e c t o r vector vector s t r i n g string string 中每个 s t r i n g string string 都指向一块堆空间。 虽然 v e c t o r vector vector 是深拷贝但是 v e c t o r vector vector 中的每个 s t r i n g string string 都是浅拷贝而每个string都指向一块资源。这意味着新开辟的 t m p tmp tmp 中每个 string 都是与对应旧空间的 string 指向同一块空间 d e l e t e delete delete 后会调用析构函数将旧空间指向的资源全部释放掉此时新空间的每个 s t r i n g string string 都是指向一块已经被释放的空间自然会出现问题。 那如何解决呢那就是对vector中的每个成员都进行深拷贝。我们不能再使用 m e m c p y memcpy 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 p u s h push push_ b a c k back 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;
}p o p pop pop_ b a c k back back 也很简单但要注意判断是否为空。
void pop_back()
{assert(!empty());--_finish;
}7 打印函数 STL库 中 v e c t o r vector vector 是没有重载 o p e r a t o r operator operator 的。 为什么呢因为库事先并不知道你要以什么形式打印是连续打印还是每打印一个数据就空格还是每打印一个就换行而且自己实现一个打印函数并不困难。因此库就交给程序员自己实现。
7.1 初写打印 那么我们就自己实现一个打印函数吧。 打印函数是一个全局函数
templateclass T
void print_vector(const vectorT v)
{vectorT::const_iterator it v.begin();while (it ! v.end()){cout *it ;it;}cout endl;
}但上述函数写的是有问题的 7.2 typename 关键字 为什么呢 问题出现在vectorT::const_iterator it;中 可以直接突破类域用类名::方式去类中取东西能取到两种一种是 静态成员变量另一种是在 类中 t y p e d e f typedef typedef 的类型。 C规定类模板没有被实例化之前编译器是不会往里面去取东西的。 编译器走到 p r i n t print print_ v e c t o r vector vector 时 v e c t o r vector vector 模板还没被实例化出来。而因为不敢去模板中取编译器不知道 c o n s t const const_ i t e r a t o r iterator iterator 是 类型 还是 静态成员变量如果取到静态成员变量后面还跟着变量 it 就会出大问题。因此编译器报错。 要解决上述问题需在前面加上 t y p e n a m e typename typename 关键字。加上 t y p e n a m e typename typename即明确告诉编译器 c o n s t const const_ i t e r a t o r iterator iterator 是类型。可以看做编译器的甩锅。编译器你说了是类型的啦我给你过了如果他是成员变量的话那也是你的问题不怪我 但如果是取静态成员变量前面什么都不用加因为如果真是静态成员变量你不会像vectorT::const_iterator it这样用的直接就vectorT::const_iterator;这样
templateclass T
void print_vector(const vectorT v)
{//没有实例化的类模板里面取东西编译器不能区分const_iterator是类型还是静态成员变量typename vectorT::const_iterator it v.begin();while (it ! v.end()){cout *it ;it;}cout endl;
}这样就可以啦 当然这还有一种更简单的方式用 a u t o auto auto 就没有那么麻烦因为 a u t o auto auto 直接是由v.begin()推导而来
templateclass T
void print_vector(const vectorT v)
{ auto it v.begin();while (it ! v.end()){cout *it ;it;}cout endl;
}7.3 打印函数进阶 但上述打印函数稍稍改进一下就可以变成所有类型容器的打印函数而不仅仅是 v e c t o r vector vector 类型的
templateclass 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())。对于 s t r i n g string string 与 v e c t o vecto vector 来说是没问题因为他们本来就是原生指针但对其他容器就不行了比例 l i s t list list 链表它的 i t e r a t o r iterator 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()
{vectorint 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()
{vectorint 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);
}运行结果 可以看到报错了 为什么呢这是因为 p o s pos pos 迭代器失效了 我们结合图来看就很容易看懂了。扩容后pos 依然指向旧空间此时旧空间已经被释放了 p o s 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 库中的查找函数 这里介绍 a l g o r i t h m algorithm algorithm 库中的查找函数 f i n d find find 函数模板适用于所有的容器只需要传一个迭代器区间给它就能帮你查找 库中的 f i n d find find函数 是一个模板 需要注意的是传值要传左闭右开区间 8.2.3 情况二insert 后再对 pos 进行访问
8.2.3.1 不扩容的情况 我们知道 i n s e r t insert insert 函数的 p o s pos pos 形参是一个迭代器如果我们想在指定数据之前插入数据就可以用 find 模板找到相应数据的迭代器 现在我用 f i n d find find函数 找到 p p p 为 5 的位置在之前插入数据 100并将 5 ∗ * ∗ 10
void test2()
{vectorint 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 呢 这是因为迭代器失效了在 i n s e r t insert insert 以后我们可以认为迭代器 p 就已经失效了。我们结合图来理解 用 i n s e r t insert insert 插入数据后 p p p 指向的位置已经变了。你以为它指向的还是 5但实际上他已经变了
8.2.3.1 扩容的情况 上述情况还不是最恐怖的最恐怖的是扩容的情况
void test3()
{vectorint 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了为什么呢还是迭代器失效的问题我们来看图 p o s pos pos 的位置还是指向旧空间这时再对 p o s pos pos 访问就是类似于野指针的访问。
8.2.4、解决方法
8.2.4.1、想法一 那应该怎么解决上述问题呢 在解决完第一种情况的代码中我们在函数内是对 p o s pos pos 进行了更新的 但是形参的改变并不影响实参那我们可不可以用引用呢
void insert(iterator pos, const T x)这样 p o s pos pos 是引用就能改变函数外的 p p p 了。 但这样是不行的因为会影响传参
vectorint v;
v1.insert(v1.begin(), 10);像这样我们传递第一个迭代器但这样传参v1.begin()的返回值中间会产生一个临时变量实际传递的就是这个临时变量。临时变量是常性必须用 c o n s t const const 引用普通的引用是传不进去的。 那如果我加 c o n s t const const 呢
void insert(const iterator pos, const T x)加了 c o n s t const const里面的 p o s pos pos 就无法改变了所以还是不行
8.2.4.2、想法二 我们来看一下库中的 i n s e r t insert insert 是怎么处理的 库中给了一个返回值返回的是更新之后的 p o s pos 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;
}所以如果真要 i n s e r t insert insert 后继续访问 p p p一定要更新 p p p 再访问
void test4()
{vectorint 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 总结 用 i n s e r t insert insert 后迭代器 p 就失效了最好的办法就是不再用 p p p 去访问。如果非要访问一定要更新一下迭代器 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;
}同样 e r a s e erase erase 也存在迭代器失效的问题。我们使用的时候一定要注意 e r a s e 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;}}
}r e s i z e resize resize 的功能与实现这里就不再过多解释这里大家直接看代码即可。 这里我们重点讲一下 const T val T()的写法 这是自定义类型给缺省值的方法。因为 v e c t o r vector vector 是模板给缺省值时不能再像 const T val 0 这样给因为是模板你不知道 T 是什么类型像前面给 0 就表示 T 一定是 0 了肯定是不合适的。T 可能是 i n t int int可能是 d o u b l e double double、也可能是自定义类型。 如果是自定义类型的对象我们就调用它的默认构造。上述给缺省值的方法就是给 T 的一个匿名对象并调用它的默认构造。 那如果 T 是内置类型 i n t int int、 d o u b l e double 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() {}学习类与对象时我们知道所有成员都会走初始化列表。如果我们没有显式写在初始化列表对于内置类型没有缺省值不做任何处理但现在我们在成员变量声明时结了缺省值则用缺省值初始化。 在C11中给了一个方式可以 强制生成默认构造
vector() default;因为编译器只有在程序员没有自己实现任何构造函数拷贝构造也是构造时才会生成默认构造如果我们自己实现了带参的构造又想编译器生成默认构造就可以用上述语法
11.2 拷贝构造
vector(const vectorT v)
{reserve(v.capacity());for (auto e : v){push_back(e);}
}拷贝构造就是遍历 对象 v v v将 v v v 的值全部 p u s h push push_ b a c k back back 进 t h i s this this 中。这里范围for用了引用是为了减少拷贝而为了避免频繁的扩容使用 r e s e r v e reserve reserve 提前开辟空间。 11.3 迭代器区间构造 与 n 个 value 构造
11.3.1 迭代器区间构造 在stl库中还提供了一个构造方法迭代器区间构造 这里讲一个新的知识点类模板里面的成员函数可以是函数模板
为什么要用模板呢这样不行吗
vector(iterator first, iterator last)如果是这样的话那么迭代器构造只能用 v e c t o r vector vector 迭代器构造如果是函数模板的话可以用任意的迭代器进行构造 代码如下
templateclass InputIterator
vector(InputIterator first, InputIterator last)
{while (first ! last){push_back(*first);first;}
}测试
void test6()
{listint 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);vectorint v1(l1.begin(), --l1.end());print_vector(v1);
}运行结果 可见迭代器区间可以用任意容器迭代器进行初始化但它要求类型是匹配的
11.3.2 n 个value构造 n n n 个 v a l u e value value 的构造很简单不断 p u s h push push_ b a c k back back 就行
vector(size_t n, const T val T())
{reserve(n);while (n--){push_back(val);}
}11.3.3 注意事项 调用 n n n 个 v a l u e value value 的构造函数时会出现一个很奇怪的报错
void test7()
{vectorint v(10, 1);print_vector(v);
}为什么我调用的时 n n n 个 v a l u e value value 的构造结果报错报到迭代器区间的构造了呢 这是因为编译器把vectorint v(10, 1);中的 10 和 1 识别成两个迭代器了。 为什么会这样呢编译器有一个原则那就是匹配最匹配的 我们先来看 n n n 个 v a l u e value value 的构造 vector(size_t n, const T val T())对 10 和 1 来说T 是 i n t int int 是确定的 但是 n n n 是 s i z e size size_ t t t i n t int int 要进行类型转换 再看迭代器区间构造 vector(InputIterator first, InputIterator last)它实例化出来是两个 i n t int int不用类型转换所以编译器选择迭代器区间构造 那怎么解决呢 stl库中选择重载多个 n n n 个 v a l u e value 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 赋值运算符重载 赋值运算符重载分为现代写法与传统写法这在 s t r i n g string string 的模拟实现中讲过类似的这里就不再细讲了我们直接看代码
12.1 传统写法
void clear()
{_finish _start;
}vectorT operator(const vectorT 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(vectorT v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);
}
vectorT operator(vectorT tmp)
{swap(tmp);return *this;
}注类里面可以用类名替代类型类外面不行 比如这样用 类名vector 替代 类型vectorint
void swap(vector v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);
}
vectorT operator(vector tmp)
{swap(tmp);return *this;
}不过并不推荐这种写法因为对新手来说不友好。
13 源码
//vector.h#pragma once
#includeiostream
#includeassert.h
#includevectornamespace my_vector
{templateclass Tclass 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){}// C11 前置生成默认构造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 vectorT v){reserve(v.capacity());const_iterator it v.begin();while (it ! v.end()){ push_back(*it);it;}}templateclass InputIteratorvector(InputIterator first, InputIterator last){InputIterator tmp first;//不能是 , list那些就不行while (tmp ! last){push_back(*tmp);tmp;}}void swap(vectorT v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}vectorT operator(vectorT 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; // 指向存储容量的尾};templateclass Tvoid vectorT::push_back(const T x){if (size() capacity()){size_t new_capacity capacity() ? 2 * capacity() : 4;reserve(new_capacity);}*_finish x;_finish;}templateclass Tvoid vectorT::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;}}templateclass Tvoid vectorT::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;}}}templateclass Tvoid vectorT::pop_back(){assert(!empty());_finish;}/templateclass Ttypename vectorT::iterator vectorT::insert(typename vectorT::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;}templateclass Ttypename vectorT::iterator vectorT::erase(typename vectorT::iterator pos){assert(pos end() pos begin());iterator it pos 1;while (it ! end()){*(it - 1) *it;it;}--_finish;return pos;}templateclass Tvoid print_vector(const vectorT v){typename vectorT::const_iterator it v.begin();while (it ! v.end()){std::cout *it ;it;}std::cout std::endl;}templateclass Containervoid print_container(const Container v){auto it v.begin();while (it ! v.end()){std::cout *it ;it;}std::cout std::endl;}
}
