一、基本框架
这里我们使用三个类，分别实现链表节点本身、迭代器的构建以及各种接口的实现与提供
二、难点
因为我们的链表在内存中不是连续存储的，所以不能够使用原生指针作为迭代器，所以需要单独封装一个类，来实现迭代器比如解引用、++、--、->、！=等运算符的重载，其实就是将原生指针版迭代器的各种运算符重载使其能够支持类
在一个就是关于iterator和const_iterator的实现问题，比较简单的方法可以是先实现一个iterator，在复制一份，将其中的解引用和箭头更改为const版本；但翻阅原码可以发现原码以一种类模版的方式实现：即让编译器生成对应的类。两种方法在效率上没有区别，但第二种相对更加简洁。
三、还有一个可以注意一下的小点是struct默认是公有，class默认是私有，因此迭代器作为非常常用的类可以将它写为struct，访问更加方便
using namespace std;
//list就是带头双向循环链表
//链表在空间上的存储是不连续的，不能使用原生指针作为迭代器
namespace wjl
{
template <class T>
class list_node
{
public:
T _data;
list_node<T>* _next;
list_node<T>* _prev;
list_node(const T& data = T())
: _data(data)
, _next(nullptr)
, _prev(nullptr)
{}
};
template <class T, class Ref, class Ptr>
struct list_iterator//默认是公有
{
typedef list_node<T> Node;
typedef list_iterator<T, Ref, Ptr> Self;
Node* _node;
list_iterator(Node* node)
:_node(node)
{}
Ref operator*()
{
return _node->_data;
}
Ptr 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);
_node = _node->_prev;
return tmp;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
};
template <class T>
class list
{
typedef list_node<T> Node;
public:
//这里原码所采取的方式是提供类模版给编译器，让编译器生成两个类
/*typedef list_iterator<T> iterator;
typedef list_const_iterator<T> const_iterator;*/
//这里就是编译器的写法：用类模版实例化出不同的迭代器类型，本质是模版复用实例化
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;
//这里将哨兵位后第一个节点视为头结点
iterator begin()
{
//最传统的写法
iterator it(_head->_next);
return it;
}
const_iterator begin() const
{
return _head->_next;
}
//这里将哨兵位视为尾节点
iterator end()
{
//单参数构造函数支持隐式类型转换
return _head;
//或者采用匿名结构体
//return iterator(_head);
}
const_iterator end() const
{
return _head;
}
void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
list()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
list(const list<T>& lt)
{
empty_init();
for (auto& e : lt)
{
push_back(e);
}
}
list(initializer_list<int> lt)
{
empty_init();
//这里范围for不知道lt类型一定要用别名
for (auto& e : lt)
{
push_back(e);
}
}
~list()
{
clear();
delete _head;
_head = nullptr;
cout << "~list()" << endl;
}
void clear()
{
auto it = begin();
while (it != end())
{
it = erase(it);//这里it就是下一个位置的迭代器
}
}
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
//赋值运算符重载都可以使用现代写法
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}
void push_back(const T& x)
{
////通过_head找到尾节点
//Node* newnode = new Node(x);//这里前面的list_node要写构造函数，否则编译器会将其视为类型转换
//
//_head->_prev->_next = newnode;
//newnode->_prev = _head->_prev;
//newnode->_next = _head;
//_head->_prev = newnode;
//++_size;
insert(end(), x);
}
void push_front(const T& x)
{
insert(begin(), x);
}
iterator insert(iterator pos, const T& x)
{
//在pos之前插入
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* newnode = new Node(x);
newnode->_prev = prev;
newnode->_next = cur;
prev->_next = newnode;
cur->_prev = newnode;
_size++;
return newnode;
}
iterator erase(iterator pos)
{
assert(pos != end());
Node* next = (pos._node)->_next;
Node* prev = (pos._node)->_prev;
prev->_next = next;
next->_prev = prev;
delete pos._node;
_size--;
return next;
}
void pop_back()
{
erase(--end());
}
void pop_front()
{
erase(begin());
}
int size() const
{
return _size;
}
bool empty() const
{
return _size == 0;
}
private:
//这里的头结点就是哨兵位，不放数据。
Node* _head;
int _size;
};