【c++】STL--List的实现

   

     

目录

一.  List的数据结构

二.  List实现的基本框架

1. list的结点结构类      

 2. List的迭代器类

正向迭代器

反向迭代器

3. List操作接口的实现

 1. 默认成员函数

构造函数 和 析构函数   

拷贝构造函数 和 赋值运算符重载

2. 修改相关函数接口 

insert 和 erase

push_back 和 push_front

pop_front 和 pop_back

 3. 迭代器相关接口

begin() 和 end()

rbegin() 和 rend()

  4. 其他相关函数接口

      swap                  

      clear

      Head_init 

三.  完整源代码实现

---

---

                      

一.  List的数据结构

     list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代，其底层是带头双向循环链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向 其前一个元素和后一个元素，即list实现上就是一个双向循环链表，list节点 有prev 和 next 两个指针。        

     使用链表存储数据，并不会将它们存储到一整块连续的内存空间中。恰恰相反，各元素占用的存储空间（又称为节点）是独立的、分散的，它们之间的线性关系通过指针来维持的

二.  List实现的基本框架

   List的实现需要实现三个类 （类模板形式）    

         list的结点结构类

         List的迭代器类

         List功能的实现类

1. list的结点结构类      

      对节点的定义如下：

    //list结点类模板template <class T>struct listnode{        listnode* prev;        listnode* next;T data;                //结点的构造函数,完成对节点的初始化listnode(const T& val = T())            :prev(nullptr),next(nullptr),data(val){}};

     可以看到，list 容器定义的每个节点中，都包含 *prev、*next 和 data。其中，prev 指针用于指向前一个节点；next 指针用于指向后一个节点；data用于存储当前元素的值。

 2. List的迭代器类

List 的迭代器迭代器有两种实现方式，具体应根据容器底层数据结构实现：

    1. 原生态指针，比如：vector

    2. 将原生态指针进行封装，因迭代器使用形式与指针完全相同，因此在自定义的类中须实现以下方法：

           1. 指针可以解引用，迭代器的类中必须重载operator*()

           2. 指针可以通过->访问其所指空间成员，迭代器类中必须重载oprator->()

           3. 指针可以++向后移动，迭代器类中必须重载operator++()与operator++(int)至于  operator--()/operator--(int)释放需要重载，根据具体的结构来抉择，双向链表可以向前移动，所以需要重载，如果是forward_list就不需要重载--

           4. 迭代器需要进行是否相等的比较，因此还需要重载operator==()与operator!=()

        和 vector 容器迭代器的实现方式不同，由于 list 容器的元素并不是连续存储的，所以该容器迭代器中，必须包含一个可以指向 list 容器的指针，并且该指针还可以借助重载的 *、++、--、->、==、!= 等运算符，实现迭代器正确的递增、递减、取值等操作，以达到 vector 迭代器的同等效果

      

正向迭代器

   list 容器正向迭代器的实现代码如下：    

    //list正向迭代器类template <class T, class Ref, class Ptr>struct _list_iterator{typedef listnode<T> Node; //在迭代器中实例化结点模板typedef _list_iterator<T, Ref, Ptr> self; //对迭代器的类型重命名，已达简化        //构造_list_iterator(Node* node = nullptr):_node(node){}        // 迭代器支持移动// 前置++self& operator++(){_node = _node->next;return *this;}//后置++self operator++(int){self tmp(*this);++_node;return tmp;}//前置--self& operator--(){_node = _node->prev;return *this;}//后置--self operator--(int){self tmp(*this);--_node;return tmp;}            // 具有指针类似行为Ref operator*(){return _node->data;}              //当结点数据类型仍然为自定义结构时Ptr operator->(){return &_node->data;}                // 迭代器支持比较bool operator!=(const self& s) const{return _node != s._node;}bool operator==(const self& s) const{return _node == s._node;}        Node* _node;};

反向迭代器

  list 容器反向迭代器的实现代码如下：

    //list反向迭代器类template <class Iterator, class Ref, class Ptr>struct _list_reverse_iterator{typedef _list_reverse_iterator<Iterator, Ref, Ptr> self;         //构造_list_reverse_iterator(Iterator it):_cur(it){}        // 迭代器支持移动//前置++self& operator++(){--_cur;return *this;}//后置++self operator++(int){self tmp(*this);--_cur;return tmp;}//前置--self& operator--(){++_cur;return *this;}//后置--self operator--(int){self tmp(*this);++_cur;return tmp;}        // 具有指针类似行为Ref operator*(){Iterator tmp = _cur;return *--tmp;}Ptr operator->(){return &(*_cur);}        // 迭代器支持比较bool operator!=(const self& s) const{return _cur != s._cur;}bool operator==(const self& s) const{return _cur == s._cur;}Iterator _cur;};

3. List操作接口的实现

 1. 默认成员函数

     构造函数 和 析构函数   

 以下，创建了空的 list 容器（即无参的构造函数），但它也包含有 1 个节点。

    除此之外，list 模板类中还提供有带参的构造函数，它们的实现过程大致分为以下 2 步：

            1. 调用 Head_init() 函数，构造带有头节点的空 list 容器链表；     

             2. 将各个参数按照次序插入到空的 list 容器链表中。

//构造函数list(){Head_init(); //初始化头结点}              //构造n个值为val的节点链表的构造函数list(int n, const T& val = T()){Head_init(); //对链表头结点初始化while (n--)  //依次尾插n各值为val的结点{push_back(val);}}//迭代器区间构造template <class Iterator>list(Iterator first, Iterator last){Head_init();while (first != last){push_back(*first);++first;}}                 //析构函数~list(){clear(); //清空链表结点delete _head; //释放头结点_head = nullptr; //头结点置空}

                       

拷贝构造函数 和 赋值运算符重载

        //拷贝构造list(const list<T>& lt){Head_init(); //初始化for (const auto& e : lt){push_back(e);}}        //赋值运算符重载list<T>& operator=(list<T> lt){swap(lt); //交换两者数据，交换两者头结点的指针即可return *this;}

2. 修改相关函数接口 

     insert 和 erase

   insert : 通过在指定位置的元素之前插入新元素(插入位置是任意的)                       

        //在pos位置插入一个结点iterator insert(iterator pos, const T& val){Node* newnode = new Node(val); //申请一个新节点Node* curnode = pos._node;  //pos位置的结点newnode->prev = curnode->prev; //先与当前结点的前一个结点链接上curnode->prev->next = newnode;newnode->next = curnode; //在与当前结点链接curnode->prev = newnode;return newnode; //返回新插入结点的迭代器}

说明：此在list中进行插入时是不会导致list的迭代 器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响

注意：节点的连接顺序，先连后断

erase: 删除所指向的位置的结点（删除位置是任意的）

        //删除pos位置的结点iterator erase(iterator pos){assert(pos != end());Node* curnode = pos._node; //保存要删除的结点Node* nextnode = curnode->next; //删除结点的下一结点curnode->prev->next = nextnode;nextnode->prev = curnode->prev;delete curnode;return nextnode; //返回删除结点的后一个结点的迭代器}

说明：list 在删除一个结点时会存在迭代器失效，(即被删除的那个位置的迭代器失效)，

push_back 和 push_front

尾插

在end()迭代器所在的位置的前一个结点之后插入新的结点

        //尾插void push_back(const T& val){/*Node* newnode = new Node(val);Node* tail = _head->prev;tail->next = newnode;newnode->prev = tail;newnode->next = _head;_head->prev = newnode;*/            //复用insertinsert(end(), val);}

在end()位置之前插入一个结点（即在尾部插入结点）

                         

头插

在begin()迭代器所在的位置之前插入新的结点

        //头插void push_front(const T& val){insert(begin(), val); //复用insert}

pop_front 和 pop_back

头删

删除begin()迭代器所在的位置的结点

        //头删void pop_front(){erase(begin()); //复用erase}

尾删

删除end()迭代器所在的位置的前一个结点

        //尾删void pop_back(){erase(--end()); }

 3. 迭代器相关接口

     begin() 和 end()

        iterator begin(){return iterator(_head->next);//构造匿名对象            //return _head->next; //隐式类型转换}iterator end(){return iterator(_head);            //return _head; }        //const的迭代器const_iterator begin() const{return const_iterator(_head->next);            //return _head->next;}const_iterator end() const{return const_iterator(_head);            //return _head;}

rbegin() 和 rend()

        reverse_iterator rbegin() {return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}        //const的反向迭代器const_reverse_iterator rbegin() const{return const_reverse_iterator(end());}const_reverse_iterator rend() const{return const_reverse_iterator(begin());}

  4. 其他相关函数接口

         swap                  

    用于交换两对象的数据的内容，实际改变头结点的指针的指向           

        void swap(list<T>& tmp){std::swap(_head, tmp._head);}

      clear

清空链表结点（头结点除外） 

        void clear(){iterator it = begin();while (it != end()){it = erase(it);}}

      Head_init 

       初始化头结点                    

        //初始化头结点        void Head_init(){_head = new Node; //申请一个空白结点（头结点）_head->next = _head; _head->prev = _head;}

三.  完整源代码实现

    //list结点类template <class T>struct listnode{T data;listnode* prev;listnode* next;listnode(const T& val = T()):data(val),prev(nullptr),next(nullptr){}};//list正向迭代器类template <class T, class Ref, class Ptr>struct _list_iterator{typedef listnode<T> Node;typedef _list_iterator<T, Ref, Ptr> self;Node* _node;_list_iterator(Node* node):_node(node){}//前置++self& operator++(){_node = _node->next;return *this;}//后置++self operator++(int){self tmp(*this);++_node;return tmp;}//前置--self& operator--(){_node = _node->prev;return *this;}//后置--self operator--(int){self tmp(*this);--_node;return tmp;}Ref operator*(){return _node->data;}Ptr operator->(){return &_node->data;}bool operator!=(const self& s) {return _node != s._node;}bool operator==(const self& s){return _node == s._node;}};//list反向迭代器类template <class Iterator, class Ref, class Ptr>struct _list_reverse_iterator{typedef _list_reverse_iterator<Iterator, Ref, Ptr> self;_list_reverse_iterator(Iterator it):_cur(it){}//前置++self& operator++(){--_cur;return *this;}//后置++self operator++(int){self tmp(*this);--_cur;return tmp;}//前置--self& operator--(){++_cur;return *this;}//后置--self operator--(int){self tmp(*this);++_cur;return tmp;}Ref operator*(){Iterator tmp = _cur;return *--tmp;}Ptr operator->(){return &(*_cur);}bool operator!=(const self& s){return _cur != s._cur;}bool operator==(const self& s){return _cur == s._cur;}Iterator _cur;};//list类template <class T>class list{typedef listnode<T> Node;public:typedef _list_iterator<T, T&, T*>  iterator;typedef _list_iterator<T, const T&, const T*>  const_iterator;typedef _list_reverse_iterator<iterator, T&, T*>  reverse_iterator;typedef _list_reverse_iterator<const_iterator, const T&, const T*>  const_reverse_iterator;iterator begin(){return iterator(_head->next);}iterator end(){return iterator(_head);}const_iterator begin() const{return const_iterator(_head->next);}const_iterator end() const{return const_iterator(_head);}reverse_iterator rbegin() {return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}const_reverse_iterator rbegin() const{return const_reverse_iterator(end());}const_reverse_iterator rend() const{return const_reverse_iterator(begin());}void Head_init(){_head = new Node;_head->next = _head;_head->prev = _head;}//构造函数list(){Head_init();}list(int n, const T& val = T()){Head_init();while (n--){push_back(val);}}//迭代器区间构造template <class Iterator>list(Iterator first, Iterator last){Head_init();while (first != last){push_back(*first);++first;}}//拷贝构造list(const list<T>& lt){Head_init();for (const auto& e : lt){push_back(e);}}void swap(list<T>& tmp){std::swap(_head, tmp._head);}//赋值运算符重载list<T>& operator=(list<T> lt){swap(lt);return *this;}//析构~list(){clear();delete _head;_head = nullptr;}//在pos位置插入一个结点iterator insert(iterator pos, const T& val){Node* newnode = new Node(val);Node* curnode = pos._node;newnode->prev = curnode->prev;curnode->prev->next = newnode;newnode->next = curnode;curnode->prev = newnode;return newnode;}//删除pos位置的结点iterator erase(iterator pos){assert(pos != end());Node* curnode = pos._node;Node* nextnode = curnode->next;curnode->prev->next = nextnode;nextnode->prev = curnode->prev;delete curnode;return nextnode;}//尾插void push_back(const T& val){/*Node* newnode = new Node(val);Node* tail = _head->prev;tail->next = newnode;newnode->prev = tail;newnode->next = _head;_head->prev = newnode;*/insert(end(), val);}//头插void push_front(const T& val){insert(begin(), val);}//尾删void pop_back(){erase(--end());}//头删void pop_front(){erase(begin());}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}private:Node* _head;};

                   

---

                      

本文链接：https://www.kjpai.cn/news/2024-03-31/151747.html，文章来源：网络cs，作者：胡椒，版权归作者所有，如需转载请注明来源和作者，否则将追究法律责任！