STL之list

list简单介绍

• list是STL的一个序列式容器，底层的实现是一个双向链表，每个节点有两个指针分别指向前一个元素和后一个元素
  
• list在恣意位置的插入与删除元素的效率很高，但是它访问元素的效率就相对比较低，它不支持恣意位置的访问
  

list与vector的对比

这里不介绍list的利用，因为它和vector大部分的接口是一样的，不了解vector的可以去看
STL之vector
差别点

• 迭代器失效的题目:vector的迭代器在插入删除时都可能导致迭代器失效但是list在插入时迭代器是不会失效的
  
• vector访问元素的效率很高它能快速访问恣意位置的数据，但是其插入与删除元素的效率极低，而list刚好与之相反
  
• 需要大量随时访问元素时优先考虑利用vector，而要求插入删除的效率更高时优先考虑list
  

list的模拟实现

需要的类模板

• ’节点类
  
  2.     // List的节点类
  3.    template<class T>
  4.     struct ListNode
  5.     {
  6.         ListNode(const T& val = T())
  7.             :_pPre(nullptr),
  8.             _pNext(nullptr),
  9.             _val(val)
  10.         {}
  11.         ListNode<T>* _pPre;
  12.         ListNode<T>* _pNext;
  13.         T _val;

  复制代码
  2.迭代器类
  
  1. //List的迭代器类
  2.     template<class T, class Ref, class Ptr>
  3.     class ListIterator
  4.          template<class T, class Ref, class Ptr>
  5.     class ListIterator
  6.     {
  7.         typedef ListNode<T>* PNode;
  8.         typedef ListIterator<T, Ref, Ptr> Self;
  9.     public:
  10.         ListIterator(PNode pNode = nullptr)
  11.             : _pNode(pNode)
  12.         {
  13.         }
  14.         ListIterator(const Self& l)
  15.             : _pNode(l._pNode)
  16.         {}
  17.         
  18. //运算符重载               
  19.         T& operator*()
  20.         {
  21.             return _pNode->_val;
  22.         }
  23.         T* operator->()
  24.         {
  25.             return & _pNode->_val;
  26.         }
  27.         Self& operator++()
  28.         {
  29.             _pNode = _pNode->_pNext;
  30.             return *this;
  31.         }
  32.         Self operator++(int)
  33.         {
  34.             Self tmp(*this);
  35.             _pNode = _pNode->_pNext;
  36.             return tmp;
  37.         }
  38.         Self& operator--()
  39.         {
  40.             _pNode = _pNode->_pPre;
  41.             return *this;
  42.         }
  43.         Self& operator--(int)
  44.         {
  45.             Self tmp(*this);
  46.             _pNode = _pNode->_pPre;
  47.             return tmp;
  48.         }
  49.         bool operator!=(const Self& l)
  50.         {
  51.             return _pNode != l._pNode;
  52.         }
  53.         bool operator==(const Self& l)
  54.         {
  55.             return _pNode == l._pNode;
  56.         }
  57.   
  58.         PNode _pNode;

  复制代码
  为了减少代码的冗余以是将 ListNode*，ListIterator<T, Ref, Ptr>，用typedef举行封装
  3.list类
  
  1. template<class T>
  2.     class list
  3.     {
  4.         typedef ListNode<T> Node;
  5.         typedef Node* PNode;
  6.     public:
  7.         typedef ListIterator<T, T&, T*> iterator;
  8.         typedef ListIterator<T, const T&, const T&> const_iterator;
  9.             private:
  10.         void CreateHead()
  11.         {
  12.             _pHead = new Node;
  13.             _pHead->_pPre = _pHead;
  14.             _pHead->_pNext = _pHead;
  15.         }
  16.         PNode _pHead;

  复制代码

同意为了减少代码的冗余以是用typedef举行封装
构造与析构

调用接口CreateHead()和push_back()很轻易实现构造

1. list()
2.         {
3.             CreateHead();
4.         }
5.         list(int n, const T& value = T())
6.         {
7.             CreateHead();
8.             for (int i = 0; i < n; ++i)
9.                 push_back(value);
10.         }
11. template <class Iterator>
12.         list(Iterator first, Iterator last)
13.         {
14.             CreateHead();
15.             while (first != last)
16.             {
17.                 push_back(*first);
18.                 ++first;
19.             }
20.         }
21.         list(const list<T>& l)
22.         {
23.             CreateHead();
25.             // 用l中的元素构造临时的temp,然后与当前对象交换
26.             list<T> temp(l.begin(), l.end());
27.             this->swap(temp);
28.         }
29.         list<T>& operator=(list<T> l)
30.         {
31.             this->swap(l);
32.             return *this;
33.         }
34.         ~list()
35.         {
36.             clear();
37.             delete _pHead;
38.             _pHead = nullptr;
39.         }

复制代码

迭代器

两种迭代器运用函数的重载即可实现

1. iterator begin()
2.         {
3.             return iterator(_pHead->_pNext);
4.         }
5.         iterator end()
6.         {
7.             return iterator (_pHead);
8.         }
9.         const_iterator begin() const
10.         {
11.             return const_iterator ( _pHead->_pNext);
12.         }
13.         const_iterator end() const
14.         {
15.             return const_iterator (_pHead);
16.         }

复制代码

容量

1.   size_t size()const
2.         {
3.             PNode cur = _pHead->_pNext;
4.             size_t count = 0;
5.             while (cur != _pHead)
6.             {
7.                 count++;
8.                 cur = cur->_pNext;
9.             }
11.             return count;
12.         }
13.         bool empty()const
14.         {
15.             return _pHead->_pNext == _pHead;
16.         }

复制代码

获取元素

返回相应值即可

1. T& front()
2.         {
3.             return _pHead->_pNext->_val;
4.         }
5.         const T& front()const
6.         {
7.             return  _pHead->_pNext->_val;
8.         }
9.         T& back()
10.         {
11.             return _pHead->_pPre->_val;
12.         }
13.         const T& back()const
14.         {
15.             return _pHead->_pPre->_val;
16.         }

复制代码

修改

1. void push_back(const T& val) { insert(end(), val); }
2.         void pop_back() { erase(--end()); }
3.         void push_front(const T& val) { insert(begin(), val); }
4.         void pop_front() { erase(begin());

复制代码

运用迭代器和insert()erase()接口
insert的实现

1. iterator insert(iterator pos, const T& val)
2.         {
3.             Node* pNewNode = new Node(val);
4.             Node* pCur = pos._pNode;
5.   
6.             pNewNode->_pPre = pCur->_pPre;
7.             pNewNode->_pNext = pCur;
8.             pNewNode->_pPre->_pNext = pNewNode;
9.             pCur->_pPre = pNewNode;
10.             return iterator(pNewNode);
11.         }

复制代码

起首创建一个的节点Node让它的向前指针指向pos节点的前一个节点，它的向后指针指向pos位置的节点
然后再让pos位置的前一个节点的向后的指针指向新的节点Node，pos位置的向前指针指向新节点Node即可
erase的实现

1. iterator erase(iterator pos)
2.         {
3.             Node* pDel = pos._pNode;
4.             Node* pRet = pDel->_pNext;
5.             pDel->_pPre->_pNext = pDel->_pNext;
6.             pDel->_pNext->_pPre = pDel->_pPre;
7.             delete pDel;
8.             return iterator(pRet);
9.         }

复制代码

起首保存被删除节点的指针用pDel保存，因为erase返回的是被删除节点的下一个节点的迭代器以是我们也要将其保存在pRet中，然后就就简单了，将被删节点的后一个节点的向前指针指向被删节点的前一个节点，将被删节点的前一个节点的向后指针指向被删除指针的反面一个节点即可。

1. void clear()
2.         {
3.             PNode cur = _pHead->_pNext;
4.             while (cur != _pHead)
5.             {
6.                 _pHead->_pNext = cur->_pNext;
7.                 delete cur;
8.                 cur = _pHead->_pNext;
9.             }
10.             _pHead->_pNext = _pHead->_pPre = _pHead;
11.         }
12.         void swap(list<T>& l)
13.         {
14.             std::swap(_pHead, l._pHead);
15.         }

复制代码

clear()遍历list删除即可，swap()用std的swap接口

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。