【C++ 】list 类

1. 标准库中的list类

list 类 的介绍：

1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代

2. list与forward_list非常相似：最主要的不同在于forward_list是单链表

3. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好，只是不支持任意位置的随机访问

a. list 的构造函数

• list() (无参构造函数)
• list (const list& x) （拷贝构造）
• list (InputIterator first, InputIterator last)

（ 用[first, last)区间中的元素构造list ）

• list (size_type n, const value_type& val = value_type())

（ 构造的list中包含n个值为val的元素 ）

注意：

list 的迭代器是双向迭代器（完成 ++ , --），可以支持传单向迭代器( 完成 ++ ) 和双向迭代器

b. list 增删查改

• push_back (尾插)
• push_front (头插)
• pop_back (尾删)
• pop_front (头删)
• insert (在某一位置前增加新节点)

代码举例1

#include <iostream>
#include <list>
using namespace std;int main()
{list<int> lt;lt.push_back(0);lt.push_back(10);lt.push_back(20);lt.push_back(30);list<int> ::iterator it = lt.begin();++it;lt.insert(it,70);it = lt.begin();while(it != lt.end()){cout << *it << endl;++it;}
}

运行结果：

• earse (删除某一位置的节点)

代码举例2

#include <iostream>
#include <list>
using namespace std;int main()
{list<int> lt;lt.push_back(0);lt.push_back(10);lt.push_back(20);lt.push_back(30);list<int> ::iterator it = lt.begin();++it;lt.erase(it);it = lt.begin();while(it != lt.end()){cout << *it << endl;++it;}
}

运行结果：

• swap ( 交换两个list中的元素 )

代码举例3

#include <iostream>
#include <list>
using namespace std;int main()
{list<int> lt;lt.push_back(10);lt.push_back(20);lt.push_back(30);list<int> llt;llt.push_back(4);llt.push_back(5);llt.push_back(6);lt.swap(llt);auto it = lt.begin();while(it != lt.end()){cout << *it << " ";++it;}cout << endl;for (auto i : llt){cout << i << " ";}
}

运行结果：

• clear (清除有效节点，即不包括哨兵位)

c. list 容量

d. list 获取元素

e. list 迭代器

• begin + end ( 返回第一个元素的迭代器+ 返回最后一个元素下一个位置的迭代器 )

画图分析

• rbegin + rend （ 返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一个位置的 reverse_iterator,即begin位置 ）

注意：

反向迭代器的模拟实现和我们理解的有偏差，图上为了理解，我们可以认为rbegin是最后一个元素，rend是第一个元素的前一个位置

但是实际上，rbegin指向的位置就是end的位置，rend指向的位置就是rbegin的位置，但是在解引用时，会运算符重载 *，得到该位置的上一个位置 （详情看 list 模拟实现）

2. 迭代器失效 

list 迭代器类似一个指针，指向节点的地址 (具体详情看 list 的模拟实现)

所以在发生 erase 的时候容易造成迭代器失效(即野指针)

3. list 类的模拟实现

代码

namespace lhy
{template<class T>
struct ListNode
{
public:ListNode* prev;ListNode* next;T val;ListNode(const T& t = T()){prev = next = nullptr;val = t;}
};
template<class T,class Ref,class Ptr>
class list_iterator
{
public:typedef list_iterator<T,Ref,Ptr>  self;list_iterator(ListNode<T>* n):_node(n){}Ptr operator->(){return &_node->val;}Ref operator*(){return _node->val;}self& operator++(){_node = _node->next;return *this;}self operator++(int){self tmp = *this;_node = _node->next;return tmp;}self& operator--(){_node = _node->prev;return *this;}self operator--(int){self tmp = *this;_node = _node->prev;return tmp;}bool operator!=(const list_iterator& t){return _node != t._node;}bool operator==(const list_iterator& t){return _node == t._node;}ListNode<T>* _node;
};template<class iterator,class Ref,class Ptr>class list_converse_iterator{private:iterator com;public:typedef list_converse_iterator  self;list_converse_iterator(iterator& it):com(it){}Ptr operator->(){return &(*com);}Ref operator*(){iterator tmp = com;--tmp;return *tmp;}self& operator++(){--com;return *this;}self operator++(int){self tmp = *this;--*this;return tmp;}self& operator--(){++com;return *this;}self operator--(int){self tmp = *this;++*this;return tmp;}bool operator!=(const self& t){return com != t.com;}bool operator==(const self& t){return com == t.com;}};template<class T>class List{public:typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<T, const T&, const T*>  const_iterator;typedef list_converse_iterator<iterator, T&, T*>  converse_iterator;typedef list_converse_iterator<iterator, const T&,const T*>  const_converse_iterator;List(){node = new ListNode<T>;node->next = node;node->prev = node;}iterator begin(){return iterator(node->next);}const const_iterator begin() const{return const_iterator(node->next);}iterator end(){return iterator(node);}const const_iterator end() const{return const_iterator(node);}converse_iterator rbegin(){return converse_iterator(end());}const_converse_iterator rbegin() const{return const_converse_iterator(end());}converse_iterator rend(){return converse_iterator(begin());}const_converse_iterator rend(){return const_converse_iterator(begin());}void push_back(const T& val){ListNode<T>* ptail = node->prev;ListNode<T>* newnode = new ListNode<T>(val);ptail->next = newnode;newnode->next = node;	newnode->prev = ptail;node->prev = newnode;}void push_front(const T& x){insert(begin(), x);}void insert(iterator pos,const T &x){ListNode<T>* cur = pos._node;ListNode<T>* newnode = new ListNode<T>(x);newnode->next = cur;newnode->prev = cur->prev;cur->prev->next = newnode;cur->prev = newnode;}void earse(iterator pos){ListNode<T>* cur = pos._node;assert(cur != node);ListNode<T>* _prev = cur->prev;ListNode<T>* _next = cur->next;_prev->next = _next;_next->prev = _prev;delete cur;}
private:ListNode<T>* node;
};
}

list 迭代器的实现 

单看这一个类的实现，可能会疑惑，已经有一个 List 类了，为什么还要加一个 list_iterator 类，并且很容易发现，两个类的成员变量是一样的

如：list<int> :: iterator it;

我们希望 *it 得到的是T类型的变量（这里是int 类型）

而 it++ 得到的是下一个节点的地址

如果是只有 List 类，无法实现

因为如果 typedef ListNode* iterator

那么 *it 的类型就是 ListNode;

it++ 也不是下一个结点的地址（这是链表，开辟的空间不是连续的）

所以这里的 list_iterator 类是为了运算符重载 *和++

代码注意事项

可以和下面的对应

 

注意：

const iterator 修饰的是 （ListNode<T>*），即指针不可以更改，但是指针所指向的内容可以更改

const_iterator 修饰的是 const ListNode<T>* ,即指针所指向的内容不可更改

注意：

对于这个运算符重载，实际写的时候只要写一个 -> 就行，编译器简化两个 ->

模板第一个传的是 正向迭代器，利用正向迭代器来实现反向迭代器的功能

这里 运算符重载* 让正向迭代器--再解引用，是为了得到 原先T 类型的数据的前一个数据，原因如下：

这里传递是 end() ，但是 对应的数据不是我们想要的

才会在解引用得到前一个数据的值