微网站设计制作,青海旭云网站建设,邯郸网络运营中心电话,闵行区天气 #x1f4dd;个人主页#xff1a;Sherry的成长之路 #x1f3e0;学习社区#xff1a;Sherry的成长之路#xff08;个人社区#xff09; #x1f4d6;专栏链接#xff1a;C初阶 #x1f3af;长路漫漫浩浩#xff0c;万事皆有期待 【C初阶】CSTL详解#xff08;三… 个人主页Sherry的成长之路 学习社区Sherry的成长之路个人社区 专栏链接C初阶 长路漫漫浩浩万事皆有期待 【C初阶】CSTL详解三—— vector的介绍及使用 文章目录 vector各函数接口总览vector当中的成员变量介绍默认成员函数构造函数1构造函数2构造函数3拷贝构造函数赋值运算符重载函数析构函数 迭代器相关函数begin和end反向迭代器 容量和大小相关函数size和capacityreserveresizeempty 修改容器内容相关函数push_backpop_backinserteraseswap 访问容器相关函数operator[ ] vector迭代器失效问题迭代器失效问题举例迭代器失效解决方法 总结 vector各函数接口总览
namespace sherry
{//模拟实现vectortemplateclass Tclass vector{public:typedef T* iterator;typedef const T* const_iterator;//默认成员函数vector(); //构造函数vector(size_t n, const T val); //构造函数templateclass InputIterator vector(InputIterator first, InputIterator last); //构造函数vector(const vectorT v); //拷贝构造函数vectorT operator(const vectorT v); //赋值运算符重载函数~vector(); //析构函数//迭代器相关函数iterator begin();iterator end();const_iterator begin()const;const_iterator end()const;//容量和大小相关函数size_t size()const;size_t capacity()const;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();void insert(iterator pos, const T x);iterator erase(iterator pos);void swap(vectorT v);//访问容器相关函数T operator[](size_t i);const T operator[](size_t i)const;private:iterator _start; //指向容器的头iterator _finish; //指向有效数据的尾iterator _endofstorage; //指向容器的尾};
}注为了防止与标准库当中的vector产生命名冲突模拟实现时需放在自己的命名空间当中。
vector当中的成员变量介绍
在vector当中有三个成员变量_start、_finish、_endofstorage。
_start指向容器的头_finish指向容器当中有效数据的尾_endofstorage指向整个容器的尾。
默认成员函数
构造函数1
vector支持一个无参的构造函数对于这个无参的构造函数我们直接将构造对象的三个成员变量都设置为空指针即可。
vector():_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{}构造函数2
vector支持使用一段迭代器区间进行对象的构造。因为该迭代器区间可以是其他容器的迭代器区间也就是说该函数接收到的迭代器的类型是不确定的所以我们这里需要将该构造函数设计为一个函数模板在函数体内将该迭代器区间的数据一个个尾插到容器当中即可。
templateclass InputIterator //模板函数
vector(InputIterator first, InputIterator last):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{//将迭代器区间在[first,last)的数据一个个尾插到容器当中while (first ! last){push_back(*first);first;}
}构造函数3
此外vector还支持构造这样一种容器该容器当中含有n个值为val的数据。对于该构造函数我们可以先使用reserve函数将容器容量先设置为n然后使用push_back函数尾插n个值为val的数据到容器当中即可。
vector(size_t n, const T valT()):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{reserve(n); //调用reserve函数将容器容量设置为nfor (size_t i 0; i n; i) //尾插n个值为val的数据到容器当中{push_back(val);}
}注意 1该构造函数知道其需要用于存储n个数据的空间所以最好用reserve函数一次性开辟好空间避免调用push_back函数时需要增容多次导致效率降低。 2该构造函数还需要实现两个重载函数。
vector(long n, const T val):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{reserve(n); //调用reserve函数将容器容量设置为nfor (size_t i 0; i n; i) //尾插n个值为val的数据到容器当中{push_back(val);}
}
vector(int n, const T val):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{reserve(n); //调用reserve函数将容器容量设置为nfor (int i 0; i n; i) //尾插n个值为val的数据到容器当中{push_back(val);}
}可以看到这两个重载函数与之不同的就是其参数n的类型不同但这却是必要的否则当我们使用以下代码时编译器会优先与构造函数2相匹配。
vectorint v(5, 7); //调用构造函数3 并且因为构造函数2当中对参数first和last进行了解引用而int类型不能进行解引用操作而报错。
拷贝构造函数
vector的构造函数涉及深拷贝问题这里提供两种深拷贝的写法 写法一传统写法 拷贝构造的传统写法的思想是我们最容易想到的先开辟一块与该容器大小相同的空间然后将该容器当中的数据一个个拷贝过来即可最后更新_finish和_endofstorage的值即可。
//传统写法
vector(const vectorT v):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{_start new T[v.capacity()]; //开辟一块和容器v大小相同的空间for (size_t i 0; i v.size(); i) //将容器v当中的数据一个个拷贝过来{_start[i] v[i];//memcpy(_start.v._start,sizeof(T)*v.size());}_finish _start v.size(); //容器有效数据的尾_endofstorage _start v.capacity(); //整个容器的尾
}注意 将容器当中的数据一个个拷贝过来时不能使用memcpy函数当vector存储的数据是内置类型或无需进行深拷贝的自定义类型时使用memcpy函数是没什么问题的但当vector存储的数据是需要进行深拷贝的自定义类型时使用memcpy函数的弊端就体现出来了。
例如如果vector当中存储的元素类型是内置类型int或浅拷贝的自定义类型Date使用memcpy函数进行进行拷贝构造是没问题的但如果vector当中存储的元素类型是深拷贝的自定义类型string则使用memcpy函数将不能达到我们想要的效果。
写法二现代写法 拷贝构造函数的现代写法也比较简单使用范围for或是其他遍历方式对容器v进行遍历在遍历过程中将容器v中存储的数据一个个尾插过来即可。
//现代写法
vector(const vectorT v):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{reserve(v.capacity()); //调用reserve函数将容器容量设置为与v相同for (const auto e : v) //将容器v当中的数据一个个尾插过来{push_back(e);}
}注意 在使用范围for对容器v进行遍历的过程中变量e就是每一个数据的拷贝然后将e尾插到构造出来的容器当中。就算容器v当中存储的数据是string类在e拷贝时也会自动调用string的拷贝构造深拷贝所以也能够避免出现与使用memcpy时类似的问题。
//现代写法
vector(const vectorT v):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{vectorTtmp(v.begin(),v.end());swap(tmp);
}赋值运算符重载函数
vector的赋值运算符重载也涉及深拷贝问题我们这里也提供两种深拷贝的写法 写法一传统写法 首先判断是否是给自己赋值若是给自己赋值则无需进行操作。若不是给自己赋值则先开辟一块和容器v大小相同的空间然后将容器v当中的数据一个个拷贝过来最后更新_finish和_endofstorage的值即可。
//传统写法
vectorT operator(const vectorT v)
{if (this ! v) //防止自己给自己赋值{delete[] _start; //释放原来的空间_start new T[v.capacity()]; //开辟一块和容器v大小相同的空间for (size_t i 0; i v.size(); i) //将容器v当中的数据一个个拷贝过来{_start[i] v[i];}_finish _start v.size(); //容器有效数据的尾_endofstorage _start v.capacity(); //整个容器的尾}return *this; //支持连续赋值
}注意 这里和拷贝构造函数的传统写法类似也不能使用memcpy函数进行拷贝。
写法二现代写法 赋值运算符重载的现代写法非常精辟首先在右值传参时并没有使用引用传参因为这样可以间接调用vector的拷贝构造函数然后将这个拷贝构造出来的容器v与左值进行交换此时就相当于完成了赋值操作而容器v会在该函数调用结束时自动析构。
//现代写法
//v1v2
vectorT operator(vectorT v) //编译器接收右值的时候自动调用其拷贝构造函数vv2
{swap(v); //交换这两个对象 v1 与v交换 顺便带走v1return *this; //支持连续赋值
}注意 赋值运算符重载的现代写法也是进行的深拷贝只不过是调用的vector的拷贝构造函数进行的深拷贝在赋值运算符重载函数当中仅仅是将深拷贝出来的对象与左值进行了交换而已。
析构函数
对容器进行析构时首先判断该容器是否为空容器若为空容器则无需进行析构操作若不为空则先释放容器存储数据的空间然后将容器的各个成员变量设置为空指针即可。
//析构函数
~vector()
{if (_start) //避免对空指针进行释放{delete[] _start; //释放容器存储数据的空间_start nullptr; //_start置空_finish nullptr; //_finish置空_endofstorage nullptr; //_endofstorage置空}
}迭代器相关函数
vector当中的迭代器实际上就是容器当中所存储数据类型的指针。 typedef T* iterator; typedef const T* const_iterator; begin和end
vector当中的begin函数返回容器的首地址end函数返回容器当中有效数据的下一个数据的地址。
iterator begin()
{return _start; //返回容器的首地址
}
iterator end()
{return _finish; //返回容器当中有效数据的下一个数据的地址
}我们还需要重载一对适用于const对象的begin和end函数使得const对象调用begin和end函数时所得到的迭代器只能对数据进行读操作而不能进行修改。
const_iterator begin()const
{return _start; //返回容器的首地址
}
const_iterator end()const
{return _finish; //返回容器当中有效数据的下一个数据的地址
}此时再让我们来看看vector使用迭代器的代码也就一目了然了实际上就是使用指针遍历容器。
vectorint v(5, 3);
vectorint::iterator it v.begin();
while (it ! v.end())
{cout *it ;it;
}
cout endl;现在我们实现了迭代器实际上也就可以使用范围for遍历容器了因为编译器在编译时会自动将范围for替换为迭代器的形式。
vectorint v(5, 3);
//范围for进行遍历
for (auto e : v)
{cout e ;
}
cout endl;反向迭代器 代码实现
namespace sherry
{templateclass Iterator, class Ref, class Ptrstruct Reverse_iterator{Iterator _it;typedef Reverse_iteratorIterator, Ref, Ptr Self;Reverse_iterator(Iterator it):_it(it){}Ref operator*(){Iterator tmp _it;return *(--tmp);}Ptr operator-(){return (operator*());}Self operator(){--_it;return *this;}Self operator--(){_it;return *this;}bool operator!(const Self s){return _it ! s._it;}};templateclass Tclass vector{public:typedef T* iterator;typedef const T* const_iterator;// 反向迭代器适配支持typedef Reverse_iteratoriterator, T, T* reverse_iterator;typedef Reverse_iteratorconst_iterator, const T, const T* const_reverse_iterator;const_reverse_iterator rbegin() const{// list_nodeint*return const_reverse_iterator(end());}const_reverse_iterator rend() const{return const_reverse_iterator(begin());}reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}};从功能上区分
容量和大小相关函数
size和capacity
对照着vector当中三个成员遍历各自的指向我们可以很容易得出当前容器中的有效数据个数和最大容量。
由于两个指针相减的结果就是这两个指针之间对应类型的数据个数所以size可以由_finish - _start得到而capacity可以由_endofstorage - _start得到。
size_t size()const
{return _finish - _start; //返回容器当中有效数据的个数
}
size_t capacity()const
{return _endofstorage - _start; //返回当前容器的最大容量
}reserve
reserve规则 1、当n大于对象当前的capacity时将capacity扩大到n或大于n。 2、当n小于对象当前的capacity时什么也不做。
reserve函数的实现思路也是很简单的先判断所给n是否大于当前容器的最大容量否则无需进行任何操作操作时直接开辟一块可以容纳n个数据的空间然后将原容器当中的有效数据拷贝到该空间之后将原容器存储数据的空间释放并将新开辟的空间交给该容器维护最好更新容器当中各个成员变量的值即可。
void reserve(size_t n)
{if (n capacity()) //判断是否需要进行操作{size_t sz size(); //记录当前容器当中有效数据的个数T* tmp new T[n]; //开辟一块可以容纳n个数据的空间if (_start) //判断是否为空容器{for (size_t i 0; i sz; i) //将容器当中的数据一个个拷贝到tmp当中{tmp[i] _start[i];}delete[] _start; //将容器本身存储数据的空间释放}_start tmp; //将tmp所维护的数据交给_start进行维护_finish _start sz; //容器有效数据的尾_endofstorage _start n; //整个容器的尾}
}在reserve函数的实现当中有两个地方需要注意 1在进行操作之前需要提前记录当前容器当中有效数据的个数。 因为我们最后需要更新_finish指针的指向而_finish指针的指向就等于_start指针加容器当中有效数据的个数当_start指针的指向改变后我们再调用size函数通过_finish - _start计算出的有效数据的个数就是一个随机值了。
2拷贝容器当中的数据时不能使用memcpy函数进行拷贝。 当vector当中存储的是string的时候虽然使用memcpy函数reserve出来的容器与原容器当中每个对应的string成员都指向同一个字符串空间但当释放原容器空间的时候原容器当中存储的每个string在释放时会调用string的析构函数将其指向的字符串也进行释放所以使用memcpy函数reserve出来的容器当中的每一个string所指向的字符串实际上是一块已经被释放的空间访问该容器时就是对内存空间进行非法访问。
所以还是用for循环将容器当中的string一个个赋值过来因为这样能够间接调用string的赋值运算符重载实现string的深拷贝。
resize
resize规则 1、当n大于当前的size时将size扩大到n扩大的数据为val若val未给出则默认为容器所存储类型的默认构造函数所构造出来的值。 2、当n小于当前的size时将size缩小到n。
根据resize函数的规则进入函数我们可以先判断所给n是否小于容器当前的size若小于则通过改变_finish的指向直接将容器的size缩小到n即可否则先判断该容器是否需要增容然后再将扩大的数据赋值为val即可。
void resize(size_t n, const T val T())
{if (n size()) //当n小于当前的size时{_finish _start n; //将size缩小到n}else //当n大于当前的size时{if (n capacity()) //判断是否需要增容{reserve(n);}while (_finish _start n) //将size扩大到n{*_finish val;_finish;}}
}注意 在C当中内置类型也可以看作是一个类它们也有自己的默认构造函数所以在给resize函数的参数val设置缺省值时设置为T( )即可。
empty
empty函数可以直接通过比较容器当中的_start和_finish指针的指向来判断容器是否为空若所指位置相同则该容器为空。
bool empty()const
{return _start _finish;
}修改容器内容相关函数
push_back
要尾插数据首先得判断容器是否已满若已满则需要先进行增容然后将数据尾插到_finish指向的位置再将_finish即可。
//尾插数据
void push_back(const T x)
{if (_finish _endofstorage) //判断是否需要增容{size_t newcapacity capacity() 0 ? 4 : 2 * capacity(); //将容量扩大为原来的两倍reserve(newcapacity); //增容}*_finish x; //尾插数据_finish; //_finish指针后移
}pop_back
尾删数据之前也得先判断容器是否为空若为空则做断言处理若不为空则将_finish–-即可。
//尾删数据
void pop_back()
{assert(!empty()); //容器为空则断言_finish--; //_finish指针前移
}insert
insert函数可以在所给迭代器pos位置插入数据在插入数据前先判断是否需要增容然后将pos位置及其之后的数据统一向后挪动一位以留出pos位置进行插入最后将数据插入到pos位置即可。
//在pos位置插入数据
void insert(iterator pos, const T x)
{if (_finish _endofstorage) //判断是否需要增容{size_t len pos - _start; //记录pos与_start之间的间隔size_t newcapacity capacity() 0 ? 4 : 2 * capacity(); //将容量扩大为原来的两倍reserve(newcapacity); //增容pos _start len; //通过len找到pos在增容后的容器当中的位置}//将pos位置及其之后的数据统一向后挪动一位以留出pos位置进行插入iterator end _finish;while (end pos 1){*end *(end - 1);end--;}*pos x; //将数据插入到pos位置_finish; //数据个数增加一个_finish后移
}注意 若需要增容则需要在增容前记录pos与_start之间的间隔然后通过该间隔确定在增容后的容器当中pos的指向否则pos还指向原来被释放的空间。
erase
erase函数可以删除所给迭代器pos位置的数据在删除数据前需要判断容器释放为空若为空则需做断言处理删除数据时直接将pos位置之后的数据统一向前挪动一位将pos位置的数据覆盖即可。
//删除pos位置的数据
iterator erase(iterator pos)
{assert(!empty()); //容器为空则断言//将pos位置之后的数据统一向前挪动一位以覆盖pos位置的数据iterator it pos 1;while (it ! _finish){*(it - 1) *it;it;}_finish--; //数据个数减少一个_finish前移return pos;
}swap
swap函数用于交换两个容器的数据我们可以直接调用库当中的swap函数将两个容器当中的各个成员变量进行交换即可。
//交换两个容器的数据
void swap(vectorT v)
{//交换容器当中的各个成员变量::swap(_start, v._start);::swap(_finish, v._finish);::swap(_endofstorage, v._endofstorage);
}注意 在此处调用库当中的swap需要在swap之前加上“::”作用域限定符告诉编译器这里优先在全局范围寻找swap函数否则编译器会认为调用的是正在实现的swap函数就近原则。
访问容器相关函数
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]; //返回对应数据
}注意 重载运算符[ ]时需要重载一个适用于const容器的因为const容器通过“下标[ ]”获取到的数据只允许进行读操作不能对数据进行修改。
vector迭代器失效问题
迭代器的主要作用就是让我们在使用各个容器时不用关心其底层的数据结构而vector的迭代器在底层实际上就是一个指针。迭代器失效就是指迭代器底层对应指针所指向的空间被销毁了而指向的是一块已经被释放的空间如果继续使用已经失效的迭代器程序可能会崩溃。
迭代器失效问题举例
实例一
#include iostream
#include algorithm
#include vector
using namespace std;int main()
{vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);//v: 1 2 3 4 5vectorint::iterator pos find(v.begin(), v.end(), 2); //获取值为2的元素的迭代器v.insert(pos, 10); //在值为2的元素的位置插入10//v: 1 10 2 3 4 5v.erase(pos); //删除元素2 error迭代器失效//v: 1 2 3 4 5return 0;
}在该代码中我们本意是使用元素2的迭代器在原序列中2的位置插入一个10然后将2删除但我们实际上获取的是指向2的指针当我们在2的位置插入10后该指针就指向了10所以我们之后删除的实际上是10而不是2。
实例二
#include iostream
#include vector
using namespace std;int main()
{vectorint v;for (size_t i 1; i 6; i){v.push_back(i);}vectorint::iterator it v.begin();while (it ! v.end()){if (*it % 2 0) //删除容器当中的全部偶数{v.erase(it);}it;}return 0;
}该代码看上去实际上并没有什么错误但如果你画图仔细分析你就会发现该代码的问题所在迭代器访问到了不属于容器的内存空间导致程序崩溃。
不仅如此而且在迭代器遍历容器中的元素进行判断时并没有对1、3、5元素进行判断。
迭代器失效解决方法
使用迭代器时永远记住一句话每次使用前对迭代器进行重新赋值。
实例一解决方案
#include iostream
#include algorithm
#include vector
using namespace std;int main()
{vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);//v: 1 2 3 4 5vectorint::iterator pos find(v.begin(), v.end(), 2); //获取值为2的元素的迭代器v.insert(pos, 10); //在值为2的元素的位置插入10//v: 1 10 2 3 4 5pos find(v.begin(), v.end(), 2); //重新获取值为2的元素的迭代器v.erase(pos); //删除元素2//v: 1 10 3 4 5return 0;
}
对于实例一我们在使用迭代器删除元素2时对其进行重新赋值便可以解决。
实例二解决方案
#include iostream
#include vector
using namespace std;int main()
{vectorint v;for (size_t i 1; i 6; i){v.push_back(i);}vectorint::iterator it v.begin();while (it ! v.end()){if (*it % 2 0) //删除容器当中的全部偶数{it v.erase(it); //删除后获取下一个元素的迭代器}else{it; //是奇数则it}}return 0;
}对于实例二我们可以接收erase函数的返回值erase函数返回删除元素的后一个元素的新位置并且控制代码的逻辑当元素被删除后继续判断该位置的元素因为该位置的元素已经更新需要再次判断。
总结
今天我们比较详细地完成了vector类的学习了解了一些有关的底层原理。接下来我们将进行STL中vector类的模拟实现。希望我的文章和讲解能对大家的学习提供一些帮助。 当然本文仍有许多不足之处欢迎各位小伙伴们随时私信交流、批评指正我们下期见~
