STL？vector！！！

一、前言

        之前我们借助手撕string加深了类和对象相关知识，今天我们将一起手撕一个vector，继续深化类和对象、动态内存管理、模板的相关知识

二、vector相关的前置知识

        1、什么是vector？

        vector是一个STL库中提供的类模板，它是存储元素对象的顺序表，其中提供了一些有关增删查改的接口，它的特点是可以通过下标的方式在表中的任意位置进行读、写

        2、vector中的相关接口

        在本文接下来的部分会介绍vector的常用接口，事实上借助这些接口就可以解决平常所能遇到的大部分问题，如果还需要了解vector提供的更多接口及使用方法的话，可以跳转到一下网页：
        vector - C++ Referencehttps://legacy.cplusplus.com/reference/vector/vector/?kw=vector

三、手撕一个vector类

        1、成员变量与整体框架

        注意：之前的顺序表我们都是通过记录指针、元素个数和空间大小来完成的，顺序表的实现自然也可以这样，但是STL库中不是这样实现的，所以今天我们学习一下STL库中的实现方式

        上面的_start、_finish、_endofstorge分别代表着指向有效元素起始位置、终止位置的下一个位置和空间终止位置的迭代器，所以在上面我们已经定义了迭代器，事实上就是指针类型，这是由于顺序表的一大特点就是在内存中连续存储，所以可以直接使用未封装的指针；另一方面，我们在声明成员变量的同时都给了一个缺省值，这是由于它们都是指针类型，在初始化时我们都要先初始化成空指针再进行下一步操作，所以我们可以直接在这里给一个缺省值，这样避免了在初始化列表多次的显示初始化成空指针

        2、构造函数

        库中的函数头：
        

        以上的三个构造函数我们都会一一实现，在这里补充一点：在上面的构造函数中出现了"clloc"，事实上，这是一个内存池，而后面所给的缺省值是STL库中提供的一个默认的内存池，它可以有效的提高开辟空间的时间消耗，但是比较复杂，所以在这里我们直接new空间，在之后，我们会专门的进行讲解

                (1).空构造：
                

                在这里实现的空构造是非常简单的，这是由于我们在声明时已经给了缺省值，但是该空构造是一定要写的，这是因为我们还要实现别的构造函数，这时候编译器就不在自动生成默认构造函数了

                (2).用n个元素对象进行初始化：
                

                在使用n个元素对象进行初始化时，我们在参数部分给了一个缺省值T()，很明显，这是一个匿名对象，同时调用了对应的默认构造函数，这是没有问题的，但是如果T是int、float等内置类型呢？事实上，这点不用担心，这是由于C++将这些内置类型都进行了升级，使它们可以象自定义类型一样调用默认构造函数，举个例子：如果T是int类型，那么此时T()就会返沪一个0进行初始化

                (3).使用一个迭代器区间进行初始化：
                

                在上面的构造函数中，我们再次使用了模板，但这里是函数模板，这是由于我们不仅要支持顺序表的迭代器类型初始化，还要支持其它类型的迭代器初始化

        3、返回顺序表一些性质的函数

                (1).size函数：返回此时vector中的元素个数

                库中的函数头：
                

                实现：
                

                (2).capacity函数：返回此时vector中的空间大小

                库中的函数头：
                

                实现：
                

        4、拷贝构造函数

        库中的函数头：

        实现：
        

        这里需要注意：我们不可以使用memcpy，这是由于memcpy会按字节将x的内容拷贝到_start，但如果T类型是动态开辟内存，也就是说是深拷贝的话，那么虽然vector整体进行了深拷贝，但是vector中的内容却只完成了浅拷贝，会出现深浅拷贝的问题，此时选择上面的方式就万无一失了，这要求元素对象重载了赋值运算符，这一点是必须的

        5、迭代器相关函数

                (1).begin函数：

                库中的函数头：
                

                begin函数进行了两个重载，分别是普通begin和const begin它们分别可以返回一个可读可写的迭代器和一个只读不写的迭代器，都指向vector的首元素位置：
                

                (2).end函数:

                库中的函数头：
                

                end函数仍然进行了两个重载，返回的迭代器都指向末尾元素的下一个位置：
                

        6、[]操作符重载

        库中的函数头：
        

        库中对[]操作符进行了两个重载，与上面的begin类似：
        

        库中对于很多类型进行了封装，事实上上面我们实现的与库中的本质是一样的

        7、交换函数

        库中的函数头：
        

        这里的交换一定是要涉及深拷贝的，在这里我们借用一下算法库中的swap函数，因为它恰好就是深拷贝：
        

        8、赋值运算符重载

        库中的函数头：
        

        在这里我们对该函数实现进行一点小改动，但是对于用户的使用来说是相同的：
        

        在上面的实现中，我们采用了传值传参，此时形参是实参的拷贝，拷贝会调用我们之前实现过的拷贝构造函数进行深拷贝，再调用swap函数，它也会进行深拷贝之下的交换，最终*this就变成了x的拷贝，最后x这一拷贝出作用域销毁，调用析构函数(后面会实现)，进行了空间的释放

        9、开空间相关函数

                (1).reserve函数：会开辟指定大小的空间，如果原来有元素，会进行拷贝，否则不进行任何处理

                库中的函数头:
                

                实现：
                

                在上面我们又遇到了象拷贝构造函数同样的问题，所以再次使用了赋值运算符重载的方式进行处理

                (2).resize函数：会开辟指定大小的空间，用val进行初始化，缺省值为T()

                库中的函数头：
                

                实现:
                

                这里我们直接对之前的函数进行复用即可

        10、插入相关函数

                (1).insert函数：在迭代器指定的位置直接插入一个值，返回最后该位置的迭代器

                库中的函数头：
                

                实现：
                

                从上面的代码可以看出：在insert函数内部可能开辟空间，这时候pos就不是原来的pos了，所以在函数外部，传给过insert函数的迭代器是不能再次使用的，因为使用过的迭代器可能已经失效，这时候我们通过反回值的方式解决了这个问题，所以如果想再次使用的话，要接受函数的返回值

                (2).push_back函数：在vector尾部插入一个对象

                库中的函数头：
                

                实现：
                

                事实上在这个位置我们直接复用刚才写过的insert就非常方便

        11、删除相关函数

                (1).erase函数：删除迭代器指定位置的元素，返回该位置的迭代器

                库中的函数头：
                

                实现：
                

                erase所删除的位置有可能是最后一个，此时删除之后传入的迭代器·就失效了，所以要接收返回值并判断

                (2).pop_back函数

                库中的函数头：

                实现：
                

                直接复用刚才写过的erase函数即可

        12、析构函数

        由于析构函数的特殊性，这里就不提供库中的函数头了：

四、vector

        下面就是我们今天一起完成的vector了：
        

#include <iostream> #include <cassert> #include <algorithm> using namespace std; namespace bea { template<class T> class vector { typedef T* iterator; typedef const T* const_iterator; public: //空构造 vector() {} //用n个元素对象进行初始化 vector(size_t n, const T& val = T()) { _start = new T[n + 5]; for (size_t i = 0; i < n; i++) { _start[i] = val; } _finish = _start + n; _endofstorge = _start + n + 4; } //使用一个迭代器区间进行初始化 template<class InputIterator> vector(InputIterator first, InputIterator last) { size_t n = last - first; _start = new T[n + 5]; InputIterator it1 = first, it2 = _start; while (it1 < last) { *it2 = *it1; it1++, it2++; } _finish = _start + n; _endofstorge = _start + n + 4; } //拷贝构造函数 vector(const vector& x) { size_t sz = x.size(); _start = new T[sz + 5]; for (size_t i = 0; i < sz; i++) { _start[i] = x._start[i]; } _finish = _start + sz; _endofstorge = _start + sz + 4; } //size函数 size_t size() const { return _finish - _start; } //capacity函数 size_t capacity() const { return _endofstorge - _start + 1; } //begin函数 iterator begin() { return _start; } const_iterator begin() const { return _start; } //end函数 iterator end() { return _finish; } const_iterator end() const { return _finish; } //[]操作符重载 T& operator[](size_t pos) { assert(pos < size()); return _start[pos]; } const T& operator[](size_t pos) const { assert(pos < size()); return _start[pos]; } //交换函数 void swap(vector& x) { std::swap(x._start, _start); std::swap(x._finish, _finish); std::swap(x._endofstorge, _endofstorge); } //赋值运算符重载 vector& operator=(const vector x) { swap(x); return *this; } //开空间相关函数 void reserve(size_t n) { size_t sz = size(); if (n <= size()) return; iterator tmp = new T[n + 5]; if (_start) { for (size_t i = 0; i < sz; i++) { tmp[i] = _start[i]; } delete[] _start; } _finish = tmp + sz; _start = tmp; _endofstorge = tmp + n + 4; } //insert函数 iterator insert(iterator pos, const T& val) { assert(pos <= _finish); int n = pos - _start; if (capacity() < size() + 1) { reserve(size() + 5); } pos = _start + n; iterator end = _finish - 1, next = _finish; while (next > pos) { *next = *end; end--, next--; } *pos = val; _finish++; return pos; } void push_back(const T& val) { insert(_finish, val); } void resize(size_t n, T& val = T()) { vector(n, val); } //erase函数 iterator erase(iterator pos) { assert(pos < _finish); iterator end = pos + 1, front = pos; while (end < _finish) { *front = *end; front++, end++; } _finish--; if (pos == _finish) return nullptr; else return pos; } //pop_back函数 void pop_back() { erase(_finish - 1); } //析构函数 ~vector() { delete[] _start; _start = nullptr; _finish = nullptr; _endofstorge = nullptr; } private: iterator _start = nullptr; iterator _finish = nullptr; iterator _endofstorge = nullptr; }; } 

五、结语

        这就是我们所实现的vector的全部内容了，我们的目的仍然是了解vector的用法、加深类和对象和模板等知识点的理解，感谢大家的阅读，欢迎各位于晏、亦菲和我一起交流、学习、进步！