目录
要模拟实现list，必须要熟悉list的底层结构以及其接口的含义，通过之前学习，这些内容已基本掌握，现在我们来模拟实现list。
参照带头双向循环链表的结构，我们可以建立以下三个类来模拟实现list
list的节点类
template<class T>
struct ListNode
{
ListNode<T>* _next;
ListNode<T>* _prev;
T _data;
// 构造函数
ListNode(const T& data = T())
:_next(nullptr),
_prev(nullptr),
_data(data)
{}
};
list的迭代器类
将原生态指针进行封装，因迭代器使用形式与指针完全相同，因此在自定义的类中必须实现以下方法：
- 指针可以解引用，迭代器的类中必须重载operator*()
- 指针可以通过->访问其所指空间成员，迭代器类中必须重载oprator->()
- 指针可以++向后移动，迭代器类中必须重载operator++()与operator++(int)，至于operator--()/operator--(int)释放需要重载，根据具体的结构来抉择，双向链表可以向前移动，所以需要重载，如果是forward_list就不需要重载--
- 迭代器需要进行是否相等的比较，因此还需要重载operator==()与operator!=()
template<class T, class Ref, class Ptr>
struct ListIterator
{
typedef ListNode<T> Node;
typedef ListIterator<T, Ref, Ptr> Self;
Node* _node;
//
// 构造
ListIterator(Node* node)
:_node(node)
{}
//
// 迭代器支持移动
// ++it;
Self& operator++()
{
_node = _node->_next;
return *this;
}
Self& operator--()
{
_node = _node->_prev;
return *this;
}
Self operator++(int)
{
Self tmp(*this);
_node = _node->_next;
return tmp;
}
Self& operator--(int)
{
Self tmp(*this);
_node = _node->_prev;
return tmp;
}
//
// 具有指针类似行为
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
//
// 迭代器支持比较
bool operator!=(const Self& it)
{
return _node != it._node;
}
bool operator==(const Self& it)
{
return _node == it._node;
}
};迭代器类不需要析构函数，我们只要能够访问list中的元素即可，访问完不需要析构节点。
可以这样理解：这里的Self是当前这个节点，通过类模板又被细化为普通类型，引用类型，指针类型，以int代替T来实例化，这时候ListIterator中的T告诉迭代器是什么类型（int），Ref代替引用（int&），Ptr代替指针（int*）。而这里的Self可以当作节点本身。
list的模拟实现
namespace bite
{
template<class T>
struct ListNode
{
ListNode<T>* _next;
ListNode<T>* _prev;
T _data;
// 构造函数
ListNode(const T& data = T())
:_next(nullptr),
_prev(nullptr),
_data(data)
{}
};
template<class T, class Ref, class Ptr>
struct ListIterator
{
typedef ListNode<T> Node;
typedef ListIterator<T, Ref, Ptr> Self;
Node* _node;
ListIterator(Node* node)
:_node(node)
{}
Self& operator++()
{
_node = _node->_next;
return *this;
}
Self& operator--()
{
_node = _node->_prev;
return *this;
}
Self operator++(int)
{
Self tmp(*this);
_node = _node->_next;
return tmp;
}
Self& operator--(int)
{
Self tmp(*this);
_node = _node->_prev;
return tmp;
}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
bool operator!=(const Self& it)
{
return _node != it._node;
}
bool operator==(const Self& it)
{
return _node == it._node;
}
};
template<class T>
class list
{
typedef ListNode<T> Node;
public:
typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T, const T&, const T*> const_iterator;
iterator begin()
{
//iterator it(_head->_next);
//return it;
return iterator(_head->_next);
}
const_iterator begin() const
{
return const_iterator(_head->_next);
}
iterator end()
{
return iterator(_head);
}
const_iterator end() const
{
return const_iterator(_head);
}
list()
{
_head = new Node();
_head->_next = _head;
_head->_prev = _head;
}
void push_back(const T& x)
{
insert(end(), x);
}
void pop_back()
{
erase(--end());
}
void push_front(const T& x)
{
insert(begin(), x);
}
void pop_front()
{
erase(begin());
}
// 不会发生迭代器失效
iterator insert(iterator pos, const T& x)
{
Node* cur = pos._node;
Node* newnode = new Node(x);
Node* prev = cur->_prev;
// prev newnode cur
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
return iterator(newnode);
}
// erase 后 pos失效了，pos指向节点被释放了
iterator erase(iterator pos)
{
assert(pos != end());
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
prev->_next = next;
next->_prev = prev;
delete cur;
return iterator(next);
}
private:
Node* _head;
};
}前面说过，此处大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。因此使用erase之后需要对迭代器进行赋值刷新。