一、常用接口
reverse逆置
sort排序（默认升序）
仿函数greater<int>
merge合并，可以全部合并，也可以一部分合并
unique：去重（先排序，再去重）
remove：删除e值，而不是erase的pos位置删
splice（粘接）：其实就是transform（转移）
把某个位置i，转移到当前链表的某个position之前
list的sort效率很低，底层用归并，但是数据访问很低，因为是链表
vectror的sort更好一些，因为是连续的空间
二、迭代器封装问题
原生指针就是天生的迭代器（但是前提是物理空间是连续的）
为什么？？
因为解引用就是该数据，++就是下一个数据
但是如果空间是不连续的就会出问题
例如list的原生指针就不能作为迭代器，因为不符合预期
因为list的原生指针式list*，但是list*++是错误的，因为不是连续的空间
解引用list*++，就是在原来地址位置，向后移动一个list类型大小的距离，指向该位置
但是因为不是连续的空间，所以，移动后的list*并不是下一个节点的地址
那怎么办呢？
改造一下
我们用一个类去封装这个原生指针，然后用这个类去控制这个原生指针
重载++list为移动到下一个节点的位置
需要处理的是这个部分
用类封装一个原生指针，这个原生指针也是一个模板
然后重定义这个原生指针为iterator
也就是说，这个itrator就是一个原生指针
这个原生指针也是一个模板
那么，当我们传入任意类型时，原生指针模板就会自动推导出其对应的指针
只是这个指针取了一个别名，叫做iterator，即迭代器
这就充分利用了类型的内涵
也就是说此处的迭代器底层还是一个指针
但是这个指针的行为不符合我们的预期
所以我们需要封装，重载行为
指针是内置类型
前置++和后置++是如何判断的呢？
因为函数重载只看参数列表，返回值不影响
所以，在后置++的重载参数列表加一个占位参数，int
这样就会区别两个函数
迭代器比较：就是比较指针，指针就是地址。地址相等，迭代器相等，否则不等
iterator的特点是不管底层是什么
三、list模拟实现（原码）
insert：
参数为iterator
找到当前的节点
记录前，后，插入即可
erase：参数pos也是iterator指针
删除节点后，当前节点的指针1iterator失效
所以要更新iterator
返回下一个节点的指针
pop_back：删除--end()
end是head，是头节点
resize：尾删和尾插
#pragma once
#include<assert.h>
#include<iostream>
using namespace std;
namespace myspace
{
//节点
template <class T>
struct list_node
{
list_node(const T& val = 0)
:_date(val)
, _next(nullptr)
, _prev(nullptr)
{
}
list_node<T>* _next;
list_node<T>* _prev;
T _date;
};
//迭代器
template <class T, class Ref, class ptr>
struct list_iterator
{
typedef list_node<T> node;
typedef list_iterator<T, Ref, ptr> self;//模板推导
list_iterator(node* node)
:_node(node)
{
}
//++it
self& operator++()
{
_node = _node->_next;
return *this;
}
//it++
self& operator++(int)
{
self tmp = _node;
_node = _node->_next;
return tmp;
}
//--it
self& operator--()
{
_node = _node->_prev;
return *this;
}
//it--
self& operator--(int)
{
self tmp = _node;
_node = _node->_prev;
return tmp;
}
//operator
T& operator*()
{
return _node->_date;
}
T* operator->()
{
return &_node->_date;
}
bool operator==(const self& it)
{
return _node == it._node;
}
bool operator!=(const self& it)
{
return _node != it._node;
}
node* _node;
};
//反向迭代器
template <class T, class Ref, class ptr>
struct list_reverse_iterator
{
typedef list_node<T> node;
typedef list_reverse_iterator<T, Ref, ptr> self;//模板推导
list_reverse_iterator(node* node)
:_node(node)
{
}
//++it
self& operator++()
{
_node = _node->_prev;
return *this;
}
//it++
self& operator++(int)
{
self tmp = _node;
_node = _node->_prev;
return tmp;
}
//--it
self& operator--()
{
_node = _node->_next;
return *this;
}
//it--
self& operator--(int)
{
self tmp = _node;
_node = _node->_next;
return tmp;
}
//operator
T& operator*()
{
node* tmp = _node->_prev;
_node = _node->_prev;
return tmp->_date;
}
T* operator->()
{
node* tmp = _node->_prev;
_node = _node->_prev;
return &tmp->_date;
}
bool operator==(const self& it)
{
return _node == it._node;
}
bool operator!=(const self& it)
{
return _node != it._node;
}
node* _node;
};
//一般对象的iterator和const对象的const_iterator
//由于两者对应的实现不同，因此，一般的方式是写两个类
//但是，二者的区别只有*引用和->引用两者的不同
//所以，如果要书写两个类，显的臃肿
//所以，可以使用模板
//在需要的地方使用模板推导
template <class T>
class list
{
typedef list_node<T> node;
public:
typedef list_iterator<T, T&, T*> iterator;//一般对象的iterator
typedef list_iterator<T, const T&, const T*> const_iterator;//const对象的iterator
typedef list_reverse_iterator<T, T&, T*> reserve_iterator;//reserve_iterator
void empty_init()
{
node* newnode = new node;
newnode->_next = newnode;
newnode->_prev = newnode;
this->_head = newnode;
_size = 0;
}
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
bool empty()
{
return size() == 0;
}
size_t size()
{
return _size;
}
list()
{
empty_init();
}
//lt1(lt2)
//需要重新搞出一个新的list
//(this指针就是lt1)
list(const list<T>& lt)
{
empty_init();
for (auto& e : lt)
{
push_back(e);
}
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
iterator begin()
{
return _head->_next;
}
iterator end()
{
return _head;
}
const_iterator begin() const
{
return _head->_next;
}
const_iterator end() const
{
return _head;
}
reserve_iterator rbegin()
{
return _head;
}
reserve_iterator rend()
{
return _head->_next;
}
//void swap(const list<T>& lt)
//{
// std::swap(_head,lt._head);
// std::swap(lt._size, _size);
//}
void push_back(const T& val)
{
insert(_head, val);
}
void push_front(const T& val)
{
insert(begin(), val);
}
void pop_back()
{
erase(_head->_prev);
}
void pop_front()
{
erase(begin());
}
void insert(iterator pos, const T& val)
{
node* tmp = new node(val);
node* next = pos._node;
node* prev = pos._node->_prev;
prev->_next = tmp;
tmp->_prev = prev;
next->_prev = tmp;
tmp->_next = next;
++_size;
}
iterator erase(iterator pos)
{
if (_size == 0)
return nullptr;
node* cur = pos._node;
node* next = cur->_next;
node* prev = cur->_prev;
next->_prev = prev;
prev->_next = next;
delete cur;
pos = nullptr;
--_size;
return next;
}
private:
node* _head;
size_t _size;
};
//打印const对象
void print(const list<int>& clt)
{
list<int>::const_iterator it = clt.begin();
while (it != clt.end())
{
cout << *it << " ";
}
cout << endl;
}
//正常的增删改
void test1()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
lt.insert(lt.begin(), 10);
//lt.erase(lt.begin());
lt.pop_back();
lt.pop_back();
lt.pop_back();
lt.pop_back();
lt.pop_back();
lt.pop_back();
list<int>::iterator it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
void test2()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
lt.clear();
list<int>::iterator it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
++it;
}
cout << lt.size() << endl;
cout << endl;
}
void test3()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
list<int>::iterator it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
++it;
}
cout << endl;
cout << lt.empty() << endl;
}
void test4()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
//list<int>::const_iterator it = lt.begin();
//while (it != lt.end())
//{
// cout << *it << " ";
// ++it;
//}
cout << endl;
cout << lt.empty() << endl;
}
void print_list(const list<int>& clt)
{
//const对象的迭代器
//const_iterator迭代器是一个单独的对象
//为了区别于一般对象，单独搞了一个const_iterator类
//这个const_iterator类的目的在于，可以正常进行遍历，但是不能对内部的内容进行修改
//因为实现方法不同，一个类无法实现，因此可以考虑使用模板
list<int>::const_iterator it = clt.begin();
while (it != clt.end())
{
//*it += 10;
cout << *it << " ";
++it;
}
cout << endl;
}
void test5()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
lt.push_front(100);
//lt.erase(lt.end());
lt.pop_back();
lt.pop_back();
lt.pop_back();
lt.pop_front();
list<int>::iterator it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
void test6()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
list<int> lt2(lt);
list<int> lt3;
lt3.push_back(10);
lt3.push_back(11);
lt3.push_back(12);
lt3.push_back(13);
//lt3.swap(lt2);
list<int>::iterator it = lt3.begin();
while (it != lt3.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
void test7()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
list<int>::reserve_iterator rlt = lt.rbegin();
while (rlt != lt.rend())
{
cout << *rlt << " ";
}
cout << endl;
}
}
四、相关细节
什么时候用struct，什么时候用class？
数据都是共有的时候就可以使用struct
模拟实现的时候，需要定义一个自己的命名空间，防止和库内冲突
将指针类型设置为模板，因为要支持不同数据的list
typedef ListNode<T> node #意为将节点设置为模板
但是，为了便于理解，我们编写代码的时候，还是使用node，便于理解
但是实际上，这个node其实是一个模板，我们用了一个typedef宏替换实现的
创建一个新节点的时候，也是，直接new node
这样就会直接开辟一个新空间节点出来，一个模板类型的空间节点
模板的理解：很简单
就是多了一个template<class T>而已
然后将对应的东西设置为T，再typedef就是了
例如：我要将list的节点设置为模板，那么：
typedef ListNode<T> node
节点设置为模板：ListNode<T>
换名字：typedef ListNode<T> node
不要把模板看的这么复杂
也不要吧typedef看的太复杂
list中at会检查越界，[]不会检查