|
目录
一、整体框架
二、节点类
三、迭代器类
四、list类
1.构造与析构
? ?1.1?普通构造? ? ?? ?
1.2迭代器区间构造
1.3拷贝构造与赋值
1.4析构
2.迭代器指针、头尾数据
3.容量
4.插入和删除
一、整体框架
? ? ? ? 总共可分为节点类，迭代器类和list类三大块。
// List的节点类
template<class T>
struct ListNode
{
ListNode(const T& val = T())；
ListNode<T>* _pPre;
ListNode<T>* _pNext;
T _val;
};
//List的迭代器类
template<class T, class Ref, class Ptr>
class ListIterator
{
typedef ListNode<T>* PNode;
typedef ListIterator<T, Ref, Ptr> Self;
public:
ListIterator(PNode pNode = nullptr);
ListIterator(const Self& l);
T& operator*();
T* operator->();
Self& operator++();
Self operator++(int);
Self& operator--();
Self& operator--(int);
bool operator!=(const Self& l);
bool operator==(const Self& l);
private:
PNode _pNode;
};
//list类
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();
list(int n, const T& value = T());
template <class Iterator>
list(Iterator first, Iterator last);
list(const list<T>& l);
list<T>& operator=(const list<T> l);
~list();
// List Iterator
iterator begin();
iterator end();
const_iterator begin();
const_iterator end();
// 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);
// 删除pos位置的节点，返回该节点的下一个位置
iterator erase(iterator pos);
void clear();
void swap(List<T>& l);
private:
void CreateHead();
PNode _pHead;
};
二、节点类
? ? ? ? list实现为双向循环链表。
// 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中存储的地址不是连续的，我们不能使用原生指针来作迭代器。将节点指针放在迭代器类中，通过重载++，--，*等运算符，来实现迭代器。
? ? ? ? 模板参数Ref,使得传入const迭代器时，操作符*重载的返回值为const T&，实现只读不能写的功能。模板参数Ptr设置的原因也是如上，同时假设有迭代器it，要访问数据按操作符->重载使用应该是it->->_val，这样有两个箭头可读性太差了，编译器会优化成一个箭头，既it->_val。
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)
{}
Ref operator*()
{
return _pNode->_val;
}
Ptr operator->()
{
return &_pNode->_val;
}
Self& operator++()
{
_pNode = _pNode->_pNext;
return *this;
}
Self operator++(int)
{
Self temp(*this);
_pNode = _pNode->_pNext;
return temp;
}
Self& operator--()
{
_pNode = _pNode->_pPre;
return *this;
}
Self& operator--(int)
{
Self temp(*this);
_pNode = _pNode->_pPre;
return temp;
}
bool operator!=(const Self& l)
{
return _pNode != l._pNode;
}
bool operator==(const Self& l)
{
return _pNode == l._pNode;
}
private:
PNode _pNode;
};
四、list类
1.构造与析构
? ? ? ? 先封装一个头节点创建函数。
void CreateHead()
{
_pHead = new Node();
_pHead->_pNext = _pHead;
_pHead->_pPre = _pHead;
}
? ?1.1?普通构造? ? ?? ?
????????无参构造只需要创建一个头节点即可
? ? ? ? 利用push_back函数复用完成n个节点的初始化构造
list()
{
CreateHead();
}
list(int n, const T& value = T())
{
CreateHead();
while (n--)
{
push_back(value);
}
}
1.2迭代器区间构造
? ? ? ? 同样使用push_back函数，遍历迭代器区间进行构造。
template <class Iterator>
list(Iterator first, Iterator last)
{
CreateHead();
while (first!=last)
{
push_back(*first);
++first;
}
}
1.3拷贝构造与赋值
? ? ? ? 复用迭代器区间构造，交换头节点指针。
list(const list<T>& l)
{
list<T> temp(l.begin(), l.end());
CreateHead();
std::swap(_pHead, temp._pHead);
}
list<T>& operator=(const list<T> l)
{
CreateHead();
std::swap(_pHead, l._pHead);
return *this;
}
1.4析构
? ? ? ? 复用clear函数再释放头节点指针。
~list()
{
clear();
delete _pHead;
_pHead = nullptr;
}
2.迭代器指针、头尾数据
// List Iterator
iterator begin()
{
return iterator(_pHead->_pNext);
}
iterator end()
{
return iterator(_pHead);
}
const_iterator begin() const
{
return const_iterator(_pHead->_pNext);
}
const_iterator end() const
{
return const_iterator(_pHead);
}
// List Access
T& front()
{
return *begin();
}
const T& front() const
{
return *begin();
}
T& back()
{
return *(--end());
}
const T& back() const
{
return *(--end());
}
3.容量
// List Capacity
size_t size() const
{
size_t count = 0;
iterator it = begin();
while (it != end())
{
count++;
it++;
}
return count;
}
bool empty() const
{
return _pHead == _pHead->_pNext;
}
4.插入和删除
? ? ? ? 通过链表断开再链接完成插入和删除，其他的尾删和尾插等函数都可以复用插入和删除即可。
// List Modify
void push_back(const T& val)
{
insert(end(), 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 cur = pos._pNode;
PNode prev = cur->_pPre;
PNode newNode = new Node(val);
prev->_pNext = newNode;
newNode->_pNext = cur;
cur->_pPre = newNode;
newNode->_pPre = prev;
return iterator(newNode);
}
// 删除pos位置的节点，返回该节点的下一个位置
iterator erase(iterator pos)
{
PNode cur = pos._pNode;
PNode prev = cur->_pPre;
PNode next = cur->_pNext;
delete cur;
prev->_pNext = next;
next->_pPre = prev;
return iterator(next);
}
void clear()
{
iterator it = begin();
while (it != end())
{
erase(it++);
}
}
|