---

前言

  我们来实现一下vector吧！
  这会很有意思的！

---

一、各函数接口总览

  不如先来看看我们要实现的接口，请注意！实际实现并未声明和定义分离，因为这涉及到模板的一些特性，我们先按下不表，后面再做解释，且为了避免与库里的vector相冲突，我们要用命名空间包起来！

namespace HQ
{//模拟实现vectortemplate<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;//默认成员函数vector();                                           //构造函数vector(size_t n, const T& val);                     //构造函数template<class InputIterator>                      vector(InputIterator first, InputIterator last);    //构造函数vector(const vector<T>& v);                         //拷贝构造函数vector<T>& operator=(const vector<T>& v);           //赋值运算符重载函数~vector();                                          //析构函数//迭代器相关函数iterator begin();iterator end();const_iterator begin() const;const_iterator end() const;//容量和大小相关函数size_t size() const;size_t capacity() const;void clear()；void reserve(size_t n);void resize(size_t n, const T& val = T());bool empty() const;//修改容器内容相关函数void push_back(const T& x);void pop_back();iterator insert(iterator pos, const T& x);iterator erase(iterator pos);void swap(vector<T>& v);//访问容器相关函数T& front();const T& front(); constT& back();const T& back(); constT& operator[](size_t i);const T& operator[](size_t i)const;private:iterator _start;        // 指向容器的头iterator _finish;       // 指向有效数据的尾iterator _endofstorage; // 指向容器的尾};template<class T>void print_vector(const vector<T>& v); 
}

二、默认成员函数

vector();

很显然的无参构造，这时候只需要将三个成员变量初始化为空指针即可：

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

vector(size_t n, const T& val = T( ));

我们可以先使用reserve函数将容器容量先设置为n，然后使用push_back函数尾插n个值为val的数据到容器当中即可，并且正如我们上篇说的一样，最好再重载一个vector(int n, const T& val = T( )); 版本:

vector(size_t n, const T& val):_start(nullptr),_finish(nullptr),_end_of_storage(nullptr)
{reserve(n); // 调用reserve函数将容器容量设置为nfor (size_t i = 0; i < n; i++) // 尾插n个值为val的数据到容器当中{push_back(val);}
}

template< class InputIterator> vector(InputIterator first, InputIterator last);

因为该迭代器区间可以是其他容器的迭代器区间，也就是说该函数接收到的迭代器的类型是不确定的，所以我们这里需要将该构造函数设计为一个函数模板：

// 请注意，接下来的接口将不再给出初始化列表
// 事实上，运用缺省值这里会更方便一些
template<class InputIterator> // 模板函数
vector(InputIterator first, InputIterator last)
{// 将迭代器区间在[first,last)的数据一个个尾插到容器当中while (first != last){push_back(*first);++first;}
}

vector(const vector& v);

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

vector& operator=(const vector& v);

//传统写法
vector<T>& operator=(const vector<T>& v)
{if (this != &v) // 防止自己给自己赋值{delete[] _start; // 释放原来的空间_start = new T[v.capacity()]; // 开辟一块和容器v大小相同的空间// 注意这里不能使用memcpy函数进行拷贝！// 原因是memcpy是值拷贝，浅拷贝！for (size_t i = 0; i < v.size(); i++) // 将容器v当中的数据一个个拷贝过来{_start[i] = v[i];}_finish = _start + v.size(); // 容器有效数据的尾_end_of_storage = _start + v.capacity(); // 整个容器的尾}return *this; //支持连续赋值
}

vector& operator=(const vector v);

事实上，赋值运算符重载还有一个非常狂野的写法，我们看这种方式舍弃了引用传值，先来个拷贝构造，接着再跟this交换数值空间，又因为v是临时变量，出作用域后立马销毁，非常巧妙，有种借力打击的感觉！：

vector<T>& operator=(vector<T> v)
{if (this != &v) // 防止自己给自己赋值{swap(v);}return *this;
}

~vector();

对容器进行析构时，首先判断该容器是否为空容器，若为空容器，则无需进行析构操作，若不为空，则先释放容器存储数据的空间，然后将容器的各个成员变量设置为空指针即可：

~vector()
{if (_start) //避免对空指针进行释放{delete[] _start; _start = _finish = _end_of_storage = nullptr;}
}

三、迭代器相关函数

vector当中的迭代器实际上就是容器当中所存储数据类型的指针：

typedef T* iterator;
typedef const T* const_iterator;

begin函数返回容器的首地址，end函数返回容器当中有效数据的下一个数据的地址，而我们还需要重载一对适用于const对象的begin和end函数，使得const对象调用begin和end函数时所得到的迭代器只能对数据进行读操作，而不能进行修改：

iterator begin()
{return _start; // 返回容器的首地址
}iterator end()
{return _finish; // 返回容器当中有效数据的下一个数据的地址
}const_iterator begin() const
{return _start; // 返回容器的首地址
}const_iterator end() const
{return _finish; // 返回容器当中有效数据的下一个数据的地址
}

四、容量和大小有关函数

size & capacity

由于两个指针相减的结果，就是这两个指针之间对应类型的数据个数，所以利用三个原生指针，我们可以很显然的得出 size 和 capacity

size_t size() const
{return _finish - _start; // 返回容器当中有效数据的个数
}size_t capacity() const
{return _endofstorage - _start; // 返回当前容器的最大容量
}

reserve

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

我们要注意两个问题：

野指针问题

迭代器失效的问题，出现野指针_finish指向错误。在delete[ ] _start的时候，_finish还在指向旧空间，导致调用size()得到数据错误，我们的解决办法就是在开辟新空间之前，保存一下旧size()的值，存在临时变量old_size里面

浅拷贝问题

memcpy是逐字节拷贝，属于浅拷贝。当T为自定义类型，使用memcpy进行浅拷贝操作，会指向同一块空间，我们的解决办法是利用赋值运算符，就算是自定义类型，也有自己的赋值构造函数

resize

根据resize函数的规则，进入函数我们可以先判断所给n是否小于容器当前的size，若小于，则通过改变_finish的指向，直接将容器的size缩小到n即可，否则先判断该容器是否需要增容，然后再将扩大的数据赋值为val即可。

那等于呢？等于怎么办？
那就不动呗~直接跳出

// 在C++当中内置类型也可以看作是一个类，它们也有自己的默认构造函数
// 所以在给resize函数的参数val设置缺省值时，设置为T()即可
void resize(size_t n, const T& val = T())
{if (n < size()) // 当n小于当前的size时{_finish = _start + n; // 将size缩小到n}else if (n > capacity()){reserve(n);while (_finish < _start + n) // 将size扩大到n{*_finish = val;_finish++;}}
}

empty

empty函数可以直接通过比较容器当中的_start和_finish指针的指向来判断容器是否为空，若所指位置相同，则该容器为空

bool empty()
{return _start == _finish;
}

五、增删查改有关函数

push_back

要尾插数据首先得判断容器是否已满，若已满则需要先进行增容，然后将数据尾插到_finish指向的位置，再将_finish++即可

void push_back(const T& x)
{// 扩容if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;++_finish;
}

pop_back

尾删数据之前也得先判断容器是否为空，若为空则做断言处理，若不为空则将_finish- -即可

//尾删数据
void pop_back()
{assert(!empty()); // 容器为空则断言--_finish; // _finish指针前移
}

insert

insert函数可以在所给迭代器pos位置插入数据，在插入数据前先判断是否需要增容，然后将pos位置及其之后的数据统一向后挪动一位，以留出pos位置进行插入，最后将数据插入到pos位置即可

iterator insert(iterator pos, const T& x)
{assert(pos >= _start);assert(pos <= _finish);// 扩容if (_finish == _end_of_storage){// 若需要增容，则需要在增容前记录pos与_start之间的间size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;return pos;
}

erase

erase函数可以删除所给迭代器pos位置的数据，在删除数据前需要判断容器释放为空，若为空则需做断言处理，删除数据时直接将pos位置之后的数据统一向前挪动一位，将pos位置的数据覆盖即可

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

swap

直接调用库当中的swap函数将两个容器当中的各个成员变量进行交换即可

void swap(vector<T>& v)
{// 根据就近原则，所以你需要加上个std::std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);
}

六、访问容器相关函数

operator[ ]

vector也支持我们使用“下标+[ ]”的方式对容器当中的数据进行访问，实现时直接返回对应位置的数据即可

T& operator[](size_t i)
{assert(i < size()); // 检测下标的合法性return _start[i]; // 返回对应数据
}const T& operator[](size_t i) const
{assert(i < size()); // 检测下标的合法性return _start[i]; // 返回对应数据
}

front & back

很简单，也是直接利用原生指针来返回即可

T& front()
{return *_start;
}const T& front() const
{return *_start;
}T& back()
{return *(_finish - 1);
}const T& back() const
{return *(_finish - 1);
}

---

总结

  怎么样，接下来我们就要迎来不太一样的list了哦！