STL-list类

list实际上是数据结构中的带头双向循环链表

由于链表的存储方式并不是连续的内存空间，因此链表list中的迭代器只支持前移(++)和后移(--)，属于双向迭代器。

一、常见接口

官方文档：list - C++ Reference (cplusplus.com)

1.1 构造函数

函数名	功能
list (size_type n, const value_type& val = value_type())	构造的list中包含n个值为val的 元素
list()	构造空的list
list (const list& x)	拷贝构造函数
list (InputIterator first, InputIterator last)	迭代器区间构造

void test1()
{    list<int> l1;                         // 构造空的l1list<int> l2(4, 100);                 // l2中放4个值为100的元素list<int> l3(l2.begin(), l2.end());  // 用l2的[begin(), end()）左闭右开的区间构造l3list<int> l4(l3);                    // 用l3拷贝构造l4
}

1.2 访问与遍历

函数名	功能
begin+ end	获取第一个数据位置的iterator/const_iterator，获取最后一个数据的下一个位置的iterator/const_iterator
rbegin + rend	获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置的reverse_iterator
范围for	搭配auto实现遍历

void test1()
{list<int> l1;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);l1.push_back(5);list<int>::iterator it = l1.begin();while (it != l1.end()){cout << *it << " ";++it;}cout << endl;for (auto e : l1){cout << e << " ";}cout << endl;}

1.3 容量操作

函数名	功能
empty	检测list是否为空，是返回true，否则返回false
size	返回list中有效节点的个数
front	返回list的第一个节点中值的引用
back	返回list的最后一个节点中值的引用
resize(num)	重新指定容器的长度为num 若容器变长，则以默认值填充新位置。 如果容器变短，则末尾超出容器长度的元素被删除。

1.4 增删查改

函数名	功能
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中的有效元素
remove(elem)	删除容器中所有与elem值匹配的元素

//插入和删除
void test1()
{list<int> L;//尾插L.push_back(10);L.push_back(20);L.push_back(30);//头插L.push_front(100);L.push_front(200);L.push_front(300);//尾删L.pop_back();printList(L);//头删L.pop_front();printList(L);//插入list<int>::iterator it = L.begin();L.insert(++it, 1000);//删除it = L.begin();L.erase(++it);//移除L.push_back(10000);L.push_back(10000);L.push_back(10000);//L.remove(10000);//清空L.clear();
}
//迭代器的底层不是原生指针
//迭代器分类
//单向：forward	-	++
//双向：bidirectional	-	++/--
//随机：random	-	++/--/+/-
void test2()
{list<int> l1;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);l1.push_back(5);//如何在特定位置插入？auto it = l1.begin();int k = 3;while (--k){++it;}l1.insert(it, 6);for (auto e : l1){cout << e << " ";}cout << endl;l1.erase(it);for (auto e : l1){cout << e << " ";}cout << endl;
}

二、模拟实现

2.1 迭代器失效

迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。与vector类的失效不同。

2.2 迭代器实现

template<class T,typename Ref,typename Ptr>
struct list_iterator
{typedef list_node<T> Node;typedef list_iterator<T, Ref, Ptr> Self;Node* _node;list_iterator(Node* node):_node(node){}Ref 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;}Ptr operator->(){return &_node->_data; }bool operator!=(const Self& s) const{return _node != s._node;}bool operator==(const Self& s) const{return _node == s._node;}
};

2.3 源代码

#pragma once
#include<iostream>
#include<assert.h>using namespace std;namespace paradiso
{template<class T>struct list_node{T _data;list_node<T>* _next;list_node<T>* _prev;list_node(const T& data = T()):_data(data), _next(nullptr), _prev(nullptr){}};template<class T,typename Ref,typename Ptr>struct list_iterator{typedef list_node<T> Node;typedef list_iterator<T, Ref, Ptr> Self;Node* _node;list_iterator(Node* node):_node(node){}Ref 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;}Ptr operator->(){return &_node->_data; }bool operator!=(const Self& s) const{return _node != s._node;}bool operator==(const Self& s) const{return _node == s._node;}};template<class T>class list{typedef list_node<T> Node;public:typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<T, const T&, const T*> const_iterator;iterator begin(){return _head->_next;}iterator end(){return _head;}const_iterator begin() const{return _head->_next;}const_iterator end() const{return _head;}void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}list(){empty_init();}list(list<T>& lt){empty_init();for (auto& e : lt){push_back(e);}}list<T>& operator=(list<T>& lt){swap(lt);return *this;}~list(){clear;delete _head;_head = nullptr;}void clear(){auto it = begin();while (it != end()){it = erase(it);++it;}}void push_back(const T& x){Node* newnode = new Node(x);Node* tail = _head->_prev;tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;++_size;//insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);// prev newnode curnewnode->_next = cur;cur->_prev = newnode;newnode->_prev = prev;prev->_next = newnode;++_size;}void pop_back(){erase(--end());}void pop_front(){erase(begin());}iterator erase(iterator pos){assert(pos != end());Node* prev = pos._node->_prev;Node* next = pos._node->_next;prev->_next = next;next->_prev = prev;delete pos._node;--_size;return next;}size_t size() const{return _size;}bool empty() const{return _size == 0;}private:Node* _head;size_t _size;};
}