【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的使用和模拟实现：👉 传送门