优秀的国外设计网站营销型网站模板
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() ，但是 对应的数据不是我们想要的
才会在解引用得到前一个数据的值
