0
0

【C++初阶】STL详解（八）List的模拟实现

本专栏内容为：C++学习专栏，分为初阶和进阶两部分。 通过本专栏的深入学习，你可以了解并掌握C++。

💓博主csdn个人主页：小小unicorn
⏩专栏分类：C++
🚚代码仓库：小小unicorn的代码仓库🚚
🌹🌹🌹关注我带你学习编程知识

STL详解（八）

list的再认识：

在之前List的介绍与使用中，我们知道list容器是一个带头双向循环链表，那么我们在模拟实现中，能不能先证明一下List是否是一个双向循环链表呢？

我们参考一下stl中list的源码：
在这里插入图片描述
我们看到，在源码中，list中有一个__list_node的节点，我们将这个链表的节点定义打开发现定义两个指针next，prev.

再来看一下它的空初始化：
在这里插入图片描述
通过观察源码中list的初始化，确实是一个双向循环链表。

接下来。我们就来自己实现一下里面的接口函数。
注意：在模拟实现中，我们采取用与与源码中相同的命名风格。
为防止与库里面的list重复，我们模拟实现将定义在自己的命名空间中。

初始化与定义节点：

首先，我们需要定义三个类，并用摸版进行封装：分别是list，list的节点，以及迭代器：

list节点：

template<classT>structlist_node{
    T _data;
    list_node<T>* _next;
    list_node<T>* _prev;list_node(const T& x=T()):_data(x),_next(nullptr),_prev(nullptr){}};

list:

template<classT>classlist{typedef list_node<T> Node;public://空初始化：voidempty_init(){
        _head =new Node;
        _head->_next = _head;
        _head->_prev = _head;}//无参构造：list(){empty_init();}voidpush_Back(const T& x){
        Node* tail = _head->_prev;
        Node* newnode =newNode(x);

        tail->_next = newnode;
        newnode->_prev = tail;

        newnode->_next = _head;
        _head->_prev = newnode;}private:
    Node* _head;};

这里我们写的是无参构造，以及实现了一个尾插接口：
尾插双向链表实现已经再简单不过了：
在这里插入图片描述
现在我们测试一下：
在这里插入图片描述
现在还不能进行遍历，因此我们自己要实现一个迭代器：

迭代器实现：

那么这个迭代器我们要作为怎么实现呢？
我们可以先回顾一下，在vector中，我们实现迭代器就是实现原生指针。
在这里插入图片描述
在vector中，给it解引用就可以访问到里面的数据，但是链表不行，因为链表中空间不是连续的。
那么应该怎么实现呢？其实这个就和我们之前的日期类一样，在日期类中我们用运算符重载与封装实现了对日期类的++操作。而我们的迭代器也使这样实现的。

这里我们需要实现迭代器的！=，*与++操作：
在这里插入图片描述
我们先看一下库里面的操作：
在这里插入图片描述

构造：

看一下库里面的操作：
在这里插入图片描述
库里面用了一个节点的指针进行构造，这是因为：单参数的构造函数支持隐式类型转换。

所以我们的构造就可以这样写：

__list_iterator(Node* node):_node(node){}

++

实现迭代器++，就是指针往后走的过程，注意返回的是迭代器。我们可以将迭代器重命名一下：

typedef __list_iterator<T> self;

实现代码：

self&operator++(){
    _node = _node->_next;return*this;}

解引用：*

返回节点里面的数据即可：

T&operator*(){return _node->_data;}

！=

两个迭代器进行比较，实质两个指针比较。

//两个迭代器进行比较，两个指针比较booloperator!=(const self& s){return _node  !=  s._node;}

基本框架搭建：

这样基本上迭代器的基本架子就完成了：

typedef __list_iterator<T> iterator;
iterator begin(){return _head->_next;}
iterator end(){return _head;}

在list中定义一下迭代器。迭代器开始位置就是返回哨兵位头节点的下一个位置，结束位置就是返回哨兵位的地址。

测试一下：

voidtest_list1(){
        list<int> lt;
        lt.push_back(1);
        lt.push_back(2);
        lt.push_back(3);
        lt.push_back(4);
        lt.push_back(5);
        list<int>::iterator it = lt.begin();while(it != lt.end()){//*it += 20;
            cout <<*it <<" ";++it;}
        cout << endl;}

测试结果：
在这里插入图片描述
有了迭代器就有范围for：

for(auto e : lt){
    cout << e <<" ";}
cout << endl;

在这里插入图片描述
总结：其实会发现就是在模拟指针，但他的底层细节很大。所以迭代器体现了封装的强势之处。封装屏蔽底层差异和实现细节，提供统一的访问修改遍历方式。这样我们就不用关注他的底层是什么.
在这里插入图片描述

举个例子：

    set<int> s;
    s.insert(1);
    s.insert(3);
    s.insert(2);
    s.insert(4);

    set<int>::iterator sit = s.begin();while(sit != s.end()){
        cout <<*sit <<" ";++sit;}
    cout << endl;}

在这里插入图片描述
这里的set就是树，我们也可以依然用这个迭代器进行遍历。

–

实现迭代器++，就是指针往前走的过程，注意返回的是迭代器。

self&operator--(){
    _node = _node->_prev;return*this;}

后置++与后置–

//后置
self operator++(int){
    self tmp(*this);
    _node = _node->_next;return tmp;}//后置
self operator--(int){
    self tmp(*this);
    _node = _node->_prev;return tmp;}

->

在讲->重载之前，先看一下这个示例：

structAA{AA(int a1 =0,int a2 =0):_a1(a1),_a2(a2){}int _a1;int _a2;};
list<AA> lt;
lt.push_back(AA(1,1));
lt.push_back(AA(2,2));
lt.push_back(AA(3,3));

list<AA>::iterator it = lt.begin();while(it != lt.end()){
    cout <<*it << endl;++it;}
cout << endl;

在这里就访问不了，因为自定义类型不支持类型。

这里我们回顾一下之前的知识，对与内置类型的指针，我们可以采用*来进行解引用。对于自定义类型的指针，我们要用->来进行解引用。

int* p =newint;*p =1;

AA* ptr =new AA;
ptr->_a1 =1;

实现->

T*operator->(){return&_node->_data;}

==

两个迭代器进行比较，就是两个指针比较

booloperator==(const self& s){return _node == s._node;}

const迭代器

在实现const迭代器之前，首先要知道一点，const迭代器是一个完全不一样的类，所以不能将非const迭代器前加const就变成const迭代器。
在这里插入图片描述
因此我们可以list类中在定义一个const迭代器：

typedef __list_const_iterator<T> const_iterator;

const_iterator begin()const{return _head->_next;}
const_iterator end()const{return _head;}

在单独实现一个const迭代器的类：

template<classT>struct__list_const_iterator{....}

const迭代器基本的功能与非const迭代器相似，只有在解引用时不同：

// *it = 10const T&operator*(){return _node->_data;}// it->a1 = 10const T*operator->(){return&_node->_data;}

测试一下：

voidprint_list(const list<int>& lt){
    list<int>::const_iterator it = lt.begin();while(it != lt.end()){//*it = 10;
        cout <<*it <<" ";++it;}
    cout << endl;for(auto e : lt){
        cout << e <<" ";}
    cout << endl;}voidtest_list4(){
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    lt.push_back(5);print_list(lt);}

在这里插入图片描述
但是这样实现，还是太冗余了，因为非const和const只有返回值不同，那么还有优化的空间吗？
我们看一下库里面的实现:
在这里插入图片描述
库里面定义只定义了同一个类模版的迭代器，只是这两个迭代器之间的摸版参数不同，实例化的参数不同，就是完全不一样的类型。也就是说把能靠模版实现的就写一份，让编译器搞。

所以我们可以将我们的迭代器进行进一步优化：

template<classT>classlist{typedef list_node<T> Node;public:typedef __list_iterator<T,T&,T*> iterator;typedef __list_iterator<T,const T&,const T*> const_iterator;....}

// T T& T*// T cosnt T& const T*template<classT,classRef,classPtr>struct__list_iterator{typedef list_node<T> Node;/*typedef __list_iterator<T> self;*/typedef __list_iterator<T, Ref, Ptr> self;
    Node* _node;...}

到这里，我们的迭代器就全部实现完了。

拓展：

在刚才的测试函数中，有一个print_list函数，但是这个测试函数里面的数据我们给定的是int,那我要是其他类型的呢，这个函数又该如何修改呢？
其实很简单：我们加一个摸版参数即可：

template<typenameT>voidprint_list(const list<T>& lt){typenamelist<T>::const_iterator it = lt.begin();while(it != lt.end()){//*it = 10;
        cout <<*it <<" ";++it;}
    cout << endl;}

测试一下：
在这里插入图片描述
注意：这里我们没有用class这个摸版参数，这是因为：

list是一个未实例化的类模板，编译器不能去他里面去找
编译器就无法确定：list::const_iterator是内嵌类型，还是静态成员变量
前面加一个typename就是告诉编译器，这里是一个类型，等list实例化后再去类里面去取

拓展2：

如果要是将刚才的类在改造一下呢？
比如：
我要打印以下内容：

vector<string> v;
v.push_back("222222222222222222222");
v.push_back("222222222222222222222");
v.push_back("222222222222222222222");
v.push_back("222222222222222222222");

这个函数对于我们的printf_list就不适用了，因为我们的print_list就只适用于链表。
这里我们就可以写一个容器（container）的打印函数：

template<typenameContainer>voidprint_Container(const Container& con){typenameContainer::const_iterator it = con.begin();while(it != con.end()){
        cout <<*it <<" ";++it;}
    cout << endl;}

测试结果：
在这里插入图片描述
总结一下：
摸版实现了泛型编程，而泛型编程的本质，就是本来我们干的活，交给了编译器。

相关函数接口：

有了迭代器的实现，我们就可以实现一下链表的相关接口：

Insert：

Insert:在pos位置之前插入：

iterator insert(iterator pos,const T& x){
    Node* cur = pos._node;
    Node* newnode =newNode(x);

    Node* prev = cur->_prev;// prev newnode cur
    prev->_next = newnode;
    newnode->_prev = prev;
    
    newnode->_next = cur;
    cur->_prev = newnode;++_size;returniterator(newnode);}

Insert迭代器不会产生失效的问题，因为没有扩容。

erase:

在指定位置删除：

iterator erase(iterator pos){
        Node* cur = pos._node;
        Node* prev = cur->_prev;
        Node* next = cur->_next;delete cur;
            prev->_next = next;
            next->_prev = prev;--_size;returniterator(next);}

注意：erase的迭代器会失效，所以我们加个返回值。

实现了insert和erase后，我们就可以服用来实现头插，头删，尾插，尾删。

push_front与pop_fronr

具体实现：

头插：

//头插voidpush_front(const T& x){insert(begin(), x);}

头删：

//头删voidpop_front(){erase(begin());}

push_back与pop_back

具体实现：

尾插：

voidpush_back(const T& x){insert(end(), x);}

尾删：

//尾删voidpop_back(){erase(--end());}

size:

为了方便计算大小，我们还可以再实现一个函数：

size_t size(){return _size;}

clear与析构：

clear：清理空间，我们可以采取迭代器访问的方式，逐个将节点释放。

//清理空间：voidclear(){
    iterator it =begin();while(it !=end()){
        it =erase(it);}}

析构：我们可以先清理空间，在将头节点释放即可。

//析构~list(){clear();delete _head;
    _head =nullptr;}

拷贝构造：

我们可以采用范围for来进行拷贝构造：

//拷贝构造：// lt2(lt1)//list(const list<T>& lt)list(list<T>& lt){empty_init();for(auto e : lt){push_back(e);}}

赋值重载：

传统写法：

list<int>&operator=(const list<int>& lt){if(this!=&lt){clear();for(auto e : lt){push_back(e);}}return*this;}

现代写法：

voidswap(list<T>& lt){
    std::swap(_head, lt._head);
    std::swap(_size, lt._size);}// lt3 = lt1
list<int>&operator=(list<int> lt){swap(lt);return*this;}

对比vector与list

在这里插入图片描述

标签： c++ list windows
本文转载自: https://blog.csdn.net/weixin_72066135/article/details/134349834
版权归原作者 小小unicorn 所有， 如有侵权，请联系我们删除。
登录后发布评论

“【C++初阶】STL详解（八）List的模拟实现”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

机器人技术在安全领域的重要作用

安全学习记录——网络篇（一）

图腾柱PFC：HP1010为您的电动两轮车之旅提供绿色，高效，安全的动力

单元测试数据库回滚问题

这才是单元测试，之前我们都错了

【C语言基础】：字符函数和字符串函数

ChatGPT-Next-Web SSRF漏洞+XSS漏洞复现(CVE-2023-49785)

文章导航