网站开发哪一门语言更快,wordpress 远程 mysql,wordpress跟随插件,免费的网页服务器vector使用以及模拟实现 vector介绍vector常用接口1.构造2.迭代器3.容量4.增删查改5.练习 vector模拟实现1.迭代器失效2.反向迭代器3.完整代码 vector介绍
和我们原来讲的string不同#xff0c;vector并不是类#xff0c;是一个类模板#xff0c;加类型实例化以后才… vector使用以及模拟实现 vector介绍vector常用接口1.构造2.迭代器3.容量4.增删查改5.练习 vector模拟实现1.迭代器失效2.反向迭代器3.完整代码 vector介绍
和我们原来讲的string不同vector并不是类是一个类模板加类型实例化以后才是类。vector是表示可变大小数组的序列容器。像数组一样vector也采用的连续存储空间来存储元素但是容量可以动态改变。和其它容器相比vector访问元素、尾插、尾删较高效但不在尾部的插入和删除效率比较低需要频繁插入和删除的话不建议使用vector。 vector常用接口
1.构造
函数声明功能vector()常用无参构造vectorsize_type n, const value_type val value_type()构造并初始化n个valvector (const vector x)常用拷贝构造vector (InputIterator first, InputIterator last)迭代器区间初始化(模板可以传入其它容器的迭代器区间) 2.迭代器
函数声明功能begin()加end() 常用获取第一个数据位置的iterator/const_iterator获取最后一个数据的下一个位置的iterator/const_iteratorrbegin()加rend()反向迭代器获取最后一个数据位置的reverse_iterator获取第一个数据前一个位置的reverse_iterator 3.容量
函数声明功能size() 常用获取数据个数capacity()获取容器容量empty()判断是否为空(size为0为空返回true)resize(size_type n, value_type val value_type()) 1.nsize()时从尾开始填充val直到容器满2.n容量就先扩容再填充 3.nsize()时缩小size()保留前n个。reserve(size_t n 0)预留空间n大于容量时扩容不然什么都不做 4.增删查改
函数声明功能push_back (const value_type val)常用尾插pop_back()常用尾删find (InputIterator first, InputIterator last, const T val)不是vector接口是算法库里面的模板传入一段迭代器区间可以在该区间查找valinsert (iterator position, const value_type val)在position前插入valerase (iterator position)删除position位置的数据swap (vector x)交换两个vector的数据空间operator[] (size_type n)像数组一样访问数据 5.练习
只出现一次的数字i
题目要求
题解
class Solution
{
public:int singleNumber(vectorint nums) {//这个题需要异或这个位运算//异或是相同为0不同为1。//所以两个相同的数异或会得到0//0和任何数异或都得到这个数本身//题目明确了只有一个数出现一次其它都出现两次//因此我们可以把所有数异或一次出现两次的数字会抵消变成0//最后出现一次的数字一定可以留下来int end 0;vectorint::iterator it nums.begin();//auto it nums.begin();while(it ! nums.end()){end ^ *it;it;}//范围for同理// for(auto ch : nums)// end ^ ch;return end;}
};删除排序数组中的重复项
题目要求 题解
class Solution {
public:int removeDuplicates(vectorint nums) {int sum 1;int slow 1;int fast 1;//快慢指针while(fast nums.size()){if(nums[fast] nums[fast-1]){nums[slow] nums[fast];sum;}else{fast;}}return sum; }
};杨辉三角
题目要求
题解
class Solution {
public:vectorvectorint generate(int numRows) {vectorvectorint vv;//把size调整为numRowsvv.resize(numRows);for(int i 0; i numRows; i){vv[i].resize(i1,0);//每一行最后一个和第一个初始为1vv[i][0] vv[i][vv[i].size()-1] 1;}for(int i 0; i numRows; i){for(int j 0; j vv[i].size(); j){if(vv[i][j] 0) vv[i][j] vv[i-1][j] vv[i-1][j-1]; }}return vv;}
};vector模拟实现
1.迭代器失效 迭代器的主要作用就是让算法能够不用关心底层数据结构而vector迭代器的底层实际是一个指针在对容器进行操作例如插入、删除、修改等后之前获取的迭代器可能会变得无效。 可能会导致其迭代器失效的操作有
会引起其底层空间改变的操作(扩容)都有可能是迭代器失效比如resize、reserve、insert、push_back等。
#define _CRT_SECURE_NO_WARNINGS 1
#include iostream
using namespace std;
#include vector
int main()
{vectorint v{ 1,2,3,4,5,6 };auto it v.begin();// 将有效元素个数增加到100个多出的位置使用8填充操作期间底层会扩容// v.resize(100, 8);// reserve的作用就是改变扩容大小但不改变有效元素个数操作期间可能会引起底层容量改变// v.reserve(100);// 插入元素期间可能会引起扩容而导致原空间被释放// v.insert(v.begin(), 0);// v.push_back(8);// 给vector重新赋值可能会引起底层容量改变v.assign(100, 8);/*出错原因以上操作都有可能会导致vector扩容也就是说vector底层旧空间被释放掉而在打印时it还使用的是释放之间的旧空间在对it迭代器操作时实际操作的是一块已经被释放的空间而引起代码运行时崩溃。解决方式在以上操作完成之后如果想要继续通过迭代器操作vector中的元素只需给it重新赋值即可。*/while (it ! v.end()){cout *it ;it;}cout endl;return 0;
}指定位置元素的删除操作–erase #define _CRT_SECURE_NO_WARNINGS 1
#include iostream
using namespace std;
#include vector
int main()
{vectorint v{ 1,2,3,4,5,6 };//earse不会影响底层的空间不进行扩容和缩容//但是也存在迭代器失效的问题//下面这段代码用来删除v中的偶数auto it v.begin();while (it ! v.end()){if (*it % 2 0) {//把这个位置数据删除掉v.erase(it);}it;}//结果程序崩溃//原因看图解erase是会改变end()的//解决方法每次erase操作后都及时更新迭代器//erase会返回被删除数据下一位置的迭代器//auto it v.begin();//while (it ! v.end())//{// if (*it % 2 0)// {// //把这个位置数据删除掉// it v.erase(it);// }// else// {// it;// }//}return 0;
}2.反向迭代器 vector的反向迭代器实现并不困难只需要复用普通的迭代器操作变成调用普通迭代器的––调用即可。 // 反向迭代器需要进行封装其实就是复用普通迭代器然后和--操作反过来
//这里设计模板参数除了迭代器还有Ref(引用)和Ptr(指针)
//这样设计是为了同时生成普通迭代器和const对象的迭代器//普通对象可读可写Reverse_iteratoriteratorTT*
//const对象可读不可写Reverse_iteratorconst_iteratorconst Tconst T*
templateclass Iterator, class Ref, class Ptr
struct Reverse_iterator
{//给自己也重命名一下方便用typedef Reverse_iteratorIterator, Ref, Ptr self;Iterator _it;Reverse_iterator(Iterator it):_it(it){}self operator(){_it--;return *this;}self operator(int){self tmp(*this);_it--;return tmp;}self operator--(){_it;return *this;}self operator--(int){self tmp(*this);_it;return tmp;}Ref operator*(){return *_it;}//返回指针可以让自定义类型自行打印访问成员//-操作符比较特殊it-_num转换出来其实是it.operator-()-_numPtr operator-(){return _it;}bool operator!(const self s){return _it ! s._it;}bool operator(const self s){return _it s._it;}
};3.完整代码
采用三个迭代器(指针)来维护底层空间
private:iterator _start nullptr;iterator _finish nullptr;iterator _endofstorage nullptr;#pragma once
#includeiostream
#includeassert.h
//#includevector
using namespace std;//和库里面的区分开
namespace MyVector
{// 反向迭代器需要进行封装其实就是复用普通迭代器然后和--操作反过来//这里设计模板参数除了迭代器还有Ref(引用)和Ptr(指针)//这样设计是为了同时生成普通迭代器和const对象的迭代器//普通对象可读可写Reverse_iteratoriteratorTT*//const对象可读不可写Reverse_iteratorconst_iteratorconst Tconst T*templateclass Iterator, class Ref, class Ptrstruct Reverse_iterator{//给自己也重命名一下方便用typedef Reverse_iteratorIterator, Ref, Ptr self;Iterator _it;Reverse_iterator(Iterator it):_it(it){}self operator(){_it--;return *this;}self operator(int){self tmp(*this);_it--;return tmp;}self operator--(){_it;return *this;}self operator--(int){self tmp(*this);_it;return tmp;}Ref operator*(){return *_it;}//返回指针可以让自定义类型自行打印访问成员//-操作符比较特殊it-_num转换出来其实是it.operator-()-_numPtr operator-(){return _it;}bool operator!(const self s){return _it ! s._it;}bool operator(const self s){return _it s._it;}};//vector类模板template typename Tclass vector{public:typedef T* iterator;typedef const T* const_iterator;typedef Reverse_iteratoriterator, T, T* reverse_iterator;typedef Reverse_iterator const_iterator, const T,const T* reverse_const_iterator;iterator begin(){//隐式类型转换return _start;}iterator end(){return _finish;}const_iterator begin()const{return _start;}const_iterator end()const{return _finish;}reverse_iterator rbegin(){return _finish-1;}reverse_iterator rend(){return _start-1;}reverse_const_iterator rbegin()const{return _finish-1;}reverse_const_iterator rend()const{return _start-1;}/////无参构造vector(){}//函数模板传入容器的一段迭代器区间template typename InputIteratorvector(InputIterator first, InputIterator last){while (first ! last){push_back(*first);first;}}//构造vector(const vectorT v){//提前开好空间reverse(v.capacity());for (auto e : v){push_back(e);}}vector(size_t n, const T val T()){reverse(n);for (size_t i 0; i n; i){push_back(val);}}//重载给内置类型使用//没有的话vectorint v(5,0)会优先和vector(InputIterator first, InputIterator last)匹配//对整形解引用会报错vector(int n, const T val T()){reverse(n);for (int i 0; i n; i){push_back(val);}}~vector(){delete[] _start;_start _finish _endofstorage nullptr;}void swap(vectorT v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);}//传值传参拷贝一份直接交换操作的空间即可vectorT operator(vectorT v){swap(v);return *this;}/// ///void reverse(size_t n){if (n capacity()){//这里扩容空间会变化先记录size//这里扩容空间会变化先记录size//这里扩容空间会变化先记录sizesize_t sz size();T* tmp new T[n];//这里涉及到深浅拷贝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{//先扩容reverse(n);while (_finish _start n){*_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];}size_t capacity()const{return _endofstorage - _start;}size_t size()const{return _finish - _start;}/// ///void push_back(const T x){//复用即可insert(end(), x);}void insert(iterator pos, const T x){assert(pos _finish pos _start);if (_finish _endofstorage){size_t gap pos - _start;//初始扩容需要指定给reverse(capacity() 0 ? 4 : 2 * capacity());pos _start gap;}iterator end _finish;while (end pos){*end *(end - 1);end--;}*pos x;_finish; }iterator erase(iterator pos){assert(pos _finish pos _start);iterator it pos 1;while (it _finish){*(it - 1) *it;it;}_finish--;return pos;}private:iterator _start nullptr;iterator _finish nullptr;iterator _endofstorage nullptr;};}
