我们模拟实现的list是带头双向循环链表，list的成员变量有指向头节点的指针。所以在实现list之前我们应该实现节点这个类型
这个是双向链表的节点的结构
template<class T>
struct ListNode
{
ListNode<T>* _prev;
ListNode<T>* _next;
T _data;
ListNode(const T& val = T())
:_prev(nullptr),
_next(nullptr),
_data(val)
{}
};
class list
{
typedef ListNode<T> Node;
Node* _head;
public:
list()
{
_head = new Node;
_head->_prev = _head;
_head->_next = _head;
}
}
void push_back(T val =T())
{
Node* tail = _head->_prev;
Node * newnode = new ListNode(val);
tail->_next = newnode;
newnode->_prev = tail;
newnode->_next = _head;
_head->_prev = newnode;
}
void pop_back()
{
Node* tail = _head->_prev;
Node* pr = tail->_prev;
_head->_prev = pr;
pr->_next = _head;
delete tail;
}
因为我们想实现list的任意位置的插入的删除都要实现list的迭代器，所以我们先实现迭代器。
vector中我们直接把指针当成迭代器，这是因为vector支持随机访问。但是链表的指针++ 就变成野指针了。我们想要控制这个指针的行为，就要把这个指针封装成类。类决定了行为
template<class T>
class Iterator
{
public:
typedef ListNode<T> Node;
typedef Iterator<T> Self;
Node* _node;
Iterator(Node* node)
:_node(node)
{}
Self& operator++()
{
_node = _node->_next;
//why
return *this; // this 指针指向当前的iterator
// 返回的就是iterator
}
Self& operator--()
{
_node = _node->_prev;
return *this;
}
Self operator++(int)
{
Iterator tmp(*this);
_node = _node->_next;
return tmp; // 出了作用域tmp就被销毁了所以不能引用tmp
}
T& operator*()
{
return _node->_data;
}
bool operator != ( const Self &it) // 引用的是 return 回来的值
//因为return 回来的值本质是拷贝的一份临时变量 具有常性
{
return _node != it._node;
}
};
void insert( iterator pos, T val = T()) // 缺省参数只能从右边缺省！
{
Node *newnode = new Node(val);
Node* cur = pos._node;
Node* prev = cur->_prev;
prev->_next = newnode;
newnode->_prev = prev;
cur->_prev = newnode;
newnode->_next = cur;
_size++;
}
void erase(iterator pos)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
prev->_next = next;
next->_prev = prev;
delete cur;
_size--;
}
void empty_list()
{
_head = new Node;
_head->_prev = _head;
_head->_next = _head;
_size = 0;
}
List()
{
empty_list();
}
List(const List<T> &It)
{
empty_list();
for (auto e : It)
{
push_back(e);
}
}
List(initializer_list<T> il)
{
empty_list();
for (auto& e : il)
{
push_back(e);
}
}
~List()
{
clear();
delete _head;
_head = nullptr;
}
class constlistiterator
{
typedef listnode<t> node; //内嵌类型
typedef constlistiterator<t> self;
public:
node* _node;
constlistiterator(node* node)
:_node(node)
{}
public:
const t& operator* ()
{
return _node->_data;
}
self& operator++()
{
_node = _node->_next;
return *this;
}
self operator++(int)
{
self tmp(*this);
_node = _node->_next;
return tmp;
}
self& operator--()
{
_node = _node->_prev;
return *this;
}
self operator--(int)
{
/// self tmp （* this);
self tmp(*this);
_node = _node->_prev;
return *tmp;
}
bool operator==(const self& it)
{
return _node == it._node;
}
bool operator!=(const self& it)
{
return _node != it._node;
}
const t* operator->()
{
return &_node->_data;
}
};
我们发现大部分内容都是一样的只是返回值不一样！
我们可以用模板把const迭代器和普通迭代器和成一个模板，当需要的时候编译器再现生成一个
class ListIterator
{
typedef ListNode<T> Node; //内嵌类型
typedef ListIterator<T,Ref,Ptr> Self;
public:
Node* _node;
ListIterator(Node* node)
:_node(node)
{}
Ref operator* ()
{
return _node->_data;
}
Self& operator++()
{
_node = _node->_next;
return *this;
}
Self operator++(int)
{
Self tmp(*this);
_node = _node->_next;
return tmp;
}
Self& operator--()
{
_node = _node->_prev;
return *this;
}
Self operator--(int)
{
/// Self tmp （* this);
Self tmp (* this);
_node = _node->_prev;
return *tmp;
}
bool operator==(const Self& it)
{
return _node == it._node;
}
bool operator!=(const Self& it)
{
return _node != it._node;
}
Ptr operator->()
{
return &_node->_data;
}
};