STL——list

一、list介绍及使用

1. list文档介绍

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

（2）list的底层是带头结点的双向循环链表，其中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。

（3）list和forward_list非常相似。最主要的不同在于forward_list是单链表，只能朝前迭代。

（4）与其他的序列式容器相比（array、vector、deque），list通常在任意位置的插入、删除元素的执行效率更高。

（5）与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问。

2. list常用接口介绍

2.1 list的构造

2.2 list iterator的使用

2.3 list capacity

 

2.4 list 元素访问

2.5 list 元素修改

3. list迭代器失效问题

3.1迭代器失效

        迭代器失效，即迭代器所指向的节点无效，在list中即该节点被删除了。

        因为list的底层结构为带头节点的双向循环链表，因此在list中插入元素是不会导致list迭代器失效，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

3.2 list可能导致迭代器失效的操作

        pop_back、pop_front、erase、resize、assign……

3.3解决方法

        在所有可能导致迭代器失效的操作之后，在使用迭代器前对迭代器进行重新赋值。

二、list与vector的区别★

 注意：

        空间利用率上，只是绝大多数情况下vector比list高，因为list每个节点多了两个指针域，但并不绝对。

三、模拟实现list

1.实现接口

1.1私有成员

void CreateHead();//创建头节点
Node* _head;

1.2默认成员

//默认构造函数
list();
//n个value构造
list(size_t n, const T& value = T());
template<class Iterator>
//区间构造
list(Iterator first, Iterator last);
//拷贝构造
list(const list<T>& L);
//赋值运算符重载
list<T>& operator=(list<T> L)//析构函数
~list();

1.3迭代器

注意：

        list迭代器不能使用原生态的指针，因为list空间不连续，不能对指针进行算数运算。所以需要自己模拟封装迭代器对应类

template<class T, class Ref, class Ptr>
struct ListIterator;
template<class Iterator>
struct ListReverseIterator;iterator begin();
iterator end();
const_iterator cbegin() const;
const_iterator cend() const;
reverse_iterator rbegin();
reverse_iterator rend();
const_reverse_iterator crbegin() const;
const_reverse_iterator crend() const;

1.4容量

size_t size() const ;
bool empty() ;
void resize(size_t newSize, const T& value = T()) ;

1.5元素访问

T& front();
const T& front() const;
T& back();
const T& back() const ;

1.6元素修改

void push_front(const T& value);
void pop_front();
void push_back(const T& value) ;
void pop_back();
iterator insert(iterator it, const T& value);
iterator erase(iterator it);
void clear();
void swap(list<T>& L) ;

2.代码实现

#include <iostream>
using namespace std;namespace MyList {//链表节点template<class T>struct ListNode {ListNode<T>* _next;ListNode<T>* _prev;T _val;ListNode(const T& value = T()): _next(nullptr), _prev(nullptr), _val(value){}};//注意：list迭代器不能使用原生态的指针//因为list空间不连续，不能对指针进行算数运算//模拟封装迭代器类template<class T, class Ref, class Ptr>struct ListIterator {typedef ListNode<T> Node;typedef Ref ItRef;typedef Ptr ItPtr;typedef ListIterator<T, Ref, Ptr> Self;public://构造ListIterator(Node* node = nullptr):_node(node){}/*----------实现类似指针的操作----------*/Ref operator*() {return _node->_val;}Ptr operator->() {return &(operator*());}/*----------实现"++""--"----------*/Self& operator++() {_node = _node->_next;return *this;}Self operator++(int) {Self temp(*this);_node = _node->_next;return temp;}Self& operator--() {_node = _node->_prev;return *this;}Self& operator--(int) {Self temp(*this);_node = _node->_prev;return temp;}/*----------实现比较----------*/bool operator!=(const Self& s) const {return _node != s._node;}bool operator==(const Self& s) const {return _node == s._node;}public:Node* _node;};//模拟封装反向迭代器：内部封装正向迭代器即可template<class Iterator>struct ListReverseIterator {//因为静态成员变量也可以通过类名::静态成员名称的方式进行访问//直接写会编译报错，编译器不确定ItRef、ItPtr是静态成员变量还是类型//所以需要显示告诉编译器是typenametypedef typename Iterator::ItRef Ref;typedef typename Iterator::ItPtr Ptr;typedef ListReverseIterator<Iterator> Self;public:ListReverseIterator(Iterator it):_it(it){}Ref operator*() {Iterator temp(_it);--temp;return *temp;}Ptr operator->() {return &(*operator*());}Self& operator++() {--_it;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;}bool operator!=(const Self& rit) const {return _it != rit._it;}bool operator==(const Self& rit) const {return _it == rit._it;}public:Iterator _it;//正向迭代器};/*=========================================================================================*/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;typedef ListReverseIterator<iterator> reverse_iterator;typedef ListReverseIterator<const_iterator> const_reverse_iterator;public:/*----------默认成员----------*///默认构造函数list() {CreateHead();}//n个value构造list(int n, const T& value = T()) {CreateHead();for (int i = 0; i < n; ++i) { push_back(value); }}template<class Iterator>//区间构造list(Iterator first, Iterator last) {CreateHead();while (first != last) {push_back(*first);++first;}}//拷贝构造list(const list<T>& L) {CreateHead();auto it = L.cbegin();while (it != L.cend()) {push_back(*it);++it;}}//赋值运算符重载list<T>& operator=(list<T> L) {this->swap(L);return *this;}//析构函数~list() {clear();delete _head;_head = nullptr;}/*----------迭代器----------*/iterator begin() {return iterator(_head->_next);}iterator end() {return iterator(_head);}const_iterator cbegin() const {return const_iterator(_head->_next);}const_iterator cend() const {return const_iterator(_head);}reverse_iterator rbegin() {return reverse_iterator(end());}reverse_iterator rend() {return reverse_iterator(begin());}const_reverse_iterator crbegin() const {return const_reverse_iterator(cend());}const_reverse_iterator crend() const {return const_reverse_iterator(cbegin());}/*----------容量----------*/size_t size() const {Node* cur = _head->_next;size_t count = 0;while (cur != _head) {++count;cur = cur->_next;}return count;}bool empty() {return _head->_next == _head;}void resize(size_t newSize, const T& value = T()) {size_t oldSize = size();if (newSize < oldSize) {for (size_t i = oldSize; i > newSize; --i) { pop_back(); }}else {for (size_t i = oldSize; i < newSize; ++i) { push_back(value); }}}/*----------元素访问----------*/T& front() {return *begin();}const T& front() const {return *cbegin();}T& back() {return *(--end);}const T& back() const {return *(--cend);}/*----------元素修改----------*/void push_front(const T& value) {insert(begin(), value);}void pop_front() {erase(begin());}void push_back(const T& value) {insert(end(), value);}void pop_back() {erase(end()--);}iterator insert(iterator it, const T& value) {Node* pos = it._node;//插入方式，将新节点连接进去，再断开原链表Node* temp = new Node(value);//(1)连接temp->_next = pos;temp->_prev = pos->_prev;//(2)断开temp->_prev->_next = temp;temp->_next->_prev = temp;return iterator(temp);}iterator erase(iterator it) {if (it == end()) return end();Node* pos = it._node;Node* ret = pos->_next;pos->_prev->_next = pos->_next;pos->_next->_prev = pos->_prev;delete pos;return iterator(ret);}void clear() {auto it = begin();while (it != end()) {it = erase(it);//记得重新赋值，防止迭代器失效}}void swap(list<T>& L) {std::swap(_head, L._head);}/*----------私有成员----------*/private:void CreateHead() {//创建头节点_head = new Node();_head->_next = _head;_head->_prev = _head;}Node* _head;};
}