【STL】vector常见用法及模拟实现(附源码）

前言

这篇文章我们来学习一下STL容器里的vector，我们先来学习一下它的使用，然后对vector进行模拟实现。

1. vector介绍及使用

1.1vector的介绍

vector文档介绍

vector是一个大小可以更改的数组序列容器。

其实这里可以简单认为vector就是之前数据结构学的顺序表。

1.2 vector的使用

vector提供的接口跟string是非常相似的，所以经过前面string的学习，再学习vector成本降低了很多。

下面我们来介绍一下常用接口。

1.2.1 构造函数

首先看第一个：

这个是用来传空间配置器的，我们可以认为这个就是无参的构造函数，构造一个空的vector。

注意：
vector是一个类模板，类模板实例化只能显式实例化，即需要在类模板名字后跟<>，然后将实例化的类型放在<>中即可。
类模板不是真正的类，其实例化的结果才是真正的类。

这个就是支持用n个val构造一个vector对象。

这个就是支持迭代器区间构造，也不难理解我们来给大家演示一下：

这个就是拷贝构造了

1.2.2 vector对象遍历

vector也重载了[]这里可以使用for循环遍历：

也可以使用迭代器，也就是支持范围for：

1.2.3 reserve和resize

首先我们来看一下vector的扩容机制：

#include <iostream>
#include <vector>
using namespace std;
int main()
{// 测试vector的默认扩容机制size_t sz;vector<int> v;sz = v.capacity();cout << "making v grow:\n";for (int i = 0; i < 100; ++i){v.push_back(i);if (sz != v.capacity()){sz = v.capacity();cout << "capacity changed: " << sz << '\n';}}return 0;
}

这里g++下是二倍扩：

当我们知道需要多少空间，直接用reserve把空间开好，就可以减少频繁扩容的一个消耗。


确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题。

我们再来看一下resize():

resize在开空间的同时还会进行初始化,当然如果传的n比size小，那它还会删除多余的数据。

1.2.4 insert和erase

与string相比vector只支持我们去传迭代器和迭代器区间了

2. vector模拟实现

2.1 vector迭代器失效问题

会引起其底层空间改变的操作，都有可能导致迭代器失效，比如：resize、reserve、insert、assign、push_back等。
出错原因：
以上操作，都有可能会导致vector扩容，迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃(即如果继续使用已经失效的迭代器，程序可能会崩溃)。

这里我们举个简单的例子，以下代码用于输出v1中所有偶数：

int main()
{vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);v1.push_back(6);for (auto e : v1){cout << e << " ";}cout << endl;auto it = v1.begin();while(it != v1.end())//错误代码{if(*it % 2 == 0){v1.erase(it);}it++;}// while (it != v1.end())// {//     if (*it % 2 == 0)//     {//         it = v1.erase(it);//     }//     else//     {//         ++it;//     }// }
}

这里程序会报错出现段错误。实际上这里是因为是因为erase删除pos位置元素后，pos位置之后的元素会往前搬移，他没有接收返回值而是一味的进行++操作导致程序越界奔溃。

2.2 模拟实现reserve函数浅拷贝问题

这里主要出现错误的原因就是内部使用了memcpy来拷贝数据。

1. memcpy是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中
2. 如果拷贝的是内置类型的元素，memcpy既高效又不会出错

但如果拷贝的是自定义类型元素，并且
自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅拷贝
我们这里以vector< string >为例：

2.3模拟实现源码

2.3.1 vector.h

#include<iostream>
#include<assert.h>
using namespace std;namespace w
{template<class T>class vector{public: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;}vector(size_t n, const T& val = T()){resize(n, val);}vector(int n, const T& val = T()){resize(n, val);}// [first, last)template<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}vector(){}vector(const vector<T>& v){_start = new T[v.capacity()];//memcpy(_start, v._start, sizeof(T)*v.size());for (size_t i = 0; i < v.size(); i++){_start[i] = v._start[i];}_finish = _start + v.size();_endofstorage = _start + v.capacity();}void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);}vector<T>& operator=(vector<T> v){swap(v);return *this;}~vector(){if (_start){delete[] _start;_start = _finish = _endofstorage = nullptr;}}void reserve(size_t n){if (n > capacity()){size_t sz = size();T* tmp = new T[n];if (_start){//memcpy(tmp, _start, sizeof(T) * sz);for (size_t i = 0; i < sz; i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + sz;_endofstorage = _start + n;}}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;}}}void push_back(const T& x){insert(end(), x);}void pop_back(){erase(--end());}size_t capacity() const{return _endofstorage - _start;}size_t size() const{return _finish - _start;}T& operator[](size_t pos){assert(pos < size());return _start[pos];}const T& operator[](size_t pos) const{assert(pos < size());return _start[pos];}iterator insert(iterator pos, const T& x){assert(pos >= _start && pos <= _finish);if (_finish == _endofstorage){size_t len = pos - _start;size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);// 解决pos迭代器失效问题pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;return pos;}iterator erase(iterator pos){assert(pos >= _start && pos < _finish);iterator it = pos + 1;while (it != _finish){*(it - 1) = *it;++it;}--_finish;return pos;}private:iterator _start = nullptr;iterator _finish = nullptr;iterator _endofstorage = nullptr;};}

2.3.2 test.cpp

#include "vector.h"
void test_vector1(){w:: vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);for (auto e : v1){cout << e << " ";}cout<<endl;for (size_t i = 0; i < v1.size(); i++){v1[i]++;}for (auto e : v1){cout << e << " ";}cout << endl;}void test_vector2(){w ::vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);v1.push_back(5);v1.push_back(5);v1.push_back(5);for (auto e : v1){cout << e << " ";}cout << endl;v1.insert(v1.begin(), 100);for (auto e : v1){cout << e << " ";}cout << endl;}int main()
{test_vector2();return 0;
}