C++中的list
namespace wolf
{
// List的节点类
template<class T>
struct ListNode
{
ListNode(const T& val = T())
: _pPre(nullptr)
, _pNext(nullptr)
, _val(val)
{}
ListNode<T>* _pPre;
ListNode<T>* _pNext;
T _val;
};
/*
List 的迭代器
迭代器有两种实现方式，具体应根据容器底层数据结构实现：
1. 原生态指针，比如：vector
2. 将原生态指针进行封装，因迭代器使用形式与指针完全相同，因此在自定义的类中必须实现以下方法：
1. 指针可以解引用，迭代器的类中必须重载operator*()
2. 指针可以通过->访问其所指空间成员，迭代器类中必须重载oprator->()
3. 指针可以++向后移动，迭代器类中必须重载operator++()与operator++(int)
至于operator--()/operator--(int)释放需要重载，根据具体的结构来抉择，双向链表可以向前
移动，所以需要重载，如果是forward_list就不需要重载--
4. 迭代器需要进行是否相等的比较，因此还需要重载operator==()与operator!=()
*/
template<class T, class Ref, class Ptr>
class ListIterator
{
typedef ListNode<T>* PNode;
typedef ListIterator<T, Ref, Ptr> Self;
public:
ListIterator(PNode pNode = nullptr)
: _pNode(pNode)
{}
ListIterator(const Self& l)
: _pNode(l._pNode)
{}
T& operator*(){return _pNode->_val;}
T* operator->(){return &(operator*());}
Self& operator++()
{
_pNode = _pNode->_pNext;
return *this;
}
Self operator++(int)
{
Self temp(*this);
_pNode = _pNode->_pNext;
return temp;
}
Self& operator--();
Self& operator--(int);
bool operator!=(const Self& l){return _pNode != l._pNode;}
bool operator==(const Self& l){return _pNode != l._pNode;}
PNode _pNode;
};
template<class T>
class list
{
typedef ListNode<T> Node;
typedef Node* PNode;
public:
typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T, const T&, const T&> const_iterator;
public:
///
// List的构造
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();
// 用l中的元素构造临时的temp,然后与当前对象交换
list<T> temp(l.cbegin(), l.cend());
this->swap(temp);
}
list<T>& operator=(const list<T> l)
{
this->swap(l);
return *this;
}
~list()
{
clear();
delete _pHead;
_pHead = nullptr;
}
///
// List Iterator
iterator begin(){return iterator(_pHead->_pNext);}
iterator end(){return iterator(_pHead);}
const_iterator begin(){return const_iterator(_pHead->_pNext);}
const_iterator end(){return const_iterator(_pHead);}
///
// List Capacity
size_t size()const;
bool empty()const;
// List Access
T& front();
const T& front()const;
T& back();
const T& back()const;
// List Modify
void push_back(const T& val){insert(begin(), val);}
void pop_back(){erase(--end());}
void push_front(const T& val){insert(begin(), val);}
void pop_front(){erase(begin());}
// 在pos位置前插入值为val的节点
iterator insert(iterator pos, const T& val)
{
PNode pNewNode = new Node(val);
PNode pCur = pos._pNode;
// 先将新节点插入
pNewNode->_pPre = pCur->_pPre;
pNewNode->_pNext = pCur;
pNewNode->_pPre->_pNext = pNewNode;
pCur->_pPre = pNewNode;
return iterator(pNewNode);
}
// 删除pos位置的节点，返回该节点的下一个位置
iterator erase(iterator pos)
{
// 找到待删除的节点
PNode pDel = pos._pNode;
PNode pRet = pDel->_pNext;
// 将该节点从链表中拆下来并删除
pDel->_pPre->_pNext = pDel->_pNext;
pDel->_pNext->_pPre = pDel->_pPre;
delete pDel;
return iterator(pRet);
}
void clear();
void swap(List<T>& l);
private:
void CreateHead()
{
_pHead = new Node;
_pHead->_pPre = _pHead;
_pHead->_pNext = _pHead;
}
private:
PNode _pHead;
};
}