【C++ STL】list详解和模拟
文章目录
- 前言
- 1. list的数据结构
- 2. list的迭代器
- 3. list的接口
- 3.1 clear
- 3.2 remove
- 3.3 unique
- 3.4 splice
- 3.5 merge
- 3.6 reverse 和 sort
- 4. list模拟实现
- 4.1 默认成员函数
- 4.2 迭代器设计
- 4.2.1 正向迭代器
- 4.2.2 反向迭代器
- 4.2.3 list的迭代器
- 4.3 增删改
- 4.3.1 insert和erase……
- 4.3.2 emplace
- 模拟源码
前言
list文档
相较于vector的连续的空间线性空间，而list是基于节点。每次插入或者删除一个元素的，就配置或释放一个元素的空间。因此，list对于空间的运用是不会产生浪费的……而且，面对插入删除操作，list的常数级别的时间。
事实上，vector和list各有优劣。在各自的擅长领域做到了极致。所以具体场景具体分析使用哪种容器就可以。并且事实上，并非所有容器的使用都是非此即彼的……
-
主要目的：
- 学习list的接口使用
- 锻炼代码能力，尝试体会STL中迭代器设计的思想。体会迭代器在STL中的超核心作用。
1. list的数据结构
-
list的节点：list和list node是不同的结构。list相当于是node的集合。我们需要了解，在STL 中的结点的字段会有什么，也方便我们后续设计list：
template<class T>
struct __list_node
{typedef void* void_pointer;void_pointer prev; //指向前一个节点的指针void_pointer next; //指向后一个对象的指针T data; //数据
};
我们看到：在STL list源码中，利用的C语言的泛型的思想（利用void*接受任意类型）。但是实际上我们设计的时候不用这么麻烦，因为我们只需要设置类型为：__list_node<T> *即可了……
从上面的节点结构来看，我们可以得出一个目前来说的结论：list是一个双向链表。
SGI的list不仅仅是一个双向链表，更是一个带头节点的双向循环链表。这也符合STL对迭代器的要求。对于list这样的数据结构来说，在逻辑上的线性空间，显然list支持迭代器的遍历效果。而STL要求的迭代器区间是：[begin, end)和[rbegin, rend)的要求的……而且对于插入删除操作来说，才能完成真正意义上的O(1)时间复杂度！！！
- 因为
list是双向循环链表，所以我们仅仅根据一个节点指针就可以得到整个list。而这个指针一般是头节点的指针！
我们来看示意图：
2. list的迭代器
-
根据上面所示的
list的数据结构图，我们大概率能得知，list的迭代器是不可能像vector那样用原生指针去作为迭代器，因为其node不保证在储存空间中连续存在。list迭代器必须有能力指向list的node，并且有能力进行正确的加、减、取值等等操作。所以，我们就不得不对list的迭代器进行封装。恰好，我们可以通过包装class来描述迭代器，并通过实现operator重载函数来实现迭代器的正常操作！！ -
由于STL
list是一个双向链表（double linked-list），迭代器必须具备前移、后移的能力，所以list提供的是Bidirectional Iterator（双向迭代器）。不支持随机的数据+=这样的操作…… -
list迭代器有一个重要的性质：insert和erase等等操作，都不会造成原有的list迭代器失效。因为list的数据空间是不连续的，是数据之间的关系是比较独立的。 -
迭代器操作示意图：
3. list的接口
- 在这里不再介绍
list的构造，增删……的接口了。我们直接看一些可能有用到但是不常用的接口。
3.1 clear
-
接口原型：
-
作用：清空链表内容……
例1：
int main()
{std::list<int> lt;for (int i = 0; i < 5; ++i){lt.push_back(i);lt.push_back(i);}for (const auto& e : lt){cout << e << " ";}cout << endl;lt.clear();for (const auto& e : lt){cout << e << " ";}return 0;
}
完成对list内容的清空。
3.2 remove
-
接口原型：
-
作用：将
list中所有值为val的元素删除。
例2：
int main()
{int arr[] = { 0,0,1,1,2,2,3,3,4,4,3,4,3 };std::list<int> lt(arr, arr + sizeof(arr)/sizeof(arr[0]));for (const auto& e : lt){cout << e << " ";}cout << endl;lt.remove(3);for (const auto& e : lt){cout << e << " ";}return 0;
}
完成对list中元素值为3的数据，进行删除。
3.3 unique
- 接口原型：
例3：
int main()
{int arr[] = { 0,0,1,1,2,2,3,3,4,4,3,4,3 };std::list<int> lt(arr, arr + sizeof(arr)/sizeof(arr[0]));for (const auto& e : lt){cout << e << " ";}cout << endl;lt.unique();for (const auto& e : lt){cout << e << " ";}return 0;
}
特定：可以用来对有序的list进行去重操作。如果想要对list用unique进行去重，那么需要在使用之前对list进行sort。
例4：
#include <string>struct Person
{std::string name;int age;
};int main()
{std::list<Person> people = {{"Alice", 20},{"Bob", 20},{"Charlie", 25},{"David", 25}};// 按年龄判定重复（年龄相同视为重复）people.unique([](const Person& a, const Person& b) {return a.age == b.age;});// 输出结果：Alice(20) Charlie(25)for (const auto& p : people) {std::cout << p.name << "(" << p.age << ") ";}return 0;
}
自定义比较方法
3.4 splice
- 接口原型：
- 作用：在一个list中插入一段list区间。（可以是别人的区间，也可以是自己的……）
例5：
#include <iostream>
#include <list>// 打印列表内容的辅助函数
void print_list(const std::list<int>& l, const std::string& name) {std::cout << name << ": ";for (int num : l) {std::cout << num << " ";}std::cout << std::endl;
}int main() {// 初始化两个列表std::list<int> list1 = {1, 2, 3};std::list<int> list2 = {4, 5, 6};print_list(list1, "初始 list1"); // list1: 1 2 3 print_list(list2, "初始 list2"); // list2: 4 5 6 // 1. 转移整个列表（将list2所有元素转移到list1末尾）auto it = list1.end(); // 插入点：list1的末尾list1.splice(it, list2);print_list(list1, "转移后 list1"); // list1: 1 2 3 4 5 6 print_list(list2, "转移后 list2"); // list2: （为空）// 重新初始化list2list2 = {7, 8, 9};print_list(list2, "重置后 list2"); // list2: 7 8 9 // 2. 转移单个元素（将list2的第一个元素转移到list1的开头）it = list1.begin(); // 插入点：list1的开头auto single_it = list2.begin(); // 要转移的元素：7list1.splice(it, list2, single_it);print_list(list1, "转移单个元素后 list1"); // list1: 7 1 2 3 4 5 6 print_list(list2, "转移单个元素后 list2"); // list2: 8 9 // 3. 转移元素范围（将list2的所有元素转移到list1中3的前面）// 找到list1中值为3的元素位置for (it = list1.begin(); it != list1.end(); ++it) {if (*it == 3) break;}// 转移list2的所有元素（范围为[begin, end)）list1.splice(it, list2, list2.begin(), list2.end());print_list(list1, "转移范围后 list1"); // list1: 7 1 2 8 9 3 4 5 6 print_list(list2, "转移范围后 list2"); // list2: （为空）return 0;
}
3.5 merge
-
接口原型：
-
作用：将两个元素有序list进行按照方法进行合并……
例6：
#include <iostream>
#include <list>// 打印列表内容
void print_list(const std::list<int>& l, const std::string& name) {std::cout << name << ": ";for (int num : l) {std::cout << num << " ";}std::cout << std::endl;
}int main() {// 1. 基本用法（默认升序合并）std::list<int> list1 = {1, 3, 5};std::list<int> list2 = {2, 4, 6};print_list(list1, "合并前 list1"); // list1: 1 3 5 print_list(list2, "合并前 list2"); // list2: 2 4 6 list1.merge(list2); // 合并list2到list1（均为升序）print_list(list1, "合并后 list1"); // list1: 1 2 3 4 5 6 print_list(list2, "合并后 list2"); // list2: （为空）// 2. 自定义比较规则（降序合并）std::list<int> list3 = {6, 4, 2};std::list<int> list4 = {5, 3, 1};print_list(list3, "合并前 list3"); // list3: 6 4 2 print_list(list4, "合并前 list4"); // list4: 5 3 1 // 自定义降序比较器auto desc_comp = [](int a, int b) { return a > b; };list3.merge(list4, desc_comp); // 按降序合并print_list(list3, "降序合并后 list3"); // list3: 6 5 4 3 2 1 print_list(list4, "降序合并后 list4"); // list4: （为空）return 0;
}3.6 reverse 和 sort
-
reverse：将list进行元素的反转。 -
sort：由于
list的迭代器类型是双向迭代器，而C++库<algorithm>中的sort方法底层采用快排的算法，这就要求我们不能用库中sort方法排序。所以list自己实现了排序方法。但是，list的内部的排序方法时间复杂度特别高……甚至不如我们将list的数据拷贝到vector中，再利用库中的sort进行排序，再拷贝会去的效率高（我们可以写程序验证）：
例7：
int main()
{srand((unsigned int)time(nullptr));std::list<int> lt1;for (int i = 0; i < 10000000; ++i) //1000w的数据量{lt1.push_back(rand());}std::list<int> lt2(lt1);int begin1 = clock();lt1.sort();int end1 = clock();int begin2 = clock();std::vector<int> v;for (auto e : lt2) //不用列表，效率低{v.push_back(e); }std::sort(v.begin(), v.end());//lt2 = { v.begin(), v.end() }; //列表，效率很低auto it = lt2.begin();int i = 0;for (auto& e : lt2){e = v[i++];}int end2 = clock();cout << "lt1的直接排序时间" << end1 - begin1 << endl;cout << "lt2的拷贝排序时间" << end2 - begin2 << endl;return 0;
}
4. list模拟实现
-
节点：
我们先把节点搭建出来：
template <class T>
struct list_node
{list_node(const T& val = T()) : _data(val),_prev(nullptr), _next(nullptr){ }list_node(T&& val = T()) //移动构造，为了让数据调用移动构造: _data(std::forward<T>(val)), _prev(nullptr), _next(nullptr){} list_node<T>* _prev;list_node<T>* _next;T _data;
};
- 框架：
template <class T>
class list
{typedef list_node<T> node;
public://……对外接口
private:node* _head;
};
4.1 默认成员函数
- 实现比较简单，我们的大多默认成员函数可以通过复用的方式进行。
- 注：大多数接口都需要迭代器完成。
public:list() //默认构造函数{empty_initnode(); //调用函数构造一个节点}list(const list<T>& lt) //拷贝构造函数{empty_initnode();for (const auto& e : lt){//push_back(e); //一直尾插即可，后面实现尾插接口}}list(list<T>&& tmp) //移动构造函数{empty_initnode();swap(tmp); //调用类中实现的方法}~list() //析构函数{clear(); //直接调用clear函数，将链表节点全部清空delete _head;_head = nullptr;}const list<T>& operator=(const list<T>& obj) //赋值重载{if (this != &obj){for (const auto& e : obj){//push_back(lt); //同}}return *this;}const list<T>& operator=(list<T>&& tmp) //移动赋值{if (this != &tmp){swap(tmp);}return *this;}void clear(){//调用pop_front/pop_back即可//TODO}
private:void empty_initnode() //一个空的构造{if (nullptr == _head){_head = new node(); //默认构造一个头节点_head->_next = _head; //下一个节点指向自己_head->_prev = _head; //上一个节点也指向自己}}void swap(list<T>& tmp){std::swap(_head, tmp._head); //交换指针即可}
private:node* _head;
};
4.2 迭代器设计
-
与库中迭代器设计不同！！！
-
list的迭代器设计，小编会和大家一步一步设计list的迭代器：- iterator
- const_iterator
- reverse_iterator
4.2.1 正向迭代器
对于代码的编写，我们有一个常用的方式：复用。我们尝试着：将const_iterator用iterator包装成const属性即可。
- 版本一：
template<class T>
class list_iterator
{ typedef list_node<T> node;typedef list_iterator<T> self; //将自己重命名
public:list_iterator(node* obj_node) //一般上不会是const node*:_node(obj_node){ }self& operator++() //前置++{_node = _node->_next; //指向下一个节点return _node; //返回新node即可，会自己发生构造}T& operator*() //返回节点的数据{return _node->_data;}T* operator->() //返回节点数据的指针{return &(_node->_data);}
private:node* _node; //指向的节点
};
-
版本一的代码，我们可以正常的写完这样的是可以正常被普通
list对象所使用的：我们只需要在
list类中重命名：typedef list_iterator<T> iterator;即可。同时我们思考：这样的迭代器设计，能实现我们的
const_iterator的复用需求吗？-
方案一：
typedef const list_iterator<T> const_iterator;行不通。因为这个迭代器是不可能完成的。因为我们迭代器是需要改变属性的指针（成员变量）的指向的，但是
const修饰的是list_iterator<T>，导致这个指针不能改变。 -
方案二：
typedef list_iterator<const T> const_iterator;行不通。对于类模板来说
list<int>和list<const int>是不同的两种类别，我们从底层来看，当我们使用了const T这样的类型之后，你就会发现，迭代器中的指针类型为node<const T>这个类型和node<T>不是一个类型！！！无法作为list中节点的指针！
我们尝试将模板参数进行扩张。添加一个
Ptr的模板参数，用于接受不同的指针类型。 -
同时我们的T&也面临类似的问题。对于调用函数：operator*。由于不管是普通迭代器还是常性迭代器本质类型都是没有常性的（不是一个类型），但是其内置的成员属性是会有常性的，所以我们需要在函数的返回值上面做文章。根据不同的传入的参数类型，打造不同的迭代器。
- 版本二：
/*只写部分接口*/
// typedef list_iterator<T, T&, T*> iterator 普通迭代器
// typedef list_iterator<T, const T&, const T*> const_iterator 常量迭代器
template<class T, class Ref, class Ptr>
class list_iterator
{typedef list_node<T> node;typedef list_iterator<T, Ref, Ptr> self; //将自己重命名
public:list_iterator(node* n):_node(n){ }self& operator++(){_node = _node->_next;return *this;}self& operator--(){_node = _node->_prev;return *this;}Ref operator*() const //如果Ref是T&，就是普通；如果是const T&就是常量{return _node->_data;}Ptr operator->() const //如果Ptr是T*，就是普通；如果是const T*就是常量{return &(operator*());}bool operator==(const self& iter) const{return _node == iter._node;}node* _node;
};
4.2.2 反向迭代器
-
事实上：反向迭代器的
++操作，对于正向迭代器来说就是--操作。它们二者的操作在迭代器的移动上几乎就是相反的操作！！所以，我们可以进行如下的包装，直接使用正向迭代器来包装反向迭代器。反向迭代器的实现：复用正向迭代器的实现！
所以我们或许会用正向迭代器作为反向迭代器的成员变量……这样的话，我们又该如何得知，迭代器指向的数据类型呢？继续作为参数传入！！！
/*只写部分接口*/
template<class Iterator, class Ref, class Ptr>
class list_reverse_iterator
{typedef list_reverse_iterator<Iterator, Ref, Ptr> self;
public:list_reverse_iterator(Iterator iter):_iter(iter){ }self& operator++(){--_iter;return *this;}self& operator--(){++_iter;return *this;}Ref operator*() const //如果Ref是T&，就是普通；如果是const T&就是常量{return *_iter;}Ptr operator->() const//如果Ptr是T*，就是普通；如果是const T*就是常量{return &(operator*()); //复用}bool operator==(const self& iter) const{return _iter == iter._iter;}
private:Iterator _iter;
};
4.2.3 list的迭代器
-
我们最后在
list类模板中为各种迭代器类型声明即可！
-
然后设计
list的迭代器函数：
iterator begin()
{return _head->_next;
}
const_iterator begin() const
{return _head->_next;
}
iterator end()
{return _head;
}
const_iterator end() const
{return _head;
}
//反向同理
4.3 增删改
-
插入一个节点的逻辑图：
4.3.1 insert和erase……
/*只写部分接口*/
iterator insert(iterator pos, const T& val)
{//1、构建新节点node* newnode = new node(val);//2、找到插入位置的前一个位置iterator pos_prev = pos._node->_prev; //不能--//3、改变链接关系pos_prev._node->_next = newnode;newnode->_prev = pos_prev._node;newnode->_next = pos._node;pos._node->_prev = newnode;return newnode;
}
iterator insert(iterator pos, T&& val)
{//完美转发的细节//1、构建新节点node* newnode = new node(std::forward<T>(val)); //保持val的属性，调用//2、找到插入位置的前一个位置iterator pos_prev = pos._node->_prev; //3、改变链接关系pos_prev._node->_next = newnode;newnode->_prev = pos_prev._node;newnode->_next = pos._node;pos._node->_prev = newnode;return newnode;
}
iterator erase(iterator pos)
{assert(pos != end()); //头节点不能删除//1、找到这个节点的前一个节点和后一个节点node* pos_prev = pos._node->_prev;node* pos_next = pos._node->_next;//2、更改链接关系pos_prev->_next = pos_next;pos_next->_prev = pos_prev;//3、析构delete pos._node;return pos_next;
}
//复用
4.3.2 emplace
- 主要细节在于将参数包向下传递……
小编这里为了简单，直接将接口设计为参数设计为iterator。不然还有const_iterator与iterator之间的构造转化问题。有需要写隐式转换运算符过于麻烦，小编这里偷个懒，之间写普通迭代器版本：
/*新增的可变参数模板接口*/
template <class T>
struct list_node
{template<class... Args>list_node(Args&&... args):_data(std::forward<Args>(args)...), _prev(nullptr), _next(nullptr){ }list_node<T>* _prev;list_node<T>* _next;T _data;
};/*list类成员函数的实现*/
template<class... Args>
iterator emplace(iterator pos, Args&&...args)
{//1、构造节点node* newnode = new node(std::forward<Args>(args)...); //将参数包往下传递//2、找到插入位置的前一个位置iterator pos_prev = pos._node->_prev;//3、改变链接关系pos_prev._node->_next = newnode;newnode->_prev = pos_prev._node;newnode->_next = pos._node;pos._node->_prev = newnode;return newnode;
}
模拟源码
#pragma once
#include <algorithm>
#include <cassert>/* STL中的list节点设计 */
//template<class T>
//struct __list_node
//{
// typedef void* void_pointer;
// void_pointer prev;
// void_pointer next;
// T data;
//};namespace LL
{template <class T>struct list_node{list_node(const T& val = T()) : _data(val), _prev(nullptr), _next(nullptr){ }list_node(T&& val): _data(std::forward<T>(val)), _prev(nullptr), _next(nullptr){}template<class... Args>list_node(Args&&... args):_data(std::forward<Args>(args)...), _prev(nullptr), _next(nullptr){ }list_node<T>* _prev;list_node<T>* _next;T _data;};// 版本一：//template<class T>//class list_iterator//{ // typedef list_node<T> node;// typedef list_iterator<T> self; //将自己重命名//public:// list_iterator(node<T>* obj_node)// :_node(obj_node)// { }// self& operator++() //前置++// {// _node = _node->_next; //指向下一个节点// return _node; //返回新node即可，会自己发生构造// }// T& operator*()// {// return _node->_data;// }// T* operator->()// {// return _node;// }//private:// node* _node; //指向的节点//};//版本二：// typedef list_iterator<T, T&, T*> iterator 普通迭代器// typedef list_iterator<T, const T&, const T*> const_iterator 常量迭代器template<class T, class Ref, class Ptr>class list_iterator{typedef list_node<T> node;typedef list_iterator<T, Ref, Ptr> self; //将自己重命名public:list_iterator(node* n):_node(n){ }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*() const//如果Ref是T&，就是普通；如果是const T&就是常量{return _node->_data;}Ptr operator->() const//如果Ptr是T*，就是普通；如果是const T*就是常量{return &(_node->_data);}bool operator==(const self& iter) const{return _node == iter._node;}bool operator!=(const self& iter) const{return _node != iter._node;}node* _node;};template<class Iterator, class Ref, class Ptr>class list_reverse_iterator{typedef list_reverse_iterator<Iterator, Ref, Ptr> self;public:list_reverse_iterator(Iterator iter):_iter(iter){ }self& operator++(){--_iter;return *this;}self operator++(int){self tmp(*this);--_iter;return tmp;}self& operator--(){++_iter;return *this;}self operator--(int){self tmp(*this);++_iter;return tmp;}Ref operator*() const //如果Ref是T&，就是普通；如果是const T&就是常量{return *_iter;}Ptr operator->() const//如果Ptr是T*，就是普通；如果是const T*就是常量{return &(operator*()); //复用}bool operator==(const self& iter) const{return _iter == iter._iter;}bool operator!=(const self& iter) const{return _iter != iter._iter;}private:Iterator _iter;};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;typedef list_reverse_iterator<iterator, T&, T*> reverse_iterator;typedef list_reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;list() //默认构造函数{empty_initnode(); //调用函数构造一个节点}list(const list<T>& lt) //拷贝构造函数{empty_initnode();for (const auto& e : lt){push_back(e); //一直尾插即可，后面实现尾插接口}}list(list<T>&& tmp) //移动构造函数{empty_initnode();swap(tmp); //调用类中实现的方法}~list() //析构函数{clear(); //直接调用clear函数，将链表节点全部清空delete _head;_head = nullptr;}const list<T>& operator=(const list<T>& obj) //赋值重载{if (this != &obj){for (const auto& e : obj){//push_back(lt); //同}}return *this;}const list<T>& operator=(list<T>&& tmp) //移动赋值{if (this != &tmp){swap(tmp);}return *this;}void clear(){//调用pop_front/pop_back即可//TODO wait eraseauto it = begin();while (it != end()){it = erase(it);}}iterator begin(){return _head->_next;}const_iterator begin() const{return _head->_next;}iterator end(){return _head;}const_iterator end() const{return _head;}reverse_iterator rbegin(){return --end();}const_reverse_iterator rbegin() const{return --end();}reverse_iterator rend(){return end();}const_reverse_iterator rend() const{return end();}iterator insert(iterator pos, const T& val){//1、构建新节点node* newnode = new node(val);//2、找到插入位置的前一个位置iterator pos_prev = pos._node->_prev; //不能--//3、改变链接关系pos_prev._node->_next = newnode;newnode->_prev = pos_prev._node;newnode->_next = pos._node;pos._node->_prev = newnode;return newnode;}iterator insert(iterator pos, T&& val){//完美转发的细节//1、构建新节点node* newnode = new node(std::forward<T>(val)); //保持val的属性，调用//2、找到插入位置的前一个位置iterator pos_prev = pos._node->_prev; //3、改变链接关系pos_prev._node->_next = newnode;newnode->_prev = pos_prev._node;newnode->_next = pos._node;pos._node->_prev = newnode;return newnode;}iterator erase(iterator pos){assert(pos != end()); //头节点不能删除//1、找到这个节点的前一个节点和后一个节点node* pos_prev = pos._node->_prev;node* pos_next = pos._node->_next;//2、更改链接关系pos_prev->_next = pos_next;pos_next->_prev = pos_prev;//3、析构delete pos._node;return pos_next;}//复用void push_back(const T& val){insert(end(), val);}void pop_back(){erase(--end()); //需要先--，找到头节点的上一个位置（即末尾）}void push_front(const T& val){insert(begin(), val);}void pop_front(){erase(begin());}template<class... Args>iterator emplace(iterator pos, Args&&...args){//1、构造节点node* newnode = new node(std::forward<Args>(args)...); //将参数包往下传递//2、找到插入位置的前一个位置iterator pos_prev = pos._node->_prev;//3、改变链接关系pos_prev._node->_next = newnode;newnode->_prev = pos_prev._node;newnode->_next = pos._node;pos._node->_prev = newnode;return newnode;}private:void empty_initnode() //一个空的构造{if (nullptr == _head){_head = new node(); //默认构造一个头节点_head->_next = _head; //下一个节点指向自己_head->_prev = _head; //上一个节点也指向自己}}void swap(list<T>& tmp){std::swap(_head, tmp._head); //交换指针即可}private:node* _head;};
}