目录

1.List

2.list 模拟实现

2.1基本框架

2.2 list_node

2.3 list

2.3.1 默认构造

2.3.2 析构函数

2.3.3 begin（）

2.3.4 end（）

2.3.5 size（）

2.3.6 empty（）

2.3.7 insert（）

2.3.8 push_back()

2.3.9 push_front（）

2.3.10 erase （）

2.3.11 pop_back()

2.3.12 pop_front()

2.4 list_iterator

2.4.1 - >

2.4.2 *

2.4.3 前置++

2.4.4 后置++

2.4.5 前置--

2.4.6 后置 --

2.4.7 ！=

2.4.8 list_iterator完整代码

2.5 list_const_iterator

3.整个实现完整代码

1.List

• List是连续的容器，而vector是非连续的容器，即list将元素存储在连续的存储器中，而vector存储在不连续的存储器中。

• 向量（vector）中间的插入和删除是非常昂贵的，因为它需要大量的时间来移动所有的元素。链表克服了这个问题，它是使用list容器实现的。

• List支持双向，并为插入和删除操作提供了一种有效的方法。

• 在列表中遍历速度很慢，因为列表元素是按顺序访问的，而vector支持随机访问。

2.list 模拟实现

2.1基本框架

list_node来实现每个节点，list_iterator和list_const_iterator是两个不同版本的迭代器一个是普通迭代器一个是const类型的迭代器，名字上也有所区分，list本身就有迭代器的效果，这个是为了模拟这个，重载了一些基本运算符，而list是统一管理节点，具有增删查改等效果

#define _CRT_SECURE_NO_WARNINGS 1 #include  #include  #include  // For std::reverse  using namespace std;  namespace List {     // 节点类     template     class list_node     {     public:         T _data;         list_node* _next;         list_node* _prev;          list_node(const T& data = T())             : _data(data)             , _next(nullptr)             , _prev(nullptr)         {}     };  //list迭代器     template     struct list_iterator     {         typedef list_node Node;         typedef list_iterator Self;          Node* _node;          list_iterator(Node* node)             : _node(node)         { }                     };  //const版本迭代器     template     struct list_const_iterator     {         typedef list_node Node;         typedef list_const_iterator Self;          Node* _node;          // 修正: list_const_iterator 的构造函数应该接受 Node* 类型         list_const_iterator(Node* node)             : _node(node)         { }           }; //实现list     template     class list     {         typedef list_node Node;     public:         typedef list_iterator iterator;         typedef list_const_iterator const_iterator;          list()         {             _head = new Node(T());             _head->_next = _head;             _head->_prev = _head;             _size = 0;         }           ~list()         {             while (!empty())             {                 pop_front();             }             delete _head;         }      private:         Node* _head;         size_t _size;     };     } 

2.2 list_node

定义节点

  template   class list_node   {   public:       T _data;       list_node* _next;       list_node* _prev;        list_node(const T& data = T())           : _data(data)           , _next(nullptr)           , _prev(nullptr)       {}   };

2.3 list

维护节点

//实现list     template     class list     {         typedef list_node Node;     public:         typedef list_iterator iterator;         typedef list_const_iterator const_iterator;          list()         {             _head = new Node(T());             _head->_next = _head;             _head->_prev = _head;             _size = 0;         }           ~list()         {             while (!empty())             {                 pop_front();             }             delete _head;         }      private:         Node* _head;         size_t _size;     }; 

2.3.1 默认构造

//默认构造   list()  {      _head = new Node(T());      _head->_next = _head;      _head->_prev = _head;      _size = 0;  }  

2.3.2 析构函数

//析构函数   ~list()  {      while (!empty())      {          pop_front();      }      delete _head;  }

2.3.3 begin（）

开始位置的迭代器

//begin（）   iterator begin()  {      return iterator(_head->_next);  }  //const   const_iterator begin() const  {      return const_iterator(_head->_next);  } 

2.3.4 end（）

结尾位置的迭代器

//普通版   iterator end()  {      return iterator(_head);  }   //const版   const_iterator end() const  {      return const_iterator(_head);  }   

2.3.5 size（）

数据个数

size_t size() const  {      return _size;  }   

2.3.6 empty（）

判空

bool empty() const  {      return _size == 0;  }   

2.3.7 insert（）

指定位置插入

void insert(iterator pos, const T& x)  {      Node* cur = pos._node;      Node* prev = cur->_prev;      Node* newnode = new Node(x);       //prev newnode cur      newnode->_next = cur;      cur->_prev = newnode;      newnode->_prev = prev;      prev->_next = newnode;       ++_size;  }  

2.3.8 push_back()

尾插

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

2.3.9 push_front（）

头插

void push_front(const T& x)  {      insert(begin(), x);  }   

2.3.10 erase （）

指定位置删除

void erase(iterator pos)  {      assert(pos != end());      Node* prev = pos._node->_prev;      Node* next = pos._node->_next;       prev->_next = next;      next->_prev = prev;      delete pos._node;      --_size;  } 

2.3.11 pop_back()

尾删

 void pop_back()  {      erase(--end());  }  

2.3.12 pop_front()

头删

   void pop_front()  {      erase(begin());  }

2.3.13 list完整代码

  template   class list   {       typedef list_node Node;   public:       typedef list_iterator iterator;       typedef list_const_iterator const_iterator;        list()       {           _head = new Node(T());           _head->_next = _head;           _head->_prev = _head;           _size = 0;       }        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);       }        size_t size() const       {           return _size;       }        bool empty() const       {           return _size == 0;       }        void insert(iterator pos, const T& x)       {           Node* cur = pos._node;           Node* prev = cur->_prev;           Node* newnode = new Node(x);            //prev newnode cur           newnode->_next = cur;           cur->_prev = newnode;           newnode->_prev = prev;           prev->_next = newnode;            ++_size;       }        void push_back(const T& x)       {           insert(end(), x);       }        void push_front(const T& x)       {           insert(begin(), x);       }        void erase(iterator pos)       {           assert(pos != end());           Node* prev = pos._node->_prev;           Node* next = pos._node->_next;            prev->_next = next;           next->_prev = prev;           delete pos._node;           --_size;       }        void pop_back()       {           erase(--end());       }        void pop_front()       {           erase(begin());       }        ~list()       {           while (!empty())           {               pop_front();           }           delete _head;       }    private:       Node* _head;       size_t _size;   };

2.4 list_iterator

为了支持list迭代器效果而模拟实现了一个迭代器

 template  struct list_iterator  {      typedef list_node Node;      typedef list_iterator Self;       Node* _node;       list_iterator(Node* node)          : _node(node)      { }        };

2.4.1 - >

 // 修正: 返回指向 _data 的指针，而不是引用      T* operator->()      {          return &_node->_data;      } 

2.4.2 *

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

2.4.3 前置++

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

2.4.4 后置++

  Self operator++(int)      {          Self tmp(*this);          _node = _node->_next;          return tmp;      }      

2.4.5 前置--

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

2.4.6 后置 --

      Self operator--(int)      {          Self tmp(*this);          _node = _node->_prev;          return tmp;      }       

2.4.7 ！=

bool operator!=(const Self& x) const      {          return _node != x._node;      } 

2.4.8 list_iterator完整代码

 template  struct list_iterator  {      typedef list_node Node;      typedef list_iterator Self;       Node* _node;       list_iterator(Node* node)          : _node(node)      { }       // 修正: 返回指向 _data 的指针，而不是引用      T* operator->()      {          return &_node->_data;      }       T& operator*()      {          return _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;      }       bool operator!=(const Self& x) const      {          return _node != x._node;      }  };

2.5 list_const_iterator

list_const_iterator和list_iterator实现原理一致，只是有些成员函数被const修饰，typedef了const 

 template  struct list_const_iterator  {      typedef list_node Node;      typedef list_const_iterator Self;       Node* _node;       // 修正: list_const_iterator 的构造函数应该接受 Node* 类型      list_const_iterator(Node* node)          : _node(node)      { }       // 修正: 返回指向 _data 的 const 指针，而不是引用      const T* operator->() const      {          return &_node->_data;      }       const T& operator*() const      {          return _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;      }       bool operator!=(const Self& x) const      {          return _node != x._node;      }  }; 

3.整个实现完整代码

#define _CRT_SECURE_NO_WARNINGS 1 #include  #include  #include  // For std::reverse  using namespace std;  namespace List {     // 节点类     template     class list_node     {     public:         T _data;         list_node* _next;         list_node* _prev;          list_node(const T& data = T())             : _data(data)             , _next(nullptr)             , _prev(nullptr)         {}     };      template     struct list_iterator     {         typedef list_node Node;         typedef list_iterator Self;          Node* _node;          list_iterator(Node* node)             : _node(node)         { }          // 修正: 返回指向 _data 的指针，而不是引用         T* operator->()         {             return &_node->_data;         }          T& operator*()         {             return _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;         }          bool operator!=(const Self& x) const         {             return _node != x._node;         }     };      template     struct list_const_iterator     {         typedef list_node Node;         typedef list_const_iterator Self;          Node* _node;          // 修正: list_const_iterator 的构造函数应该接受 Node* 类型         list_const_iterator(Node* node)             : _node(node)         { }          // 修正: 返回指向 _data 的 const 指针，而不是引用         const T* operator->() const         {             return &_node->_data;         }          const T& operator*() const         {             return _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;         }          bool operator!=(const Self& x) const         {             return _node != x._node;         }     };      template     class list     {         typedef list_node Node;     public:         typedef list_iterator iterator;         typedef list_const_iterator const_iterator;          list()         {             _head = new Node(T());             _head->_next = _head;             _head->_prev = _head;             _size = 0;         }          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);         }          size_t size() const         {             return _size;         }          bool empty() const         {             return _size == 0;         }          void insert(iterator pos, const T& x)         {             Node* cur = pos._node;             Node* prev = cur->_prev;             Node* newnode = new Node(x);              //prev newnode cur             newnode->_next = cur;             cur->_prev = newnode;             newnode->_prev = prev;             prev->_next = newnode;              ++_size;         }          void push_back(const T& x)         {             insert(end(), x);         }          void push_front(const T& x)         {             insert(begin(), x);         }          void erase(iterator pos)         {             assert(pos != end());             Node* prev = pos._node->_prev;             Node* next = pos._node->_next;              prev->_next = next;             next->_prev = prev;             delete pos._node;             --_size;         }          void pop_back()         {             erase(--end());         }          void pop_front()         {             erase(begin());         }          ~list()         {             while (!empty())             {                 pop_front();             }             delete _head;         }      private:         Node* _head;         size_t _size;     };      void test1()     {         list lt;         lt.push_back(1);         lt.push_back(2);          list::iterator it = lt.begin();         while (it != lt.end())         {             cout << *it << " ";             ++it;         }         cout << endl;     } }