一：list的节点和构造函数
<1>：_list_node
- list的底层是带头双向循环链表，所以每个节点中除了存储val和next，还需要存储前一个节点prev
template <class T>
struct _list_node
{
T _val;
_list_node<T>* _next;
_list_node<T>* _prev;
_list_node(const T& val = T())
:_val(val)
,_next(nullptr)
,_prev(nullptr)
{}
};
<2>： private成员与构造函数
- 因为list是带头双向循环链表，所以我们只用一个成员_head记录哨兵位的头就可以
- 所以构造函数我们只需要构造哨兵位的头节点，就可以完成list的构造，其余节点可以通过push_back，push_front,insert插入
- 当然我们还可以通过迭代器直接构造一个链表,这个我们等讲完迭代器再说
public:
list()
{
CreateHead();
}
private:
void CreateHead()
{
_head = new node;
_head->_next = _head;
_head->_prev = _head;
}
node* _head;
二：迭代器（iterator）
- 回想一下，再模拟实现string和vector时，我们迭代器都是原生指针进行封装
- 即
char*和T*，const迭代器就是const char*,const T* - 现在list还能用原生指针么，显然不行，光是++这个操作原生指针就不支持，_list_node不是连续的，++一下不知道跑哪去了，所以我们需要用一个类封装list的迭代器，并在里面重载++，–，！=，==,*,->等操作符
- 以*为例，可能你想这么做
template <class T>
struct _list_iterator
{
typedef _list_node<T> node;
typedef _list_iterator<T> self;
node* _pnode;
_list_iterator(node* pnode)
:_pnode(pnode)
{}
T& operator*()
{
return _pnode->_val;
}
};
- 这样做确实没错，那么const迭代器呢，像下面这样重载一个const版本？
template <class T>
struct _list_iterator
{
typedef _list_node<T> node;
typedef _list_iterator<T> self;
node* _pnode;
_list_iterator(node* pnode)
:_pnode(pnode)
{}
T& operator*()
{
return _pnode->_val;
}
const T& operator*() const
{
return _pnode->_val;
}
};
- 如果这么做，那就戳啦
- 后面的const修饰的是this指针，也就是迭代器自己，而不是修饰迭代器指向的值
- 所以这样不是const版本的迭代器，迭代器指向的值仍然能被修改，只是迭代器不能被修改
- 那我们就在封装一个类叫const _list_iterator，然后把返回值改成const T&?
- 这样做的确没问题，但是代码很冗余，有没有办法通过一个类同时封装两种迭代器呢？
- 的确可以，这就是前辈们的智慧了
template <class T,class Ref,class Ptr>
struct _list_iterator
{
typedef _list_node<T> node;
typedef _list_iterator<T,Ref,Ptr> self;
node* _pnode;
_list_iterator(node* pnode)
:_pnode(pnode)
{}
self& operator++()
{
_pnode = _pnode->_next;
return *this;
}
self& operator--()
{
_pnode = _pnode->_prev;
return *this;
}
self operator++(int)
{
self tmp(*this);
_pnode = _pnode->_next;
return tmp;
}
self operator--(int)
{
self tmp(*this);
_pnode = _pnode->_prev;
return tmp;
}
bool operator!=(const self&s)
{
return _pnode != s._pnode;
}
bool operator==(const self& s)
{
return _pnode == s._pnode;
}
Ref operator*()
{
return _pnode->_val;
}
Ptr operator->()
{
return &_pnode->_val;
}
};
- 我们将模板参数改为3个，第一个还是T，后面两个一个是Ref,一个是Ptr
- 这样有啥用呢？
- 前面我们重载operator*的返回类型就可以写成Ref，而不是T&了
- 对于const迭代器和普通迭代器，我们可以通过传不同的模板参数来控制
typedef _list_iterator<T,T&,T*> iterator;
typedef _list_iterator<T,const T&,const T*> const_iterator;
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);
}
- 对于const迭代器就传const T&,const T*，普通迭代器就传T&，T*，完美解决
- 而begin就直接返回哨兵位的下一个位置，end就更妙了，直接返回哨兵位，这是它循环的特性造成的，走到最后一个节点后就会走回哨兵位
- 至于具体如何实现这几个重载，就不赘述，代码十分简单，相信你一看就懂
- 唯一需要注意的是operator->，它的返回类型是
T*，而如果T是一个非内置类型 - 比如Date,我们想访问里面的year，是不是得要两个->，就像这样
it->->year，第一个->返回的是Date*,我们还需要再一个->才能访问到year - 编译器对此做了优化，实际上使用时我们只需要一个->就能访问到year
三：insert与erase
<1>： insert
- insert通过传入迭代器来进行插入，注意的是它是在pos位置之前插入，这样头插因为有哨兵位存在也可以进行，而如果在pos位置之后插入，尾插就得特殊考虑了
void insert(iterator pos, const T& x)
{
assert(pos._pnode);
node* cur = pos._pnode;
node* prev = cur->_prev;
node* newnode = new node(x);
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev=newnode;
}
- 通过复用insert，很快就能实现push_back和push_front
void push_back(const T& x)
{
insert(end(), x);
}
void push_front(const T& x)
{
insert(begin(),x);
}
<2>: erase
- erase的使用会使迭代器失效，我们需要返回删除后的节点位置保证迭代器仍然有效
- 注意：哨兵位的头不能删！
iterator erase(iterator pos)
{
assert(pos._pnode);
assert(pos != end());
node* cur = pos._pnode;
node* prev = cur->_prev;
node* next = cur->_next;
delete cur;
prev->_next = next;
next->_prev = prev;
return iterator(next);
}
- 复用erase实现pop_back和pop_front
void pop_back()
{
erase(--end());
}
void pop_front()
{
erase(begin());
}
四：拷贝构造与operator=
<1> 拷贝构造
- 有了迭代器就很好实现拷贝构造了，构造头结点后使用迭代器遍历另一个链表，将其每个节点push_back进当前链表
list(const list<T>& lt)
{
CreateHead();
for (const auto& e : lt)
{
push_back(e);
}
}
<2> operator=
list<T>& operator=(list<T> lt)
{
swap(_head, lt._head);
return *this;
}
<3> 利用iterator进行构造
- 这里不直接使用iterator作为参数类型，而是使用模板参数，是为了支持所有类型的迭代器
template<class Iterator>
list(Iterator first, Iterator end)
{
CreateHead();
while (first != end)
{
push_back(*first++);
}
}
五：析构和size
<1>: 析构函数
- 析构函数是先通过clear释放所有的节点，再释放哨兵位的头，完成析构
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
<2>:size
- 遍历链表进行计算节点个数，时间复杂度O(n),不推荐频繁调用
size_t size()
{
size_t sz;
iterator it = begin();
while (it != end())
{
sz++;
it++;
}
return sz;
}
|