模板与vector的学习

目录1.模板1.1函数模板1.2类模板2.vector2.1vector的使用2.1.1vector的定义​编辑2.1.2vector迭代器的使用2.1.3vector的空间管理​编辑2.1.4vector的增删查改操作2.2vector迭代器失效3.vector的模拟实现3.1构造函数和析构函数3.2头尾迭代器3.3空间管理函数3.4增删查改函数3.5补充1.模板在之前学习函数重载时我们知道形参的类型不同可以构成重载但是如果我们对该函数有很多种输入的要求例如整型字符类型浮点数类型的变量写交换函数时就需要写三个函数但是模板可以进行一个泛型编程的操作把识别类型交给编译器来做1.1函数模板如下三个交换函数构成函数重载很明显这样写很冗余void swap(int x, int y) { int tmp x; x y; y tmp; } void swap(double x, double y) { double tmp x; x y; y tmp; } void swap(char x, char y) { char tmp x; x y; y tmp; }所以我们就可以使用模板来写函数模板的写法如下T1T2等就是虚拟变量在使用时由编译器自动匹配类型class也可以用typename来写注意模板中也可以存在真实的类型不全是虚拟变量例如可以在模板中写size_t nint xtemplateclass T1,class T2.....代码如下这就是一个简易的模板函数当我们需要对某个类型的两个变量进行交换时只需要将变量直接放入函数中即可编译器会自动识别类型templateclass T void swap(T x, T y) { T tmp x; x y; y tmp; }注意在这个swap函数中如果传入的x和y不是一个类型的就会产生报错因为只有一个T无法匹配两个类型编译器就不能确定T的类型导致编译报错这就引出模板的隐式实例化和显式实例化例如一个加法函数只用了一个虚拟变量T那么如果传入的参数类型不同就会报错所以第二个输出add(x,z)会显示报错但是第三个输出就不会这就是显式实例化直接规定T的类型传入参数时会强行转换成对应类型进行操作不加int就是隐式实例化类型交给编译器自己识别注意一个点在形参部分要加上const因为进行类型强转时会产生一个临时对象这个临时对象具有常性如果不加const就造成了权限的放大templateclass T T add(const T x, const T y) { return x y; } int main(){ int x 10; int y 20; double z 1.1; cout add(x, y) endl; cout add(x, z) endl; cout addint(x, z) endl; return 0; }如果既有匹配的普通函数也可以用模板函数会优先调用普通函数因为现成的函数不需要编译器去识别类型更加方便templateclass T T add(const T x, const T y) { cout 调用了模板函数 endl; return x y; } int add(const int x, const int y) { cout 调用了普通函数 endl; return x y 10; } int main(){ int x 10; int y 20; cout add(x, y) endl; //输出40 return 0; }1.2类模板和函数模板的使用没有很大区别例如一个栈我们之前如果想改变内部存储的数据类型直接在typedef的位置修改类型即可但是如果要创建好几个存储不同数据类型的栈就需要使用到模板直接进行显式实例化即可具体的使用可以根据下文讲解vector的时候继续理解2.vectorvector和之前学的string一样都是一种存储数据的容器在使用上和string有相似之处所以学过string之后继续学vector就觉得比较轻松而vector其实就是顺序表只不过它可以使用很多函数直接进行操作比自己创建的数组顺序表要方便很多2.1vector的使用2.1.1vector的定义vector在初始化时常见的有几种方式1.无参构造2.通过n个相同类型的val来构造注意val不一定是内置类型也可以是其他类或者嵌套vector3.通过一段迭代器区间将这一段的数据依次放入vector4.拷贝构造直接拷贝现成的vector#includeiostream #includevector using namespace std; int main(){ vectorint v1;//无参构造 vectorint v2(5, 1);//通过n个val来构造(size_t n,const T valT()) int arr[5] { 1,2,3,4,5 }; vectorint v3(arr, arr 4);//通过一段迭代器区间 vectorint v4(v3);//拷贝构造 for (auto e : v2) { cout e; } cout endl; for (auto e : v3) { cout e; } cout endl; for (auto e : v4) { cout e; } return 0; }2.1.2vector迭代器的使用和string一样有begin和end函数用于指示开头和末尾例如用两个迭代器分别正向逆向遍历vector注意反向迭代器名字要加上reverse并且之后是朝着开头位置走的而不是往末尾#includeiostream #includevector using namespace std; int main(){ vectorint v1 { 1,2,3,4,5,6,7 }; vectorint::iterator it v1.begin(); vectorint::reverse_iterator it1 v1.rbegin(); while (it ! v1.end()) { cout *it; it; } cout endl; while (it1 ! v1.rend()) { cout *it1; it1; } cout endl; return 0; }2.1.3vector的空间管理可以使用size函数获取元素个数capacity函数获取空间大小resize可以改变元素的个数如果传入的参数小于原来的元素个数那么就会直接删除多余的元素如果大于原来元素个数在比空间还大的情况下会进行扩容的操作大于元素个数小于空间个数那么只会填充vector使其元素个数达到目标reverse函数可以为vector预留空间指定vector的空间大小#includeiostream #includevector using namespace std; int main(){ vectorint v1 { 1,2,3,4,5,6,7 }; cout v1.size() endl; cout v1.capacity() endl; v1.resize(5); v1.reserve(10); cout v1.size() endl; cout v1.capacity() endl; return 0; }2.1.4vector的增删查改操作push_back尾插元素pop_back尾删元素insert和erase用于指定位置插入和删除元素注意传入的参数要是迭代器类型使用迭代器表示位置而不是下标swap函数可以直接交换两个vector容器中的数据find函数不是vector的成员接口但是用于查找对应元素下标也可以使用但是要注意加上头文件algorithm才能调用算法库的find返回值是一个迭代器减去开头的迭代器就可以获取下标#includeiostream #includevector #includealgorithm using namespace std; int main() { vectorint v1 { 1,2,3,4,5,6,7 }; vectorint v2 { 10,9,8,7,6,5,4 }; cout 交换前的v1:; for (auto e : v1) { cout e ; } cout endl; cout 交换前的v2:; for (auto e : v2) { cout e ; } cout endl; swap(v1, v2); cout 交换后的v1:; for (auto e : v1) { cout e ; } cout endl; cout 交换后的v2:; for (auto e : v2) { cout e ; } cout endl; cout v1[1] v1[2] endl; v1.push_back(9); v1.push_back(10); v1.insert(v1.begin() 1, 20); for (auto e : v1) { cout e ; } cout endl; v1.pop_back(); v1.pop_back(); v1.erase(v1.begin() 4); for (auto e : v1) { cout e ; } cout endl; auto f find(v1.begin(), v1.end(), 7); cout f - v1.begin() endl; return 0; } }2.2vector迭代器失效对于改变底层空间的操作可能会引起迭代器失效1.插入元素时如果空间不够那么此时会进行扩容扩容完的空间和原来不是一个空间而迭代器还留在旧空间的位置所以此时迭代器失效2.删除元素时删除某个位置的元素后后面所有的元素均往前移动此时没有造成空间的改变但是如果此时删除的是最后一个元素此时就会获取到一个空的位置再进行解引用就会产生报错而编译器就认为这样的操作是不安全的为了防止对空指针进行解引用所以此时的迭代器就失效了判定它不可继续使用所以对于下面的代码当vector进行删除操作时该位置及其之后的迭代器就会失效当进行insert插入操作时如果没有进行扩容迭代器不失效但是扩容的时候就会失效#includeiostream #includevector #includealgorithm using namespace std; int main() { vectorint v1 { 1,2,3,4,5,6,7 }; vectorint::iterator it v1.begin(); while (it ! v1.end()) { v1.erase(it); it; } vectorint::iterator it1 v1.begin(); while (it1 ! v1.end()) { if (*it1 5) { v1.insert(it1, 8); } it1; } return 0; }为了避免迭代器失效我们只需要对迭代器重新赋值即可因为insert和erase函数都会返回下一个位置的迭代器所以重新获取一个有效的迭代器就行3.vector的模拟实现先构造一个命名空间防止和系统库的vector发生冲突写出vector的基本结构因为传入的数据类型比较复杂所以用迭代器去封装指针然后让编译器自动识别传入数据的类型即可所以成员变量有三个开始位置的迭代器元素末尾的迭代器以及空间迭代器#pragma once #includeiostream #includeassert.h #includestdbool.h namespace Vec { templateclass T class vector { typedef T* iterator; typedef const T* const_iterator; public: //成员函数 private: iterator _start nullptr; iterator _finish nullptr; iterator _endofstorage nullptr; //给上缺省值避免初始化的问题 }; }3.1构造函数和析构函数无参构造默认给三个迭代器赋值为nullptr如果不写可以用vector()default的方式让编译器声明默认构造对于拷贝构造我们先使用reverse函数为容器开辟相同大小的空间然后使用范围for遍历需要拷贝的vector依次尾插元素即可但是之前模拟实现string的时候使用memcpy进行拷贝为什么这里缺不使用因为memcpy如果拷贝字符串是浅拷贝如果内部数据是string类型那么拷贝的时候只是指向了同一块空间而不是额外开空间所以这里使用遍历尾插的方式拷贝第三种方法新创建一个模板用于兼容任意容器的迭代器只要传入对应的迭代器然后让迭代器一边往后走一边将遍历到的元素尾插进vector析构函数比较简单如果_start不为空指针那么就删除该空间并将三个迭代器置为空vector()//构造函数 : _start(nullptr) , _finish(nullptr) , _endofstorage(nullptr) {} vector() default; //强制编译器生成默认构造 vector(const vectorT v) { reverse(v.capacity()); for (auto e : v) { push_back(e); } } templateclass InputIterator //兼容任意容器的迭代器 vector(InputIterator start, InputIterator finish) { while (start ! finish) { push_back(*start); start; } } ~vector() { if (_start) { delete[] _start; _start _finish _endstorage nullptr; } //指针不为空才需要释放空间 }3.2头尾迭代器写法很简单只要返回成员变量中的_start和_finish即可分为普通迭代器和const迭代器const迭代器指向的内容不可更改iterator begin() { return _start; } iterator end() { return _finish; } const_iterator begin() const{ return _start; } const_iterator end() const { return _finish; }3.3空间管理函数因为迭代器底层使用了指针所以可以通过指针的相减返回空间大小和元素个数reserve函数当传入的n大于当前空间的时候会进行扩容的操作此处使用2倍扩容如果_start不为空那么要先进行赋值然后释放原空间注意原空间的元素个数要提前存储不然后续使用size函数给_finish赋值就会使用新的_start而不是原来的会产生报错resize函数需要用元素填充vector这里使用T()是为了通用性如果是内置类型不做特殊处理如果是其他类那么会调用其默认构造函数进行初始化如果需要开空间可以复用reserve函数如果不需要开空间那么直接移动末尾指针_finish即可empty函数用于判断vector是否为空那么只要判断size是否为0size_t capacity() { return _endofstorage - _start; } size_t size() { return _finish - _start; } void reserve(size_t n) { //对空间大小进行调整 //一般只进行扩容不进行缩容 //所以传入的n如果比较小是不会进行操作的 if (n capacity()) { T* tmp new T[n]; size_t old_size size();//先存储旧空间的元素个数 if(_start){ for (size_t i 0; i old_size; i) { tmp[i] _start[i];//依次赋值 } delete[] _start; //如果原来有内存空间 //先进行释放 } _start tmp; _finish _start old_size; //如果此处不使用old_size而是size() //size()中的_start用的是更新后的_finish还是之前的 _endofstorage _start n; } } void resize(size_t n, T val T()) { //对元素个数进行调整 //如果小于原来元素个数直接把后续元素删除 //如果大于原来元素个数先使用reserve保证有足够空间 //然后从原末尾开始依次插入val直到扩充到新的元素个数 if (n size()) { reserve(n); while (_finish ! _start n) { *_finish val; _finish; } } else { _finish _start n; } } bool empty() { return size() 0; }3.4增删查改函数push_back尾插函数如果空间不足那么需要进行扩容然后在末尾处加上新元素并移动_finishpop_back尾删函数要先判断是否存在元素可以删除然后移动_finishswap函数直接调用库里的swap函数对三个成员变量进行交换clear函数清除元素直接令_finish_start即可注意并不是把空间一起清除了insert插入函数使用迭代器指示位置同样先判断是否需要扩容然后从末尾依次移动元素给指定位置腾出一个空间然后插入指定元素并移动_finisherase函数判断迭代器位置是否在_start和_finish之间否则视为非法操作从指定位置开始依次往前赋值覆盖指定位置的元素然后将_finish--void push_back(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; } void swap(vectorT v) { //引用减少拷贝 //但是为了不修改被拷贝的vector //调用该函数时先将被拷贝的vector拷贝一份 //再进行使用就可以达到赋值的效果 std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_endofstorage, v._endofdstorage); } void clear() { _finish _start; } iterator insert(iterator pos, const T x) { assert(pos _finish); assert(pos _start); if (_finish _endofstorage) { size_t newcapacity (capacity() 0) ? 4 : 2 * capacity(); reserve(newcapacity); } iterator end _finish 1; while (end ! pos) { *end *(end - 1); end--; } *pos x; _finish 1; return pos; } iterator erase(iterator pos) { assert(pos _finish); assert(pos _start); while (pos ! _finish) { *pos *(pos 1); pos; } --_finish; return pos; }3.5补充写完swap函数后对于赋值重载就可以写的很简单使用传值调用传入的vector所以形参不会改变实参所以直接将形参传入swap中然后交换当前类和v的成员变量还有对于[ ]的两种重载因为底层使用指针所以直接用_start[pos]即可访问对应数据vectorT operator(vectorT v) { //因为形参v的成员要发生改变不加const swap(v); return *this; } T operator[](size_t pos) { assert(pos size()); return _start[pos]; } const T operator[](size_t pos) const { assert(pos size()); return _start[pos]; }