C++中vector的简单实现

一、主要任务

1. 查看文档的网站的链接

cplusplus网站
cppreference网站

2.内部模拟的函数

namespace myvector
{
  template<class T>
  class vector
  {
  public:
    // Vector的迭代器是一个原生指针
    typedef T* iterator；
    typedef const T* const_iterator；

    iterator begin()；
    iterator end()；
    const_iterator cbegin()；
    const_iterator cend() const；

    // construct and destroy
    vector()；
    vector(int n, const T& value = T())；
    template<class InputIterator>
    vector(InputIterator first, InputIterator last)；
    vector(const vector<T>& v)；
    vector<T>& operator= (vector<T> v)；
    ~vector()；

    // capacity
    size_t size() const ；
    size_t capacity() const；
    void reserve(size_t n)；
    void resize(size_t n, const T& value = T())；

    ///access///
    T& operator[](size_t pos)；
    const T& operator[](size_t pos)const；

    ///modify/
    void push_back(const T& x)；
    void pop_back()；
    void swap(vector<T>& v)；
    iterator insert(iterator pos, const T& x)；
    iterator erase(Iterator pos)；
    
  private:
    iterator _start; // 指向数据块的开始
    iterator _finish; // 指向有效数据的尾
    iterator _endOfStorage; // 指向存储容量的尾
  };

}

主要实现的函数有几个模块，分别为：
1、构造析构
2、容量大小与扩容
3、运算符重载
4、插入删除
5、迭代器
（这里直接使用迭代器来访问了，这里简单实现的迭代器就是原生指针）

二、本人的模拟实现过程

这里可以去看文档使用与模拟实现，有些缺省参数啥的我这就不实现了
有些缺省参数没学之前可以直接不用

1. 所需模拟实现的函数

用红色框框起来

a.构造、拷贝构造

b. reverse()扩容

reverse()扩容只需要传一个参数，，这个参数可能是最后的容量
在这里，扩容会有两种情况：
1、n > _endOfStorage就需要扩容（_endOfStorage是指向所开辟的总空间的最后一个的下一个位置）
（这里是指针，指向的确实是最后的下一个位置的空间如同capacity）
2、 n <= _endOfStorage就什么都不做，总容量不变，该函数不缩容

c.insert()、push_back()插入数据

（1）在position位置插入一个数据
（2）在position位置插入n个数据
（3）在position位置向后插入一段迭代区间
（4）不会玩
（5）插入一个initializer_list对象（常见的是这种：{value1, value2, ....}）

这里push_back()重载成两个，我这只实现第一个
第一个和第二个的区别是后面的形参中是否带了const
但以我们习惯，插入的时候是不需要修改要插入的数据的
并且以外层来看，const对象也无法插入数据

d. erase()、pop_back()删除数据

erase()是用来删除数据的
第一个是删除position位置的数据
第二个是删除first到last的一段空间，删除范围为：[first, last)
我这简单实现第一个方法吧，主要都是挪动数据，第二个方法只要计算好从哪个挪动到哪个就好了

pop_back()删除最后一个数据
最后一个数据的位置就是类内置属性_finish的前一个位置

e. swap()交换

swap交换两个对象的内容
我们这里是以迭代器实现指向（本质也是指针）
这里的交换可以直接交换两个对象里面的属性的指向就好了
（如这里_start, _finish, _endOfStorage就是属性）

f. begin()、end()非const与const迭代器

begin()与end()是用来初始化迭代器或者给迭代器赋值的
有了begin()与end()方法，这里就可以使用迭代器变量了
另外，有了begin与end就可以使用范围for了，范围for底层是迭代器，不需要自己实现，编译器会自动转换
const与非const的区别就是无法修改内容而已，代码实现相似

g. 完善构造函数之一：多个同数值参数构造

这里是n个value构造一个对象

h. 完善构造函数之二：拷贝构造

拷贝构造是：使用已经存在的对象初始化另一个对象

i. 完善构造函数之三：迭代区间构造

迭代区间构造：使用其他对象的迭代区间来构造该对象
（这里挺有意思的，可以使用其他类对象的迭代区间构造）

j. 完善构造函数之四：初始化列表构造

初始化列表构造，初始化列表例如：{ 1,2,3,4 }这种的
使用也有两种方式：
1、vector<int> v1 = { 1,2,3,4 };
2、vector<int> v2({ 1,2,3,4 });
这样子也挺方便使用的

k. 赋值重载

赋值重载函数，上面图片的这里不重载，这里玩个新的
赋值重载如果使用const&则需要做扩容什么的，这里让编译器做

l. size()数据有效个数

很简单的函数，返回有效数据个数

m. resize()调整数据有效个数

实现第二个，能把空间初始化，第一个只是能扩大有效数据个数，但是里面的值可能是随机值
这里的n和string里的n是一样的功能：
（这里我把_finish - _start说成size吧，这也是有效数据个数）
（并且把_endOfStorage - _start 说成容量capacity）
1、如果n == size，则什么都不做
2、如果n < size，则把_finish调整到n位置（有效数据个数减小）
3、如果n > size && n <= capacity ,则把_finish调整到n位置，并且把旧_finish到新_finish的空间用value填充
4、如果n > capacity ,则扩容，并且把_finish调整到n位置，调整过来的空间也用value填充
（理论成立，实践开始）

n. operator运算符重载

重载[]是因为要下标访问，本来就是连续空间，还不能下标访问就扯蛋了
const对应const对象，非const对应普通对象，重载成两份

o. 析构函数

析构函数，对象生命周期结束自动调用
这里主要是释放空间，把申请的空间delete了

2.内置类型声明

这里的内置类型的typedef出来的指针
主要是：
1、类模版
2、模版类型指针typedef重命名为迭代器
3、迭代器管理数据的开始、结束和容量的末尾（本质也是管理指针）
（这里使用类模版主要是兼容各内置类型与自定义类型，编译器自动判别类型）

3. 基础无参构造函数实现

无参构造函数可以不实现，编译器会自动生成，但不同编译器可能不会初始化
这里使用了初始化列表，也可以在构造函数内赋值

4. insert()插入

这里我假设有revers()扩容函数和capacity()计算总容量的函数
这里主要流程思路是：
1、断言pos，不让pos是一个越界指针
2、判断_finish是否到尾了，容量是否不够了
	a. 不够容量，扩容，扩容机制是两倍，如果本来就为空就开始4个空间
		扩容之前得计算pos到_start的距离，以便扩容之后更新pos
	b. 容量足够，继续下一步
3、定义一个指针来遍历移动数据，我这里是前一个数据移到当前位置，有兴趣可以做当前位置数据移到下一个位置
4、pos位置直接插入需要插入的数据
5、插入了数据_finish向后走一步
6、返回插入数据的位置的迭代器，主要是外面使用时需要更新迭代器

5. capacity()计算容量

这里capacity()就是为了计算总容量的，返回的是非负数（无符号整型）
咋计算剩余容量？在外部就是调用capacity() - size()不就可以了嘛
在内部就_endOfStorage - _finish，但通常是判断_endOfStorage == _finish
（这里使用const修饰是因为能方便const与非const对象使用）

6. reverse()扩容

reserve()主要做扩容，判断传参的n与总容量对比，n > capacity()就扩容
主要流程思维：
1、判断是否扩容（可以复用capacity()函数来判断）
	a. 不需要扩容，直接不运行if里面了
	b. 需要扩容，进入if执行语句
2、扩容前计算之前的有效数据个数（后面需要更新指针）
3、定义新变量接收申请空间
4、旧空间的数据循环赋值给新的空间
5、释放旧空间（内存泄漏问题很严重的啊）
6、_start指向新空间，_finish根据之前旧的数据个数指向新空间的有效数据个数末尾，_endOfStorage根据开的空间指向新空间
（这里如果不记录旧的空间有效数据个数，那么后面跟新_finish就会出问题，如果不更新，后面访问就找不到_finish）

我们这里清晰的看到注释了memcpy的内存字节拷贝函数，为啥呢？
因为内置类型可以，但vector也支持内置类型

例如：
vector<string> v; 这种样子的

memcpy()的拷贝就是让里面的指针指向了string那片空间
接下来的delete[]，string对象会调用自己的析构，但tmp还指向那片string对象空间
等到最后vector对象也析构的时候对已经释放的空间进行第二次析构释放就会出问题

所以，以上代码中是使用赋值，赋值是最简单的方法了
为啥赋值能过？
因为string类里有自己的赋值重载，一个存在的对象对另一个对象进行赋值不影响该对象的结构

7. push_back()尾插

push_back()可以直接复用insert()方法
insert()是在迭代器位置插入数据，而最后一个位置是_finish管理的
（也是指针，_finish指向最后一个数据的下一个位置）

※简单1-7 test()测试

因为insert()还没有迭代器的的遍历就没有测试
insert()可以简单的用push_back()简单测试
reverse()是扩容，在插入的时候自动扩容，搭配类构造函数看能不能正常扩容

以上运行可以看出，从开始3个容量，插入的时候扩两倍
4个数据输入，3+4已经超过6个了，再次两倍扩容
根据这些可以看出扩容时正常的，数据最后位置插入正常

8. erase()删除

erase()删除pos位置数据，这里使用覆盖的方式
主要思想流程：
1、断言判断pos是否合法
2、定义另外一个迭代器，用于遍历覆盖
3、循环判断，这里使用后一个覆盖前一个
4、_finish减1，最后返回pos的位置以便于更新迭代器

9. pop_back()尾删

直接复用erase()方法
假设有一个方法end()是返回最后一个数据的下一个位置的迭代器
让这位置减1并让erase()执行删除
（当然也可以直接传_finish - 1，也可以直接 --_finish）

10. swap()交换

这里swap()交换主要是对象里属性的内容交换
一个指针的内容交换了，逻辑上指向也交换了
这里调用的是库中的swap()方法，简单交换可以这样子用挺好的

11. begin()、end()非const与const迭代器

主要思维不难
因为底层的属性也是迭代器iterator定义的，而iterator是用T*定义的，一层套一层
所以我知道，只需要返回指向数据的开始和指向数据的结束的迭代器就好了
这里哪怕没有实现什么++/--啥的也能用，底层不过是指针++/--而已
（注意，这里是使用原生指针实现，但stl库不是）

※测试iterator迭代器const与非const

这里范围for可以直接使用，因为类内部存在begin与end方法
（使用范围for类里面必须是begin与end名字，编译器只认这两个方法）
上面是两种迭代器的用法
（个人使用迭代器简单测试了，insert与erase方法是没问题的）

12.多个同数值构造

使用n个value构造对象
这里可以看到两个参数，一个是n，一个是const T& value
第一个容易理解，第二个不是那么容易理解
这里的T()是类型的默认构造形成的匿名对象，会有不理解内置类型（如整型）的怎么会有默认构造
这是C++为了方便通用，类是一个类型，类定义是一个对象，内置类型是类型，内置类型定义也成为了一个对象
如果是一个自定义类型，如vector<Date>，传进来前面的const T&就是类型（这里对象实例化的时候T已经出来了）
后面的T()调用了默认构造，也就是一个空对象，这时下面的赋值也不会出问题

假如是vector<int>这种内置类型，是n个value构造对象并且不传第二个参数
如果没有自适应T()无法生成int对象（变量），那么value的值就不匹配，后面就没办法执行
所以这里的T()是能完成自定义类型与内置类型的默认构造的，内置类型也有默认构造了

主要思维流程：
1、复用reserve()方法，使用n给正在初始化的对象扩容
2、使用循环，复用push_back()方法直接尾插（因为不会改变value的值）
（因为在扩容的时候_endOfStorage已经指向后面，并且在push_back()的时候_finish已经走了，所以这都不用改变了）

13. 拷贝构造

主要思维流程：
1、使用人家的capacit()容量方法扩容
2、使用范围for遍历传进来的对象，并让每个内容push_back()在要实例化的对象
（因为push_bakc()不会改变传进来的实参）

14. 迭代区间构造

迭代区间如果不是定义赋值出问题，迭代区间不会出什么大问题
那里的函数模版，是因为不能确定是哪个类的迭代器，可以根据不同的类的迭代器生成不会的构造函数
这迭代区间初始化可以使用其他类对象的迭代区间，如这里是vector<int>的，可以给list<int>的迭代区间赋值

15. 初始化列表构造

初始列表这里比较特殊，可以查看手册
假设是vector<int> v1 = { 1,2,3,4,5 };
这里的括号就会经过隐式类型转换变成initializer_list
到里面的构造函数，因为initializer_list是一个类，形参是类对象
它也有它的迭代器，这个类挺方便的

16. operator=()赋值重载

看形参列表，因为是传值传参，编译器自动调用拷贝构造生成v
因为是走了拷贝构造，形参变化不改变实参，这里让形参和对象交换内容
那么，这里属性指向内容就发生了改变
返回的也是等号的右参数
出了作用域，v生命周期结束，自动调用它的析构

17.size()有效数据个数

有效个数就是_start到_finish之间的空间个数
因为在迭代器不飘的情况下_finish永远要大于等于_start
使用const修饰也是为了const对象与非const对象都能使用
（因为如果没有const，则const对象无法使用该方法，多写一个又没什么大作用，也没有修改）

18. resize()调整数据有效个数

我这里手搓的思维分为n == size、n > size、n < szie
1、n == size我什么都不做，直接返回
2、n > size
	a. 我不知道会不会超出我的容量，但我reverse方法里面有判断，所以我直接交给reverse扩容
	b. 扩不扩容我都在_start到n位置做个标记位，以便我插入数据能走到那停
	（因为push_back()方法里面会自动走_finish，所以我不用自己手动走）
3、n < szie，直接把_finish调整到n的位置，也不用覆盖，_finish就是有效个数的限制
（这里以及上面说跳到n位置，连续的空间的指针可以当成数组来使用）

19.operator[]运算符重载

这里[]运算符重载，是为了下标访问
const修饰是为了对应const对象，另外一个就是普通对象的重载
这里思路很简单：
1、断言限制下标合法性
2、_start可以当成数组首元素地址，可以直接当数组使用，也可以*(_start + pos);

20. 析构函数

这里主要是释放申请的空间
因为_start指向申请的空间的第一个位置，所以直接delete[] _start就好了
最后让三个迭代器指向空，虽然对象不存在也无法再使用到他们了，但为了规范性

※[]与resize简单测试

可以看到[]运算符重载是能正常运行的，并且resize也能正常的扩容与缩小
默认值value填充也正常

总结

多用就会了，手搓理解就更深，因为这是一边写代码一边写博客的，可能展示上不是很好
但这里是我一边理解一边描述的
加油吧，少年