网站建设 熊掌号,建立一个商城网站,wordpress安装创建数据库,济南网站价格目录 一、vector的介绍及使用1.1 介绍vector1.2 vector的使用1.2.1 构造1.2.2 遍历访问1.2.3 容量空间1.2.4 增删查改 二、vector的模拟实现2.1 成员变量2.2 迭代器相关函数2.3 构造-析构-赋值重载2.3.1 无参构造2.3.2 有参构造12.3.3 有参构造22.3.4 拷贝构造2.3.5 赋值重载2.… 目录 一、vector的介绍及使用1.1 介绍vector1.2 vector的使用1.2.1 构造1.2.2 遍历访问1.2.3 容量空间1.2.4 增删查改 二、vector的模拟实现2.1 成员变量2.2 迭代器相关函数2.3 构造-析构-赋值重载2.3.1 无参构造2.3.2 有参构造12.3.3 有参构造22.3.4 拷贝构造2.3.5 赋值重载2.3.6 析构 2.4 容量操作2.4.1 size和capacity2.4.2 reserve2.4.3 resize 2.5 插入与删除2.5.1 尾插2.5.2 尾删2.5.3 pos位置插入2.5.3 pos位置删除 2.6 遍历访问2.7 全部代码2.7.1 vector.h2.7.2 test.cpp 一、vector的介绍及使用
1.1 介绍vector
vector是一个可变大小数组的容器与数组一样vector也是一块连续的空间可以像数组一样对元素进行高效的遍历访问但是普通数组的大小是不变的vector可以改变自身大小。vector是采用动态分配数组来存储数据即插入新元素时要改变存储空间大小往往要分配一个新的数组然后把原来数组的元素转移到新的空间里。vector的尾插尾删效率高中间插入和删除效率较低。
1.2 vector的使用
1.2.1 构造
1️⃣无参 vector() vectorint v;2️⃣构造并初始化n个val vectorsize_type n, const value_type val value_type() vectorint v(10, 7);3️⃣拷贝构造 vector (const vector x) vectorint v1{ 1,2,3,4 };vectorint v2(v1);4️⃣使用迭代器进行初始化构造 vector (InputIterator first, InputIterator last) vectorint v1{ 5,6,7,8};vectorint v2(v1.begin(), v1.end());1.2.2 遍历访问
1️⃣beginend vectorint v{ 1,2,3,4,5 };auto it v.begin();while (it ! v.end()){cout *it ;it;}cout endl;获取数组第一个元素的位置像指针一样遍历整个数组直到最后一个元素结束。auto是自动推导类型。
2️⃣下标operator[ ] vectorint v{ 1,2,3,4,5 };for (int i 0; i 5; i){cout v[i] ;}cout endl;3️⃣范围for vectorint v{ 1,2,3,4,5 };for (auto e : v){cout e ;}cout endl;1.2.3 容量空间
1️⃣获取元素个数 vectorint v{ 1,2,3,4,5 };cout v.size() endl;//52️⃣获取容量大小 vectorint v{ 1,2,3,4,5 };cout v.capacity() endl;//53️⃣判断是否为空 vectorint v;cout v.empty() endl;4️⃣改变vector的size void resize (size_type n, value_type val value_type()); vectorint v{ 1,2,3,4,5 };for (auto e : v){cout e ;}cout endl;cout v.size() endl;cout v.capacity() endl;v.resize(10, 9);cout endl;for (auto e : v){cout e ;}cout endl;cout v.size() endl;cout v.capacity() endl;如果超出原来的存储空间那么capacity也会改变
5️⃣改变vector的capacity void reserve (size_type n); vectorint v{ 1,2,3,4,5 };for (auto e : v){cout e ;}cout endl;cout v.size() endl;cout v.capacity() endl;v.reserve(10);cout endl;for (auto e : v){cout e ;}cout endl;cout v.size() endl;cout v.capacity() endl;1.2.4 增删查改
1️⃣尾插 vectorint v{ 1,2,3,4,5 };v.push_back(9);for (auto e : v){cout e ;}cout endl;2️⃣尾删 vectorint v{ 1,2,3,4,5 };v.pop_back();for (auto e : v){cout e ;}cout endl;3️⃣查找 注意查找不是vector的接口是算法模块实现的。 template class InputIterator, class T InputIterator find (InputIterator first, InputIterator last, const T val); vectorint v{ 1,2,3,4,5 };auto it find(v.begin(), v.end(), 2);cout *it endl;//24️⃣交换 void swap (vector x); vectorint v1{ 1,2,3,4,5 };vectorint v2{ 6,7,8,9,10 };v2.swap(v1);5️⃣在pos位置插入 iterator insert (iterator position, const value_type val); vectorint v{ 1,2,3,4,5 };auto pos find(v.begin(), v.end(), 2);v.insert(pos, 10);for (auto e : v){cout e ;}cout endl;6️⃣在pos位置删除 iterator erase (iterator position);//指定位置删除 iterator erase (iterator first, iterator last);//指定范围删除 有两种写法
// 一vectorint v{ 1,2,3,4,5 };auto pos find(v.begin(), v.end(), 2);v.erase(pos);for (auto e : v){cout e ;}cout endl;// 二vectorint v{ 1,2,3,4,5 };v.erase(v.begin() 1, v.end() - 1);for (auto e : v){cout e ;}cout endl; 注意insert 和 erase 一般只使用一次重复使用可能导致迭代器失效。 二、vector的模拟实现
2.1 成员变量
vector的迭代器是一个原生指针它的三个成员变量分别是 typedef T* iterator;typedef const T* const_iterator;//————————iterator _start nullptr;iterator _finish nullptr;iterator _endofstorage nullptr;这里在声明时先给成员变量缺省值为空指针声明时给缺省值是给初始化列表的后续写的时候就比较方便。
2.2 迭代器相关函数
begin函数返回空间的起始位置end函数返回空间的最后一个有效元素的下一位。 // 通过迭代器访问元素时可修改iterator begin(){return _start;}iterator end(){return _finish;}// 通过迭代器访问元素时不可修改const_iterator begin() const {return _start;}const_iterator end() const{return _finish;}2.3 构造-析构-赋值重载
2.3.1 无参构造
没有传参数 vector(){}2.3.2 有参构造1
代码
templateclass InputIterator
vector(InputIterator first, InputIterator last)
{reserve(last - first);//复用扩容函数while (first ! last)//判断条件{push_back(*first);//复用尾插函数first;//尾插一次后加1}
}这个函数看起来有些奇怪为啥还要套一层模板呢使用这里就不说了其实这个构造函数的作用是只要传进来的是迭代器就可以初始化该迭代器的内容前提是该迭代器是指向连续物理空间的指针。比如用vector定义了一个v1v1已经是构造好的有具体的元素再定义一个v2我想让v2的内容跟v1是一样的就可以使用这个函数传的迭代器指向的是v1的头和尾它就会构造出和v1一样的内容。前面的使用方法有代码。不仅可以vector传vector还可以list传vector只要是迭代器即可。
2.3.3 有参构造2
vector(size_t n, const T x T())
{resize(n, x);//复用修改元素个数函数
}
vector(int n, const T x T())
{resize(n, x);//复用修改元素个数函数
}该构造函数是初始化为n大小的空间每个元素是x。可以直接复用resize函数下面会介绍。这里写了两个构造函数唯一的区别是size_t 和int 因为如果只有size_t 类型的那个构造函数构造时不会调用该函数会调用前面的构造函数有参构造1这与函数模板的匹配调用原则有关。假如传进来的n不是size_t 类型那么它就要发生隐式类型转换但是编译器想隐式类型转换感觉麻烦就使用有模板的那个函数。
为了防止出现以上情况同时是模拟实现要尽可能像标准库里面的vector所以多重载了一个函数它的参数n是int 类型的这样的话传进来的参数n是int 类型那么它就会直接调用这个构造函数避免了以上情况。
2.3.4 拷贝构造
拷贝构造要注意深浅拷贝问题 1️⃣写法1
vector(const vectorT v)
{_start new T[v.capacity()];//开一样大的空间memcpy(_start, v._start, sizeof(T) * v.size());//拷贝数据_finish _start v.size();_endofstorage _start v.capacity();
}与string的拷贝构造类似开一块新空间拷贝数据后指向这个新空间这样防止两个指针指向同一块空间。 写法1还要注意memcpy的深浅拷贝问题与元素的类型有关这个在后面会具体介绍现在假设统一使用的元素类型先是 int 类型。
1️⃣写法2
vector(const vectorT v)
{reserve(v.capacity());//复用扩容函数for (const auto e : v)//范围for循环直接放入数据即可{push_back(e);//复用尾插函数}
}先开与参数v一样大的空间然后使用范围for直接放入数据只要参数v里面有元素都可以把元素一个一个的尾插到要构造的空间里面同时也不影响v最终完成拷贝构造。
2.3.5 赋值重载
1️⃣写法1
vectorT operator(const vectorT v)
{if (this ! v)//相同就不用赋值{T* tmp new T[v.capacity()];//临时空间memcpy(tmp, v._start, sizeof(T) * v.size());//拷贝数据delete[] _start;//清理旧空间_start tmp;//指向新空间_finish _start v.size();//_endofstorage _start v.capacity();}return *this;
}1️⃣写法2 与string的是一样的直接代码
vectorT operator(vectorT v)
{swap(v);//复用交换函数return *this;
}//交换
void swap(vectorT v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);
}2.3.6 析构
如果空间里有元素才清理让3个指针置空没有元素本来就是空指针不能清理。
~vector()
{if (_start){delete[] _start;_start _finish _endofstorage nullptr;//}
}2.4 容量操作
2.4.1 size和capacity
根据三个指针的指向可以确定有效元素个数和容量的区间
//返回个数
size_t size() const
{return _finish - _start;
}
//返回容量
size_t capacity() const
{return _endofstorage - _start;
}2.4.2 reserve
如果存储的元素超出原来的空间大小要扩容扩容要开辟一块新空间然后拷贝数据到新空间里再让指针重新指向这块新空间。 代码
//扩容
void reserve(size_t n)
{if (n capacity())//满了要扩容{size_t old size();//记录当前元素个数T* tmp new T[n];//新空间if(_start){//memcpy(tmp, _start, sizeof(T) * old);//将数据拷贝到新空间-浅拷贝for (size_t i 0; i old; i){tmp[i] _start[i];//深拷贝}delete[] _start;//释放就空间}_start tmp;//指向新空间_finish _start old;//防止迭代器失效_endofstorage _start n;}
}问题1为什么要定义变量old 开空间拷贝数据后旧空间被释放指向新空间_finish等于_start 加上元素个数注意如果没有old前面先记录元素个数的值加上的是调用size函数返回的元素个数那么就会出现迭代器失效问题。因为_start已经指向新的空间而_finish还是指向旧空间的某个位置那个不同空间相减就出问题了。 所以这里提前用变量old记录好元素的个数_finsih等于_startold就不会出现以上情况。 问题2memcpy是浅拷贝 元素类型是int 等内置类型没关系如果是自定义类型比如string这里就会出现浅拷贝的问题。 深拷贝的做法是以赋值的形式逐个把旧空间的字符串给新空间
2.4.3 resize
该函数可通过参数n修改元素个数超出容量也会扩容。主要分为以下3点 1.n小于等于元素个数 2.n大于元素个数且小于等于容量 3.n大于容量 代码
void resize(size_t n, const T x T())
{if (n size()){_finish _start n;//修改_finish指向即可}else//nsize(){size_t len n - size();//n与元素个数的差值if (n capacity())//n大于容量要扩容{reserve(n);//复用扩容函数}while (len--)//插入len个x只要n大于size()都要插入{*_finish x;_finish;}}
}2.5 插入与删除
2.5.1 尾插
void push_back(const T x)
{if (_finish _endofstorage){size_t newcapacity capacity() 0 ? 4 : 2 * capacity();reserve(newcapacity);}*_finish x;_finish;
}尾插数据_finish 指向同_endofstorage说明空间内数据已满要扩容。然后插入在_finish指向的位置插入数据_finish往后移。
2.5.2 尾删
void pop_back()
{assert(size() 0);//有元素才能删--_finish;
}2.5.3 pos位置插入
首先断言pos的位置是否合理然后凡是插入数据都要检查是否需要扩容。接着挪动数据在pos位置插入新的元素。
iterator insert(iterator pos, const T x)
{assert(pos _start pos _finish);//检查pos位置是否合理size_t len pos - _start;//记录pos与开始位置差值if (_finish _endofstorage)//满了要扩容{size_t newcapacity capacity() 0 ? 4 : 2 * capacity();reserve(newcapacity);pos _start len;//防止迭代器失效}iterator end _finish - 1;while (end pos)//挪动数据{*(end 1) *end;--end;}*pos x;//插入新数据_finish;return pos;
}这里唯一要注意的是如果有发生扩容pos的位置要进行更新。
2.5.3 pos位置删除
判断pos位置是否合理然后挪动数据往前覆盖一个元素。
iterator erase(iterator pos)
{assert(pos _start pos _finish);iterator begin pos 1;while (begin _finish){*(begin - 1) *begin;begin;}--_finish;return pos;
}2.6 遍历访问
遍历访问有两种实现方式一种是迭代器前面已经写过了另一种是方括号重载运算符即我们常见的下标。
T operator[](size_t pos)
{assert(pos size());return _start[pos];
}
const T operator[](size_t pos) const
{assert(pos size());return _start[pos];
}2.7 全部代码
2.7.1 vector.h
#include iostream
#include assert.h
using namespace std;namespace yss
{template class Tclass 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;}//构造1vector(){}//构造2vector(size_t n, const T x T()){resize(n, x);}vector(int n, const T x T()){resize(n, x);}//构造3templateclass InputIteratorvector(InputIterator first, InputIterator last){reserve(last - first);while (first ! last){push_back(*first);first;}}//拷贝构造//写法1//vector(const vectorT v)//{// _start new T[v.capacity()];//开一样大的空间// memcpy(_start, v._start, sizeof(T) * v.size());//拷贝数据// _finish _start v.size();//// _endofstorage _start v.capacity();//}//写法2vector(const vectorT v){reserve(v.capacity());for (const auto e : v){push_back(e);}}//赋值重载//写法1//vectorT operator(const vectorT v)//{// if (this ! v)// {// T* tmp new T[v.capacity()];//临时空间// memcpy(tmp, v._start, sizeof(T) * v.size());//拷贝数据// delete[] _start;// _start tmp;// _finish _start v.size();//// _endofstorage _start v.capacity();// }// return *this;//}//写法2vectorT operator(vectorT v){swap(v);return *this;}//析构~vector(){if (_start){delete[] _start;_start _finish _endofstorage nullptr;//}}//返回个数size_t size() const{return _finish - _start;}//返回容量size_t capacity() const{return _endofstorage - _start;}//交换void swap(vectorT v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);}//扩容void reserve(size_t n){if (n capacity())//满了要扩容{size_t old size();//记录当前元素个数T* tmp new T[n];//新空间if(_start){//memcpy(tmp, _start, sizeof(T) * old);//将数据拷贝到新空间-浅拷贝for (size_t i 0; i old; i){tmp[i] _start[i];//深拷贝}delete[] _start;//释放就空间}_start tmp;//指向新空间_finish _start old;//防止迭代器失效_endofstorage _start n;}}//改变元素个数void resize(size_t n, const T x T()){if (n size()){_finish _start n;}else{size_t len n - size();if (n capacity()){reserve(n);}while (len--){*_finish x;_finish;}}}//尾插void push_back(const T x){if (_finish _endofstorage){size_t newcapacity capacity() 0 ? 4 : 2 * capacity();reserve(newcapacity);}*_finish x;_finish;}//尾删void pop_back(){assert(size() 0);--_finish;}//pos位置插入iterator insert(iterator pos, const T x){assert(pos _start pos _finish);size_t len pos - _start;//记录pos与开始位置差值if (_finish _endofstorage){size_t newcapacity capacity() 0 ? 4 : 2 * capacity();reserve(newcapacity);pos _start len;//防止迭代器失效}iterator end _finish - 1;while (end pos){*(end 1) *end;--end;}*pos x;_finish;return pos;}//pos位置删除iterator erase(iterator pos){assert(pos _start pos _finish);iterator begin pos 1;while (begin _finish){*(begin - 1) *begin;begin;}--_finish;return pos;}//下标T operator[](size_t pos){assert(pos size());return _start[pos];}const T operator[](size_t pos) const{assert(pos size());return _start[pos];}private:iterator _start nullptr;iterator _finish nullptr;iterator _endofstorage nullptr;};
}2.7.2 test.cpp
#includevector.hint main()
{/*yss::vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);auto it v.begin();while (it ! v.end()){cout *it ;it;}cout endl;*//*yss::vectorint v(10);for (auto e : v){cout e ;}cout endl;*//*yss::vectorint v1(5, 99);yss::vectorint v2(v1.begin(), v1.end());for (auto e : v2){cout e ;}cout endl;*//*yss::vectorint v1(5, 55);yss::vectorint v2(v1);for (auto e : v2){cout e ;}cout endl;*//*yss::vectorint v1(7, 44);yss::vectorint v2 v1;for (auto e : v2){cout e ;}cout endl;*//*yss::vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);auto pos find(v.begin(), v.end(), 2);v.insert(pos, 99);for (auto e : v){cout e ;}*//*yss::vectorint v;v.push_back(1);v.push_back(22);v.push_back(43);v.push_back(64);v.push_back(85);for (size_t i 0; i v.size(); i){cout v[i] ;}cout endl;*/return 0;
}
