海盐网站设计,比wordpress更好,简单网站建设,本地wordpress搬家目录
一. vector概述
二. vector接口函数的使用方法和模拟实现
2.1 vector类模板的成员变量
2.2 构造函数的使用和模拟实现
2.2.1 构造函数的使用方法
2.2.2 构造函数的模拟实现
2.3 析构函数的模拟实现
2.4 赋值运算符重载函数的使用和模拟实现
2.4.1 函数的使用
2.…目录
一. 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* iteratortypedef const T* const_iterator
vector类有三个成员变量分别为_start、_finish、_endOfStorage它们的类型都为iterator
_start为指向第一个元素的位置的指针。_finish指向最后一个有效数据后面那个位置处的指针。_endOfStorage指向可用空间末尾位置的指针。图2.1 vector类成员变量意义图解2.2 构造函数的使用和模拟实现
2.2.1 构造函数的使用方法
C STL标准中给出了四种常用的方法构造vector类对象
默认方法构造explicit vector() -- 构造出的对象不存储任何数据。给定n个初始化值来构造explicit vector(size_t n, const T val T()) -- 创建的类含有n个数据均为val。给出一段迭代器区间以迭代器区间中的数据作为初始化值进行初始化 --vector(InputIterator first, InputIterator)拷贝构造vector(const vector v)
int main()
{vectorint v1; //构造空类vectorint v2(3, 5); //构造类用3个5作为初始化值vectorint v3(v2.begin(), v2.end()); //用指向v2起始位置和终止位置的迭代的区间的数据作为初始化值vectorint 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 InputIteratorvector(InputIterator first, InputIterator last): _start(nullptr), _finish(nullptr), _endOfStorage(nullptr){while (first ! last){push_back(*first);first;}}void swap(vectorT v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endOfStorage, v._endOfStorage);}//拷贝构造函数vector(const vectorT v): _start(nullptr), _finish(nullptr), _endOfStorage(nullptr){vectorT 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()
{vectorint v1(3, 6);vectorint 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 vectorT v){vectorT 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()
{vectorint 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()
{vectorint v1(5, 2); //v1中存储5个2const vectorint v2(5, 5); //v2中存储5个5vectorint::iterator it1 v1.begin();while (it1 ! v1.end()) //调用普通对象迭代器将v1的每个成员1并打印{(*it1);cout *it1 ; //3 3 3 3 3it1;}cout endl;vectorint::const_iterator it2 v2.begin(); while (it2 ! v2.end()) //调用const对象迭代器打印v2的每个数据{//(*it2); //const对象成员变量的值不能被改变报错cout *it2 ; //5 5 5 5 5it2;}cout endl;return 0;
}
2.6.2 函数的模拟实现
begin函数直接返回_startend函数直接返回_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()
{vectorint 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;vectorint::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语句就会存在迭代器失效。
下面的代码希望完成的操作是在vectorint对象中删除所有的偶数数据通过测试我们发现
如果vector中的数据为1 2 3 4 5正常删除所有偶数。如果vector中的数据为1 2 3 4则程序会崩溃。如果vector中的数据为1 2 4 5那么会有偶数没有被删除。vectorint::iterator it v.begin();while (it ! v.end()){if (*it % 2 0){v.erase(it);}it;} 图2.3 执行erase操作时迭代器失效问题图解下面这段代码通过接收erase的返回值并赋给it就不会存在迭代器失效的问题。 vectorint::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 Tclass vector{public://迭代器定义typedef T* iterator; //对于普通对象的迭代器typedef const T* const_iterator; //对于const对象的迭代器//-------------------------------------------------------------------------//构造、赋值和析构相关函数vector() //默认构造函数: _start(nullptr), _finish(nullptr), _endOfStorage(nullptr){ }//以迭代器区间数据为初始化值的构造函数template class InputIteratorvector(InputIterator first, InputIterator last): _start(nullptr), _finish(nullptr), _endOfStorage(nullptr){while (first ! last){push_back(*first);first;}}void swap(vectorT v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endOfStorage, v._endOfStorage);}//拷贝构造函数vector(const vectorT v): _start(nullptr), _finish(nullptr), _endOfStorage(nullptr){vectorT tmp(v.begin(), v.end()); //构建与v相同的临时对象swap(tmp); //交换this和tmp的内容这样tmp被析构时就会销毁原来_start指向的空间}//析构函数~vector(){delete[] _start;_start _finish _endOfStorage nullptr;}//赋值函数vector operator(const vectorT v){vectorT 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; //指向存储空间末尾后面那个位置的指针};
}
