[STL]List的實現

STL（Standard template Library）:c++的標準模板庫

STL是算法和數據結構的軟件框架，它包含了六大組件：算法、迭代器、容器、仿函數、配接器、空間配置器。

迭代器：我們可以把迭代器相當于智能指針，（其實指針也就是一個迭代器）迭代器的類型有：前向迭代器（適用于單鏈表），雙向迭代器（適用于雙向鏈表），隨機迭代器（隨機指向），反向迭代器。

容器：像vector，list，map，set這些都屬于容器。分為序列式容器、關聯式容器及其他容器。

序列式容器：vector、list、deque、string

關聯式容器：set、map、multiset、multimap、hash_set、hash_map、hash_multiset、hash_multimap

其他容器：stack、queue、bitset

仿函數：我們之前在冒泡排序的時候用opertor()模擬實現仿函數，來實現排序的升序和降序。

配接器：是一種設計模式，它在原有類型的基礎上擴展成為另一個接口，使原本因為接口不兼容而不能合作的類型可以一起工作。就類似于電源適配器一樣。這里有應用于容器的適配器，應用于仿函數的適配器，應用于配接器的適配器等。

空間配置器：用戶數據都是保存在內存中的，那么內存的申請釋放（malloc/free）工作都是由“空間配置器”承擔的。標準c++中提供了std::allocator類。

我們今天要模擬實現STL中的list:（STL庫中的list是一個雙向循環且帶頭節點的鏈表）

它的節點原型是這樣的：

template<typename T>
struct ListNode
{
?? ?struct ListNode* _next;???????????? //指向下一個節點，即后繼節點
?? ?struct ListNode* _prev;???????????? //指向前一個節點，即前驅節點
?? ?T _data;
?? ?ListNode(const T& data)
?? ??? ?:_data(data)
?? ??? ?,_next(NULL)
?? ??? ?,_prev(NULL)
?? ?{}
};

我們還要用到迭代器，重載了++、--、*、->、==、!=等操作符。主要實現了以下函數：

begin：指向的是第一個元素的位置，即頭節點的下一個位置；

end：指向的是最后一個元素的下一個位置，即頭節點的位置。

如圖：

對于迭代器，還有一個重要的問題就是迭代器失效的問題，當然迭代器失效和指針指向未知區域的道理是一樣的。存在的原因是刪除的時候，在鏈表中，你刪除一個元素后，指針必須修改位置，即保存起來以便找到下一個位置。

舉個例子（迭代器失效）：

//list.cpp

#include<iostream>
using namespace std;
#include<list>
#include<algorithm>void Print(list<int> l)
{list<int>::iterator it = l.begin();while(it != l.end()){cout<<*it<<" ";++it;}
}int main()
{list<int> l;l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4);list<int>::iterator it = l.begin();while(it != l.end()) {if(*it == 2) {l.erase(it);      //it刪除后不知道指向哪里}++it;}Print(l);return 0;
}

看一下監視窗口：

刪除前：

刪除后：

那么怎么解決迭代器失效問題呢？

只要保存之前it的指向，以便找到下一個指向就ok啦。

	list<int>::iterator it = l.begin();while(it != l.end()){if(*it == 2){it = l.erase(it);       //此處用it來接收解決迭代器失效問題}++it;}

運行結果：

再來說說list，對于庫里邊的list的函數，如push_back,pop_back,push_front,pop_front,Insert,Erase等函數，下面一一實現一下哦。

//List.h

#pragma once
#include<iostream>
using namespace std;
template<typename T>
struct ListNode
{struct ListNode* _next;struct ListNode* _prev;T _data;ListNode(const T& data):_data(data),_next(NULL),_prev(NULL){}
};template<typename T,typename Ref,typename Ptr>
struct ListIterator
{typedef ListNode<T> Node;typedef ListIterator<T,T&,T*> Iterator;typedef ListIterator<T,const T&,const T*> ConstIterator;typedef ListIterator<T,Ref,Ptr> Self;ListIterator(Node* node):_node(node){}bool operator==(const Self& x){return _node == x._node;}bool operator!=(const Self& x){return _node != x._node;}Ref operator*(){return (*_node)._data;}Ref operator*() const{return (*_node)._data;}Ptr operator->(){return &(*_node)._data;}Self& operator++(){_node = (*_node)._next;return *this;}Self operator++(int){Self tmp = *this;++(*this);return tmp;}Self& operator--(){_node = (*_node)._prev;return *this;}Self operator--(int){Self tmp = *this;--(*this);return tmp;}Node* _node;
};template<typename T>
class List
{
public:typedef ListNode<T> Node;typedef ListIterator<T,T&,T*> Iterator;typedef ListIterator<T,const T&,const T*> ConstIterator;
public:Node* BuyNode(const T& data){return new Node(data);}
public:List():_head(BuyNode(T())){_head->_next = _head;_head->_prev = _head;}
public:Iterator Begin()              {return (*_head)._next;}Iterator End(){return _head;}ConstIterator Begin() const{return (*_head)._next;}ConstIterator End() const{return _head;}public:void PushBack(const T& data)              //尾插{Node* tmp = BuyNode(data);Node* tail = _head->_prev;tail->_next = tmp;tmp->_prev = tail;tmp->_next = _head;_head->_prev = tmp;}void PopBack()                //尾刪{Node* del = _head->_prev;Node* pre = del->_prev;Node* next = del->_next;pre->_next = next;next->_prev = pre;delete del;}void PushFront(const T& data)          //頭插{Node* tmp = BuyNode(data);Node* next = _head->_next;_head->_next = tmp;tmp->_prev = _head;tmp->_next = next;next->_prev = tmp;}void PopFront()               //頭刪{Node* prev = _head->_prev;Node* next = _head->_next;prev->_next = next;next->_prev = prev;_head = next;}Iterator Insert(Iterator pos,const T& data)      //某一個位置前插入{Node* tmp = BuyNode(data);Node* prev = pos._node->_prev;Node* cur = pos._node;prev->_next = tmp;tmp->_prev = prev;tmp->_next = cur;cur->_prev = tmp;return tmp;}ConstIterator Insert(ConstIterator pos,const T& data)      //某一個位置前插入{Node* tmp = BuyNode(data);Node* prev = pos._node->_prev;Node* cur = pos._node;prev->_next = tmp;tmp->_prev = prev;tmp->_next = cur;cur->_prev = tmp;return tmp;}Iterator Erase(Iterator pos)            //刪除某個位置{assert(pos._node && pos._node != _head);    //判斷節點是否為空，或只剩一個頭節點Node* prev = pos._node->_prev;Node* next = pos._node->_next;prev->_next = next;next->_prev = prev;delete pos._node;return Iterator(next);           //返回下一個位置}bool Empty()        //判斷鏈表是否為空{return _head == _head->_next;}T& Front(){return _head->_next->_data;}T& Back(){return _head->_prev->_data;}const T& Front() const{return _head->_next->_data;}const T& Back() const{return _head->_prev->_data;}void Swap(List<T>& l){swap(_head,l._head);}template<typename InputIterator>void Insert(Iterator pos,InputIterator first,InputIterator last){while(first != last){Insert(pos,*first);++first;}}void Insert(Iterator pos,ConstIterator first,ConstIterator last)  //在pos位置插入一段區間{for(;first != last;++first)Insert(pos,*first);}
private:Node* _head;
};void PrintList(List<int>& l)
{List<int>::Iterator it = l.Begin();while(it != l.End()){cout<<*it<<" ";++it;}cout<<endl;
}

//List.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
#include<vector>
int main()
{List<int> l;List<int> l1;const List<int> l3;l.PushBack(1);l.PushBack(2);l.PushBack(3);l.PushBack(4);l.PopBack();PrintList(l);l.PushFront(0);PrintList(l);l.PopFront();l.Insert(l.End(),4);l.Insert(l.Begin(),0);PrintList(l);cout<<"Front:"<<l.Front()<<endl;cout<<"Back:"<<l.Back()<<endl;cout<<"Empty:"<<l.Empty()<<endl;l1.Swap(l);PrintList(l1);PrintList(l);l.PushBack(10);l.PushBack(11);l.PushBack(12);l1.Insert(l1.Begin(),l.Begin(),l.End());PrintList(l1);vector<int> v;v.push_back(55);v.push_back(66);l1.Insert(l1.Begin(),v.begin(),v.end());PrintList(l1);char str[] = {'a','b'};l1.Insert(l1.Begin(),str,str+2);PrintList(l1);return 0;
}

運行結果：