【十五】【C++】list的简单实现

时间:2024-02-17 21:18:19

list 的迭代器解引用探究

 
/*list的迭代器解引用探究*/
#if 1
#include <list>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

class Date {
    private:
        int _year;
        int _month;
        int _day;
    public:
        Date()
            : _year(2024)
            , _month(1)
            , _day(1)
        {}

        void Show() {
            cout << _year << "-" << _month << "-" << _day << endl;
        }
 };
void TestList8() {
    list<Date> L1;
    L1.push_back(Date());
    L1.push_back(Date());
    L1.push_back(Date());
    L1.push_back(Date());
    
     auto it1=L1.begin();
    while(it1!=L1.end()){
        it1->Show();
        it1++;
    }
    
     list<int> L2;
    L2.push_back(1);
    L2.push_back(2);
    L2.push_back(3);
    L2.push_back(4);
    
     auto it2=L2.begin();
    while(it2!=L2.end()){
        cout<<*it2<<endl;
        it2++;
    }
 }

int main() {
    TestList8();
 }
#endif

这段代码主要展示了如何在 C++ 中使用 std::list 容器来存储和遍历自定义类型(Date 类)的对象以及基本数据类型(int)的值。程序定义了一个 Date 类,用于表示日期,并提供了一个 Show 成员函数来打印日期。然后,它在函数 TestList8 中创建了两个 std::list 容器:一个存储 Date 对象,另一个存储 int 值。通过迭代器遍历这些列表,并展示了如何访问和操作容器中的元素。

这段代码看似平平无奇,细心的小伙伴可能会发现,在遍历L1list对象的时候,it1->Show();这一行代码似乎有一点问题。it1迭代器底层是list结点的指针,it1->得到的结果应该是Date类型对象而不能直接访问Date类型对象的成员才对。如果it1底层指针存储的是节点中Date类型的对象的地址,那么it1->Show();就没有任何问题。

实际上list类中->底层会返回*it迭代器的地址,Ptr operator->(){return &(operator*()); },但即使返回了地址,我们还需要一个->才能访问Date的对象才对。正确的做法就变成了it1->->Show();这个样子。但是这样的代码可读性太差了,为了提高代码的可读性,编译器自动给我们添加一个->,使得我们仅仅使用it1->Show();这样的代码就可以完成实现。

代码实现

 
#include<iostream>
using namespace std;
#include<algorithm>
namespace Mylist
{
    template<class T>
    struct ListNode
    {
        ListNode<T>* _next;
        ListNode<T>* _prev;
        T _value;
        
         ListNode(const T& value = T())
        : _next(nullptr)
        , _prev(nullptr)
        , _value(value)
        {}
    };
    
     // 1. 封装迭代器对应的类
    template<class T, class Ref, class Ptr>
    struct ListIterator
    {
        typedef ListNode<T> Node;
        typedef Ref ItRef;
        typedef Ptr ItPtr;
        
         typedef ListIterator<T, Ref, Ptr> Self;
    public:
        ListIterator(Node* pNode = nullptr)
        : _pNode(pNode)
        {}
        
         //
        // 具有指针类似的操作
        Ref operator*()
        {
            return _pNode->_value;
        }
        
         Ptr operator->()
        {
            return &(operator*());
        }
        
         
        // 移动
        Self& operator++()
        {
            _pNode = _pNode->_next;
            return *this;
        }
        
         Self operator++(int)
        {
            Self temp(*this);
            _pNode = _pNode->_next;
            return temp;
        }
        
         Self& operator--()
        {
            _pNode = _pNode->_prev;
            return *this;
        }
        
         Self operator--(int)
        {
            Self temp(*this);
            _pNode = _pNode->_prev;
            return temp;
        }
        
         ///
        // 比较
        bool operator!=(const Self& s)const
        {
            return _pNode != s._pNode;
        }
        
         bool operator==(const Self& s)const
        {
            return _pNode == s._pNode;
        }
        
         Node* _pNode;
    };
    
     
     // 反向迭代器:就是对正向迭代器的包装
    template<class Iterator>
    struct ListReverseIterator
    {
        // 静态成员变量也可以通过类名::静态成员变量名称
        // typedef Iterator::ItRef Ref;  编译报错
        // 编译器无法在编译时无法确定ItRef是静态成员变量 还是 类型
        // 需要显式告诉编译器ItRef就是Iterator类中的类型
        // typename
        typedef typename Iterator::ItRef Ref;
        typedef typename Iterator::ItPtr Ptr;
        typedef ListReverseIterator<Iterator> Self;
    public:
        ListReverseIterator(Iterator it)
        : _it(it)
        {}
        
         Ref operator*()
        {
            Iterator temp(_it);
            --temp;
            return *temp;
        }
        
         Ptr operator->()
        {
            return &(operator*());
        }
        
         Self& operator++()
        {
            --_it;
            return *this;
        }
        
         Self operator++(int)
        {
            Self temp(*this);
            --_it;
            return temp;
        }
        
         Self& operator--()
        {
            ++_it;
            return *this;
        }
        
         Self operator--(int)
        {
            Self temp(*this);
            ++_it;
            return temp;
        }
        
         bool operator!=(const Self& rit)const
        {
            return _it != rit._it;
        }
        
         bool operator==(const Self& rit)const
        {
            return _it == rit._it;
        }
        
         Iterator _it;
    };
    
     template<class T>
    class list
    {
        typedef ListNode<T> Node;
        
         // 2. 在容器中给迭代器类型取别名---public
    public:
        typedef ListIterator<T, T&, T*> iterator;
        typedef ListIterator<T, const T&, const T*> const_iterator;
        
        typedef ListReverseIterator<iterator> reverse_iterator;
        typedef ListReverseIterator<const_iterator> const_reverse_iterator;
    public:
        // 注意:list的迭代器一定不能是原生态的指针
        // vector之所以可以,因为vector底层是连续空间
        // 如果指针指向连续的空间,对指针++/--,该指针就可以移动到下一个/前一个位置
        // 但是list不行,因为链表中的节点是通过next和prev指针组织起来的,不一定连续
        // 如果将list的迭代器设置为原生态指针,++it/--it没有意义
        // typedef Node* iterator;  // ???
        
     public:
        
        // 构造
        list()
        {
            CreateHead();
        }
        
         list(int n, const T& value = T())
        {
            CreateHead();
            for (int i = 0; i < n; ++i)
            {
                push_back(value);
            }
        }
        
         template<class Iterator>
        list(Iterator first, Iterator last)
        {
            CreateHead();
            while (first != last)
            {
                push_back(*first);
                ++first;
            }
        }
        
         list(const list<T>& L)
        {
            CreateHead();
            auto it = L.cbegin();
            while (it != L.cend())
            {
                push_back(*it);
                ++it;
            }
        }
        
         list<T>& operator=(list<T> L)
        {
            this->swap(L);
            return *this;
        }
        
         ~list()
        {
            clear();
            delete _head;
            _head = nullptr;
        }
        
         //
        // 迭代器
        // 3. 增加begin和end的方法
        iterator begin()
        {
            /*iterator ret(_head->_next);
            return ret;*/
            
             return iterator(_head->_next);
        }
        
         iterator end()
        {
            return iterator(_head);
        }
        
         const_iterator cbegin()const
        {
            /*iterator ret(_head->_next);
            return ret;*/
            
             return const_iterator(_head->_next);
        }
        
         const_iterator cend()const
        {
            return const_iterator(_head);
        }
        
         reverse_iterator rbegin()
        {
            return reverse_iterator(end());
        }
        
         reverse_iterator rend()
        {
            return reverse_iterator(begin());
        }
        
         const_reverse_iterator crbegin()const
        {
            return const_reverse_iterator(cend());
        }
        
         const_reverse_iterator crend()const
        {
            return const_reverse_iterator(cbegin());
        }
        
         //
        // 容量
        size_t size()const
        {
            size_t count = 0;
            Node* cur = _head->_next;
            while (cur != _head)
            {
                count++;
                cur = cur->_next;
            }
            
             return count;
        }
        
         bool empty()const
        {
            return _head == _head->_next;
        }
        
         void resize(size_t newsize, const T& value = T())
        {
            size_t oldsize = size();
            if (newsize <= oldsize)
            {
                for (size_t i = newsize; i < oldsize; ++i)
                {
                    pop_back();
                }
            }
            else
            {
                for (size_t i = oldsize; i < newsize; ++i)
                {
                    push_back(value);
                }
            }
        }
        
         //
        // 元素访问
        T& front()
        {
            return *begin();
        }
        
         const T& front()const
        {
            //return _head->_next->_value;
            return *cbegin();
        }
        
         T& back()
        {
            return *(--end());
        }
        
         const T& back()const
        {
            // return _head->_prev->_value;
            return *(--cend());
        }
        
         ///
        // 修改
        void push_front(const T& value)
        {
            insert(begin(), value);
        }
        
         void pop_front()
        {
            erase(begin());
        }
        
         void push_back(const T& value)
        {
            insert(end(), value);
        }
        
         void pop_back()
        {
            erase(--end());
        }
        
         iterator insert(iterator it, const T& value)
        {
            Node* pos = it._pNode;
            Node* newNode = new Node(value);
            newNode->_next = pos;
            newNode->_prev = pos->_prev;
            newNode->_prev->_next = newNode;
            pos->_prev = newNode;
            
             return newNode;
        }
        
         iterator erase(iterator it)
        {
            if (it == end())
                return end();
            
             Node* pos = it._pNode;
            Node* ret = pos->_next;
            pos->_prev->_next = pos->_next;
            pos->_next->_prev = pos->_prev;
            delete pos;
            return ret;
        }
        
         void clear()
        {
            auto it = begin();
            while (it != end())
            {
                it = erase(it);
            }
        }
        
         void swap(list<T>& L)
        {
            std::swap(_head, L._head);
        }
    private:
        void CreateHead()
        {
            _head = new Node();
            _head->_next = _head;
            _head->_prev = _head;
        }
        
     private:
        Node* _head;
    };
 }

void TestList1()
 {
    Mylist::list<int> L1;
    Mylist::list<int> L2(10, 5);
    
     int array[] = { 1, 2, 3, 4, 5 };
    Mylist::list<int> L3(array, array+sizeof(array)/sizeof(array[0]));
    
     Mylist::list<int> L4(L3);
    
     for (auto e : L3)
    {
        cout << e << " ";
    }
    cout << endl;
    
     Mylist::list<int>::iterator it = L4.begin();
    while (it != L4.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
 }

void TestList2()
 {
    int array[] = { 1, 2, 3, 4, 5 };
    Mylist::list<int> L1(array, array + sizeof(array) / sizeof(array[0]));
    auto itL1 = L1.begin();
    *itL1 = 10;
    
//    auto citL1 = L1.cbegin();
    //*citL1 = 100;
    
     cout << L1.front() << endl;
    cout << L1.back() << endl;
    cout << L1.size() << endl;
    
     const Mylist::list<int> L2(L1);
//    auto it = L2.cbegin();
    
     cout << L2.front() << endl;
    cout << L2.back() << endl;
 }

void TestLst3()
 {
    Mylist::list<int> L;
    L.push_back(1);
    L.push_back(2);
    L.push_back(3);
    L.push_back(4);
    L.push_back(5);
    cout << L.size() << endl;
    
     L.push_front(0);
    for (auto e : L)
        cout << e << " ";
    cout << endl;
    
     L.pop_front();
    for (auto e : L)
        cout << e << " ";
    cout << endl;
    
     // find(L.begin(), L.end(), 4);
}

void TestLst4()
 {
    Mylist::list<int> L;
    L.push_back(1);
    L.push_back(2);
    L.push_back(3);
    L.push_back(4);
    L.push_back(5);
    
     auto it = L.rbegin();
    while (it != L.rend())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
    
     auto rit = L.crbegin();
    while (rit != L.crend())
    {
        cout << *rit << " ";
        ++rit;
    }
    cout << endl;
 }
int main(){
    Mylist::list<int> L;
    L.push_back(1);
    L.push_back(2);
    L.push_back(3);
    L.push_back(4);
    L.push_back(5);
    auto it=L.begin();
    
//    L.assign(10, 5);
    Mylist::list<int> L1(5,10);
    L = L1;
    
     while (it != L.end())
    {
        cout << *it << " ";
        ++it;
    }
 }

ListNode 结构

 
    template<class T>
    struct ListNode
    {
        ListNode<T>* _next;
        ListNode<T>* _prev;
        T _value;
        
         ListNode(const T& value = T())
        : _next(nullptr)
        , _prev(nullptr)
        , _value(value)
        {}
    };

ListNode 是一个结构体,用于表示链表中的一个节点。它包含指向下一个节点的指针 _next、指向前一个节点的指针 _prev 和存储的数据 _value。构造函数允许用一个值初始化节点,并默认设置前后节点为 nullptr

ListIterator

 
    template<class T, class Ref, class Ptr>
    struct ListIterator
    {
        typedef ListNode<T> Node;
        typedef Ref ItRef;
        typedef Ptr ItPtr;
        
         typedef ListIterator<T, Ref, Ptr> Self;
    public:
        ListIterator(Node* pNode = nullptr)
        : _pNode(pNode)
        {}
        
         //
        // 具有指针类似的操作
        Ref operator*()
        {
            return _pNode->_value;
        }
        
         Ptr operator->()
        {
            return &(operator*());
        }
        
         
        // 移动
        Self& operator++()
        {
            _pNode = _pNode->_next;
            return *this;
        }
        
         Self operator++(int)
        {
            Self temp(*this);
            _pNode = _pNode->_next;
            return temp;
        }
        
         Self& operator--()
        {
            _pNode = _pNode->_prev;
            return *this;
        }
        
         Self operator--(int)
        {
            Self temp(*this);
            _pNode = _pNode->_prev;
            return temp;
        }
        
         ///
        // 比较
        bool operator!=(const Self& s)const
        {
            return _pNode != s._pNode;
        }
        
         bool operator==(const Self& s)const
        {
            return _pNode == s._pNode;
        }
        
         Node* _pNode;
    };

ListIterator 是一个迭代器类,支持对链表的正向遍历。它重载了操作符,以提供类似指针的行为。包括解引用 (operator*operator->)、迭代(operator++operator--)和比较(operator==operator!=)。ListIterator 使得用户可以通过迭代器遍历链表,访问或修改节点的值。

类模板参数:

 
    template<class T, class Ref, class Ptr>
    struct ListIterator
    {
        typedef ListNode<T> Node;
        typedef Ref ItRef;
        typedef Ptr ItPtr;
        
        typedef ListIterator<T, Ref, Ptr> Self;

我们在list类里面定义迭代器是这样定义的。typedef ListIterator<T, T&, T*> iterator;其中Ref用来接收T&Ptr用来接收T*

这三个模版参数的具体含义如下所示:

T: 数据类型,指定链表节点存储的数据的类型。

Ref: 引用类型,决定了解引用操作符 (operator*) 返回值的类型,可以是数据的引用,允许通过迭代器修改链表节点的值。

Ptr: 指针类型,指定通过迭代器访问成员时的指针类型,通常是数据的指针类型。

这里的三个模版参数可以理解为数据类型占位符,每一个参数都有其特定的含义以及对应的数据类型,当我们使用的时候,传入的参数会与对应模版参数意义相吻合。

类型定义:

Node: 代表链表节点的类型,使用了模板参数 T 来指定节点存储的数据类型。

ItRefItPtr: 分别代表迭代器的引用和指针类型,这些类型允许迭代器通过类似指针的方式操作数据。

Self: 代表迭代器自身的类型,用于实现链式调用和返回正确的迭代器类型。

成员变量

Node* _pNode;

_pNode: 指向当前迭代器所指向的链表节点的指针。

构造函数:

 
        ListIterator(Node* pNode = nullptr)
        : _pNode(pNode)
        {}

ListIterator(Node* pNode = nullptr): 允许通过给定一个链表节点的指针来构造迭代器。默认参数为 nullptr,允许创建一个不指向任何节点的迭代器。

解引用操作符重载:

 
        // 具有指针类似的操作
        Ref operator*()
        {
            return _pNode->_value;
        }
        
         Ptr operator->()
        {
            return &(operator*());
        }

operator*(): 解引用操作符,返回当前迭代器指向的节点中存储的数据的引用,允许读取或修改该数据。针对于内置类型。

operator->(): 成员访问操作符,提供对当前迭代器指向的节点中存储的数据成员的访问。针对于自定义类型。

->返回的是list元素中的地址,编译器自动帮我们添加了一个->使得我们可以通过list元素自定义类型的地址进行访问成员属性。

迭代器移动:

 
        // 移动
        Self& operator++()
        {
            _pNode = _pNode->_next;
            return *this;
        }
        
         Self operator++(int)
        {
            Self temp(*this);
            _pNode = _pNode->_next;
            return temp;
        }
        
         Self& operator--()
        {
            _pNode = _pNode->_prev;
            return *this;
        }
        
         Self operator--(int)
        {
            Self temp(*this);
            _pNode = _pNode->_prev;
            return temp;
        }

operator++(): 前缀递增操作符,使迭代器前进到链表的下一个节点,并返回当前迭代器的引用。

operator++(int): 后缀递增操作符,使迭代器前进到链表的下一个节点,返回迭代器递增前的副本。

operator--(): 前缀递减操作符,使迭代器后退到链表的前一个节点,并返回当前迭代器的引用。

operator--(int): 后缀递减操作符,使迭代器后退到链表的前一个节点,返回迭代器递减前的副本。

operator!=operator==: 比较操作符,分别用于判断两个迭代器是否不相等或相等,即它们是否指向同一个链表节点。

小结论:

通过测试我们发现,在list简单实现过程中,如果不显示定义operator*()operator->()重载,就没办法解引用迭代器,但在vector简单实现过程中,并不需要显示定义operator*()operator->()重载就可以完成解引用迭代器。

ListReverseIterator

 
     // 反向迭代器:就是对正向迭代器的包装
    template<class Iterator>
    struct ListReverseIterator
    {
        // 静态成员变量也可以通过类名::静态成员变量名称
        // typedef Iterator::ItRef Ref;  编译报错
        // 编译器无法在编译时无法确定ItRef是静态成员变量 还是 类型
        // 需要显式告诉编译器ItRef就是Iterator类中的类型
        // typename
        typedef typename Iterator::ItRef Ref;
        typedef typename Iterator::ItPtr Ptr;
        typedef ListReverseIterator<Iterator> Self;
    public:
        ListReverseIterator(Iterator it)
        : _it(it)
        {}
        
         Ref operator*()
        {
            Iterator temp(_it);
            --temp;
            return *temp;
        }
        
         Ptr operator->()
        {
            return &(operator*());
        }
        
         Self& operator++()
        {
            --_it;
            return *this;
        }
        
         Self operator++(int)
        {
            Self temp(*this);
            --_it;
            return temp;
        }
        
         Self& operator--()
        {
            ++_it;
            return *this;
        }
        
         Self operator--(int)
        {
            Self temp(*this);
            ++_it;
            return temp;
        }
        
         bool operator!=(const Self& rit)const
        {
            return _it != rit._it;
        }
        
         bool operator==(const Self& rit)const
        {
            return _it == rit._it;
        }
        
         Iterator _it;
    };

ListReverseIterator 是一个反向迭代器类,对 ListIterator 进行了包装,使其能够以相反的顺序遍历链表。它通过改变迭代方向(即通过递减其底层正向迭代器)来实现反向遍历。反向迭代器同样重载了类似指针的操作。

模板参数Iterator

 
     // 反向迭代器:就是对正向迭代器的包装
    template<class Iterator>
    struct ListReverseIterator
    {
        // 静态成员变量也可以通过类名::静态成员变量名称
        // typedef Iterator::ItRef Ref;  编译报错
        // 编译器无法在编译时无法确定ItRef是静态成员变量 还是 类型
        // 需要显式告诉编译器ItRef就是Iterator类中的类型
        // typename
        typedef typename Iterator::ItRef Ref;
        typedef typename Iterator::ItPtr Ptr;
        typedef ListReverseIterator<Iterator> Self;

ListReverseIterator是模板结构体,其模板参数Iterator代表它将要包装的正向迭代器的类型。

类型别名定义(typedef):

使用typedef typename Iterator::ItRef Ref;定义了一个类型别名Ref,它引用了正向迭代器中定义的ItRef类型。这里的typename关键字是必需的,因为Iterator::ItRef是一个依赖于模板参数的类型,编译器需要明确地被告知这是一个类型名。

类似地,PtrSelf别名分别为迭代器的指针类型和反向迭代器自身的类型。

构造函数:

 
        ListReverseIterator(Iterator it)
        : _it(it)
        {}

接受一个正向迭代器作为参数,并初始化内部的迭代器_it

解引用操作符重载:

 
         Ref operator*()
        {
            Iterator temp(_it);
            --temp;
            return *temp;
        }
        
         Ptr operator->()
        {
            return &(operator*());
        }

operator*:解引用操作符,返回当前迭代器前一个位置的元素的引用。这是因为反向迭代时,当前位置实际对应的是正向迭代器的前一个元素。

operator->:成员访问操作符,返回当前元素的指针。

反向迭代器是通过正向迭代器封装复用实现的,反向迭代器的rbegin对应正向迭代器的end,反向迭代器的rend对应正向迭代器的begin。反向迭代器中的operator*()解引用实际上是返回正向迭代器前一个位置的解引用。即创建一个临时的正向迭代器对象,这个正向迭代器对象进行--操作指向前一个位置,返回的是前一个位置的迭代器的解引用。因为*temp实际上返回的是list具体对象,temp出作用域消失,但是list中的具体对象不会消失。

->返回的是list元素中的地址,编译器自动帮我们添加了一个->使得我们可以通过list元素自定义类型的地址进行访问成员属性。

迭代器移动:

 
         Self& operator++()
        {
            --_it;
            return *this;
        }
        
         Self operator++(int)
        {
            Self temp(*this);
            --_it;
            return temp;
        }
        
         Self& operator--()
        {
            ++_it;
            return *this;
        }
        
         Self operator--(int)
        {
            Self temp(*this);
            ++_it;
            return temp;
        }

对于反向迭代器,递增意味着正向迭代器实际上是递减的,递减则相反。

相等与不等operator运算符重载:

 
         bool operator!=(const Self& rit)const
        {
            return _it != rit._it;
        }
        
         bool operator==(const Self& rit)const
        {
            return _it == rit._it;
        }
        
         

operator!=operator==:比较操作符,用于比较两个反向迭代器是否不相等或相等。

成员变量

Iterator _it;

内部迭代器_it:这是被包装的正向迭代器的实例,反向迭代器通过操作这个内部迭代器来实现反向遍历。

ListIterator类和ListReverseIterator类的思考

在这两类中,模版参数可以理解为对应类型的占位符,也就是明确告诉编译器这些参数对应的是什么样的数据类型,因为在后面的使用过程中,我们会对其进行封装,以至于传入模版参数的数据类型就是我们希望的数据类型。

注意ListReverseIterator类中的Ref operator*()解引用是调用正向迭代器的前一个位置的解引用。因为反向迭代器是对正向迭代器进行封装,复用,来实现反向遍历的功能。

在list类中我们使用反向迭代器时,rbegin传入的是end迭代器,也就是正向迭代器的最后一个元素的后一个位置。简单来说,反向迭代器实际上是正向迭代器的逆用,利用正向迭代器的end来封装复用实现rbegin,利用正向迭代器的begin来封装复用实现rend

正向迭代器的区间是[begin,end),为了统一反向迭代器的区间也应该是[rbegin,rend)。而rbegin是通过正向迭代器end实现的,rend是通过正向迭代器begin实现的,为了统一实现,反向迭代器的解引用operator*全部都返回当前迭代器前一个位置的元素的引用。

list

 
     template<class T>
    class list
    {
        typedef ListNode<T> Node;
        
         // 2. 在容器中给迭代器类型取别名---public
    public:
        typedef ListIterator<T, T&, T*> iterator;
        typedef ListIterator<T, const T&, const T*> const_iterator;
        
        typedef ListReverseIterator<iterator> reverse_iterator;
        typedef ListReverseIterator<const_iterator> const_reverse_iterator;
    public:
        // 注意:list的迭代器一定不能是原生态的指针
        // vector之所以可以,因为vector底层是连续空间
        // 如果指针指向连续的空间,对指针++/--,该指针就可以移动到下一个/前一个位置
        // 但是list不行,因为链表中的节点是通过next和prev指针组织起来的,不一定连续
        // 如果将list的迭代器设置为原生态指针,++it/--it没有意义
        // typedef Node* iterator;  // ???
        
     public:
        
        // 构造
        list()
        {
            CreateHead();
        }
        
         list(int n, const T& value = T())
        {
            CreateHead();
            for (int i = 0; i < n; ++i)
            {
                push_back(value);
            }
        }
        
         template<class Iterator>
        list(Iterator first, Iterator last)
        {
            CreateHead();
            while (first != last)
            {
                push_back(*first);
                ++first;
            }
        }
        
         list(const list<T>& L)
        {
            CreateHead();
            auto it = L.cbegin();
            while (it != L.cend())
            {
                push_back(*it);
                ++it;
            }
        }
        
         list<T>& operator=(list<T> L)
        {
            this->swap(L);
            return *this;
        }
        
         ~list()
        {
            clear();
            delete _head;
            _head = nullptr;
        }
        
         //
        // 迭代器
        // 3. 增加begin和end的方法
        iterator begin()
        {
            /*iterator ret(_head->_next);
            return ret;*/
            
             return iterator(_head->_next);
        }
        
         iterator end()
        {
            return iterator(_head);
        }
        
         const_iterator cbegin()const
        {
            /*iterator ret(_head->_next);
            return ret;*/
            
             return const_iterator(_head->_next);
        }
        
         const_iterator cend()const
        {
            return const_iterator(_head);
        }
        
         reverse_iterator rbegin()
        {
            return reverse_iterator(end());
        }
        
         reverse_iterator rend()
        {
            return reverse_iterator(begin());
        }
        
         const_reverse_iterator crbegin()const
        {
            return const_reverse_iterator(cend());
        }
        
         const_reverse_iterator crend()const
        {
            return const_reverse_iterator(cbegin());
        }
        
         //
        // 容量
        size_t size()const
        {
            size_t count = 0;
            Node* cur = _head->_next;
            while (cur != _head)
            {
                count++;
                cur = cur->_next;
            }
            
             return count;
        }
        
         bool empty()const
        {
            return _head == _head->_next;
        }
        
         void resize(size_t newsize, const T& value = T())
        {
            size_t oldsize = size();
            if (newsize <= oldsize)
            {
                for (size_t i = newsize; i < oldsize; ++i)
                {
                    pop_back();
                }
            }
            else
            {
                for (size_t i = oldsize; i < newsize; ++i)
                {
                    push_back(value);
                }
            }
        }
        
         //
        // 元素访问
        T& front()
        {
            return *begin();
        }
        
         const T& front()const
        {
            //return _head->_next->_value;
            return *cbegin();
        }
        
         T& back()
        {
            return *(--end());
        }
        
         const T& back()const
        {
            // return _head->_prev->_value;
            return *(--cend());
        }
        
         ///
        // 修改
        void push_front(const T& value)
        {
            insert(begin(), value);
        }
        
         void pop_front()
        {
            erase(begin());
        }
        
         void push_back(const T& value)
        {
            insert(end(), value);
        }
        
         void pop_back()
        {
            erase(--end());
        }
        
         iterator insert(iterator it, const T& value)
        {
            Node* pos = it._pNode;
            Node* newNode = new Node(value);
            newNode->_next = pos;
            newNode->_prev = pos->_prev;
            newNode->_prev->_next = newNode;
            pos->_prev = newNode;
            
             return newNode;
        }
        
         iterator erase(iterator it)
        {
            if (it == end())
                return end();
            
             Node* pos = it._pNode;
            Node* ret = pos->_next;
            pos->_prev->_next = pos->_next;
            pos->_next->_prev = pos->_prev;
            delete pos;
            return ret;
        }
        
         void clear()
        {
            auto it = begin();
            while (it != end())
            {
                it = erase(it);
            }
        }
        
         void swap(list<T>& L)
        {
            std::swap(_head, L._head);
        }
    private:
        void CreateHead()
        {
            _head = new Node();
            _head->_next = _head;
            _head->_prev = _head;
        }
        
     private:
        Node* _head;
    };
 }

list类代码解析

 
     template<class T>
    class list
    {
        typedef ListNode<T> Node;
        
         // 2. 在容器中给迭代器类型取别名---public
    public:
        typedef ListIterator<T, T&, T*> iterator;
        typedef ListIterator<T, const T&, const T*> const_iterator;
        
        typedef ListReverseIterator<iterator> reverse_iterator;
        typedef ListReverseIterator<const_iterator> const_reverse_iterator;

类模板声明:

template<class T> class list定义了一个泛型链表,T是链表中存储元素的类型。

迭代器类型别名:

定义了两种迭代器:iteratorconst_iterator,分别用于访问可修改的数据和只读数据。这些迭代器不是原生指针,而是封装过的,因为链表的元素不是连续存储的,不能直接通过指针算术操作访问。

还定义了反向迭代器reverse_iteratorconst_reverse_iterator,用于实现反向遍历。

构造函数和析构函数:

无参构造函数

 
        // 构造
        list()
        {
            CreateHead();
        }
        
                void CreateHead()
        {
            _head = new Node();
            _head->_next = _head;
            _head->_prev = _head;
        }

list()是无参构造函数,它只是创建了一个头节点。

指定的元素数量和值的构造函数

 
         list(int n, const T& value = T())
        {
            CreateHead();
            for (int i = 0; i < n; ++i)
            {
                push_back(value);
            }
        }

list(int n, const T& value = T())根据指定的元素数量和值进行初始化。实际上就是不断地调用push_back操作。

范围构造函数

 
         template<class Iterator>
        list(Iterator first, Iterator last)
        {
            CreateHead();
            while (first != last)
            {
                push_back(*first);
                ++first;
            }
        }

list(Iterator first, Iterator last)是范围构造函数,根据给定的迭代器范围来构造链表。

拷贝构造函数

 
         list(const list<T>& L)
        {
            CreateHead();
            auto it = L.cbegin();
            while (it != L.cend())
            {
                push_back(*it);
                ++it;
            }
        }

list(const list<T>& L)是拷贝构造函数,用另一个链表的内容来初始化新链表。

析构函数

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

~list()是析构函数,它清除链表中的所有元素,并删除头节点。

赋值操作符:

 
         list<T>& operator=(list<T> L)
        {
            this->swap(L);
            return *this;
        }

使用了拷贝并交换的技巧来实现赋值操作符。

迭代器方法:

 
        // 迭代器
        // 3. 增加begin和end的方法
        iterator begin()
        {
            /*iterator ret(_head->_next);
            return ret;*/
            
             return iterator(_head->_next);
        }
        
         iterator end()
        {
            return iterator(_head);
        }
        
         const_iterator cbegin()const
        {
            /*iterator ret(_head->_next);
            return ret;*/
            
             return const_iterator(_head->_next);
        }
        
         const_iterator cend()const
        {
            return const_iterator(_head);
        }
        
         reverse_iterator rbegin()
        {
            return reverse_iterator(end());
        }
        
         reverse_iterator rend()
        {
            return reverse_iterator(begin());
        }
        
         const_reverse_iterator crbegin()const
        {
            return const_reverse_iterator(cend());
        }
        
         const_reverse_iterator crend()const
        {
            return const_reverse_iterator(cbegin());
        }

提供了begin, end, cbegin, cend, rbegin, rend, crbegin, crend等方法来获取迭代器,分别对应于开始、结束的正向和反向迭代器。

反向迭代器中的rbegin复用正向迭代器中的end操作,反向迭代器中的rend复用正向迭代器中的begin操作。

注意正向迭代器的end是最后一个元素后面一个位置,因为这是循环双向链表,因此end实际上指向的是head头结点。

容量和大小操作:

 
        // 容量
        size_t size()const
        {
            size_t count = 0;
            Node* cur = _head->_next;
            while (cur != _head)
            {
                count++;
                cur = cur->_next;
            }
            
             return count;
        }
        
         bool empty()const
        {
            return _head == _head->_next;
        }
        
         void resize(size_t newsize, const T& value = T())
        {
            size_t oldsize = size();
            if (newsize <= oldsize)
            {
                for (size_t i = newsize; i < oldsize; ++i)
                {
                    pop_back();
                }
            }
            else
            {
                for (size_t i = oldsize; i < newsize; ++i)
                {
                    push_back(value);
                }
            }
        }

size()方法计算链表的大小。注意只有随机访问迭代器才支持迭代器相减的操作。

随机访问迭代器(Random Access Iterator):支持直接相减操作,因为它们可以在常数时间内访问序列中的任何元素。vectordeque 容器提供的迭代器就是随机访问迭代器。list的迭代器并不属于随机访问迭代器,所以size操作只能通过迭代器的移动来计算个数,而不能通过迭代器的相减操作。

empty()检查链表是否为空。

resize()调整链表的大小,根据需要添加或移除元素。

元素访问:

 
        // 元素访问
        T& front()
        {
            return *begin();
        }
        
         const T& front()const
        {
            //return _head->_next->_value;
            return *cbegin();
        }
        
         T& back()
        {
            return *(--end());
        }
        
         const T& back()const
        {
            // return _head->_prev->_value;
            return *(--cend());
        }

front()back()方法分别用于访问链表的第一个元素和最后一个元素。

修改操作:

 
        // 修改
        void push_front(const T& value)
        {
            insert(begin(), value);
        }
        
         void pop_front()
        {
            erase(begin());
        }
        
         void push_back(const T& value)
        {
            insert(end(), value);
        }
        
         void pop_back()
        {
            erase(--end());
        }
        
         iterator insert(iterator it, const T& value)
        {
            Node* pos = it._pNode;
            Node* newNode = new Node(value);
            newNode->_next = pos;
            newNode->_prev = pos->_prev;
            newNode->_prev->_next = newNode;
            pos->_prev = newNode;
            
             return newNode;
        }
        
         iterator erase(iterator it)
        {
            if (it == end())
                return end();
            
             Node* pos = it._pNode;
            Node* ret = pos->_next;
            pos->_prev->_next = pos->_next;
            pos->_next->_prev = pos->_prev;
            delete pos;
            return ret;
        }
        
         void clear()
        {
            auto it = begin();
            while (it != end())
            {
                it = erase(it);
            }
        }
        
         void swap(list<T>& L)
        {
            std::swap(_head, L._head);
        }

功能:在链表的前端插入一个新元素。

实现方式:通过调用insert方法,在begin()位置插入新元素。begin()返回指向链表第一个元素的迭代器。

pop_front()

功能:删除链表的第一个元素。

实现方式:通过调用erase方法,删除begin()位置的元素。这 effectively removes the first element of the list.

push_back(const T& value)

功能:在链表的末尾添加一个新元素。

实现方式:通过调用insert方法,在end()位置插入新元素。由于end()返回的迭代器实际上指向链表尾部的哑元节点,插入操作会在链表的最后一个元素之后插入新元素。

pop_back()

功能:删除链表的最后一个元素。

实现方式:通过调用erase方法,删除--end()位置的元素。--end()操作返回指向链表最后一个元素的迭代器。

insert(iterator it, const T& value)

功能:在指定位置it前插入一个新元素。

实现方式:首先获取it指向的节点pos,然后创建一个新节点newNode,并将其插入到pos前面。更新相邻节点的指针以维持链表的连贯性。最后,返回指向新插入节点的迭代器。

erase(iterator it)

功能:删除指定位置it的元素。

实现方式:首先检查it是否为end(),如果是,则不进行任何操作并返回end()。否则,获取it指向的节点pos,调整前后节点的指针跳过pos,然后删除pos节点,最后返回指向被删除节点下一个节点的迭代器。

clear()

功能:清空链表,删除所有元素。

实现方式:从链表的开始遍历,使用erase方法逐个删除元素,直到整个链表被清空。

swap(list<T>& L)

功能:与另一个链表L交换内容。

实现方式:简单地交换两个链表的头节点指针_head。这是通过std::swap实现的,是一个非常高效的操作,因为它仅仅交换了指针,而不需要移动或复制链表中的元素。

私有成员和方法:

 
    private:
        void CreateHead()
        {
            _head = new Node();
            _head->_next = _head;
            _head->_prev = _head;
        }
        
     private:
        Node* _head;
    };

_head是指向链表头节点的指针。

CreateHead()是一个辅助方法,用于初始化链表,创建一个哨兵节点作为头节点。

结尾

最后,感谢您阅读我的文章,希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点,请随时在评论区留言。

同时,不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中,我将继续探讨这个话题的不同方面,为您呈现更多深度和见解。

谢谢您的支持,期待与您在下一篇文章中再次相遇!