C++ STL：vector的使用方法及模拟实现

目录

一. vector概述

二. vector接口函数的使用方法和模拟实现

2.1 vector类模板的成员变量

2.2 构造函数的使用和模拟实现

2.2.1 构造函数的使用方法

2.2.2 构造函数的模拟实现

2.3 析构函数的模拟实现

2.4 赋值运算符重载函数的使用和模拟实现

2.4.1 函数的使用

2.4.2 函数的模拟实现

2.5 vector类对象容量相关函数的使用和模拟实现

2.5.1 函数的使用

2.5.2 函数的模拟实现

2.6 迭代器相关函数的使用和模拟实现

2.6.1 函数的使用

2.6.2 函数的模拟实现

2.7 数据插入函数的使用和模拟实现

2.7.1 函数的使用

2.7.2 函数的模拟实现

2.8 数据删除函数的使用及模拟实现

2.8.1 函数的使用

2.8.2 函数的模拟实现

附录：vector类模拟实现完整版

---

一. vector概述

vector是可以动态改变容量大小的顺序存储容器，其本质为模板类，用于在一块连续的空间存储特定类型的数据。

简单来说，可以将vector理解为顺序表或数组，可以通过特定的函数，对一个vector类对象完成增删查改等操作，可以通过下标访问特定位置处的元素。

图1.1 vector的结构示意图

二. vector接口函数的使用方法和模拟实现

2.1 vector类模板的成员变量

我们假设vector的模板参数类型为template <class T>，并且定义了一个普通对象迭代器iterator和const属性对象迭代器const_iterator：

• typedef T* iterator
• typedef const T* const_iterator

vector类有三个成员变量，分别为_start、_finish、_endOfStorage，它们的类型都为iterator

1. _start：为指向第一个元素的位置的指针。
2. _finish：指向最后一个有效数据后面那个位置处的指针。
3. _endOfStorage：指向可用空间末尾位置的指针。

图2.1 vector类成员变量意义图解

2.2 构造函数的使用和模拟实现

2.2.1 构造函数的使用方法

C++ STL标准中给出了四种常用的方法构造vector类对象：

1. 默认方法构造：explicit vector() -- 构造出的对象不存储任何数据。
2. 给定n个初始化值来构造：explicit vector(size_t n, const T& val = T()) -- 创建的类含有n个数据，均为val。
3. 给出一段迭代器区间，以迭代器区间中的数据作为初始化值进行初始化 --vector(InputIterator first, InputIterator)
4. 拷贝构造：vector(const vector& v)

int main()
{vector<int> v1;  //构造空类vector<int> v2(3, 5);   //构造类，用3个5作为初始化值vector<int> v3(v2.begin(), v2.end());   //用指向v2起始位置和终止位置的迭代的区间的数据作为初始化值vector<int> v4(v3);   //拷贝构造//输出v1到v4类中的值for (auto e : v1)  //输出空{cout << e << " ";}cout << endl;for (auto e : v2)  //5 5 5{cout << e << " ";}cout << endl;for (auto e : v3)  //5 5 5{cout << e << " ";}cout << endl;for (auto e : v4)  //5 5 5{cout << e << " ";}cout << endl;return 0;
}

2.2.2 构造函数的模拟实现

这里我对默认构造、迭代器区间构造以及拷贝构造进行模拟实现。

• 默认构造函数：只需要将vector的三个成员变量_start、_finish、_endOfStorage均初始化为nullptr即可。
• 迭代器区间构造：检查迭代器的有效性，调用push_back（尾插函数），将迭代器区间中的数据依次插入到vector对象中即可。
• 拷贝构造：可以通过本本分分进行深拷贝来构造，也可以通过创建一个临时对象来构造。

        vector()  //默认构造函数: _start(nullptr), _finish(nullptr), _endOfStorage(nullptr){ }//以迭代器区间数据为初始化值的构造函数template <class InputIterator>vector(InputIterator first, InputIterator last): _start(nullptr), _finish(nullptr), _endOfStorage(nullptr){while (first != last){push_back(*first);++first;}}void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endOfStorage, v._endOfStorage);}//拷贝构造函数vector(const vector<T>& v): _start(nullptr), _finish(nullptr), _endOfStorage(nullptr){vector<T> tmp(v.begin(), v.end());  //构建与v相同的临时对象swap(tmp);  //交换this和tmp的内容，这样tmp被析构时，就会销毁原来_start指向的空间}

2.3 析构函数的模拟实现

析构函数在vector对象的生命周期结束时由编译器自动调用，并不需要用户来显示地进行调用，因此不需要探究其使用方法。

模拟实现的~vector()函数，只需要释放_start指向的内存空间，然后将三个成员变量都置为nullptr即可。

		~vector(){delete[] _start;_start = _finish = _endOfStorage = nullptr;}

2.4 赋值运算符重载函数的使用和模拟实现

2.4.1 函数的使用

我们只需要获取两个已经存在的类对象，将其中一个的作为右值赋给另外一个即可，赋值之后，两个类对象的数据、容量均相同。

int main()
{vector<int> v1(3, 6);vector<int> v2(5, 1);v2 = v1;for (auto e : v2)  //6 6 6{cout << e << " ";}cout << endl;
}

2.4.2 函数的模拟实现

通过创建一个临时的类对象tmp，来实现对vector对象之间的赋值，其中vector对象中存储的内容和右值相同。

		vector& operator=(const vector<T>& v){vector<T> tmp(v.begin(), v.end());swap(tmp);return *this;}

2.5 vector类对象容量相关函数的使用和模拟实现

2.5.1 函数的使用

• size：获取vector对象中存储的有效数据个数。
• capacity：获取vector对象的容量（最多存储多少个数据）。
• reserve：将vector对象的容量扩大到n，如果对象当前的容量小于等于n，则不执行任何操作。
• resize：删除数据，或将vector对象的容量扩大到n并进行初始化。

int main()
{vector<int> v1(5, 3);cout << "size = " << v1.size() << endl;   //获取有效数据个数cout << "capacity = " << v1.capacity() << endl;   //获取容量v1.reserve(7);  //扩容cout << "capacity = " << v1.capacity() << endl;   //获取容量v1.resize(10, 5);  //扩容并初始化cout << "capacity = " << v1.capacity() << endl;   //获取容量for (auto e : v1)  {cout << e << " ";}cout << endl;return 0;
}

2.5.2 函数的模拟实现

• size：通过指针减法来实现，即：_finish - _start，获取对象中的数据个数。
• capacity：与size一样，通过指针减法来实现，_endOfStorage - _start。
• reserve：检查待扩容容量n是否大于原容量capacity，如果小于，就不执行任何操作，如果大于，就开辟一块新的内存空间，并将原来_start指向的内存空间的内容拷贝到新的内存空间中去，释放掉原来_start指向的内存空间，对_start、_finish、_endOfStorage进行更新。
• resize：函数参数为size_t n，如果n < size()，那么就将数据删除到n个，如果大于capacity，就扩容，将从_finish到_endOfStroage的内存空间的内容都初始化为指定值。

		size_t capacity() const //获取对象容量函数{return _endOfStorage - _start;}size_t size() const //数据个数获取函数{return _finish - _start;}void reserve(size_t n)  //扩容函数{if (n > capacity()){T* tmp = new T[n];   //新的存储数据的空间size_t sz = size();  //获取数据个数//将原来的内容拷贝到新的空间中去for (size_t i = 0; i < sz; ++i){tmp[i] = _start[i];}delete[] _start;  //释放原空间_start = tmp;  //_start指向新空间//更新容量(_finish、_endOfStroage)_finish = _start + sz;_endOfStorage = _start + n;}}//扩容 + 初始化 或 删除数据void resize(size_t n, const T& val = T()){if (n < size()){_finish = _start + n;}else{if (n > capacity()){reserve(n);}while (_finish != _endOfStorage){*_finish = val;++_finish;}}}

2.6 迭代器相关函数的使用和模拟实现

2.6.1 函数的使用

• begin：返回vector对象中首个元素的地址。
• end：返回vector对象中最后一个元素后面那个位置的地址。

迭代器主要用于遍历数据，以及作为find(数据查找函数)的返回值，以及插入数据函数insert和删除数据函数erase的位置参数。

图2.1 begin和end返回值指向的位置

int main()
{vector<int> v1(5, 2);   //v1中存储5个2const vector<int> v2(5, 5);   //v2中存储5个5vector<int>::iterator it1 = v1.begin();while (it1 != v1.end())  //调用普通对象迭代器，将v1的每个成员+1并打印{(*it1)++;cout << *it1 << " ";  //3 3 3 3 3++it1;}cout << endl;vector<int>::const_iterator it2 = v2.begin();   while (it2 != v2.end())  //调用const对象迭代器，打印v2的每个数据{//(*it2)++;   //const对象成员变量的值不能被改变，报错cout << *it2 << " ";  //5 5 5 5 5++it2;}cout << endl;return 0;
}

2.6.2 函数的模拟实现

begin函数直接返回_start，end函数直接返回_finsih即可。注意begin和end都要写成重载的形式，以适用于普通对象和const属性对象。

		iterator begin(){return _start;}const_iterator begin() const{return _start;}iterator end(){return _finish;}const_iterator end() const{return _finish;}

2.7 数据插入函数的使用和模拟实现

2.7.1 函数的使用

• push_back：在vector对象尾部插入一个数据。
• insert：在pos位置处插入数据。

其中insert函数返回指向插入数据位置处的指针，这样做是为了防止迭代器失效。insert函数的函数原型为iterator insert(iterator pos, const T& val)，即：在pos位置处插入val值。

迭代器失效发生在原vector对象容量不足无法容纳新数据时，此时函数会先执行扩容操作，然后再插入数据。而扩容实际上是新开辟了一块内存空间，将原来vector中的内容复制到了新的空间，而我们传给函数的pos指向的是原来那块空间的某个位置。综上，如果扩容，pos就不再指向vector对象的空间，从而引发迭代器失效。

如图2.2所示，在capacity = 4的vector对象的pos位置（第二个数据位置）插入一个新数据5，而原来的对象中已经存放了4个数据，那么函数会新开一块空间，然后指向插入。但此时pos依然指向原来vector的内存空间，但这块空间已经换给了操作系统。

图2.2  迭代器失效问题及insert返回值图解

int main()
{vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);  //将1、2、3依次尾插到v1尾部for (auto e : v1)  //打印v1中的每个元素{cout << e << " ";  //1 2 3}cout << endl;vector<int>::iterator pos = find(v1.begin(), v1.end(), 2);  //找v1中数据2的位置pos = v1.insert(pos, 10);  pos = v1.insert(pos, 20);  pos = v1.insert(pos, 30);  //在pos位置依次插入10、20、30for (auto e : v1)  //打印v1中的每个元素{cout << e << " ";  //1 30 20 10 2 3}cout << endl;return 0;
}

2.7.2 函数的模拟实现

• push_back函数：首先检查是否需要扩容，需要就调用reserve函数扩容。然后在_finish指向的位置插入特定值，更新_finish的指向。
• insert函数的实现：检查是否需要扩容，如果需要，就调用reserve函数扩容，并且在扩容的同时更改形参pos的指向。然后将pos位置往后的数据全部后移，在pos位置插入数据，更新_finish的指向，返回pos。

		void push_back(const T& val)  //尾插数据函数{if (_finish == _endOfStorage){//如果没有剩余容量，就扩容reserve(capacity() == 0 ? 4 : 2 * capacity());}*_finish = val;++_finish;}//在pos位置插入数据iterator insert(iterator pos, const T& val){if (_finish == _endOfStorage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : 2 * capacity());pos = _start + len;}//pos开始的数据后移一个单位iterator end = _finish;while (end > pos){*end = *(end - 1);--end;}//在pos位置插入数据*pos = val;++_finish;return pos;}

2.8 数据删除函数的使用及模拟实现

2.8.1 函数的使用

• erase函数：删除pos位置处的元素，返回插入指向插入数据位置处的指针pos。

erase函数与insert函数一样，会存在迭代器失效问题。因为删除数据要将pos后面的数据向前移动，则会覆盖掉原来pos位置，如果想删除pos位置的数据之后，再删除pos位置后面的那个数据，如果指型++pos语句，就会存在迭代器失效。

下面的代码希望完成的操作是在vector<int>对象中删除所有的偶数数据，通过测试，我们发现：

• 如果vector中的数据为1 2 3 4 5，正常删除所有偶数。
• 如果vector中的数据为1 2 3 4，则程序会崩溃。
• 如果vector中的数据为1 2 4 5，那么会有偶数没有被删除。

	vector<int>::iterator it = v.begin();while (it != v.end()){if (*it % 2 == 0){v.erase(it);}++it;}

图2.3 执行erase操作时迭代器失效问题图解

 

下面这段代码，通过接收erase的返回值并赋给it，就不会存在迭代器失效的问题。

	vector<int>::iterator it = v.begin();while (it != v.end()){if (*it % 2 == 0){it = v.erase(it);}else{++it;}}

2.8.2 函数的模拟实现

检查pos是否越界，然后将pos后面的数据全部向前移动一个单位，再更新_finish，返回pos即可。

		iterator erase(iterator pos){assert(pos >= _start);assert(pos < _finish);//将pos后面的数据向前移动一个单位iterator begin = pos + 1;while (begin < _finish){*(begin - 1) = *begin;++begin;}--_finish;return pos;}

附录：vector类模拟实现完整版

namespace zhang
{template <class T>class vector{public://迭代器定义typedef T* iterator;   //对于普通对象的迭代器typedef const T* const_iterator;  //对于const对象的迭代器//-------------------------------------------------------------------------//构造、赋值和析构相关函数vector()  //默认构造函数: _start(nullptr), _finish(nullptr), _endOfStorage(nullptr){ }//以迭代器区间数据为初始化值的构造函数template <class InputIterator>vector(InputIterator first, InputIterator last): _start(nullptr), _finish(nullptr), _endOfStorage(nullptr){while (first != last){push_back(*first);++first;}}void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endOfStorage, v._endOfStorage);}//拷贝构造函数vector(const vector<T>& v): _start(nullptr), _finish(nullptr), _endOfStorage(nullptr){vector<T> tmp(v.begin(), v.end());  //构建与v相同的临时对象swap(tmp);  //交换this和tmp的内容，这样tmp被析构时，就会销毁原来_start指向的空间}//析构函数~vector(){delete[] _start;_start = _finish = _endOfStorage = nullptr;}//赋值函数vector& operator=(const vector<T>& v){vector<T> tmp(v.begin(), v.end());swap(tmp);return *this;}//--------------------------------------------------------------------------//对象成员及容量相关函数size_t capacity() const //获取对象容量函数{return _endOfStorage - _start;}size_t size() const //数据个数获取函数{return _finish - _start;}void reserve(size_t n)  //扩容函数{if (n > capacity()){T* tmp = new T[n];   //新的存储数据的空间size_t sz = size();  //获取数据个数//将原来的内容拷贝到新的空间中去for (size_t i = 0; i < sz; ++i){tmp[i] = _start[i];}delete[] _start;  //释放原空间_start = tmp;  //_start指向新空间//更新容量(_finish、_endOfStroage)_finish = _start + sz;_endOfStorage = _start + n;}}//扩容 + 初始化 或 删除数据void resize(size_t n, const T& val = T()){if (n < size()){_finish = _start + n;}else{if (n > capacity()){reserve(n);}while (_finish != _endOfStorage){*_finish = val;++_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 push_back(const T& val)  //尾插数据函数{if (_finish == _endOfStorage){//如果没有剩余容量，就扩容reserve(capacity() == 0 ? 4 : 2 * capacity());}*_finish = val;++_finish;}//在pos位置插入数据iterator insert(iterator pos, const T& val){if (_finish == _endOfStorage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : 2 * capacity());pos = _start + len;}//pos开始的数据后移一个单位iterator end = _finish;while (end > pos){*end = *(end - 1);--end;}//在pos位置插入数据*pos = val;++_finish;return pos;}//删除pos位置处的数据iterator erase(iterator pos){assert(pos >= _start);assert(pos < _finish);//将pos后面的数据向前移动一个单位iterator begin = pos + 1;while (begin < _finish){*(begin - 1) = *begin;++begin;}--_finish;return pos;}//---------------------------------------------------------------------------//迭代器相关函数iterator begin(){return _start;}const_iterator begin() const{return _start;}iterator end(){return _finish;}const_iterator end() const{return _finish;}private:iterator _start;   //指向数组起始位置的指针iterator _finish;  //指向数组中最后一个元素后面那个位置的指针iterator _endOfStorage;   //指向存储空间末尾后面那个位置的指针};
}