前言：list是带头双向循环链表，物理空间不连续，导致对于迭代器的操作需要进行运算符重载，难点也在于对迭代器的使用与实现
//底层代码
#pragma once
#include<assert.h>
#include<iostream>
using namespace std;
namespace bit
{
template <typename T>
struct ListNode
{
ListNode<T>* next;
ListNode<T>* prev;
T data;
ListNode(T x = 0)//在这里进行数据的深拷贝
: next(nullptr), prev(nullptr), data(x)//初始化列表
{}
};
template<typename T,typename ptr , typename ref>
struct NodeIterator
{
typedef ListNode<T> Node;
typedef NodeIterator<T,ptr,ref> iterator;
NodeIterator(Node* tmp)
: _node( tmp)
{}
ref operator*() const
{
return _node->data;
}
//++it
iterator operator++()
{
_node = _node->next;
return *this;
}
// it++
iterator operator++(int)
{
iterator tmp(*this);
_node = _node->next;
return tmp;
}
//it--
iterator operator--(int)
{
iterator tmp(*this);
_node = _node->prev;
return tmp;
}
iterator operator--()
{
_node = _node->prev;
return *this;
}
bool operator!=(const iterator& n) const
{
return _node != n._node;
}
ptr operator->()
{
return &(_node->data);
}
Node* _node;
};
template<typename T>
class list
{
public:
typedef NodeIterator<T,T* , T&> iterator;
typedef NodeIterator<T,const T* ,const T&> const_iterator;
typedef ListNode<T> Node;
list(const list& s)
{
size = 0;
phead = new Node(0);
phead->prev = phead->next = phead;
for (auto& e : s)
push_back(e);
}
void clear()
{
auto it = begin();
while (it != end())
it = erase(it);
}
~list()
{
clear();
delete phead;
size = 0;
phead = nullptr;
}
list()
{
size = 0;
phead = new Node(0);
phead->prev = phead->next = phead;
}
void push_back(const T& x)
{
insert(end(), x);
}
void push_front(const T& x)
{
insert(begin(), x);
}
void pop_back()
{
erase(end()._node->prev);
}
void pop_front()
{
erase(begin());
}
iterator begin()
{
return phead->next;
}
iterator end()
{
return phead;
}
const_iterator begin()const
{
return phead->next;
}
const_iterator end()const
{
return phead;
}
void insert(iterator position, const T& val)
{
Node* _position = position._node;
Node* tmp = new Node(val);
tmp->next = _position;
tmp->prev = _position->prev;
_position->prev->next = tmp;
_position->prev = tmp;
size++;
}
iterator erase(iterator position)
{
Node* _position = position._node;
Node* tt = _position->next;
Node* tmp = _position->prev;
tmp->next = _position->next;
_position->next->prev = tmp;
delete _position;
size--;
_position = nullptr;
return tt;
}
list& operator= ( list x )
{
swap(x);
return *this;
}
bool empty()
{
return size == 0;
}
void swap(list<T> s)
{
std::swap(size, s.size);
std::swap(phead, s.phead);
}
list& operator= (list<T> x)
{
swap(x);
return *this;
}
private:
Node* phead;//头结点
int size;
};
}迭代器
迭代器一般需要进行如下操作
std::list<int>::iterator it = s.begin();
while( it != s.end())
{
cout << *it << " ";
it++;
}
也就是需要对运算符 * != ++ 对操作符重载
明确一点：链表中的迭代器是节点的指针 ， 指针是内置类型 ，但需要对内置类型的行为重新定义，则可以把内置类型转换成自定义类型（单独为迭代器写一个类）
首先 * 一般是取链表中的元素（节点中的data) ，在迭代器中需要取data，只需要将节点的指针作为迭代器类的成员变量
第二点 迭代器可以分为const 或者是 非const ，则可以将迭代器写成一个类模版
// 首先在begin函数中 分为 iterator begin() const_iterator begin() const
// typedef NodeIterator< T , T& , typename T*> iterator;
// typedef NodeIterator< T , const T& , T* > const_iterator;
// 就导致NodeIterator只生成两个类
// iterator begin 放回的是iterator（他就只会调用第一个类）
// const_iterator begin返回的是const_iterator(只会调用第二个类)
template<typename T,typename ptr , typename ref>
struct NodeIterator
{
typedef ListNode<T> Node;
typedef NodeIterator<T,ptr,ref> iterator;
NodeIterator(Node* tmp)
: _node( tmp)
{}
ref operator*() const
{
return _node->data;
}
//++it
iterator operator++()
{
_node = _node->next;
return *this;
}
// it++
iterator operator++(int)
{
iterator tmp(*this);
_node = _node->next;
return tmp;
}
//it--
iterator operator--(int)
{
iterator tmp(*this);
_node = _node->prev;
return tmp;
}
iterator operator--()
{
_node = _node->prev;
return *this;
}
bool operator!=(const iterator& n) const
{
return _node != n._node;
}
ptr operator->()
{
return &(_node->data);
}
Node* _node;
};构造函数
方法1：初始化链表初始化
#include<iostream>
#include<vector>
#include<list>
#include<stack>
using namespace std;
int main()
{
list<int> s = { 1 , 2 , 3 , 4 , 5 };
for (auto& e : s)cout << e << " ";
cout << endl;
}方法2：迭代器区间初始化
#include<iostream>
#include<vector>
#include<list>
#include<stack>
using namespace std;
int main()
{
vector<int> dp = { 1 , 2 , 3 ,4 , 6 };
auto it = dp.begin();
list<int> s(it + 2, dp.end() - 1);
for (auto& e : s)cout << e << " ";
cout << endl;
}方法3：不加任何条件
#include<iostream>
#include<vector>
#include<list>
#include<stack>
using namespace std;
int main()
{
list<int> s;
return 0;
}拷贝构造与赋值重载
均为深拷贝
front与back函数
返回头和尾元素
#include<iostream>
#include<vector>
#include<list>
#include<stack>
using namespace std;
int main()
{
vector<int> dp = { 1 , 2 , 3 ,4 , 6 };
int f = dp.front();
int t = dp.back();
cout << f << " " << t << endl;
}insert函数
在某一个位置之前插入一个值或一段区间
#include<iostream>
#include<vector>
#include<list>
#include<stack>
using namespace std;
int main()
{
list<int> s = { 1 , 2 , 4 , 5 , 6 };
auto it = s.begin();
vector<int> dp = { 1 , 0 , 9 };
s.insert(it, dp.begin(), dp.end());
for (auto& e : s)cout << e << " ";
cout << endl;
s.insert(s.end(), 10);
for (auto& e : s)cout << e << " ";
cout << endl;
}erase函数
去除某一个位置的值，或某一段区间的值
#include<iostream>
#include<vector>
#include<list>
#include<stack>
using namespace std;
int main()
{
list<int> s = { 1 , 2 , 3 , 5 , 3 };
s.erase(s.begin());
list<int> p = { 4 , 5 , 12 , 3 , 4 };
s.erase(++p.begin(), --p.end());
for (auto& e : p)cout << e << " ";
cout << endl;
}push_back 与push_front函数
本质复用insert函数 尾插 头插
pop_back与pop_front函数
本质复用erase函数
assign函数
将链表中的内容重新分配
#include<iostream>
#include<vector>
#include<list>
#include<stack>
using namespace std;
int main()
{
list<int> s = { 1, 2, 3, 4, 6 };
list<int> k = { 9 , 1 , 0 };
s.assign({ 2,3,45 });
for (auto& e : s)cout << e << " ";
cout << endl;
s.assign(k.begin(),k.end());
for (auto& e : s)cout << e << " ";
cout << endl;
}