0


【C++】SLT — list的使用 + 模拟实现

文章目录

📖前言:

本章我们将学习STL中另一个重要的类模板vector…

  • list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。
  • list的底层是双向链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向其前一个元素和后一个元素。
  • list与forward_list非常相似:主要区别在于forward_list对象是单链接列表,因此它们只能向前迭代,以换取更小、更高效。
  • 与其他的序列式容器相比(array,vector,deque),list通常在任意位置进行插入、移除元素的执行效率更好。
  • 与其他序列式容器相比,list和forward_list最大的缺陷是不支持任意位置的随机访问,需要线性的时间开销

list的学习文档:👉 传送门


1. list的使用

我们学习的STL中的list是一种:带头双向循环链表。(带有哨兵位头结点的)

  • 带头双向循环链表 – 链表中的最优设计
  • 可以实现任意位置〇(1)的插入删除,只需要改前后的关系

1.1 list的初始化 + 迭代器的使用:

在我们使用list之前我们需要先包一下头文件#include< list >。

直接见代码:

尾插:

voidtest_list1(){
        list<int> lt;
        lt.push_back(1);
        lt.push_back(2);
        lt.push_back(3);
        lt.push_back(4);//正向迭代器
        list<int>::iterator it = lt.begin();while(it != lt.end()){
            cout <<*it <<" ";++it;}
        cout << endl;for(auto e : lt){
            cout << e <<" ";}
        cout << endl;//反向迭代器//list<int>::reverse_iterator rit = lt.rbegin();auto rit = lt.rbegin();while(rit != lt.rend()){
            cout <<*rit <<" ";++rit;}
        cout << endl;}

在这里插入图片描述
头插:

voidtest_list2(){
        list<int> lt;
        lt.push_back(1);
        lt.push_back(2);
        lt.push_back(3);
        lt.push_back(4);for(auto e : lt){
            cout << e <<" ";}
        cout << endl;

        lt.push_front(10);
        lt.push_front(20);
        lt.push_front(30);
        lt.push_front(40);for(auto e : lt){
            cout << e <<" ";}
        cout << endl;

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

在这里插入图片描述
list::push_back的使用方法和vector::push_back的使用方法一样。


1.2 对list的排序:

对于一般的容器而言,我们包一个算法库 #incldue < alogrithm > 可以对普通的容器进行排序。

voidtest_list2(){
    vector<int> v;
    v.push_back(1);
    v.push_back(4);
    v.push_back(2);
    v.push_back(4);
    v.push_back(3);sort(v.begin(), v.end());for(auto e : v){
        cout << e <<" ";}
    cout << endl;

    list<int> lt;
    lt.push_back(1);
    lt.push_back(4);
    lt.push_back(2);
    lt.push_back(4);
    lt.push_back(3);
    lt.sort();for(auto e : lt){
        cout << e <<" ";}
    cout << endl;}
  • 像vector和string而言,这种连续的容器可以直接用库中的sort
  • 而对于list而言和之前的顺序容器有所区别,因为其链式结构,库中的算法不支持
  • list单独实现了一个自己的排序
  • 但是list的排序效率很低在这里插入图片描述

排序需用时间:

voidTestOP(){srand(time(0));constint N =10000000;
        vector<int> v;
        v.reserve(N);

        list<int> lt1;
        list<int> lt2;for(int i =0; i < N;++i){//v.push_back(rand());auto e =rand();
            lt1.push_back(e);
            lt2.push_back(e);}//拷贝到vector排序,排完以后再拷贝回来int begin1 =clock();for(auto e : lt1){
            v.push_back(e);}sort(v.begin(), v.end());
        size_t i =0;for(auto& e : lt1){
            e = v[i++];}int end1 =clock();int begin2 =clock();//sort(lt.begin(), lt.end());
        lt2.sort();int end2 =clock();printf("vector Sort:%d\n", end1 - begin1);printf("list Sort:%d\n", end2 - begin2);}

在这里插入图片描述

注意:
可见把list的数据拷贝到vector中再,用sort算法对vector中排序,再将vector中的数据拷贝到list中都比直接用list排序要快,所以list的排序效率很低。

2. list的模拟实现(list.h)

2.1 链表结点的申请:

namespace bit
{template<classT>//结点structlist_node{
        list_node<T>* _next;
        list_node<T>* _prev;
        T _data;list_node(const T& val =T()):_next(nullptr),_prev(nullptr),_data(val){}};//复用性很差//单独实现一个类,支持不能修改迭代器指向结点的数据//template<class T>//struct __list_const_iterator;//软件工程中很讲究复用原则 -- 尽量不去写重复的代码//重复的代码不方便维护//typedef __list_iterator<T, T&, T*> iterator;//typedef __list_iterator<T, const T&, const T*> const_iterator;

2.2 用类封装迭list代器:

为了在上层用户使用迭代器的方式和使用原生指针迭代器一样,所以我们做了如下的操作。

  • 用一个类将迭代器封装起来 – 来模拟指针的行为。

这样我们在上层使用上和普通迭代器的使用没有区别但是,底层是不一样的,实现了一个封装。

见如下代码:

template<classT,classRef,classPtr>struct__list_iterator{typedef list_node<T> Node;typedef __list_iterator<T, Ref, Ptr> self;//用来支持反向迭代器typedef Ptr pointer;typedef Ref reference;
        
        Node* _node;//list_node<const int>*explicit__list_iterator(Node* node):_node(node){}//解引用 -- *it//返回const别名的引用
        Ref operator*(){return _node->_data;}

        Ptr operator->(){//return &(operator*());0return&_node->_data;}//前置++
        self&operator++(){
            _node = _node->_next;return*this;}//后置++
        self operator++(int){
            self tmp(*this);
            _node = _node->_next;return tmp;}//前置--
        self&operator--(){
            _node = _node->_prev;return*this;}//后置--
        self operator--(int){
            self tmp(*this);
            _node = _node->_prev;return tmp;}booloperator!=(const self& it){return _node != it._node;}booloperator==(const self& it){return _node == it._node;}};

注意:

  • 析构函数(不需要写)-- 节点不属于迭代器,不需要迭代器释放

  • 结点不是属于迭代器的,拿结点的指针构造迭代器

  • 迭代器的目标是遍历链表,访问和修改这个链表

  • 迭代器不能拿着结点的指针把链表的结点给释放了

    • 编译器生成的默认析构函数,对内置类型不敢处理,只对自定义类型处理
    • 因为指针不能乱释放
  • 拷贝构造和赋值重载(不需要写)

  • 默认生成的浅拷贝就可以

补充:

  • 传引用返回和支持返回值修改
  • 还可以减少拷贝构造

(1)对封装迭代器的使用:

1.为了使我们使用的时候更顺畅,更接近于平时的使用,我们将迭代器在list这个类中再次重命名。

  • 这样我们在使用的过程中就可以这样使用: list::iterator it = lt.begin();

在这里插入图片描述

(2)运算符重载 - > :

在这里插入图片描述
为什么这里返回的是一个地址呢?
在这里插入图片描述

在这里插入图片描述

那么这个时候一定有个疑问,为啥这时,不直接返回要取的值呢?

  • 由上图可见,当list的链表中的结点数据内容不是内置类型数据时
  • 上图中链表结点的数据是一个一个的对象,这时候传值返回就不行了
  • 若是返回值的话,此时返回的是一个对象

解决办法:

  • 方法一:(->操作符重载,传值返回,类内操作) 把类中的成员函数给改了,在类中再去调用一层缺点: 不能广泛的用,不符合泛型编程的思维,要根据不同的场景改动。
  • 方法二:(不重载->操作符,多次调用 . 操作符,类外操作) 在类外对象创建完成之后,拿到迭代器,在调用的时候(it)对象用 “.” 操作符,一层一层调用去找到所需要的数据内容。*缺点: 当调用的层数多时,写起来很麻烦。
  • 方法三:(->操作符重载,传迭代器返回,类外操作) 返回的是迭代器,再通过返回的迭代器调用->的运算符重载,和方法二一样,当调用的层数多时,写起来很麻烦。但是编译器对此进行了优化。

优化如下:

  • it.operator->() – 返回类型是AA*的迭代器
  • it.operator->()->_a1;
  • 编译器为了可读性进行了优化处理
  • 如果不优化应该是it->->_a1;
  • 优化以后,省略了一个->

2.3 链表的资源管理:

这里我们实现的是带头双向循环链表,和之前我们数据结构中实现的结构一样,我们写起来更是轻车熟路了~

  • 这里的拷贝构造和赋值重载都运用到了现代写法
  • 和之前模拟实现容器的时候用到的现代方法一样
//list的实现:template<classT>classlist{typedef list_node<T> Node;public://资源管理:list(){
            _head =newNode();
            _head->_next = _head;
            _head->_prev = _head;}//拷贝构造传统写法:(创造一个哨兵位,挨个尾插)//lt2(lt1)/*list(const list<T>& lt)
        {
            _head = new Node();
            _head->_next = _head;
            _head->_prev = _head;

            for (auto e : lt)
            {
                push_back(e);
            }
        }*///拷贝构造现代写法:(利用一个迭代器区间构造)//创造一个哨兵位头结点出来voidempty_init(){
            _head =newNode();
            _head->_next = _head;
            _head->_prev = _head;}template<classInputIterator>list(InputIterator first, InputIterator last){empty_init();while(first != last){push_back(*first);
                first++;}}voidswap(list<T>& lt){
            std::swap(_head, lt._head);}//lt2(lt1) -- 现代写法list(const list<T>& lt){empty_init();
            list<T>tmp(lt.begin(), lt.end());swap(tmp);}//lt2 = lt1 -- 所有的深拷贝的赋值都可以这么写
        list<T>&operator=(list<T> lt){swap(lt);return*this;}~list(){clear();delete _head;
            _head =nullptr;}//clear不是把数据清掉,大结构还在,没有清掉哨兵位voidclear(){//在成员函数内部不需要对象. 来访问
            iterator it =begin();while(it !=end()){//erase就会往后走起到了迭代的作用//这样写哨兵位还在
                it =erase(it);}}

在这里插入图片描述

交换完之后,拷贝构造结束之后,tmp此时管理的是只有一个哨兵位的链表,tmp对象会被调用的析构函数销毁掉。


2.4 list的主要成员函数:

//迭代器://同样一个类模板,给不同的模板参数,就实例化不同的类型//typedef的类型是受到作用域的限制的typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T,const T&,const T*> const_iterator;//反向迭代器适配支持/*typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;
        typedef Reverse_iterator<const_iterator, const T&, T*> const_reverse_iterator;*/typedef Reverse_iterator<iterator> reverse_iterator;typedef Reverse_iterator<const_iterator> const_reverse_iterator;//正向迭代器://正向迭代器和const修饰的迭代器
        iterator begin(){//返回一个匿名对象,用匿名对象还能被优化成直接构造returniterator(_head->_next);//可以直接返回_head->_next//因为单参数的构造函数支持隐式类型的转换//return _head->_next;}

        iterator end(){returniterator(_head);}

        const_iterator begin()const{//返回一个匿名对象,用匿名对象还能被优化成直接构造//list_node<int>returnconst_iterator(_head->_next);//可以直接返回_head->_next//因为单参数的构造函数支持隐式类型的转换//return _head->_next;}

        const_iterator end()const{returnconst_iterator(_head);}//反向迭代器://反向迭代器和const修饰的反向迭代器
        reverse_iterator rbegin(){returnreverse_iterator(end());}

        reverse_iterator rend(){returnreverse_iterator(begin());}
           
        const_reverse_iterator rbegin()const{returnreverse_iterator(end());}

        const_reverse_iterator rend()const{returnreverse_iterator(begin());}//增添和删除:voidpush_back(const T& x){//Node* tail = _head->_prev;//Node* newnode = new Node(x); _head       tail  newnode//tail->_next = newnode;//newnode->_prev = tail;//newnode->_next = _head;//_head->_prev = newnode;insert(end(), x);}voidpush_front(const T& x){insert(begin(), x);}voidpop_back(){erase(--end());}voidpop_front(){erase(begin());}//插入在pos位置之前
        iterator insert(iterator pos,const T& x){//pos是任意位置,也不需要检查 -- 断言
            Node* newnode =newNode(x);
            Node* cur = pos._node;
            Node* prev = cur->_prev;//prev  newnode  cur
            prev->_next = newnode;
            newnode->_prev = prev;
            newnode->_next = cur;
            cur->_prev = newnode;returniterator(newnode);}

        iterator erase(iterator pos){assert(pos !=end());

            Node* cur = pos._node;
            Node* prev = cur->_prev;
            Node* next = cur->_next;//prev next
            prev->_next = next;
            next->_prev = prev;delete cur;returniterator(next);}private:
        Node* _head;};}

3. 迭代器失效的问题

  • list insert迭代器不失效,不存在野指针的问题,也不存在意义变了的问题
  • ist erase(it)以后,迭代器是会失效的
  • 经典野指针失效,因为这个迭代器指向的结点,已经被释放了
voidtest_list5(){
        list<int> lt;
        lt.push_back(1);
        lt.push_back(2);
        lt.push_back(2);
        lt.push_back(3);
        lt.push_back(4);
        lt.push_back(5);
        lt.push_back(6);要求:删除所有的偶数list<int>::iterator it1 = lt.begin();迭代器会失效//auto it1 = lt.begin();//while (it1 != lt.end())//{//    if (*it1 % 2 == 0)//    {//        lt.erase(it1);//    }//    it1++;//}//list<int>::iterator it1 = lt.begin();auto it1 = lt.begin();while(it1 != lt.end()){if(*it1 %2==0){
                it1 = lt.erase(it1);}else{
                it1++;}

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

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

        lt.push_back(10);
        lt.push_back(20);
        lt.push_back(30);for(auto e : lt){
            cout << e <<" ";}
        cout << endl;}

在这里插入图片描述
当删除结点的时候,it迭代器指向的空间不存在了,此时再对这块空间解引用就会产生非法访问。

在这里插入图片描述
解决办法和之前vector容器迭代器失效时解决办法一样。

参考:
vector的使用和模拟实现:👉 传送门

标签: c++ list

本文转载自: https://blog.csdn.net/m0_63059866/article/details/127003343
版权归原作者 yy_上上谦 所有, 如有侵权,请联系我们删除。

“【C++】SLT &mdash; list的使用 + 模拟实现”的评论:

还没有评论