C++标准模板库STL——list的使用及其模拟实现

1.list的介绍

list的文档介绍

1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向
其前一个元素和后一个元素。
3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)

list的基本结构图

2.list的使用

我们这里可以简单看一下文档里面关于list各种构造函数的介绍

2.1list的构造

目前我们只掌握这四种构造函数的使用方法

代码案例

#include<iostream>
#include<list>using namespace std;void test_list1()
{list<int> lt1;   //1.这里我们构造了一个空的list对象list<int> lt2(10, 100);  // 2.这里我们通过用构造了10个100的方式构造了lt2//由于list不支持随机访问，所以下面我们需要借助迭代器遍历一下lt2cout << "lt2中的元素遍历：" << endl;list<int>::iterator it = lt2.begin();while (it != lt2.end()){cout << *it << " ";it++;}cout << endl;cout << "lt3拷贝lt2构造后的元素遍历：" << endl;list<int> lt3(lt2);list<int>::iterator its = lt3.begin();while (its != lt3.end()){cout << *its << " ";its++;}cout << endl;list<int> lt4(lt3.begin(), lt3.end());cout << "lt4用lt3的迭代器区间构造后的元素遍历：" << endl;list<int>::iterator it1 = lt4.begin();while (it1 != lt4.end()){cout << *it1 << " ";it1++;}cout << endl;}int main()
{test_list1();return 0;
}

代码运行结果：

2.2 list 迭代器 iterator 的使用

迭代器分为正向迭代器和反向迭代器，像begin() 和end()返回的是正向迭代器，rbegin()和rend()返回的是反向迭代器，然后这两种迭代器又可以和const进行结合形成上面c++11新加的cbegin()和cend(),crbegin()和crend()，其对应的迭代器名称也要跟着变化,我们可以看一下文档中的这些函数的说明,

注意

iterator T* 可读可写

const_iterator T* 只读

const iterator 这样实现是迭代器本身不能修改

const_iterator 重新定义的一个类型，做到的是本身可以修改，但是指向的内容不能修改

下面我们通过代码举个例子

测试代码：

void test_list2()
{//迭代器的使用,我们就简单通过常用的正反向迭代器进行说明,//前面加了const的迭代器只需要记得不能修改迭代器所指向的内容//1.正向迭代器，我们用简单的遍历list元素来说明list<int> lt;lt.push_back(1);    //在list里面插入6个结点lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);lt.push_back(6);cout << "正向迭代器的遍历：" << endl;list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";it++;}cout << endl;// 2.反向迭代器list<int>::reverse_iterator rit = lt.rbegin();cout << "反向迭代器的遍历：" << endl;while (rit != lt.rend()){cout << *rit << " ";rit++;}cout << endl;}

注意

1. begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
2. rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动

2.3 list的容量大小接口的使用

代码测试：

void test_list3()
{//empty()接口和size()接口的使用，你会发现跟vector相比没有capacity（）list<int>  lt;cout << "empty():" << lt.empty() << endl;cout << "size():" << lt.size() << endl;lt.push_back(1);lt.push_back(2);lt.push_back(3);cout << "插入三个元素之后" << endl;cout << "empty():" << lt.empty() << endl;cout << "size():" << lt.size() << endl;
}

运行结果：

2.4 list访问头尾元素的接口

测试代码：

void test_list4()
{//front()接口和 back()接口的测试list<int>  lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);cout << "遍历" << endl;list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";it++;}cout << endl;cout << "第一个元素" << endl;cout << lt.front() << endl;cout << "最后一个元素" << endl;cout << lt.back() << endl;
}

测试结果：

这个list底层是一个双向循环链表，所以通过头结点访问到第一个元素和最后一个元素比较简单，但是中间的元素就不支持随机访问了。

2.5 list Modifiers

我们先了解下以下这几个接口的使用方法

//头插
void push_front (const value_type& val);//头删
void pop_front();//尾插
void push_back (const value_type& val);//尾删
void pop_back();//在pos位置插入元素val
single element (1)	
iterator insert (iterator position, const value_type& val);//在pos位置插入n个元素val
fill (2)	void insert (iterator position, size_type n, const value_type& val);//在pos位置插入一段迭代器区间的结点
range (3)	
template <class InputIterator>void insert (iterator position, InputIterator first, InputIterator last);//删除pos位置的结点
iterator erase (iterator position);//删除一段迭代器区间的结点
iterator erase (iterator first, iterator last);//交换两个链表，实际上只需要将头结点的指针跟大小size进行交换即可
void swap (list& x);//将链表数据清空
void clear();

下面带大家来看看我们的使用案例

测试代码：

void test_list5()
{list<int> lt;//尾插for (int i = 0; i < 10; i++)//尾插后的结点值是0 1 2 3 4 5 6 7 8 9{lt.push_back(i);}//我们这里使用简单的范围for来进行遍历cout << "尾插后链表中的结点值为：" << endl;for (auto e : lt)//范围for借助迭代器自动推导e的类型，自动给e赋值，自动往后++{cout << e << " ";}cout << endl;//头插lt.push_front(10);lt.push_front(20);    //头插这两个结点后变成：20 10 0 1 2 3 4 5 6 7 8 9cout << "头插后的链表结点值为：" << endl;for (auto e : lt){cout << e << " ";}cout << endl;//头删lt.pop_front();lt.pop_front();lt.pop_front();     //头删之后变成：1 2 3 4 5 6 7 8 9cout << "头删之后：" << endl;for (auto e : lt){cout << e << " ";}cout << endl;//尾删lt.pop_back();lt.pop_back();lt.pop_back();     //尾删之后变成： 1 2 3 4 5 6cout << "尾删之后：" << endl;for (auto e : lt){cout << e << " ";}cout << endl;//在pos位置插入一个值为val的结点list<int>::iterator it = lt.begin();it++;lt.insert(it, 20);  //此时变成 1 20 2 3 4 5 6cout << "在第2个结点位置插入一个20:" << endl;for (auto e : lt){cout << e << " ";}cout << endl;//在pos位置插入n个值为val的结点it++;++it;lt.insert(it, 5, 30);//在第4个结点的位置插入5个30cout << "在第4个结点的位置插入5个30后：" << endl;for (auto e : lt){cout << e << " ";}cout << endl;//在pos位置插入一段迭代器区间list<int> lt2(10, 100);lt.insert(it, lt2.begin(), lt2.end());//将lt2的10个值为100的结点从lt的第4个结点插入cout << "插入一段迭代器区间之后:" << endl;for (auto e : lt){cout << e << " ";}cout << endl;//删除pos位置的结点   这里我们会涉及一个迭代器失效的问题，我们后面再说it = lt.erase(it);cout << "删除it位置的结点后：" << endl;for (auto e : lt){cout << e << " ";}cout << endl;//删除一段迭代器区间的结点it = lt.erase(it, lt.end());//我们将it以及之后的结点都删除cout << "将it后面位置的结点都删除了" << endl;for (auto e : lt){cout << e << " ";}cout << endl;//交换两个链表//我们先看看lt和lt2的两个链表结点的值，然后交换cout << "lt：" << endl;for (auto e : lt){cout << e << " ";}cout << endl;cout << "lt2:" << endl;for (auto e : lt2){cout << e << " ";}cout << endl;//交换后lt.swap(lt2);cout << "交换后：" << endl;cout << "lt：" << endl;for (auto e : lt){cout << e << " ";}cout << endl;cout << "lt2:" << endl;for (auto e : lt2){cout << e << " ";}cout << endl;//将链表数据清空cout << "将两个链表的数据都清空之后：" << endl;lt.clear();lt2.clear();cout << "lt：" << endl;for (auto e : lt){cout << e << " ";}cout << endl;cout << "lt2:" << endl;for (auto e : lt2){cout << e << " ";}cout << endl;}

测试结果：

2.6 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;}
}

运行这段代码之后，因为迭代器失效导致运行失败

所以当我们删除了某个结点之后，迭代器需要重新赋值，而为了解决这个问题，给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);}
}

这样就没有什么大问题了

3. list 的模拟实现

#pragma once
#include<string>
#include<vector>
#include<iostream>using namespace std;
namespace mylist 
{template<class T>//链表的每个结点的结构struct list_node {T _data;            //存放数据list_node<T>* _prev;//指向前一个结点的指针list_node<T>* _next;//指向后一个结点的指针list_node(const T& val = T())  //构造一个结点对象:_data(val), _prev(nullptr), _next(nullptr){ }};// T T& T*// T cosnt T& const T*template<class T,class Ref,class Ptr>struct __list_iterator                   //list的迭代器结构{typedef list_node<T> Node;             //结点typedef __list_iterator<T,Ref,Ptr> _self; //_self就是一个实例化的迭代器Node* _node;                          //结点的指针__list_iterator(Node* node):_node(node){}Ref operator*()                //重载运算符* 通过*能够访问结点里面的数据{return _node->_data;}Ptr operator->()         //重载-> ， 结构体指针访问成员可以用结构体对象->结构体成员{return &_node->_data;}_self& operator++()   //重载运算符前置++,返回下一个结点的迭代器{_node = _node->_next;return (*this);}_self& operator--()  //重载运算符前置--,返回前一个结点的迭代器{_node = _node->_prev;return (*this);}_self operator++(int)  //重载运算符后置++,返回当前结点的迭代器的拷贝再++{Node* tmp(_node);_node = _node->_next;return tmp;}_self operator--(int) //重载运算符前置--,返回当前一个结点迭代器的拷贝再--{Node* tmp(_node);_node = _node->_prev;return tmp;}bool operator!=(const _self& n)  //重载迭代器的比较运算符!={return this->_node != n._node;}bool operator==(const _self& n)  //重载迭代器的比较运算符=={return this->_node == n._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;const_iterator begin() const{return const_iterator(_head->_next);}const_iterator end() const{return const_iterator(_head);}iterator begin(){return (_head->_next);}iterator end(){return _head;}void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}list(){empty_init();}//lt1(lt2)list(const list<T>& lt){empty_init();for (auto e : lt){push_back(e);}}~list(){clear();delete _head;_head = nullptr;}list<int>& operator=(list<int>lt){swap(lt);return *this;}void push_back(const T& x){insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_back(const T& x){erase(--end());}void pop_front(const T& x){erase(begin());}iterator insert(iterator pos, const T& x){Node* newnode = new Node(x);Node* cur = pos._node;Node* prev = cur->_prev;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;++_size;return iterator(newnode);}iterator erase(iterator pos){Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;delete cur;prev->_next = next;next->_prev = prev;--_size;return iterator(next);}size_t size(){return _size;}private:Node* _head; //list的头结点size_t _size;//list的大小};
}