list_1">list介绍
- list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
- list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
- list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
- 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率好。
- 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)
list_10">list的使用
list中的接口比较多，此处类似，只需要掌握如何正确的使用，然后再去深入研究背后的原理，已达到可扩展
的能力。以下为list中一些常见的重要接口：
list构造
| 构造函数 | 接口说明 |
|---|---|
| list (size_type n, const value_type& val = value_type()) | 构造的list中包含n个值为val的元素 |
| list() | 构造空的list |
| list (const list& x) | 拷贝构造函数 |
| list (InputIterator first, InputIterator last) | 用[first, last)区间中的元素构造list |
list_iterator_25">list iterator的使用
此处，大家可暂时将迭代器理解成一个指针，该指针指向list中的某个节点。
| 函数声明 | 接口说明 |
|---|---|
| begin + end | 返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器 |
| rbegin + rend | 返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一个位置的reverse_iterator,即begin位置 |
【注意】
- begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动。
- rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动。
list capacity
| 函数声明 | 接口说明 |
|---|---|
| empty | 检测list是否为空，是返回true，否则返回false |
| size | 返回list中有效节点的个数 |
list element access
| 函数声明 | 接口说明 |
|---|---|
| front | 返回list的第一个节点中值的引用 |
| back | 返回list的最后一个节点中值的引用 |
list_modifiers_57">list modifiers
| 函数声明 | 接口说明 |
|---|---|
| push_front | 在list首元素前插入值为val的元素 |
| pop_front | 删除list中第一个元素 |
| push_back | 在list尾部插入值为val的元素 |
| pop_back | 删除list中最后一个元素 |
| insert | 在list position 位置中插入值为val的元素 |
| erase | 删除list position位置的元素 |
| swap | 交换两个list中的元素 |
| clear | 清空list中的有效元素 |
list_70">list的迭代器失效
前面说过，此处大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节
点被删除了。因为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);}
}
list_105">list的模拟实现
要模拟实现list，必须要熟悉list的底层结构以及其接口的含义，通过上面的学习，这些内容已基本掌握，现
在我们来模拟实现list。
#pragma once
template<class Iterator, class Ref, class Ptr>
struct ReverseIterator {typedef ReverseIterator<Iterator, Ref, Ptr> self;//// 构造ReverseIterator(Iterator it):_cur(it){}//// 迭代器支持移动self& operator++(){--_cur;return *this;}self operator++(int){self temp(*this);--_it;return temp;}self& operator--(){++_it;return *this;}self operator--(int){self temp(*this);++_it;return temp;}//// 具有指针类似行为Ref operator*(){Iterator tmp = _cur;--tmp;return *tmp;}Ptr operator->(){return &(operator*());}//// 迭代器支持比较bool operator!=(const self& s){return _cur != s.cur;}bool operator==(const self& s){return _cur == s.cur;}Iterator _cur;
};
#include<iostream>
#include<assert.h>
#include"ReverseIterator.h"
using namespace std;
namespace jz {template<class T> struct listnode {//成员属性listnode<T>* _next;listnode<T>* _prev;T _data;//成员函数listnode(const T& x = T()):_next(nullptr),_prev(nullptr),_data(x){}};/*List 的迭代器迭代器有两种实现方式，具体应根据容器底层数据结构实现：1. 原生态指针，比如：vector2. 将原生态指针进行封装，因迭代器使用形式与指针完全相同，因此在自定义的类中必须实现以下方法：1. 指针可以解引用，迭代器的类中必须重载operator * ()2. 指针可以通过->访问其所指空间成员，迭代器类中必须重载oprator->()3. 指针可以++向后移动，迭代器类中必须重载operator++()与operator++(int)至于operator--() / operator--(int)释放需要重载，根据具体的结构来抉择，双向链表可以向前移动，所以需要重载，如果是forward_list就不需要重载--4. 迭代器需要进行是否相等的比较，因此还需要重载operator == ()与operator != ()*/template<class T,class Ref,class Ptr>struct _list_iterator {//成员属性typedef listnode<T> Node;typedef _list_iterator<T,Ref,Ptr> self;public://// 构造_list_iterator(Node* x):_node(x){}//// 迭代器支持移动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;}//// 具有指针类似行为Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}//// 迭代器支持比较bool operator==(const self& s){return _node == s._node;}bool operator!=(const self& s){return _node != s._node;}Node* _node;};template<class T>class list {typedef listnode<T> Node;public://正向迭代器typedef _list_iterator<T, T&, T*> iterator;typedef _list_iterator<T, const T&, const T*> const_iterator;//反向迭代器typedef ReverseIterator<iterator, T&, T*> reverse_iterator;typedef ReverseIterator<const_iterator,const T&,const T*> const_reverse_iterator;///// List的构造list(){empty_init();}list(list<T>& s){empty_init();for (const auto& it : s){push_back(it);}}list(int n, const T& value = T()){empty_init();for (int i = 0; i < n; ++i)push_back(value);}template <class Iterator>list(Iterator first, Iterator last){empty_init();while (first != last){push_back(*first);++first;}}list<T>& operator=(list<T> lt){swap(lt);return *this;}~list(){clear();delete _head;_head = nullptr;}///// List的迭代器iterator begin(){return _head->_next;}iterator end(){return _head;}const_iterator begin() const{return _head->_next;}const_iterator end() const{return _head;}reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}const_reverse_iterator rbegin() const{return reverse_iterator(end());}const_reverse_iterator rend() const{return reverse_iterator(begin());}///// List的容量相关size_t size() const{Node* cur = _head->_next;size_t count = 0;while (cur != _head){count++;cur = cur->_next;}return count;}bool empty() const {return _head->_next == _head;}void resize(size_t newsize, const T& data = T()){size_t oldsize = size();if (newsize <= oldsize){// 有效元素个数减少到newsizewhile (newsize < oldsize){pop_back();oldsize--;}}else{while (oldsize < newsize){push_back(data);oldsize++;}}}// List的元素访问操作// 注意：List不支持operator[]T& front(){return _head->_next->_val;}const T& front()const{return _head->_next->_val;}T& back(){return _head->_prev->_val;}const T& back()const{return _head->_prev->_val;}// List的插入和删除void push_back(const T& x){insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}// 在pos位置前插入值为val的节点iterator insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;//prev cur nextNode* newnode = new Node(x);prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;return newnode;}// 删除pos位置的节点，返回该节点的下一个位置iterator erase(iterator pos){assert(pos != end());Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;return next;}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}void swap(list<T>& lt){std::swap(_head, lt._head);}private:void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;}private:Node* _head;};void print_list(const list<int>& lt){list<int>::const_iterator it = lt.begin();while (it != lt.end()){//*it += 10;cout << *it << " ";++it;}cout << endl;for (auto e : lt){cout << e << " ";}cout << endl;}///
// 对模拟实现的list进行测试
// 正向打印链表template<class T>void PrintList(const list<T>& l){auto it = l.begin();while (it != l.end()){cout << *it << " ";++it;}cout << endl;}void test(){list<int> l1;list<int> l2(10, 5);PrintList(l2);int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l3(array, array + sizeof(array) / sizeof(array[0]));PrintList(l3);list<int> l4(l3);PrintList(l4);l1 = l4;PrintList(l1);}
}
欢迎留言！！！
（全文完)
