目录简单提一下模板函数模板的原理类模板Vector初始化析构迭代器const与非const其他短小的成员函数reserve有问题吗改正push_backoperator[]访问元素const与非constinsert这里会出现一个问题迭代器失效如何改正我们再想想还会有什么问题吗怎么办---加返回值erase看这样一个场景给出一串数字要求删除奇数会有什么问题怎么改如何从根本上解决resize内置类型也会调用构造函数吗拷贝构造赋值先实现清除操作再实现赋值操作迭代器区间构造还有最后一个小问题修改reserve那该怎么改呢总结简单提一下模板为什么要有模板解决 代码复用 和 泛型编程我们看以下三种交换函数如果没有模板需要为不同类型的交换函数各写一个版本void Swap(int n1, int n2) { int temp n1; n1 n2; n2 temp; } void Swap(double n1, double n2) { double temp n1; n1 n2; n2 temp; } void Swap(char n1, char n2) { char temp n1; n1 n2; n2 temp; }且模板允许我们定义泛型容器像栈队列等数据结构逻辑与存储的数据类型无关可以定义泛型容器无需为每种类型进行重复设计。泛型编程的两种实现函数模板和类模板函数模板类似刚刚的swap函数定义一个通用的函数框架适配多种数据类型//函数模板定义 templatetypename T void Swap(T n1, T n2) T temp n1; n1 n2; n2 temp; }格式template typename T1,typename T2... 返回值类型 函数名 ( 参数列表 ) {}函数模板的原理模板本身是一个蓝图只有在被使用时编译器才会为特定类型创建具体的函数这个过程叫做函数模板的实例化。templatetypename T void Swap(T n1, T n2) { T temp n1; n1 n2; n2 temp; } int main() { int a 1, b 2; Swap(a, b); double c 1.0, d 2.0; Swap(c, d); return 0; }这个过程是隐式实例化编译器会根据使用场景自动推导类型参数并进行函数模板实例化。如ab是int类型自动识别T为int实例出Swapint单独处理int类型的代码注意以下场景templatetypename T void Add(const T n1,const T n2) { return n1 n2; } int main() { int a 1; double b 2.0; Add(a, b); return 0; } //在编译器阶段编译器看到隐式类型实例化会自动推导T的类型 //a为intb为double但只有一个T类型无法确定是int还是double因此出现两中解决方法1.用户强制类型转换Add(a,intb)。2.显式实例化Addint(a,b)T被直接实例化成int显式实例化手动指定参数类型函数名模板参数类型ab类型不匹配编译器会进行隐式类型转换无法转换会编译报错注意模板和现成函数先走现成函数因为模板只是蓝图类模板定义一个通用的类框架只是存储的数据类型不同比如栈类能存储intcouble等不同类型//类模板 templatetypename T class Stack { public: Stack(size_t capacity 4) { _arr new T[capacity]; _size 0; _capacity capacity; } private: T* _arr; size_t _size; size_t _capacity; };格式templatetypename T1,typename T2... class 类模板名 { //成员 }类模板的使用必须是显式实例化因为类模板创建对象时Stack sk编译器无法知道sk存储的是什么类型必须显示Stackint sk;因此类模板实例化需要在类模板后跟类模板的名字Stack不是真正的类型加类型Stackdoubel才是。模板声明和定义不支持分离在两个文件里会链接错误后面会讲。Vectorvector的底层就是可以动态申请资源的顺序表之前的数据结构实现过相关的顺序表功能这里的成员变量只不过将_size,_capacity改成了指针vector容器存储的数据形式可以不同类型intdouble因此可以定义一个vector模板namespace sxm { template typename T class vector { public: typedef T* iterator; private: iterator _start; iterator _finish; iterator _end_of_storage; }; }_start指向数组中首元素_finish指向数组中最后一个有效元素1_end_of_storage指向数组空间末尾初始化直接给类内成员变量一个默认的nullptrtemplate typename T class vector { public: typedef T* iterator; private: iterator _start nullptr; iterator _finish nullptr; iterator _end_of_storage nullptr; };析构~vectorT() { if(_start!nullptr) { delete[] _start; _start _finish _end_of_storage nullptr; } }迭代器begin直接返回一个迭代器指向第一个元素end直接返回 一个past-the-endelement 迭代器不指向任何元素typedef T* iterator; iterator begin() { return _start; } iterator end() { return _finish; }可以修改元素(T*)vectorint v {1, 2, 3}; vectorint::iterator it v.begin(); *it 10; // 合法可以修改元素const与非const如果一个vector对象是被const修饰的返回第一个元素时不能修改const T*那就要引入const迭代器typedef const T* const_iterator; const_iterator begin()const { return _start; } const_iterator end()const { return _finish; }如const vectorint c {4, 5, 6}; // const 容器 vectorint::const_iterator cit c.begin(); // *cit 20; // 编译错误不能修改元素只读其他短小的成员函数size_t size()const { return _finish - _start;//return the number of elements in the vector } size_t capacity()const { return _end_of_storage - _start;//return the size of the storage space } bool empty()const { return _start _finish;//returns whether the vector is empty }reservereserve针对capacity即最多容纳数元素的个数调整vector容量到n如果ncapacity什么也不做如果ncapacity将进行扩容capacity到nvoid reserve(size_t n) { if (n capacity()) { T* temp new T[n];//已经初始化好的空间可以直接赋值 memcpy(temp, _start, sizeof(T) * size()); delete[] _start; _start temp; _finish _start size(); _end_of_storage _start n;//temp临时变量出作用域后自动调用析构函数 } }有问题吗但是我接下来进行数据插入发现出现了问题_finishnullptr;这也是因为size()出现的位置不对_start已经更新但_finish没有更新这样求得的size()就不是有效的数据个数_finish也就不对了改正在没有更新_start之前求得有效数据个数size()然后将_finish更新void reserve(size_t n) { if (n capacity()) { size_t old_size size(); T* temp new T[n]; memcpy(temp, _start, sizeof(T) * size()); delete[] _start; _start temp; _finish _start old_size; _end_of_storage _start n; } }push_back增加一个新的元素到vector末尾void push_back(const T x)//add a new element at the end of the vector, { if (_finish _end_of_storage) { reserve(_end_of_storage 0 ? 4 : 2 * capacity()); } (*_finish) x;//拷贝赋值如果是右值版本T x可以调用移动赋值重载(*_finish)std::move(x) _finish; }operator[]访问元素T operator[](size_t i)//return a reference to the element at position i { assert(i size()); return _start[i];//返回可以修改的引用 } T operator[](size_t i)const { assert(i size()); return _start[i];//不能修改 }const与非const同end(),begin()类型需要const和非const如vectorint v {1, 2, 3}; v[0]10; // 正确v 是非 const 的 const vectorint cv {4, 5, 6}; // cv[0] 20; // 错误编译报错const 容器的元素不能修改insert本质上通过两移动指针指向的元素进行移动和插入数据void insert (iterator position, const T val);pos是vector中插入新元素位置处的指针val待插入元素的值void insert(iterator pos,T val) { if (_finish _end_of_storage) { reserve(_finish 0 ? 4 : 2 * capacity()); } iterator end _finish - 1;//endpos是指针,指向最后一个有效元素 while (end pos) { *(end 1) (*end); end--; } *pos val; _finish; }这里会出现一个问题迭代器失效当进行insert操作时由于空间不够会进行扩容此时会开辟一段新的空间将旧元素复制到新空间释放旧内存此时所有指向旧内存的迭代器都会失效因为它们仍然指向旧内存。如何改正将pos指向旧内存的地址更新到新内存的地址利用已经更新的_startlenvoid insert(iterator pos, const T val) { if (_finish _end_of_storage) { size_t len pos - _start; reserve(_finish 0 ? 4 : 2 * capacity());//_start已经更新 pos _start len;//pos指向新空间 } iterator end _finish - 1;//pos是指针,指向最后一个有效元素 while (end pos) { *(end 1) (*end); end--; } *pos val; _finish; }我们再想想还会有什么问题吗如果这样调用可以吗v.insert(it, 50); (*it) * 10;nononopos是副本形参进行扩容时将旧空间释放it指向的空间但由于pos是形参即使pos已经更新了实参it仍不会指向新的内存空间it就失效了野指针不要访问可以加引用吗iterator pos不可以因为不支持v.insert(v.begin() 2, 20);这种写法了。因为v.begin() 2返回的是临时变量表达式计算的中间结果具有常性。不能给给到普通的引用非const因为权限会放大。那可以将普通的引用改为const引用来接收吗const iterator pos不可以因为pospos _start len;就不能改变了怎么办---加返回值如果要访问的话需要重新获取新的内存空间此时我们可以返回新插入元素的内存空间iteratorT*it接收后就可以访问了iterator insert(iterator pos, const T val) { if (_finish _end_of_storage) { size_t len pos - _start; reserve(_finish 0 ? 4 : 2 * capacity());//_start已经更新 pos _start len;//pos指向新空间 } iterator end _finish - 1;//pos是指针,指向最后一个有效元素 while (end pos) { *(end 1) (*end); end--; } *pos val; _finish; return pos; }这样就可以修改vector中的元素了it v.insert(it, 40);//更新一下it (*it) * 10;erasevoid erase(iterator pos)//remove from the vector a single element { iterator it pos 1; while (it ! end()) { *(it - 1) *it;//*(end()),无效元素 it; } _finish--; } //void erase(iterator pos)//remove from the vector a single element //{ // while (pos end()) // { // *pos *(pos 1);//*(end()),无效元素 // pos; // } // _finish--; //}看这样一个场景给出一串数字要求删除奇数会有什么问题auto v1 v.begin(); while (v1 ! v.end()) { if (*v1 % 2 0) { v.erase(v1); } v1; }第一个坑it已经挪动将原本要删除的地方覆盖消消乐此时it就已经是下一个要判断的数据了但是it将下一个带判断的元素跳过.第二个坑当最后一个元素是偶数时最后一个元素1_finish_finish--此时_finish指向最后一个元素接下来v1此时v1指向最后一个元素的下一个元素。至此v1的下一个元素!_finish一直在移动。怎么改每次只能走一步如果是偶数调用erase删除后不必v1因为数据已经挪动此时v1指向的元素就是下一个元素。如果是奇数v1。auto v1 v.begin(); while (v1 ! v.end()) { if (*v1 % 2 0) { v.erase(v1); } else { v1; } }以上也称为迭代器失效元素被删除pos指向的位置被覆盖。如vectorint v {1,2,3,4}; auto it v.begin() 1; // 指向2 v.erase(it); // 删除2后it已失效 // 此时用户不知道下一个有效元素是3继续使用it会导致未定义行为 it; // 错误it已失效如何从根本上解决在此基础上如果返回 “被删除元素的下一个元素” 的迭代器可以解决上述问题。iterator erase(iterator pos)//return an iterator pointing to the new location of the element that followed the last element erased { iterator it pos 1; while (it ! end()) { *(it - 1) *it; it; } _finish--; return pos;// 此时pos已指向原pos1的元素下一个有效位置 }auto v1 v.begin(); while (v1 ! v.end()) { if (*v1 % 2 0) { v1 v.erase(v1); } else { v1;//偶数走过了erase不必,返回值已经是下一个位置间接 } }迭代器失效如果要访问的话一定要更新resize针对vector中有效的元素调整为n个元素如果nsize将删除多余的元素如果nsize将在尾部添加新增加的元素如果capacity不够会扩容void resize(size_t n,const T valT()) { if (n size())//删除多余的元素 { _finish _start n; } else { reserve(n); while(_finish _start n)//将指针_start向后移动 n 个元素的位置 { *_finish val; _finish; } } }如果调用resize时不提供第二个参数val会默认初始化为T()类型的值内置类型也会调用构造函数吗T valT()意思是用默认构造构造了一个匿名对象再拷贝构造。为什么不给0T val0因为T是什么类型我们不知道。如果是stringvector等类类型会调用无参的那个构造。如果T是intdouble等内置类型没有默认构造函数的概念编译器会处理为了兼容这些场景内置类型也有了这些概念int iint();int iint(1);int j(2);等会生成零值int()是 0 double() 是 0.0。拷贝构造默认是浅拷贝我们要手动实现深拷贝如v1v3先对v1进行开空间然后将v3中的元素添加到v1中vector(const vectorT v) { if (this ! v) { reserve(v.size());//为v1开空间 for (const auto e : v) { push_back(e); } } }为什么这里是auto?这里e是v的别名减少不必要的临时拷贝直接通过引用操作v中的元素。且const引用确保不会改变原vector中的元素。但此时如果我尝试vectorint v;编译会报错因为虽然类内成员有默认值如_startnullptr但是类内默认值需要通过构造函数的初始化阶段才能生效当成员变量在构造函数的初始化列表中 未被显示初始化时会自动使用这个默认值。初始化列表优先于函数体内赋值但是默认构造生成的原则是当没有自己定义构造函数时编译器会自动生成一个无参的默认构造但当自己定义了构造函数时如当前的拷贝构造编译器就不会生成默认构造。这意味着当我们自己写了拷贝构造而没手动定义默认构造时就无法通过vectorint v;这样的代码创建对象因为找不到构造函数。接下来我们手动定义构造函数vector() {}也可以这样定义意思是显示要求编译器生成默认构造vector() default;赋值v1v3两个对象已经创建不用为v1开辟空间可以先清除v1中的内容再将v2中的内容给给到v1先实现清除操作void clear() { _start _finish; }再实现赋值操作vectorT operator(const vectorT v)// { if(this! v) { clear();//清除v1内容 reserve(v.size());//提前扩容防止push_back频繁扩容导致效率低 for (auto e : v) { push_back(e); } return *this; } }这里的返回值为什么不用传值返回 vectorT operator呢传值返回会产生一个临时副本会调用拷贝构造效率低且逻辑不直观如,v1v2v3当返回引用vectorT时v2 v3 执行后返回的是 v2 本身的引用因此 v1 ( v2 v3 ) 等价于 v1 v2 正确将 v2 的值赋给 v1 。注意不要返回局部域的引用当返回值vectorT时v2 v3 执行后返回的是通过拷贝构造得到的 v2 的临时副本因此 v1 ( v2 v3 )等价于 v1 临时副本最终 v1 复制的是临时副本的值而非 v2 的值。迭代器区间构造//可以在类模板中继续定义函数模板为了突破类模板参数的限制如vectorinttemplate typename InputIterator vector(InputIterator first, InputIterator last);firstlast是迭代器拷贝[first,last)之间的数据到新的vector中这里使用模板参数 InputIterator 而非具体迭代器类型iterator(T*)是为了支持任意输入迭代器包括其他容器的迭代器、原生数组指针等如int arr[] {1, 2, 3, 4}; vectorint v1(arr, arr 4); // 用数组指针迭代器构造 vectorint v2 {10, 20, 30}; vectorint v3(v2.begin(), v2.end()); // 用其他vector的迭代器构造可以处理指向intdouble等类型的迭代器只要能转化为Ttemplatetypename IntputIterator vector(IntputIterator first, IntputIterator last) { while (first ! last) { push_back(*first); first; } }还有最后一个小问题修改reserve如果vector中的元素是string类型在vector中插入string类类型的元素会出现BUG新内存 temp 中的 string 对象与旧内存 _start 中的 string 对象共享同一个字符数组指针因为只复制了指针地址。那该怎么改呢不用memcpy而是利用元素赋值赋值运算符实现深拷贝//赋值来进行深拷贝 void reserve(size_t n) { if (n capacity()) { size_t old_size size(); T* temp new T[n]; //memcpy(temp, _start, sizeof(T) * size()); for (size_t i 0; i old_size; i) { temp[i] _start[i]; } delete[] _start; _start temp; _finish _start old_size; _end_of_storage _start n; } }总结memcpy 仅适用于无指针成员的类型对于包含指针或动态资源的类型如string必须利用元素自身的拷贝构造 / 赋值运算符实现深拷贝否则会出现对野指针解引用、重复释放等错误。vectorvectorint