C++ VECTOR容器

SLT中的VECTOR

vector与string一样是STL标准库中的容器，可以将其理解为C语言中的数组，不过数组里面存放的是内置类型，而为了让其能支持更多的数据类型(自定义类型)，C++在STL中规定了vector模板标准，使得我们的自定义类型数据也能存放在数组当中。

template < class T, class Alloc = allocator<T> > class vector;

与string不同string只需要管理字符类型的数据，vector则是大部分类型(主要是自定义类型)数据的管理，所以vector在库中是一个模板类，在创建实例化对象时需要传递数据类型

这里就是定义三个int类型的数组的实例化v,v1,v2。

vector类模板

在vector类里面也是有很多的功能包括基本的增删查改，与数组一样的随机访问，与string一样扩容机制，迭代器等。

vector模拟实现

为了更好了解vector我们模拟实现一个vector模板。里面包含vector的常用功能，使其能代替vector在简单的环境下正常使用。

因为数组管理的数据类型多种多样，我们不能直接将其参数定位int或是char，所以定义一个模板类型T占参数类型的位置在实例化时编译器从实例化中推到其类型并将T替换掉。

这里我们就不同于string使用char*来管理数据，因为这不是一个固定的类型，所以我们直接使用迭代器即实例化指针来管理，三个指针，一个指向有效数据的起始位置start，一个指向有效数据的末尾位置finish，一个指向当前数组的最后一个位置作为数组的结束标志，这里finish就如同string里面的’\0‘一样，当遇到endOFstorage就等于到了当前数组的最大存储极限了。

构造函数

第一个的无参构造什么都不需要因为我们在定义成员变量的时候给了缺省参数的。无参代表数组啥也没有，也就不需要存放数据，后续需要添加数据的时候在扩容就好了。

vector(int n, const T& val = T())这个函数类型可能有些奇怪，这是为了照顾自定义数据的缺省参数，若是没有传具体数据则会调用自定义数据类型的无参构造函数，若是内置类型，那么在C++11中也定义了如int，double，float这类的都有无参构造函数，值为0，但是char类型是没有无参构造的，因为若是需要存放char类型直接使用string就可以了，这里其实还有一个右值引用的概念就是简单说就是C++11中能引用常量所以前面还添加了const这再写代码的时候会方便一些。第二个是拷贝构造函数，因为存在自定义类型这个一定得自己实现不能使用自动生成得拷贝构造函数。

这是一个迭代器构造函数，因为库得vector也是支持了使用迭代器来构造一个vector所以这里也实现了，这个类型因为并不是数据类型而是数据类型得迭代器，如string里面就是char*跟数据本身得数据类型是不同得所以需要另外定义一个模板，在调用迭代器构造函数的时候记得传入类型。

析构函数

将new出来得空间释放掉，将三个指针重置。只要当心new[]对应delete[]析构函数一般没什么大问题。

迭代器

因为这里得vector就是用得迭代器来访问管理数据，所以先实现迭代器得功能

vector里面得迭代器也是一个指针，所以对其管理要严格一些，容易出现越界非法访问等情况，我是直接断言，其实也可以做一个判断。C++中是不能进行权限扩大得，所以需要有const迭代器来支持如vector<const  int>这类得数组。

赋值运算符重载

我这里用了一个比较省力得写法，假如我们现在有两个vector  v1和v2 然后有以下语句v1=v2，就是v2赋值给v1调用这个函数，那么这个参数就是v2，这里我没有使用引用所以这是个传值传参，传自定义类型编译器会调用它得拷贝构造函数，所以进入这个函数就已经有一份v2得拷贝了，然后我只需要交换三个指针，让v1得成员变量指针指向拷贝构造出来的数据就可以完成赋值，然后出了函数，v2的指针是指向v1的旧数据的，过了生命周期v2调用它的析构函数就会将其释放。所以全部工作由编译器自动完成，当然你想手动传引用创建空间拷贝释放旧空间也可以，不过效率是差不多的，完成的工作基本是一样的只是多了一个交换指针的过程而已，但是这么写能节省很多程序员的工作量。

vector的大小和容量

指针相减就是之间的数据个数。

修改容量

对容量修改有两种情况，修改后的容量比之前的容量大或者是小，这里可以增加一个判断若是相等就什么都不做返回，这里我忘记加了。这里说的是有效数据与容量的对比，若是小的话就需要截取修改后容量的数据将其拷贝到新的空间中，若是大的话全部拷贝过去即可。修改三指针指向新空间。

这是修改有效数据个数的函数，两种情况与之前对比下雨或是等于直接修改指向最后一个有效数据的指针到指定的位置即可，这里相等是不需要单独判断的，可以用一个逻辑完成。

若是修改后比之前有效数据个数还要多那么就将后面的数据进行初始化。

添加元素

这里实现两个添加数据的成员函数，一个是尾插，一个是随机位置插入，尾插很简单就是需要检查是否需要扩容，扩容之后直接在最末尾插入数据size++就可以。

随机位置插入会麻烦一些，因为数据需要挪动，同样先判断是否需要扩容，扩容之后定义一定指针指向最后一个有效数据的下一个位置，从最后一个数据开始向后挪动一个位置，直到指定位置停下，然后对指定位置赋值，这里用tail来赋值也可以，tail指针已经移动过来了。

删除元素

尾删，直接将指向最后一个有效数据得到指针向前挪动一格。这里需要判断若是vector里面没有数据是不能改动的，没有数据的时候finish指针是指向NULL，对NULL--不知道会发生什么这跟对NULL的定义有关，不过一般编译器都会直接报错了。

随机位置删除，从删除位置开始，让后一个数据覆盖这个数据到finish前一个位置完成覆盖，修改finish指针，注意finish指向的是有效数据的后一个位置就是空位置，这是一个标志位，标志着一般用户访问到这里就到头了。这里返回的是删除前的元素的位置。

随机访问

随机访问是数组很重要的一个特征所以vector模仿数组这个一定得有，比数组的访问更好的是这里可以做越界检查，比数组更加安全。