初识c++——list

一、list

1、list结构

c++中list为双向带头循环列表：

二、list接口

1、构造

using namespace std;
#include<iostream>
#include<list>
#include<vector>
int main()
{list<int> lt; //构造空的listlist<int> lt1(10, 1); //构造的list中包含n个值为val的元素for (auto& it : lt1){cout << it;}list<int> lt2 = lt1;//拷贝构造函数vector<int>vr(10, 2);list<int> lt3(vr.begin(), vr.end());for (auto& it : lt3){cout << it;}return 0;
}

2、迭代器

注：c++的迭代器不支持+，-操作符

1. begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动

2. rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动

3、空间

using namespace std;
#include<iostream>
#include<list>
#include<vector>
int main()
{list<int> lt; //构造空的listlist<int> lt1(10, 1); //构造的list中包含n个值为val的元素for (auto& it : lt1){cout << it;}list<int> lt2 = lt1;//拷贝构造函数vector<int>vr(10, 2);list<int> lt3(vr.begin(), vr.end());for (auto& it : lt3){cout << it;}if (!lt3.empty()){cout << lt3.size();}return 0;
}

4、节点访问

using namespace std;
#include<iostream>
#include<list>
#include<vector>
int main()
{list<int> lt; //构造空的listlist<int> lt1(10, 1); //构造的list中包含n个值为val的元素for (auto& it : lt1){cout << it;}list<int> lt2 = lt1;//拷贝构造函数vector<int>vr(10, 2);list<int> lt3(vr.begin(), vr.end());for (auto& it : lt3){cout << it;}cout << endl;if (!lt3.empty()){cout << lt3.size() << lt3.front() << lt3.back();}return 0;
}

5、修改元素

using namespace std;
#include<iostream>
#include<list>
#include<vector>
int main()
{list<int> lt1(10, 1); list<int> lt2(10, 2);lt1.push_back(3);//尾插lt1.pop_back();//尾删lt1.push_front(3);//头插lt1.pop_front();//头删lt1.insert(lt1.begin(), 3);//在list position 位置中插入值为val的元素lt1.erase(lt1.begin()); //删除list position位置的元素lt1.swap(lt2);//交换两个list中的元素for (auto& it : lt1){cout << it;}lt1.clear();//清空list中的有效元素for (auto& it : lt1){cout << it;}return 0;
}

三、迭代器失效

我们在平时可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无

效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入

时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭

代器，其他迭代器不会受到影响。

void TestListIterator1()
{int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array + sizeof(array) / sizeof(array[0]));auto it = l.begin();while (it != l.end()){// erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给其赋值l.erase(it);++it;}
}
// 改正
void TestListIterator()
{int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array + sizeof(array) / sizeof(array[0]));auto it = l.begin();while (it != l.end()){l.erase(it++); // it = l.erase(it);}
}

四、模拟实现

1、构造和析构

void CreateHead()
{_pHead = new Node;_pHead->_pNext = _pHead->_pPre = _pHead;_list_size = 0;
}
list()
{CreateHead();
}list(int n, const T& value = T())
{for (size_t i = 0; i < n; i++){push_back(value);}
}template <class Iterator>
list(Iterator first, Iterator last)
{auto it = first;while (it!=last){push_back(*it);it++;}
}list(const list<T>& l)
{CreateHead();for (auto& e : lt){push_back(e);}
}void swap(list<T>& l)
{std::swap(_pHead, l._pHead);std::swap(_list_size, l._list_size);
}
list<T>& operator=(const list<T> l)
{swap(lt);return *this;
}~list()
{clear();delete _pHead;_pHead = nullptr;
}

2、迭代器

由于list的储存空间不是连续的，所以我们要单独实现++/–等操作，所以我们直接放在一个类中去实现它（但是我们还是用节点指针去实现它，所以成员函数还是节点指针），这里以const_iterator为例子

template<class T>
struct list_const_iterator
{typedef list_node<T> Node;typedef list_const_iterator<T> Self;Node* _node;list_const_iterator(Node* node):_node(node){}const T& operator*(){return _node->_data;}const T* operator->()//这里主要是为了有成员变量也是类的情况{return &_node->_data;}Self& operator++(){_node = _node->_next;return *this;}Self& operator--(){_node = _node->_prev;return *this;}Self operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}Self& operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const Self& s) const{return _node != s._node;}bool operator==(const Self& s) const{return _node == s._node;}
};

但是这样写太过麻烦，我们看库里面是如何实现的：

template<class T, class Ref, class Ptr>
struct ListIterator
{typedef ListNode<T>* PNode;typedef ListIterator<T, Ref, Ptr> Self;
public:ListIterator(PNode pNode = nullptr):_node(pNode){}T& operator*(){return _node->_val;}T* operator->(){return &_node->_val;}Self& operator++() {_node = _node->_pNext;return *this;}Self& operator++(int){Self tmp(*this);_node = _node->_pNext;return tmp;}Self& operator--(){_node = _node->_pPre;return *this;}Self& operator--(int){Self tmp(*this);_node = _node->_pPre;return tmp;}bool operator!=(const Self& l) const{return _node != l._node;}bool operator==(const Self& l) const{return _node == l._node;}PNode _node;
};iterator begin(){return _pHead->_pNext;//这走隐式类型转化}iterator end(){return _pHead;}const_iterator begin() const{return _pHead->_pNext;}const_iterator end() const{return _pHead;}

这里画个图帮大家理解一下：

3、空间

size_t size()const
{return _list_size;
}
bool empty()const
{return _list_size == 0;
}

4、数据操作

// List Access
T& front()
{return _pHead->_pNext->_val;
}
const T& front()const
{return _pHead->_pNext->_val;
}
T& back()
{return _pHead->_pPre->_val;
}
const T& back()const
{return _pHead->_pPre->_val;
}// List Modifyvoid push_back(const T& val){insert(begin(), val);}void pop_back(){erase(--end());}void push_front(const T& val){insert(end(), val);}void pop_front(){erase(begin());}// 在pos位置前插入值为val的节点iterator insert(iterator pos, const T& val){Node* node = new Node(val);Node* pre = pos._node->_pPre;pre->_pNext = node;pos._node->_pPre = node;node->_pNext = pos._node;node->_pPre = pre;++_list_size;return node;}// 删除pos位置的节点，返回该节点的下一个位置iterator erase(iterator pos){assert(pos != end());//不能释放哨兵位头节点Node* pre = pos._node->_pPre;Node* next = pos._node->_pNext;pre->_pNext = next;next->_pPre = pre;delete pos._node;--_list_size;return next;}void clear(){auto it = begin();while (it != end()){it = erase(it);}_list_size = 0;}

这里唯一要注意不能删除哨兵位的节点，这样会导致无法访问该list（begin，end都和l哨兵位有关），所以erase不能删除end的节点（end指向的就是哨兵位节点）

5、总文件

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
namespace lt
{// List的节点类template<class T>struct ListNode{ListNode(const T& val = T()):_val(val),_pPre(nullptr),_pNext(nullptr){}ListNode<T>* _pPre;ListNode<T>* _pNext;T _val;};//List的迭代器类template<class T, class Ref, class Ptr>struct ListIterator{typedef ListNode<T>* PNode;typedef ListIterator<T, Ref, Ptr> Self;public:ListIterator(PNode pNode = nullptr):_node(pNode){}T& operator*(){return _node->_val;}T* operator->(){return &_node->_val;}Self& operator++() {_node = _node->_pNext;return *this;}Self& operator++(int){Self tmp(*this);_node = _node->_pNext;return tmp;}Self& operator--(){_node = _node->_pPre;return *this;}Self& operator--(int){Self tmp(*this);_node = _node->_pPre;return tmp;}bool operator!=(const Self& l) const{return _node != l._node;}bool operator==(const Self& l) const{return _node == l._node;}PNode _node;};//list类template<class T>class list{typedef ListNode<T> Node;public:typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T*> const_iterator;public:///// List的构造list(const T& value = T()){CreateHead();}list(int n, const T& value = T()){for (size_t i = 0; i < n; i++){push_back(value);}}template <class Iterator>list(Iterator first, Iterator last){auto it = first;while (it!=last){push_back(*it);it++;}}list(const list<T>& l){CreateHead();for (auto& e : lt){push_back(e);}}list<T>& operator=(const list<T> l){swap(lt);return *this;}~list(){clear();delete _pHead;_pHead = nullptr;}///// List Iteratoriterator begin(){return _pHead->_pNext;//这走隐式类型转化}iterator end(){return _pHead;}const_iterator begin() const{return _pHead->_pNext;}const_iterator end() const{return _pHead;}///// List Capacitysize_t size()const{return _list_size;}bool empty()const{return _list_size == 0;}// List AccessT& front(){return _pHead->_pNext->_val;}const T& front()const{return _pHead->_pNext->_val;}T& back(){return _pHead->_pPre->_val;}const T& back()const{return _pHead->_pPre->_val;}// List Modifyvoid push_back(const T& val){insert(begin(), val);}void pop_back(){erase(--end());}void push_front(const T& val){insert(end(), val);}void pop_front(){erase(begin());}// 在pos位置前插入值为val的节点iterator insert(iterator pos, const T& val){Node* node = new Node(val);Node* pre = pos._node->_pPre;pre->_pNext = node;pos._node->_pPre = node;node->_pNext = pos._node;node->_pPre = pre;++_list_size;return node;}// 删除pos位置的节点，返回该节点的下一个位置iterator erase(iterator pos){assert(pos != end());//不能释放哨兵位头节点Node* pre = pos._node->_pPre;Node* next = pos._node->_pNext;pre->_pNext = next;next->_pPre = pre;delete pos._node;--_list_size;return next;}void clear(){auto it = begin();while (it != end()){it = erase(it);}_list_size = 0;}void swap(list<T>& l){std::swap(_pHead, l._pHead);std::swap(_list_size, l._list_size);}private:void CreateHead(){_pHead = new Node;_pHead->_pNext = _pHead->_pPre = _pHead;_list_size = 0;}Node* _pHead;size_t _list_size = 0;};
}

五、list和vector的对比