List
- list
- list的常用接口模拟实现
- 完整代码
- list与vector的区别
list
list是一个带头双向循环链表。 list文档介绍：https://legacy.cplusplus.com/reference/list/list/ list因为是链表结构，所以没有 [] 去访问数据的方式，只有用迭代器，list当中迭代器是很重要的。 这里透彻尾插不会导致迭代器失效问题，不过删除会导致迭代器失效。 list还有一个特性，就是他的sort排序接口函数效率是低于算法库中排序的效率。 更多内容就配合模拟实现来看。
list的常用接口模拟实现
list基本结构
代码语言：javascript复制template<class T>
struct list_node//结点
{
list_node* _next;
list_node* _prev;
T _data;
list_node(const T& x)
:_next(nullptr)
,_prev(nullptr)
,_data(x)
{}
};下面都是模拟list类中的结构 在list中其实控制整个链表的就是头节点，这样交换内容也是非常的方便。 list成员变量：
代码语言：javascript复制_head因为list是带头双向循环链表，所以最重要的是创建头节点，这里因为后面结构需要大量重复这个动作我就单独写了个函数。
代码语言：javascript复制void initialize()//创建头节点
{
_head = new node(T());
_head->_next = _head;
_head->_prev = _head;
}构造函数：（无参）
代码语言：javascript复制list()
{
initialize();
}在pos位置之前插入：
代码语言：javascript复制void insert(iterator pos, const T& x)//在pos位置之前插入
{
node* newnode = new node(x);
node* cur = pos._pnode;//pos位置的结点
node* p = cur->_prev;//pos位置之前的结点
p->_next = newnode;
newnode->_prev = p;
newnode->_next = cur;
cur->_prev = newnode;
}删除pos位置的结点：（返回值是迭代器类型）
代码语言：javascript复制iterator erase(iterator pos)//删除pos位置的结点
{
assert(pos != end());
node* cur = pos._pnode;
node* front = cur->_prev;
node* later = cur->_next;
front->_next = later;
later->_prev = front;
delete cur;
return iterator(later);
}其实完成这两个函数就很方便各种插入删除了。
代码语言：javascript复制void push_back(const T& x)//尾插
{
insert(end(), x);
}
void push_front(const T& x)//头插
{
insert(begin(), x);
}
void pop_back()//尾删
{
erase(--end());
}
void pop_front()//头删
{
erase(begin());
}清空链表：（注意不清理头结点）
代码语言：javascript复制void clear()//清空链表
{
iterator front = begin();
while (front != end())
{
front = erase(front);
}
}拷贝构造：
代码语言：javascript复制template<class _iterator>//这里如果不是模板会导致不同类中的迭代器有冲突
list(_iterator front, _iterator later)
{
initialize();
while (front != later)
{
push_back(*front);
front;
}
}
list(const list<T>& it)//拷贝构造
{
initialize();//必须创建头节点，不然交换会传过去一个空指针导致析构出现问题
list<T>newnode(it.begin(), it.end());
swap(newnode);
}赋值重载：（现代写法）
代码语言：javascript复制list<T>& operator=(list<T> p)
{
swap(p);
return *this;
}这里传参的值不是引用，也就等于p是一个拷贝构造出来的对象，也就是说和之前赋值的对象没有任何关系，只是内容相同罢了。 所以这里直接交换就好了出了这个函数的p就会自动销毁。 交换函数：
代码语言：javascript复制void swap(list<T>& tmp)
{
std::swap(_head, tmp._head);//交换头结点就好
}这里就体现出头结点的好处了，因为空间不是连续的，是随机的，所以控制整个链表就是头结点，所以交换了头结点就等于交换了两个list。 析构函数：
代码语言：javascript复制~list()
{
clear();
delete _head;//清理头结点
_head = nullptr;
}C 有一个特性：
我们发现参数不是完整的类型（缺一个模板参数T），也就是说在类里面类名等于类型。 begin与end：
代码语言：javascript复制typedef _list_iterator<T, T&> iterator;//模板函数下面实现
typedef _list_iterator<T, const T&> const_iterator;
const_iterator begin()const
{
return const_iterator(_head->_next);
}
const_iterator end()const
{
return const_iterator(_head);
}
iterator begin()
{
return iterator(_head->_next);
}
iterator end()
{
return iterator(_head);
}迭代器（非常重要）
代码语言：javascript复制template<class T, class cur, class prt>
struct _list_iterator//用struct是因为里面的内容都需要公开使用
{
typedef list_node<T> node;
typedef _list_iterator<T, cur, prt> coord;
node* _pnode;//迭代器指针的本质
_list_iterator(node* p)
:_pnode(p)
{}
cur operator*()//返回值分const与非const
{
return _pnode->_data;
}
prt operator->()
{
return &_pnode->_data;//注意->的优先级大于&
}
coord& operator ()//前置
{
_pnode = _pnode->_next;
return *this;
}
coord& operator (int)//后置
{
coord old(*this);
_pnode = _pnode->_next;
return old;
}
coord& operator--()//前置--
{
_pnode = _pnode->_prev;
return *this;
}
coord& operator--(int)//后置--
{
coord old(*this);
_pnode = _pnode->_prev;
return old;
}
bool operator!=(const coord& it)
{
return _pnode != it._pnode;
}
bool operator==(const coord& it)
{
return _pnode == it._pnode;
}
};list因为是个链表，所以和vector，string不一样，空间不是连续的，想进行 ，- -，就等于访问下一个结点或者上一个结点。 这里要注意迭代器是需要有const的： 迭代器指向的内容不能被修改，并不代表不能 ，- - 所以就需要实现一份const迭代器，其实也就是解引用的不同，解引用返回的是const，和非const，其他函数一摸一样，进行函数重载是不行的，因为参数也要加const，不然无法重载，但是参数加了const其他函数就无法进行调用了，涉及到了权限放大，如果再写一个类太麻烦，这时候就可以加一个模板参数cur来决定用的时候添加什么参数。 重点是重载的-> 如果list中的类型是一个自定义类型呢？
代码语言：javascript复制 struct test
{
int row;
int col;
test(int x = 0, int y = 0)
:row(x)
,col(y)
{}
};
void test4()
{
list<test>arr;
arr.push_back(test(1, 2));
arr.push_back(test(3, 4));
arr.push_back(test(5, 6));
arr.push_back(test(7, 8));
list<test>::iterator cur = arr.begin();
while (cur != arr.end())
{
cout << cur->row << ' ';//这里如果用解引用是不可以的，因为cout需要再次进行重载才能打印出来内容
}
cout << endl;
}这时候就要用->就方便了，首先cur要是个指针才行，很明显它不是，所以返回的时候需要返回地址，并且要注意const的类型，就和解引用一样。 还有一点很奇怪：
cur->row == cur.operator->(row)
这里返回的是地址，为什么还能进行访问row呢？这是因为编译器在这里进行了特殊处理，原本面貌是这样的：
cur->->row
这样的代码看起来非常不美观，所以就进行了处理，去掉了一个->。
完整代码
代码语言：javascript复制 #include <iostream>
#include <list>
#include <assert.h>
#include <algorithm>
using namespace std;
template<class T>
struct list_node//结点
{
list_node* _next;
list_node* _prev;
T _data;
list_node(const T& x)
:_next(nullptr)
,_prev(nullptr)
,_data(x)
{}
};
template<class T, class cur, class prt>
struct _list_iterator
{
typedef list_node<T> node;
typedef _list_iterator<T, cur, prt> coord;
node* _pnode;//迭代器指针的本质
_list_iterator(node* p)
:_pnode(p)
{}
cur operator*()//返回值分const与非const
{
return _pnode->_data;
}
prt operator->()
{
return &_pnode->_data;//注意->的优先级大于&
}
coord& operator ()//前置
{
_pnode = _pnode->_next;
return *this;
}
coord& operator (int)//后置
{
coord old(*this);
_pnode = _pnode->_next;
return old;
}
coord& operator--()//前置--
{
_pnode = _pnode->_prev;
return *this;
}
coord& operator--(int)//后置--
{
coord old(*this);
_pnode = _pnode->_prev;
return old;
}
bool operator!=(const coord& it)
{
return _pnode != it._pnode;
}
bool operator==(const coord& it)
{
return _pnode == it._pnode;
}
};
template<class T>
class list
{
typedef list_node<T> node;
public:
typedef _list_iterator<T, T&, T*> iterator;
typedef _list_iterator<T, const T&, const T*> const_iterator;
const_iterator begin()const
{
return const_iterator(_head->_next);
}
const_iterator end()const
{
return const_iterator(_head);
}
iterator begin()
{
return iterator(_head->_next);
}
iterator end()
{
return iterator(_head);
}
void initialize()//创建头节点
{
_head = new node(T());
_head->_next = _head;
_head->_prev = _head;
}
list()
{
initialize();
}
template<class _iterator>
list(_iterator front, _iterator later)
{
initialize();
while (front != later)
{
push_back(*front);
front;
}
}
list(const list<T>& it)//拷贝构造
{
initialize();//必须创建头节点，不然交换会传过去一个空指针导致析构出现问题
list<T>newnode(it.begin(), it.end());
swap(newnode);
}
void insert(iterator pos, const T& x)//在pos位置之前插入
{
node* newnode = new node(x);
node* cur = pos._pnode;//pos位置的结点
node* p = cur->_prev;//pos位置之前的结点
p->_next = newnode;
newnode->_prev = p;
newnode->_next = cur;
cur->_prev = newnode;
}
iterator erase(iterator pos)//删除pos位置的结点
{
assert(pos != end());
node* cur = pos._pnode;
node* front = cur->_prev;
node* later = cur->_next;
front->_next = later;
later->_prev = front;
delete cur;
return iterator(later);
}
list<T>& operator=(list<T> p)
{
swap(p);
return *this;
}
void push_back(const T& x)//尾插
{
insert(end(), x);
}
void push_front(const T& x)//头插
{
insert(begin(), x);
}
void pop_back()//尾删
{
erase(--end());
}
void pop_front()//头删
{
erase(begin());
}
void clear()//清空链表
{
iterator front = begin();
while (front != end())
{
front = erase(front);
}
}
void swap(list<T>& tmp)
{
std::swap(_head, tmp._head);
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
private:
node* _head;
};list与vector的区别
list： 优点： 按照需要申请空间，不需要扩容。 任意位置插入删除。
缺点： 不支持下标随机访问。 cpu命中率低。（因为list是随机结构，vector是连续空间地址）
vector： 优点： 支持下标随机访问. 尾插尾删效率高。 cpu命中率高。 缺点： 前面插入删除效率低。 需要扩容。（可能导致浪费空间）
迭代器失效问题 vector插入删除都会失效，list只有删除会失效。
