list（带头结点的双向循环链表）的详细介绍

一.list的介绍及使用
1.list是什么？
1.list可以在常数范围内在任意位置进行插入和删除的序列，并且该容器可以前后双向迭代。
2.list的底层是双向链表结构。
3.list和forward_list非常相似，forward_list是单链表，只能朝前迭代。
4.与其他容器相比，list通常在任意位置进行插入，移除元素的执行效率更好。缺陷是不支持任意位置的随机访问。
二.接口介绍
1.构造
list() //构造空的list
list(size_type n,const value_type&val=value_type())//构造的list中包含n个值为value的元素
list(const list& x) //拷贝构造函数
list(InputIitor first,InputIterator last) //用[first,last)区间中的元素构造list。

 list<int> L1;
 list<int> L2(10, 5);
 vector<int> v{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
 list<int> L3(v.begin(), v.end());
 list<int> L4(L3);

2.迭代器
1.begin+end
返回第一个元素的迭代器+返回最后一个元素的迭代器
2.rbegin+rend
返回第一个元素的reverse_iterator.即end位置，返回最后一个元素下一个位置的reverse_iterator，即begin位置
注意：
begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动。
rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动。

void TestList1()
{
 list<int> L1;
 list<int> L2(10, 5);
 vector<int> v{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
 list<int> L3(v.begin(), v.end());
 list<int> L4(L3);
//采用迭代器的方式
 //list<int>::iterator it = L2.begin();
 auto it = L2.begin();
 while (it != L2.end())
 {
  cout << *it << " ";
  ++it;
 }
 cout << endl;
 
 for (auto e : L3)
  cout << e << " ";
 cout << endl;
 
 auto rit = L4.rbegin();
 while (rit != L4.rend())
 {
  cout << *rit << " ";
  ++rit;
 }
 cout << endl;
}

3.容量
size
返回list中有效字节的个数 L.size();
empty
检测list是否为空，是返回true，否则返回false L.empty();
4.访问
front
返回list的第一个结点中值的引用
L.front();
back
返回list的最后一个结点中方值得引用
L.back();
5.修改
push_front
在list首元素前插入值为val的元素
L.push_front(0); //在list头部插入0
pop_front
删除list中第一个元素
L.pop_front(); //删除list头部节点
push_back
在list尾部插入值为val的元素
L.push_back(4); //在尾部插入4
pop_back
删除list中最后一个元素
L.pop_back(); //删除list尾部节点
insert
在list position位置中插入值为val的元素
L.insert(pos, 4);//在pos前加入值为4的结点 //1 4 2 3
L.insert(pos, v.begin(), v.end());
//在pos前插入[v.begin(),v.end()]区间中的元素
erase
删除list position位置的元素
L.erase(pos); //删除pos位置上的元素1 4 7 8 9 3
L.erase(L.begin(), L.end()); //删除list中[begin,end]区间中的元素
swap
交换两个list中的元素
L1.swap(L2);//交换L1和L2中的元素
clear
清空list中的有效元素
L1.clear();
resize
有效元素的个数
1.new>old
mylist.resize(8,100); //有效元素的个数是8个，个数不够用100填充。
mylist.resize(12); //有效元素的个数是12个，个数不够用0填充。
2.new<old
mylist.resize(5); //有效元素为五个

reverse
反转list
L.reverse();

5.特殊操作
sort
L.sort();
unique
前提：必须先排序。L.unique();
从容器中的每个连续的相等元素组中除去除第一个元素外的所有元素。
remove
L.remove(2); //删除所有的2
remove_if(函数名）
L.remove_if(IsOdd); //删除满足IsOdd函数的数据

void TestList4()
{
 list<int> L{ 9, 1, 2, 2, 3, 4, 2 };
 L.sort();//1 2 2 2 3 4 9
 L.unique();//1 2 3 4 9
}

remove：void remove (const value_type& val);
//L.remove(2);//删除所有的2
remove_if:
template <class Predicate> void remove_if (Predicate pred);
// L.remove_if(IsOdd);//删除所有的偶数

bool IsOdd(int data)
{
 if (0 == data % 2)
  return true;
 return false;
}
void TestList3()
{
 list<int> L{ 9, 1, 2, 2, 3, 4, 2 };
 for (auto e : L)
  cout << e << " ";
 cout << endl;
 //L.remove(2);//删除所有的2 //9 1 3 4 2
 //remove_if:删除所有满足条件的结点
 //条件：就是该函数的参数
 //该函数实现的原理：对每个节点中的值域用参数条件进行验证，如果满足则删除，如果不满足什么都不做。
 L.remove_if(IsOdd);//删除所有的偶数
 for (auto e : L)
  cout << e << " ";//9 1 3

}

三.迭代器失效
1.迭代器失效即迭代器所指向的节点无效，即该节点被删除了。
2.list进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效。
3.解决办法，重新赋值。

void TestListIterator()
{
 list<int> L{ 1, 2, 3, 4 };
 auto it = L.begin();
 L.erase(it);
 //erase之后，it所指向的节点已经被删除掉了
 //it迭代器失效
 //解决方法：给迭代器重新赋值
 it = L.begin();
 while (it != L.end())
 {
  cout << *it << " ";
  ++it;
 }
 cout << endl;
}

四,list的模拟实现
a>封装list的节点类
b>封装list的正反迭代器<list的迭代器不是原生态指针>
c>模拟实现list类相关函数

namespace bit
{

a>封装list的节点类

 //list:带头结点双向循环列表
 //list的节点类
 template<class T>
 struct ListNode
 {
  ListNode(const T&data = T())
   :_pNext(nullptr)
   , _pPre(nullptr)
   , _data(data)
  {}
  ListNode<T> * _pNext;
  ListNode<T>* _pPre;
  T _data;
 };

b>封装list的正反迭代器

//List迭代器：将节点类型的指针重新封装
 //封装正向迭代器：
 template<class T>
 struct list_iterator
 {
  typedef ListNode<T> Node;
  typedef list_iterator<T> Self;
 public:
  list_iterator(Node* pCur)
   :_pCur(pCur)
  {}
  //按指针的方式进行应用
  T& operator*()
  {
   return _pCur->_data;
  }
  T* operator->()
  {
   return &(_pCur->data);
  }
  //3.移动
  Self& operator++()
  {
   _pCur = _pCur->_pNext;
   return *this;
  }
  Self operator++(int)
  {
   Self temp(*this);
   _pCur = _pCur->_pNext;
   return temp;
  }
  Self& operator--()
  {
   _pCur = _pCur->_pPre;
   return *this;
  }
  Self operator--(int)
  {
   Self temp(*this);
   _pCur = _pCur->__pPre;
   return temp;
  }
  //4.比较
  bool operator!=(const Self& s)
  {
   return _pCur != s._pCur;
  }
  bool operator==(const Self& s)
  {
   return _pCur == s._pCur;
  }
  Node* _pCur;
 };

//封装反向迭代器
 template<class Iterator,class T>
 struct list_reverse_iterator
 {
  typedef list_reverse_iterator<Iterator, T> Self;
 public:
  list_reverse_iterator(Iterator it)
  :_it(it)
  {}
  //按指针的方式进行应用
  T& operator*()
  {
   Iterator temp = _it;
   --temp;
   return *temp;
  }
  T* operator->()
  {
   return &(operator*());
  }
  //3.移动
  Self& operator++()
  {
   --_it;
   return *this;
  }
  Self operator++(int)
  {
   Self temp(*this);
   _it--;
   reurn temp;
  }
  Self& operator--()
  {
   ++_it;
   return(*this);
  }
  Self operator--(int)
  {
   Self temp(*this);
   ++_it;
   return temp;
  }
  //4.比较
  bool operator!=(const Self& s)
  {
   return _it != s._it;
  }
  bool operator==(const Self& s)
  {
   return _it == s._it;
  }
  Iterator _it;
 };

c>模拟实现list类相关函数

template<class T>
 class list
 {
  typedef ListNode<T> Node;
 public:
  typedef list_iterator<T> iterator;
  typedef list_reverse_iterator<iterator, T> reverse_iterator;
  //list的构造
  list()
  {
   CreateHead();
  }
  list(int n, const T& data)
  {
   CreateHead();
   for (size_t i = 0; i < n; i++)
    push_back(data);
  }
  template<class Iterator>
  list(Iterator first, Iterator last)
  {
   CreateHead();
   while (first != last)
   {
    push_back(*first);
    ++first;
   }
  }
  list(const list<T>& L)
  {
   CreateHead();
   Node *pCur = L._pHead->_pNext;
   while (pCur != L._pHead)
   {
    push_back(pCur->_data);
    pCur = pCur->_pNext;
   }
  }
  //list(const list<T>& L)
  //{
  // CreateHead();
  // //用L中的元素构造临时的temp，然后与当前对象交换
  // list<T> temp(L.cbegin(), L.cend());
  // this->swap(temp);
  //}
  list<T>& operator=(const list<T>& L)
  {
   if (this != &L)
   {
    clear();
    Node* pCur = L._pHead->_pNext;
    while (pCur != L._pHead)
    {
     push_back(pCur->_data);
     pCur = pCur->_pNext;
    }
   }
   return *this;
  }
  /*list<T>& operator=(const list<T> L)
  {
   this->swap(L);
   return *this;
  }*/
  ~list()
  {
   clear();
   delete _pHead;
  }

/////////////////////////////////////
  //迭代器
  iterator begin()
  {
   return iterator(_pHead->_pNext);
  }
  iterator end()
  {
   return iterator(_pHead);
  }
  reverse_iterator rbegin()
  {
   return end();
  }
  reverse_iterator rend()
  {
   return begin();
  }

//////////////////////////////////////////
//容量
  size_t size()const
  {
   size_t count = 0;
   Node* pCur = _pHead->_pNext;
   while (pCur != _pHead)
   {
    ++count;
    pCur = pCur->_pNext;
   }
   return count;
  }
  size_t empty() const
  {
   return _pHead->_pNext == _pHead;
  }
  void resize(size_t newsize, const T&data = T())
  {
   size_t oldsize = size();
   if (newsize > oldsize)
   {
    //结点增多
    for (size_t i = oldsize; i < newsize; ++i)
     push_back(data);
   }
   else
   {
    //结点减少
    for (size_t i = newsize; i < oldsize; ++i)
     pop_back();
   }
  }

/////////////////////////////////////
  //元素访问
  T& front()
  {
   return _pHead->_pNext->_data;
  }
  const T& front()const
  {
   return _pHead->_pNext->_data;
  }
  T& back()
  {
   return _pHead->_pPre->_data;
  }
  const T& back()const
  {
   return _pHead->_pPre->_data;
  }

///////////////////////////////////
  //修改
  void push_back(const T& data)
  {
   insert(end(), data);
  }
  void pop_back()
  {
   erase(--end());
  }
  void push_front(const T& data)
  {
   insert(begin(), data);
  }
  void pop_front()
  {
   erase(begin());
  }
  //在pos为之前插入值为data的结点
  iterator insert(iterator pos, const T& data)  
  {
   Node* pNewNode = new Node(data);  
   Node* pCur = pos._pCur;  
   pNewNode->_pPre = pCur->_pPre; 
   pNewNode->_pNext = pCur;  
   pNewNode->_pPre->_pNext = pNewNode;  
   pCur->_pPre = pNewNode;  
   return iterator(pNewNode); 
  }
  //删除pos位置的结点，返回该节点的下一个位置
  iterator erase(iterator pos)
  {
   Node *pDelNode = pos._pCur;
   if (pDelNode == _pHead)
    return end();
   Node* pRet = pDelNode->_pNext;//保存返回的下一个结点的位置
   pDelNode->_pPre->_pNext = pDelNode->_pNext;
   pDelNode->_pNext->_pPre = pDelNode->_pPre;
   delete pDelNode;
   return iterator(pRet);
  }
  void clear()
  {
   Node* pCur = _pHead->_pNext;
   //头删法
   while (pCur != _pHead)
   {
    _pHead->_pNext = pCur->_pNext;
    delete pCur;
    pCur = _pHead->_pNext;
   }
   _pHead->_pNext = _pHead;
   _pHead->_pPre = _pHead;
  }
  void swap(list<T>& L)
  {
   swap(_pHead, L._pHead);
  }

private:
   void CreateHead()
   {
    _pHead = new Node;
    _pHead->_pNext = _pHead;
    _pHead->_pPre = _pHead;
   }
  protected:
   Node* _pHead;
 };
}