❤️欢迎来到我的博客❤️ |
前言
- list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代
- list的底层是双向链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向其前一个元素和后一个元素
- list与forward_list非常相似:最主要的不同在于forward_list是单链表,只能朝前迭代,已让其更简单高效
- 与其他的序列式容器相比(array,vector,deque),list通常在任意位置进行插入、移除元素的执行效率更好
- 与其他序列式容器相比,list和forward_list最大的缺陷是不支持任意位置的随机访问,比如:要访问list的第6个元素,必须从已知的位置(比如头部或者尾部)迭代到该位置,在这段位置上迭代需要线性的时间开销;list还需要一些额外的空间,以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)
list相比于vector在insert和erase上有很大的区别
vector想在第五个位置插入数据可以直接+5
int main()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
v1.push_back(7);
v1.insert(v1.begin() + 5, 6);
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
//输出结果为:1 2 3 4 5 6 7
return 0;
}
而list想在第五个位置插入数据只能使用迭代器,不可以直接+5
int main()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
lt.push_back(7);
//lt.insert(lt.begin() + 5, 10);
auto it = lt.begin();
for (size_t i = 0; i < 5; i++)
{
++it;
}
lt.insert(it, 6);
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
//输出结果为:1 2 3 4 5 6 7
return 0;
}
list使用insert之后迭代器不会失效,因为结点的位置没有发生改变
但list使用erase之后迭代器就会失效,因为结点位置发生了改变(结点已经被删除)
排序相关
可以看到list单独提供了sort库里明明有一个sort为什么list还要单独提供呢?
我们来试试:
可以看到,当我们使用库里的sort的时候编译报错了
我们转到库定义可以看到,库里的sort用了一个last-first,原理是快排,需要三数取中,但在链表中就不适合三数取中的场景
迭代器从功能的角度是会分类的,他分为:单向、双向和随机
单向可以进行 ++
双向可以进行 ++/–
随机可以进行 ++/–/+/-
单向迭代器有:forward_list / unordered_map / unordered_set
双向迭代器有:list / map / set
随机迭代器有:vector / string / deque
在形参的名字中就暗示了我们适合用哪一种算法,比如reverse就适合用双向,find适合用单向,sort适合用随机
InputIterator(find):只写迭代器(他在单向迭代器的上面)也就是说单向 / 双向 / 随机都可以使用
双向迭代器(reverse):双向 / 随机可以使用
随机迭代器(sort):只有随机能用
容器的迭代器类型在文档中是有说明的:
list:
vector:
set:
forward_list:
在数据量大的情况下,我们可以把list拷贝到vector中,使用库里的排序,再把数据拷贝回去效率更高,我们来对比一下:
数据个数为一千万
int main()
{
srand(time(0));
const int N = 10000000;
vector<int> v;
v.reserve(N);
list<int> lt1;
list<int> lt2;
for (int i = 0; i < N; i++)
{
auto e = rand();
lt2.push_back(e);
lt1.push_back(e);
}
//拷贝到vector
int begin1 = clock();
//拷贝
for (auto e : lt1)
{
v.push_back(e);
}
//排序
sort(v.begin(), v.end());
//拷贝回去
size_t i = 0;
for (auto& e : lt1)
{
e = v[i++];
}
int end1 = clock();
//直接使用list排序
int begin2 = clock();
lt2.sort();
int end2 = clock();
cout << "使用vector排序:" << end1 - begin1 << endl;
cout << "直接使用list排序:" << end2 - begin2 << endl;
return 0;
}
可以看到效率差了近十倍,所以在数据量特别大的时候就不要直接使用list排序了,排少量数据则可以直接使用
merge
可以将两个链表归并(前提是链表有序)
unique
去重(前提是链表有序)
remove
remove就是find+erase,如果要删除的值不存在则不进行任何操作
splice
可以把一个链表的内容转移到另一个链表(直接把结点拿走)
转移全部
int main()
{
list<int> list1, list2;
list<int>::iterator it;
for (int i = 1; i <= 4; ++i)
{
list1.push_back(i); //list1:1 2 3 4
}
for (int i = 1; i <= 3; ++i)
{
list2.push_back(i * 10); //list2:10 20 30
}
cout << "list1转移前:";
for (auto e : list1)
{
cout << e << " ";
}
cout << endl;
cout << "list2转移前:";
for (auto e : list2)
{
cout << e << " ";
}
cout << endl;
it = list1.begin();
++it;//2位置
//把list2全部转移到list1中2之前的位置
list1.splice(it, list2);
cout << "list1转移后:";
for (auto e : list1)
{
cout << e << " ";
}
cout << endl;
cout << "list2转移后:";
for (auto e : list2)
{
cout << e << " ";
}
cout << endl;
return 0;
}
转移某一个结点
//转移某一个结点
list1.splice(it, list2,++list2.begin());
部分转移
//部分转移
list1.splice(it, list2,++list2.begin(),list2.end());
自己转移自己
//把第二位置转移到第一个位置的前面
list1.splice(list1.begin(),list1,++list1.begin());
注意:转移重叠位置会造成死循环
模拟实现list
基本框架
namespace List
{
template<class T>
struct list_node
{
list_node<T>* _next;
list_node<T>* _prev;
T _val;
//构造函数
list_node(const T& val = T()) //缺省值不能给0,因为T不一定是内置类型
:_next(nullptr)
,_prev(nullptr)
,_val(val)
{}
};
template<class T>
class list
{
typedef list_node<T> Node;
public:
list()
{
_head = new Node;
//哨兵位指向自己
_head->_prev = _head;
_head->_next = _head;
}
//尾插
void push_back(const T& x)
{
Node* tail = _head->_prev;//找尾
Node* newnode = new Node(x);//调用构造函数
tail->_next = newnode;
newnode->_prev = tail;
newnode->_next = _head;
_head->_prev = newnode;
}
private:
Node* _head;
};
void test1()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
}
}
尾插
//尾插
void push_back(const T& x)
{
Node* tail = _head->_prev;//找尾
Node* newnode = new Node(x);//调用构造函数
tail->_next = newnode;
newnode->_prev = tail;
newnode->_next = _head;
_head->_prev = newnode;
}
迭代器
由于结点的地址不是连续的,那我们的迭代器该如何设置呢,这时候就要用到运算符重载
我们先来看迭代器的使用:
list<int>::iterator it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
++it;
}
cout << endl;
那么我们的begin应该返回的是第一个数据的位置,end在最后一个数据的下一个位置
迭代器是一个自定义类型,这个自定义类型是一个结点的指针,所以在list中他的迭代器需要自己设计而不是像vector或string那样使用原生指针(不同平台下实现方式不同,个别平台也可能对其进行二次封装,也可能不是用原生指针实现)作为迭代器,原因如下:
- list 的元素在内存中不是连续存储的,而是通过指针链接起来的。这意味着你不能简单地使用原生指针作为迭代器,因为原生指针只能访问连续内存块中的元素
- list 的迭代器需要提供额外的功能,如在链表中前进或后退,这些操作涉及到修改指针以跳转到下一个或上一个元素。原生指针不支持这些操作,因此需要自定义迭代器来实现
- 自定义迭代器可以针对链表的特性进行优化。例如,链表迭代器在插入或删除操作时,只需要调整相邻元素的指针,而不需要移动大量元素,这使得链表在某些操作上比数组更高效
- list中,插入或删除元素通常不会使迭代器失效(除非删除的是迭代器指向的元素),这与vector不同。自定义迭代器可以确保这些操作的正确性,而原生指针无法提供这种保证
- 自定义迭代器可以提供更好的封装性,隐藏链表的内部实现细节,这样,即使链表的实现发生变化,只要迭代器的接口保持不变,使用迭代器的代码就不需要修改
begin和end
template<class T>
class list
{
typedef list_node<T> Node;
public:
typedef __list_iterator<T> iterator;
iterator begin()
{
//单参数的构造函数支持隐式类型转换
//return _head->_next;
return iterator(_head->_next);
}
iterator end()
{
//return _head;
return iterator(_head);
}
list()
{
_head = new Node;
//哨兵位指向自己
_head->_prev = _head;
_head->_next = _head;
}
private:
Node* _head;
};
* / ++ / – / != / ==
template<class T>
struct __list_iterator
{
typedef list_node<T> Node;
Node* _node;
//用一个结点的指针构造一个迭代器
__list_iterator(Node* node)
:_node(node)
{}
T& operator*()
{
//*it默认解引用是结点,我们不想要结点,我们要的是数据
return _node->_val;
}
//迭代器++返回的还是迭代器
__list_iterator<T>& operator++()
{
//我们想++做的是让他走向下一个结点
//(原生指针是加一个结点的大小,这样并不能到下一个结点的位置)
_node = _node->_next;
return *this;
}
//后置++
__list_iterator<T> operator++(int)
{
__list_iterator<T> 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;
}
bool operator!=(const __list_iterator<T>& it)
{
//使用结点的指针来进行比较
return _node != it._node;
}
bool operator==(const __list_iterator<T>& it)
{
//使用结点的指针来进行比较
return _node == it._node;
}
};
这样我们的迭代器就可以正常使用了
void test1()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
list<int>::iterator it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
int main()
{
List::test1();
return 0;
}
运行效果:
const迭代器
迭代器模拟的是指针的行为,指针有2种const指针:
1:const T* ptr1; (指针指向的内容不能修改)
2:T* const ptr2;(指针本身不能修改)
const迭代器模拟的是第一种指针的行为
我们可以通过一个类型来控制返回值,给不同的模板参数不同的实例化,他们就是不同的类
template<class T,class Ref>//添加一个class Ref参数
struct __list_iterator
{
Ref operator*()//返回值改为Ref
{
return _node->_val;
}
}
template<class T>
class list
{
typedef list_node<T> Node;
public:
typedef __list_iterator<T,T&> iterator;//普通迭代器
typedef __list_iterator<T, const T&> const_iterator;//const迭代器
//提供const接口
const_iterator begin() const
{
return const_iterator(_head->_next);
}
const_iterator end() const
{
return const_iterator(_head);
}
};
->
T* operator->()
{
return &_node->_val;
}
struct A
{
A(int a1 = 0,int a2 = 0)
:_a1(a1)
,_a2(a2)
{}
int _a1;
int _a2;
};
void test1()
{
list<A> lt;
lt.push_back(A(1, 1));
lt.push_back(A(2, 2));
lt.push_back(A(3, 3));
lt.push_back(A(4, 4));
list<A>::iterator it = lt.begin();
while (it != lt.end())
{
cout << it->_a1 << " " << it->_a2 << endl;
++it;
}
cout << endl;
}
运行效果
const迭代器,也需要添加一个模板参数
//typedef __list_iterator<T,T&,T*> iterator;//普通迭代器
//typedef __list_iterator<T, const T&,const T*> const_iterator;//const迭代器
template<class T,class Ref,class Ptr>
insert
insert默认都是在pos位置之前插入(任意位置都可以),所以insert不需要做检查
erase则需要检查(因为哨兵位的结点不可删)
//pos位置之前插入
iterator insert(iterator pos, const T& x)
{
//首先得换成结点的指针,因为迭代器不好访问数据
Node* cur = pos._node;
Node* prev = cur->_prev; //前一个位置
Node* newnode = new Node(x); //新结点
prev->_next = newnode;
newnode->_next = cur;
cur->_prev = newnode;
newnode->_prev = prev;
return newnode;
}
库里面的insert返回的是新插入位置的迭代器,所以我们实现时和库里保持一致
erase
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; //返回下一个位置
}
注意:这里会存在迭代器失效的问题,因为pos位置的结点已经被我们释放掉了,所以我们需要返回下一个位置的迭代器,而不是void
代码复用
当我们实现完insert和erase之后,尾插、头插、尾删、头删都可以复用
尾插
//尾插
void push_back(const T& x)
{
//Node* tail = _head->_prev;//找尾
//Node* newnode = new Node(x);//调用构造函数
//tail->_next = newnode;
//newnode->_prev = tail;
//newnode->_next = _head;
//_head->_prev = newnode;
//复用
//尾插 - 在哨兵位的前面插入
insert(end(), x);
}
头插
void push_front(const T& x)
{
//头插
//在第一个位置插入,也就是begin的前面
insert(begin(), x);
}
尾删
void pop_back()
{
//尾删
erase(--end());
}
头删
void pop_front()
{
//头删
erase(begin());
}
size
size有两种实现方法
方法一:
size_t size()
{
size_t sz = 0;
iterator it = begin();
while (it != end())
{
++sz;
++it;
}
return sz;
}
方法二:
增加一个_size成员初始化为0,每次插入++_size,每次删除–_size
size_t size()
{
return _size;
}
private:
Node* _head;
size_t _size;//增加成员
clear和析构
void clear()
{
//clear - 清除所有数据,不清哨兵位
iterator it = begin();
while (it != end())
{
//这里erase之后就不能进行++了,因为他失效了
//所以得接收返回值(返回值是下一个结点)
it = erase(it);
}
}
析构可以直接复用clear
~list()
{
//析构
clear();
delete _head;
_head = nullptr;
}
测试一下:
void test1()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.insert(lt.end(), 3);
lt.push_back(4);
lt.push_back(5);
lt.erase(lt.begin());
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
lt.push_front(1);
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
lt.pop_front();
lt.pop_back();
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
lt.clear();
lt.push_back(10);
lt.push_back(20);
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
cout << "size=" << lt.size() << endl;
}
运行效果
拷贝构造和empty_init
拷贝构造
// lt2(lt1)
list(const list<T>& lt)
{
//初始化
_head = new Node;
//哨兵位指向自己
_head->_prev = _head;
_head->_next = _head;
//T对象不确定,所以最好加上引用
//遍历lt1,把lt1的数据插入到lt2
for (auto& e : lt)
{
push_back(e);
}
}
empty_init
void empty_init()
{
_head = new Node;
//哨兵位指向自己
_head->_prev = _head;
_head->_next = _head;
}
复用
list()
{
empty_init();
}
// lt2(lt1)
list(const list<T>& lt)
{
empty_init();
//T对象不确定,所以最好加上引用
//遍历lt1,把lt1的数据插入到lt2
for (auto& e : lt)
{
push_back(e);
}
}
赋值和swap
void swap(list<T>& lt)
{
std::swap(_head, lt.head);
}
赋值
list<T>& operator=(list<T> lt)
{
//现代写法
swap(lt);
return *this;
}
测试一下
void test2()
{
list<int> lt1;
lt1.push_back(1);
lt1.push_back(2);
lt1.push_back(3);
lt1.push_back(4);
list<int> lt2(lt1);
for (auto e : lt2)
{
cout << e << " ";
}
cout << endl;
list<int> lt3;
lt3.push_back(10);
lt3.push_back(20);
lt3.push_back(30);
lt3.push_back(40);
lt1 = lt3;
for (auto e : lt1)
{
cout << e << " ";
}
cout << endl;
}
运行效果
完整代码
#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
namespace List
{
template<class T>
struct list_node
{
list_node<T>* _next;
list_node<T>* _prev;
T _val;
//构造函数
list_node(const T& val = T()) //缺省值不能给0,因为T不一定是内置类型
:_next(nullptr)
,_prev(nullptr)
,_val(val)
{}
};
template<class T,class Ref,class 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*()
{
//*it默认解引用是结点,我们不想要结点,我们要的是数据
return _node->_val;
}
Ptr operator->()
{
return &_node->_val;
}
//迭代器++返回的还是迭代器
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;
}
bool operator!=(const self& it) const
{
//使用结点的指针来进行比较
return _node != it._node;
}
bool operator==(const self& it) const
{
//使用结点的指针来进行比较
return _node == it._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;
return iterator(_head->_next);
}
iterator end()
{
//return _head;
return iterator(_head);
}
const_iterator begin() const
{
//单参数的构造函数支持隐式类型转换
//return _head->_next;
return const_iterator(_head->_next);
}
const_iterator end() const
{
//return _head;
return const_iterator(_head);
}
void empty_init()
{
_head = new Node;
//哨兵位指向自己
_head->_prev = _head;
_head->_next = _head;
}
list()
{
empty_init();
}
// lt2(lt1)
list(const list<T>& lt)
{
empty_init();
//T对象不确定,所以最好加上引用
//遍历lt1,把lt1的数据插入到lt2
for (auto& e : lt)
{
push_back(e);
}
}
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
}
list<T>& operator=(list<T> lt)
{
//现代写法
swap(lt);
return *this;
}
~list()
{
//析构
clear();
delete _head;
_head = nullptr;
}
void clear()
{
//clear - 清除所有数据,不清哨兵位
iterator it = begin();
while (it != end())
{
//这里erase之后就不能进行++了,因为他失效了
//所以得接收返回值(返回值是下一个结点)
it = erase(it);
}
}
//尾插
void push_back(const T& x)
{
//Node* tail = _head->_prev;//找尾
//Node* newnode = new Node(x);//调用构造函数
//tail->_next = newnode;
//newnode->_prev = tail;
//newnode->_next = _head;
//_head->_prev = newnode;
//复用
//尾插 - 在哨兵位的前面插入
insert(end(), x);
}
void push_front(const T& x)
{
//头插
//在第一个位置插入,也就是begin的前面
insert(begin(), x);
}
void pop_back()
{
//尾删
erase(--end());
}
void pop_front()
{
//头删
erase(begin());
}
//pos位置之前插入
iterator insert(iterator pos, const T& x)
{
//首先得换成结点的指针,因为迭代器不好访问数据
Node* cur = pos._node;
Node* prev = cur->_prev; //前一个位置
Node* newnode = new Node(x); //新结点
prev->_next = newnode;
newnode->_next = cur;
cur->_prev = newnode;
newnode->_prev = prev;
return newnode;
}
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;
}
size_t size()
{
size_t sz = 0;
iterator it = begin();
while (it != end())
{
++sz;
++it;
}
return sz;
}
private:
Node* _head;
};
void Print(const list<int>& lt)
{
list<int>::const_iterator it = lt.begin();
while (it != lt.end())
{
//(*it) += 1;
cout << *it << " ";
++it;
}
cout << endl;
}
struct A
{
A(int a1 = 0,int a2 = 0)
:_a1(a1)
,_a2(a2)
{}
int _a1;
int _a2;
};
void test1()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.insert(lt.end(), 3);
lt.push_back(4);
lt.push_back(5);
lt.erase(lt.begin());
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
lt.push_front(1);
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
lt.pop_front();
lt.pop_back();
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
lt.clear();
lt.push_back(10);
lt.push_back(20);
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
cout << "size=" << lt.size() << endl;
}
void test2()
{
list<int> lt1;
lt1.push_back(1);
lt1.push_back(2);
lt1.push_back(3);
lt1.push_back(4);
list<int> lt2(lt1);
for (auto e : lt2)
{
cout << e << " ";
}
cout << endl;
list<int> lt3;
lt3.push_back(10);
lt3.push_back(20);
lt3.push_back(30);
lt3.push_back(40);
lt1 = lt3;
for (auto e : lt1)
{
cout << e << " ";
}
cout << endl;
}
}
以上就是本篇文章的全部内容了,希望大家看完能有所收获
❤️创作不易,点个赞吧❤️ |