目录
List介绍：
1、list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
2、list的底层是带头结点双向循环链表结构，双向循环链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
3、list和forwoed_list非常相似：最主要的不同在于forword链表是单链表，只能向前迭代，以让其更简单高效。
4、与其他的序列式容器相比（array, vector, deque），list通常在任意位置进行插入、移除元素的效率更好。
5、与其他序列式容器相比，list和forword_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第六个元素，必须从已知的位置迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关信息（对于存储类型较小元素的 list来说这可能是一个重要的因素）
list的接口：
构造：
1、explicit list(const allocator_type&alloc = allocator_type())：默认构造函数，构造一个仅有空节点的空链表。
2、explicit list(size_type n, const value_type& val = value_type(),const allocator_type&alloc = allocator_type())：使用n个值为val的元素构造双向链表。
3、template<class InputIterator>
explicit list(InputIterator first, InputIterator last, const allocator_type&alloc = allocator_type())：用区间[first, last)之间的元素来构造双向链表。
4、list(const list& x)：拷贝构造函数
析构：
?~list()：用来释放资源，在对象使用完毕后会自动调用。
赋值运算符重载：
list& operator=(const list& x)
?迭代器：
iterator begin() | const_iterator begin() const;
iterator end() | const_iterator end() const;
????????begin：返回链表的第一个元素的位置
? ? ? ? end：返回链表的最后一个元素的下一个位置也就是头节点的位置。
reverse_iterator rbegin() | const_reverse_iterator rbegin() const;
reverse_iterator rend() | const_reverse_iterator rend() const;
可以看到此时it2调用的是下面的函数重载。
C++11:
const_iterator cbegin() const noexcept;
const_iterator cend() const noexcept;
const_reverse_iterator crbegin() const noexcept;
const_reverse_iterator crend() const noexcept;
注意：这两组接口的返回值指向的元素不可被修改
容量相关：
?bool empty() const：判空
size_type size() const：求链表有效元素个数
注意：list没有capacity和reserve方法
元素访问相关：
?reference front() | const_reference front() const：获取链表的第一个元素
reference back() | const_reference back() const：获取链表最后一个元素
注意：因为list是带头节点的双向循环链表，不支持随机访问，所以没有[]重载
修改相关：
?1、assign&reserve3
将新内容分配给列表容器，替换当前内容，并相应地修改其大小。
template <class InputIterator>
void assign (InputIterator first, InputIterator last)：使用区间[first, last)之间的元素重新构建新容器。
void assign (size_type n, const value_type& val)：使用n个值为val的元素重新构建新容器。
void resize(size_type n, value_type val = value_type())：将链表的有效元素调整为n个
? ? ? ? n > oldsize：多出来的节点使用
? ? ? ? n < oldsize：将链表的有效元素个数缩小为n
? ? ? ? n == oldsize：不做任何操作
??
2、头插和头删
void push_front(const value_type& val)：头插一个值为val的元素，时间复杂度O(1)
void pop_front()：头删一个节点，O(1)
?3、尾插和尾删
void push_back(const value_type& val)：尾插一个值为val的元素
void pop_back()：尾删
4、任意位置的插入?
iterator insert (iterator position, const value_type& val)：在position位置插入元素val
void insert(iterator position, size_type n, const value_type& val)：在position位置插入n个值为val的元素。
template <class InputIterator>
void insert (iterator position, InputIterator firet, InputIterator last)：在position位置插入区间[first, last)的内容
5、任意位置的删除：
?iterator erase(iterator position)：删除pos位置的元素
iterator erase(iterator first, iterator last)：删除区间[first, last)之间的元素。
其他：
?void swap(list& x)：交换两个链表
void clear()：清空链表
List容器的模拟实现：
?
#include<iostream>
using namespace std;
namespace DL {
//list的节点类
template<class T>
class ListNode {
public:
ListNode<T>* prev;
ListNode<T>* next;
T data;
ListNode(const T& value = T())
:prev(nullptr)
,next(nullptr)
,data(value){}
};
//正向迭代器
template<class T, class Ref, class Ptr>
class ListIterator {
public:
typedef ListNode<T> Node;
typedef Ref Reference;
typedef Ptr Pointer;
typedef ListIterator<T, Ref, Ptr> Self;
public:
ListIterator(Node* pNode = nullptr)
:_pNode(pNode){}
//解引用
Ref operator*() {
return _pNode->data;
}
//只有当T是自定义类型的时候才有意义
Ptr operator->() {
return &_pNode->data;
}
//前置++
Self operator++() {
_pNode = _pNode->next;
return *this;
}
//后置++
Self operator++(int) {
Self temp(*this);
_pNode = _pNode->next;
return temp;
}
Self operator--() {
_pNode = _pNode->prev;
return *this;
}
Self operator--(int) {
Self temp(*this);
_pNode = _pNode->prev;
return temp;
}
bool operator==(const Self& it) {
return _pNode == it._pNode;
}
bool operator!=(const Self& it) {
return _pNode != it._pNode;
}
public:
Node* _pNode;
};
//反向迭代器
template<class Iterator>
class ListReverseIterator {
typedef typename Iterator::Reference Reference;
typedef typename Iterator::Pointer Pointer;
typedef ListReverseIterator<Iterator> Self;
public:
ListReverseIterator(Iterator it)
:_it(it){}
Reference operator*() {
auto temp = _it;
--temp;
return *temp;
}
Pointer operator->() {
return &(operator*());
}
Self& operator++() {
--_it;
return *this;
}
Self operator++(int) {
Self temp(*this);
--_it;
return temp;
}
Self& operator--() {
++_it;
return *this;
}
Self operator--(int) {
Self temp(*this);
++_it;
return temp;
}
bool operator==(const Self& rit) {
return _it == rit._it;
}
bool operator!=(const Self& rit) {
return _it != rit._it;
}
public:
Iterator _it;
};
//list类
template<class T>
class List {
public:
typedef ListNode<T> Node;
typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T, const T&, const T*> const_iterator;
typedef ListReverseIterator<iterator> reverse_iterator;
typedef ListReverseIterator<const_iterator> const_reverse_iterator;
public:
//构造和析构
List() {
CreateHead(); //默认构造空的List
}
List(int n, const T& val = T()) {
CreateHead();
for (int i = 0; i < n; i++) {
push_back(val);
}
}
List(const List<T>& L) {
CreateHead();
auto iter = L.cbegin();
while (iter != L.cend()) {
push_back(*iter);
++iter;
}
}
template<class Iterator>
List(Iterator first, Iterator last) {
CreateHead();
auto it = first;
while (it != last) {
push_back(*it);
++it;
}
}
//析构
~List() {
clear();
delete(_head);
_head = nullptr;
}
//赋值运算符重载
List<T>& operator=(List<T>& L) {
if (this != &L) {
clear();//将this指向的元素清空
auto it = L.begin();
while (it != L.end()) {
push_back(*it);
++it;
}
}
return *this;
}
///
//迭代器
iterator begin() {
return iterator(_head->next);
}
iterator end() {
return iterator(_head);
}
const_iterator cbegin()const {
return const_iterator(_head->next);
}
const_iterator cend() const{
return const_iterator(_head);
}
//反向迭代器
reverse_iterator rbegin() {
return reverse_iterator(end());
}
reverse_iterator rend() {
return reverse_iterator(begin());
}
const_reverse_iterator crbegin() {
return const_reverse_iterator(cend());
}
reverse_iterator crend() {
return const_reverse_iterator(cbegin());
}
/
//容量相关
size_t size()const{
auto it = cbegin();
size_t count = 0;
while (it != cend()) {
++count;
++it;
}
return count;
}
bool empty()const {
return _head == _head->next;
}
//调整链表有效元素的个数
void resize(size_t newsize, const T& value = T()) {
size_t oldsize = size();
if (newsize <= oldsize) {
for (size_t i = newsize; i < oldsize; i++) {
pop_back();
}
}
else {
for (size_t i = oldsize; i < newsize; i++) {
push_back(value);
}
}
}
//访问元素
T& front() {
return *begin();
}
const T& front()const {
return *cbegin();
}
T& back() {
return *(--end());
}
const T& back()const {
return _head->prev->data;
}
//
//修改
//尾插
void push_back(const T& value) {
insert(end(), value);
}
void pop_back() {
if (empty()) {
return;
}
auto it = end();
--it;
erase(it);
}
//头插
void push_front(const T& value) {
insert(begin(), value);
}
void pop_front() {
erase(begin());
}
//任意位置插入
iterator insert(iterator InsertPos, const T& value) {
Node* newnode = new Node(value);
Node* pos = InsertPos._pNode;
newnode->next = pos;
newnode->prev = pos->prev;
newnode->prev->next = newnode;
pos->prev = newnode;
return iterator(newnode);
}
//任意位置的删除
iterator erase(iterator Erasepos) {
Node* pos = Erasepos._pNode;
if (Erasepos == end()) {
return end();
}
Node* nextPos = pos->next;
pos->prev->next = nextPos;
nextPos->prev = pos->prev;
delete pos;
return iterator(nextPos);
}
iterator erase(iterator first, iterator last) {
auto it = first;
while (it != last) {
it = erase(it);
}
return it;
}
/
void clear() {
erase(begin(), end());
}
void swap(List<T>& L) {
std::swap(_head, L._head);
}
private:
//对于一个链表，即使是空链表也会有一个头节点，将它设置为私有
void CreateHead() {
_head = new Node;
_head->next = _head;
_head->prev = _head;
}
private:
Node* _head;
};
