【C++】list迭代器的深度剖析及模拟实现（感受类封装，类和对象的思想） |
您所在的位置：网站首页 › 内置类型和自定义类型 › 【C++】list迭代器的深度剖析及模拟实现（感受类封装，类和对象的思想） |
|
一、通过list迭代器来感受类和对象以及类封装的思想1.迭代器的特征和本质是什么？（两大特征：类的内嵌类型，行为像指针。本质：内置类型定义的变量或自定义类型实例化的对象） 1. 从迭代器的上层角度来看，vector和list的迭代器的使用没有差别，迭代器的begin和end返回的是左闭右开的区间位置[ begin(),end() )。 2. 迭代器的一大特征就是类的内嵌类型，在使用时要指定迭代器属于的类域，是哪个容器的迭代器就属于哪个容器的类域。在类里面定义内嵌类型一般有两种方式，一种是typedef，另一种就是内部类，C++不太喜欢用内部类这种方式，可能是因为代码的维护性较低，所以弃用了内部类这样的方式。 内嵌类型迭代器基本都是在类里面typedef出来的，C++喜欢这样内嵌类型的定义方式。 迭代器的另一大特征就是像指针一样的东西，对于使用者来讲不必关心底层实现细节，将迭代器当作指针一样使用即可。 list迭代器遍历时，while循环的判断条件只能是!=，不能是的成员选择，你都不用担心，在STL源码里面这些操作都会被实现，迭代器将所有负责的操作都封装起来，默默替你承受着一切。 5. 前面是站在上层使用和底层实现的角度看待迭代器，再以物理角度（内存中实际存储所占的空间大小）看待一下迭代器吧，vector的迭代器是4个字节，因为他是原生指针直接指向变量_data，解引用获得_data的数据内容。 list的迭代器也是4个字节，因为自定义类型迭代器实例化出来的对象的成员变量只有一个结构体指针，结构体指针大小也是4个字节，所以it对象和vector的迭代器大小相同均为4字节。 void test_set1() { set s; s.insert(3); s.insert(2); s.insert(1); s.insert(5); set::iterator it = s.begin(); while (it != s.end()) { cout _prev = tail; //newnode->_next = _head; //_head->_prev = newnode; insert(end(), x); } void push_front(const T& x) { insert(begin(), x); } void pop_front() { erase(begin()); } void pop_back() { erase(--end());//调用迭代器对象的operator--运算符重载 } iterator insert(iterator pos, const T& x) { node* newnode = new node(x);//调用node类的带参构造 node* cur = pos._pnode; //通过迭代器对象pos拿到当前结点的结构体指针，pos所属类是struct，则成员是公有 node* prev = cur->_prev; //拿到前一个和当前位置的node指针 //prev newnode cur prev->_next = newnode; newnode->_prev = prev; newnode->_next = cur; cur->_prev = newnode; ++_size; return iterator(newnode);//返回插入结点的迭代器对象 } iterator erase(iterator pos) { //assert(pos != _head);//一个是指针，一个是迭代器类型，这里类型不匹配，选择用end()来进行比较 assert(pos != iterator(_head));//迭代器位置不能是哨兵卫结点 //assert(pos != end());//上下两种assert方式都可以 //拿到当前位置的前一个和后一个位置的结构体指针 node* prev = pos._pnode->_prev; node* next = pos._pnode->_next; prev->_next = next; next->_prev = prev; delete pos._pnode; --_size; return iterator(next);//返回删除位置的下一个位置的迭代器，这个迭代器现在是一个对象。vector那里是原生指针。 }2.list的拷贝构造、赋值重载、析构函数1. 如果我们不写拷贝构造，那么链表就会发生浅拷贝，但如果此时我们没写析构函数，则程序运行起来是不会报错的，但实际程序已经有问题了，因为发生了内存泄露。 首先链表浅拷贝时，会直接将哨兵卫结点的地址拷贝给新链表的哨兵卫结点地址_head，此时两个链表头结点指针指向的是同一块儿空间，不写析构函数，编译器默认生成的析构函数对内置类型不会处理，所以堆上开辟的空间就不会处理，这就产生了内存泄露，只能等待进程结束，操作系统回收对应进程资源后，堆上申请的空间才会被释放掉。 2. 这也从另一方面体现了内存泄露的危害所在，因为一旦程序产生了内存泄露，编译器是不会报错的，所以你以为你的程序好好的跑起来了，感觉没有什么bug产生，但你的程序其实已经产生了问题，那就是内存泄露。 3. 只要写了正确的析构函数，浅拷贝就肯定会出现问题了，因为同一块空间被析构两次，第二次就会变成野指针的越界访问，这个时候程序就会报错。 4. clear()用于释放除哨兵卫结点之外的其他所有结点资源，析构函数用于释放链表所有的结点资源，包括哨兵卫结点。 clear再实现时有两种写法，一种就是定义两个结构体指针，一个指向头结点，一个指向下一个位置的结点，然后依次向后遍历释放结点资源。 另一种写法就是利用迭代器和erase，进行代码复用，遍历迭代器直到开区间end()就结束迭代器的遍历，然后依次调用erase释放结点，erase之后迭代器会失效，所以我们要用erase的返回值来更新迭代器，但需要注意的是erase更新迭代器之后，迭代器不用++了，否则会出现部分结点未释放的问题，又是内存泄露，因为erase的返回值就已经更新了，你再++就相当于更新两次，则释放时会漏掉一个结点。 析构函数实现时，我们代码复用clear将除哨兵卫结点之外的其他结点释放，最后再释放哨兵卫结点即可。 5. 拷贝构造的传统写法就是自己先初始化好哨兵卫结点，然后用迭代器或范围for（本质就是迭代器）遍历链表，将遍历到的每一个结点的数据都尾插到链表里面去，范围for就是将遍历到的迭代器进行解引用然后拷贝构造给auto推导的变量，值得注意的是，在auto变量这里，推荐使用auto的引用，因为数据类型是泛型，内置类型用个拷贝构造还好说，但如果是自定义类型，则拷贝构造的代价太大，所以推荐auto用引用。 现代写法还是找打工人，对于拷贝构造来说，打工人还是迭代器为参数的构造函数，所以除无参的构造函数外，我们再多实现一个参数为迭代器区间的构造函数，让这个构造函数给我们打工，构造出一个临时list对象，最后再调用swap交换这个临时list对象和被拷贝构造对象即可，等到离开函数栈帧tmp对象就会被销毁。 6. 赋值重载的传统写法依旧是用范围for遍历list的数据，然后将遍历到的数据都尾插到被赋值链表里面，但是尾插数据之前需要clear一下，将链表里面原有数据对应的结点释放掉，然后再进行遍历到的元素的push_back，另外为了防止自己给自己赋值我们还调用了一下最最不常用的取地址重载函数，保证两个链表对象是不相同的。 现代写法也是找打工人，对于赋值重载来说，打工人就是拷贝构造，我们利用传值拷贝的形参临时对象和被赋值对象直接进行swap，道理相同形参临时对象在函数栈帧销毁时会跟着一起被析构掉。 7. swap的实现也比较简单，直接交换两个链表头结点指针即可。 size()接口返回链表结点的个数，如果遍历链表计数结点个数来实现size()的话，在size()频繁调用的情况下，效率就会降下来，所以我们用空间换时间，牺牲空间来换取效率的提升，增加一个list成员变量_size，表示链表当前节点个数，插入结点就++_size，删除结点就–_size，调用size()接口时，直接返回成员变量_size的大小即可。 list() { empty_initialize(); } template list(InputIterator first, InputIterator last)//迭代器区间为参数的默认构造 { empty_initialize();//如果不调用初始化接口，则被拷贝对象的_head是一个野指针，交换后析构会出问题。 while (first != last) { push_back(*first); ++first; } } void swap(list& lt) { std::swap(_head, lt._head); std::swap(_size, lt._size); } // lt2(lt1) //list(const list& lt)//传统写法 //{ // empty_initialize();//初始化被拷贝链表，先搞一个头结点出来。 // //下面的范围for会傻瓜式的替换为const迭代器 // for (auto& e : lt)//如果T是自定义类型，则会调用该类的拷贝构造，代价会很大，为了提高效率，这里用引用。 // //范围for本质就是取容器里面的每一个迭代器，然后解引用迭代器赋值给元素e，如果T是string类型拷贝的字节会很多 // { // //如果已知auto的类型是int，char等，可以不用引用，但如果是泛型或自定义类型，就应该用引用减少拷贝的消耗 // push_back(e);//e是数据不是结点，解引用迭代器拿到的是数据，然后将数据尾插到链表里 // } //} list(const list& lt)//拷贝构造的现代写法 //:_head(nullptr)//不能用空指针初始化_head，否则在析构时，进入到clear里面，begin()会访问空指针，造成越界访问 { empty_initialize(); list tmp(lt.begin(), lt.end());//交换两个指向头结点的结构体指针，就完成了链表的交换 swap(tmp); } list& operator=(list lt)//现代写法 { swap(lt); return *this;//返回list类的对象 } // lt1=lt2 //list& operator=(const list& lt)//传统写法 //{ // if (this != )//对象的取地址运算符重载 // { // //将this对象的数据先清掉，但不要清掉哨兵卫的头结点，就算你清了，等会儿还得empty_initialize // clear(); // for (auto& e : lt)//这里也用auto引用 // { // push_back(e); // } // return *this; // } //} void clear()//clear不清除头结点 { //C语言实现的方式：定义下一个节点的地址cur，删除cur->prev，++cur，cur->prev!=end()； //C++可以直接利用迭代器和erase进行删除。迭代器是真牛啊 iterator it = begin(); while (it != end()) { it = erase(it);//不更新it，会出现迭代器失效的问题。 //++it;//再++it的位置就不对了，clear无法完全删除除头之外的节点，erase会自动返回删除位置的下一个位置的迭代器 } } size_t size()const//提供const版本，这样const对象和非const对象都可以调用 { //如果搞一个迭代器循环，计数器记录到底有多少个结点，然后返回计数器大小。 //但如果频繁调用size()的话，则效率就会降下来。所以可以想到以空间换时间，多在list里面加一个成员变量 return _size; } bool empty()const { return _size == 0;//两个条件都可以 //return _head == _head->_next; } ~list()//析构函数清除头结点 { //如果显示写了析构函数会存在野指针访问的问题，没写则依靠不处理内置类型的默认析构来析构对象。 //如果内置类型涉及堆空间的资源申请，则调用编译器的默认析构会导致内存泄露的问题，但内存泄露又不会报错， //这真是令人害怕的事情！ clear(); delete _head; _head = nullptr; }三、const迭代器的实现1.const迭代器的错误实现（const修饰了迭代器本身而不是迭代器指向的内容）1. 在迭代器前面加个const并没有完成const迭代器的实现，因为我们所说的const迭代器指的是解引用迭代器之后的内容不能被修改，但迭代器本身也可以理解为指针本身是可以被修改的，因为迭代器需要++或 - -来移动自己的位置，就像指针一样能够++或 - -来移动自己的位置。所以你在迭代器前面加个const表示的是迭代器本身不能被修改，而不是解引用迭代器后的内容不能被修改。 // const T* p1; // T* const p2; //正确的const迭代器类似于p1的行为，解引用迭代器后的内容不能被修改，但迭代器本身可以被修改，因为无论是const还是非const迭代器都要++或-- void print_list(const list& lt) { //普通迭代器前面加个const肯定是不行的，这不符合const迭代器的意义。 const list::iterator cit = lt.begin(); //这样写的话，const修饰的是迭代器本身，迭代器不能++或--了，我们要的是const修饰迭代器指向的内容 list::const_iterator it = lt.begin(); while (it != lt.end()) { //(*it) += 2;//实现const迭代器之后，这里就不能写了 cout _next; return *this; } __list_iterator& operator--() { _pnode = _pnode->_prev; return *this; }2.重新构建一个__list_const_iterator的类（菜鸟的做法）1. 实现const迭代器的一种方式就是重新构建一个类，类里面原有成员函数都不变，仅仅是将类名做出修改，然后我们把解引用函数的返回值修改成常引用，在使用const_iterator迭代器类型的时候，如果你解引用迭代器则直接调用__list_const_iterator类里面的返回常引用的重载函数。 这样就可以实现解引用const_iterator后的内容不可被修改了，因为我们重新构建了一个类，将类里面解引用函数的返回值重新修改为常引用。 2. 可能会有人有疑问，为什么我们不能在原来的那个类里面重载一个返回值为常引用的解引用函数呢？答案是不可以，因为返回值不同无法构成重载函数，所以这两个不同返回值的函数不能在同一个类里面出现，这也是为什么我们重建了一个类，专门搞了一个返回值为常引用的解引用函数。 template struct __list_const_iterator//将迭代器进行了封装，以便于解引用，++，--等运算符依旧对迭代器适用 { //迭代器的封装完美体现了面向对象封装的思想，以及类和对象强大的力量。一个成员变量仅仅是结构体指针的迭代器对象 //可以通过运算符重载和类封装的思想，将迭代器的功能实现的滴水不漏，隐藏底层实现的机制。 typedef list_node node; node* _pnode; __list_const_iterator(node* p) :_pnode(p) {} const T& operator*() { return _pnode->_data;//返回变量_data的引用，表示数据可以被读或修改，_data的类型是T } __list_const_iterator& operator++()//++改变的就是成员变量_pnode，所以不能用const修饰此函数 { _pnode = _pnode->_next; return *this; } __list_const_iterator& operator--() { _pnode = _pnode->_prev; return *this; } bool operator!=(const __list_const_iterator& it)const//比较两个迭代器是否相等，实际比较的是list_node的地址是否相等 { return _pnode != it._pnode; } }; template class list { typedef list_node node; public: typedef __list_iterator iterator;//iterator是类模板的typedef，模板也是类型，只不过还没有实例化 typedef __list_const_iterator const_iterator; const_iterator begin()const//const修饰*this，代表list对象的成员变量不可被修改，用于const的list对象调用。 { return const_iterator(_head->_next); } const_iterator end()const { return const_iterator(_head); } iterator begin() { return iterator(_head->_next); } iterator end() { return iterator(_head); } ……………………省略 }3.增加模板参数，根据类模板参数的不同，实例化出不同的类（大佬的做法）1. 上面重建一个类，这样代码冗余的做法大佬是要被笑话的，尤其STL还是开源的代码，大佬其实是通过增加模板参数，在传参数时，根据参数类型的不同实例化出不同的类。 2. 例如下面代码，用const_iterator时，就是用第二个模板参数为const T&的类模板，等T类型确定时，就会实例化出具体的类，当用iterator时，我们就用第二个模板参数为T&的类模板，等T类型确定时，又会实例化出另一个不同的类。 3. 下面是SGI版本源码，可以看到iterator和const_iterator对应的类模板的第二个参数的不同，一个是普通引用，一个是常引用。第三个模板参数T*在下面的部分会讲。 // typedef __list_iterator iterator; // typedef __list_iterator const_iterator; template struct __list_iterator { typedef list_node node; typedef __list_iterator Self; node* _pnode; __list_iterator(node* p) :_pnode(p) {} Ref operator*() { return _pnode->_data;//返回的是数据类型，所以用Ref } Self& operator++() { _pnode = _pnode->_next; return *this; //返回的是迭代器对象，所以用该迭代器对应的类的类型，实际就是__list_iterator //只是将__list_iterator typedef为 Self } Self& operator--() { _pnode = _pnode->_prev; return *this; } bool operator!=(const Self& it) { return _pnode != it._pnode; } }; template class list { typedef list_node node; public: typedef __list_iterator iterator; //typedef __list_const_iterator const_iterator; typedef __list_iterator const_iterator; const_iterator begin() const { return const_iterator(_head->_next); } const_iterator end() const { return const_iterator(_head); } ……………………省略 }4.类名和类型的区别1. list是类型，list是类名。 构造函数的函数名和类名相同。 在类外面不能用类名代表类型，在类里面可以用类名代表类型，这算C++的一个坑，但非常不建议这么用，如果在类里面用类名代表类型，这很容易把自己搞晕。 2. 但我们还是用最标准的写法，无论是在类里面还是在类外面，将类名和类型严格区分开来。 四、实现迭代器 + →的访问方式（像结构体指针 + →一样的行为）1.迭代器指向对象为结构体时，编译器对→的特殊处理（省略一个箭头，提升代码可读性）1. 当list存的是结构体类型Pos时，直接打印解引用迭代器后的值就会出现问题，因为解引用迭代器后拿到的是Pos类的对象，所以如果想要打印对象的值，我们可以重载Pos类的流插入运算符来实现，如果Pos类的成员变量是私有的，我们也可以用友元函数来解决。 2. 如果不想用流插入，而是就想直接用解引用，那我们需要像下面这样去使用，利用对象.的运算符来进行成员选择。但下面这样的使用方式不怎么舒服，一般情况下如果有结构体指针，而不是结构体对象时，我们喜欢用结构体指针 + →的方式来访问结构体成员。 cout |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |