【C++】——list 容器的解析与极致实现

如意.759 2024-10-22 09:05:01 阅读 80

人的一切痛苦，本质上都是对自己的无能的愤怒。

—— 王小波

1、list 介绍

2、list的使用

2.1 list 的构造

2.2 iterator 的使用

2.3 list 的修改

2.4一些特殊接口

2.5 迭代器失效问题

3、实现list

3.1底层结构

结点类

list类

迭代器类

3.2功能接口

迭代器接口

插入删除

拷贝赋值析构函数

4、list与vector 区别对比

1、list 介绍

List是C++标准模板库(STL)中的一个成员，其本质为带头双向循环链表。不同于连续的、紧密排列的数组容器Vector，List容器的内部是由双向链表构成的，使得它在插入和删除操作上，就如同行云流水一般顺畅，不需移动其它元素。

List的结构示意图如下：环状链表的尾是一个空节点，符合“左闭右开”区间。

List适合的场景是那些需要频繁进行插入和删除操作的场合。

例如，如果你正在管理一个动态变化的列表，如任务调度、人员排队等场景，List的特性将大放异彩。但是如果你的应用场景更多地需要随机访问元素，那么Vector或者数组可能是更佳的选择。因为List的顺序访问性能相比之下会显得有些力不从心。

所以如果需要频繁随机的访问数据，那么选择vector容器如果需要频繁插入删除数据，那么选择list容器排序不要选择list ！！！可以先拷贝给vector排序后再拷贝回来

迭代器的介绍

迭代器可以按照功能、性质两大模块分类

迭代器的一些性质（重载的运算符）决定着算法库里对算法的调用

而这些迭代器是子类与父类的继承关系

2、list的使用

list 中的接口比较多，此处类似，只需要掌握如何正确的使用，然后再去深入研究背后的原理，已达到可扩展的能力。以下为list中一些常见的重要接口。

2.1 list 的构造

<code>void TestList1()

{

list<int> l1; // 构造空的l1

list<int> l2(4, 100); // l2中放4个值为100的元素

list<int> l3(l2.begin(), l2.end()); // 用l2的[begin(), end()）左闭右开的区间构造l3

list<int> l4(l3); // 用l3拷贝构造l4

// 以数组为迭代器区间构造l5

int array[] = { 16,2,77,29 };

list<int> l5(array, array + sizeof(array) / sizeof(int));

// 列表格式初始化C++11

list<int> l6{ 1,2,3,4,5 };

list<int> l7 = { 1,2,4,5,6,7,8 };

// 用迭代器方式打印l5中的元素

list<int>::iterator it = l5.begin();

while (it != l5.end())

{

cout << *it << " ";

++it;

}

cout << endl;

// C++11范围for的方式遍历

for (auto& e : l5)

cout << e << " ";

cout << endl;

}

2.2 iterator 的使用

关于 list 的迭代器可以姑且理解为指针，本质是通过运算符重载模拟指针的行为

【TIP】

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

<code>void PrintList(const list<int>& l)

{

// 注意这里调用的是list的 begin() const，返回list的const_iterator对象

for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it)

{

cout << *it << " ";

// *it = 10; 编译不通过

}

cout << endl;

}

void TestList2()

{

int array[] = { 1, 2, 3, 4, 5, 6, };

list<int> l(array, array + sizeof(array) / sizeof(array[0]));

// 使用正向迭代器正向list中的元素

// list<int>::iterator it = l.begin(); // C++98中语法

auto it = l.begin(); // C++11之后推荐写法

while (it != l.end())

{

cout << *it << " ";

++it;

}

cout << endl;

// 使用反向迭代器逆向打印list中的元素

// list<int>::reverse_iterator rit = l.rbegin();

auto rit = l.rbegin();

while (rit != l.rend())

{

cout << *rit << " ";

++rit;

}

cout << endl;

//迭代器不支持因为 list 迭代器是双向不支持 + -

/*l.insert(l.begin() + 3);*/

//想要实现第三个位置后插入一个数可以通过下面代码

it = l.begin();

int k = 3;

while (k--)

{

it++;//支持++

}

l.insert(it, 40);

PrintList(l);

}

2.3 list 的修改

<code>struct A {

public:

A(int a1 = 1, int a2 = 1)

:_a1(a1)

, _a2(a2)

{

cout << "A(int a1=1,int a2=1)" << endl;

}

A(const A& aa)

:_a1(aa._a1)

, _a2(aa._a2)

{

cout << "A(const A& aa)" << endl;

}

private:

int _a1;

int _a2;

};

void TestList3()

{

int array[] = { 1, 2, 3 };

list<int> L(array, array + sizeof(array) / sizeof(array[0]));

// 在list的尾部插入4，头部插入0

L.push_back(4);

L.push_front(0);

PrintList(L);

// 删除list尾部节点和头部节点

L.pop_back();

L.pop_front();

PrintList(L);

list<A>lt;

A aa1(1, 1);

lt.push_back(aa1);//有名对象尾插

lt.push_back(A(2, 2));//匿名对象尾插

//lt.push_back(3, 3);//不支持 push back只支持一个参数

lt.emplace_back(aa1);

lt.emplace_back(A(2, 2));

cout << endl;

// 前面的插入都是构造+拷贝构造

// (3,3)的插入并没有拷贝构造性能上来说优于 push back

lt.emplace_back(3, 3);//支持本质支持直接传构造A对象的参数

}

可以看到 emplace_back 可以支持直接传构造A的参数省去了临时变量的拷贝构造

插入与删除

<code>// insert /erase

void TestList4()

{

int array1[] = { 1, 2, 3 };

list<int> L(array1, array1 + sizeof(array1) / sizeof(array1[0]));

// 获取链表中第二个节点

auto pos = ++L.begin(); //pos 可以理解为下标

cout << *pos << endl;

// 在pos前插入值为4的元素

L.insert(pos, 4);

PrintList(L);

// 在pos前插入6个值为5的元素

L.insert(pos, 6, 5);

PrintList(L);

// 在pos前插入[v.begin(), v.end)区间中的元素

vector<int> v{ 7, 8, 9 };

L.insert(pos, v.begin(), v.end());

PrintList(L);

// 删除pos位置上的元素

L.erase(pos);

PrintList(L);

// 删除list中[begin, end)区间中的元素，即删除list中的所有元素

L.erase(L.begin(), L.end());

PrintList(L);

}

<code>// resize/swap/clear

void TestList5()

{

// 用数组来构造list

int array1[] = { 1, 2, 3 };

list<int> l1(array1, array1 + sizeof(array1) / sizeof(array1[0]));

PrintList(l1);

// 交换l1和l2中的元素

list<int> l2;

l1.swap(l2);

PrintList(l1);

PrintList(l2);

// 将l2中的元素清空

l2.clear();

cout << l2.size() << endl;

}

2.4一些特殊接口

reverse 逆置链表 sort 排序（算法库里没有list的排序（迭代器不匹配））

<code>void test_list4()//容器的逆置与排序

{

list<int>lt;

lt.push_back(1);

lt.push_back(2);

lt.push_back(3);

lt.push_back(4);

lt.push_back(5);

print_list(lt);

lt.reverse();

print_list(lt);

reverse(lt.begin(), lt.end());

print_list(lt);

reverse(++lt.begin(), --lt.end());

print_list(lt);

//算法库里的排序和容器的排序都是默认升序

lt.sort();

print_list(lt);

//想要降序则需要仿函数

//less<int>ls;//升序

//greater<int>gt;//降序

//还可以结合匿名对象使用

lt.sort(greater<int>());

print_list(lt);

}

merge 合并与 unique 去重（前提均有序链表）

<code>void test_list5() // merge有序list合并 unique 有序list去除重复数据

{

std::list<double> first, second;

first.push_back(3.1);

first.push_back(2.2);

first.push_back(2.9);

second.push_back(3.7);

second.push_back(7.1);

second.push_back(1.4);

first.sort();

second.sort();

//将 second和first合并 second置为空前提两list有序

first.merge(second);

print_list(first);

print_list(second);

list<int>lt;

lt.push_back(1);

lt.push_back(2);

lt.push_back(3);

lt.push_back(4);

lt.push_back(1);

print_list(lt);

lt.sort();

//有序的数据去掉重复的数据

lt.unique();

print_list(lt);

}

剪切拼接 splice 的妙用

<code>void test_list6()

{

//把一个链表结点转移给另一个链表

std::list<int> mylist1, mylist2;

std::list<int>::iterator it;

// set some initial values:

for (int i = 1; i <= 4; ++i)

mylist1.push_back(i); // mylist1: 1 2 3 4

for (int i = 1; i <= 3; ++i)

mylist2.push_back(i * 10); // mylist2: 10 20 30

it = mylist1.begin();

++it; // points to 2

mylist1.splice(it, mylist2); // mylist1: 1 10 20 30 2 3 4

// mylist2 (empty)

// "it" still points to 2 (the 5th element)

print_list(mylist1);

print_list(mylist2);// splice 剪切功能

//splice 还可以调整当前list的顺序

list<int>lt;

lt.push_back(1);

lt.push_back(2);

lt.push_back(3);

lt.push_back(4);

lt.push_back(5);

print_list(lt);

int x = 0;

cin >> x;

it = find(lt.begin(), lt.end(), x);

if (it != lt.end())

{

// 调整当前链表的元素顺序将 it指向元素调整到 begin

lt.splice(lt.begin(), lt, it);

// //迭代器区间

//lt.splice(lt.begin(), lt, it,lt.end());

}

print_list(lt);

}

2.5 迭代器失效问题

前面说过，此处可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。

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

这在 vector 是不成立的，因为 vector 的插入操作有元素移动可能导致重新配置空间，导致原有的迭代器全部失效。

<code>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;

}

VS2022 对于迭代器失效有着严格的监控机制直接报错

<code>// 改正

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); erase 返回下一个位置的迭代器

}

这里的 erase 会返回下一个结点的位置

对于 erase(it++); 可以理解为先it++了再执行erase 代码块里的内容

3、实现list

list 容器的底层是一个带头双向循环链表

双向链表的意思是：每个节点不仅存储着数据，还包含两个指针，分别指向前一个节点和后一个节点。这使得 list 可以在常数时间内进行双向遍历和插入、删除操作。

库里的节点结构大致如下：

头节点和尾节点会分别指向 nullptr ，这表明链表的边界。

这种双向链表的结构给予了 list 灵动的特性：它能够轻松地在任意位置增加或移除元素，而这种操作几乎是与容器大小无关的，体现了时间复杂度上的优势。但这种优势的代价是，与数组相比，List在访问元素时的速度会较慢，因为它需要从头开始遍历。这也决定了list的更适合频繁插入的动态数据。

3.1底层结构

根据对链表的理解，我们需要封装一个结点类，为了兼容迭代器的使用，我们需要对结点指针封装一下即迭代器，最后就是实现功能函数的list 类了，我们可以加入一个头结点方便插入删除和兼容容器的左闭右开。

结点类

<code>// 结点结构体

template<class T>

struct list_node //默认公有 struct

{

T _data;

list_node<T>* _prev;

list_node<T>* _next;

list_node(const T& data=T())

:_data(data)

,_prev(nullptr)

,_next(nullptr)

{}

~list_node()

{

_next = nullptr;

_prev = nullptr;

}

};

结点类的结构还是很简单的结构体里包含着数据和前后指针即可，因为要多次访问结点所以设置为 struct 较合适

list类

构造函数需要创建一个头结点，因为我们要创建双向循环链表，所以头尾都要指向头结点本身。 _size统计元素个数。

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;

void empty_init()

{

//_head = new Node;//这里写了 Node 带参数构造所以报错需要匿名参数

_head = new Node(T());

_head->_next = _head;

_head->_prev = _head;

_size = 0;

}

list()

{

empty_init();

}

list(initializer_list<T>il)

{

empty_init();

for (auto& e : il)

{

push_back(e);

}

_size = il.size();

}

private:

Node* _head;

size_t _size;

};

这里的 list(initializer_list<T>il) 是C++11出现的语法，就可以像数组一样进行初始化了

迭代器类

list的迭代器显然不是指针！！ 链表的物理地址并不是连续存储的，指针的++ -- 操作是没有意义的，所以我们需要实现一个用结点指针封装的迭代器类，通过运算符重载去模拟指针的行为

可以看到库里所实现的迭代器类与我们所预想的一致！

如何实现++ 到下一个结点呢？？

通过重载 ++运算符获取地址返回下一个结点即可

迭代器实现：

由于STL list是一个双向链表，迭代器必须具备迁移，后移的能力，所以 list 提供的是 Birdirectional Iterator（双向）

List 的迭代器

迭代器有两种实现方式，具体应根据容器底层数据结构实现：

1. 原生态指针，比如：vector

2. 将原生态指针进行封装，因迭代器使用形式与指针完全相同，因此在自定义的类中必须实现以下方法：

（1）指针可以解引用，迭代器的类中必须重载 operator*()

（2）指针可以通过->访问其所指空间成员，迭代器类中必须重载 oprator->()

（3）指针可以++向后移动，迭代器类中必须重载 operator++() 与 operator++(int)

至于 operator--() / operator--(int) 是否需要重载，根据具体的结构来抉择，双向链表可以向前移动，所以需要重载，如果是forward_list（单向）就不需要重载--

（4）迭代器需要进行是否相等的比较，因此还需要重载 operator==() 与 operator!=()

<code>template<class T>

struct list_iterator

{

typedef list_node<T> Node;

typedef list_iterator<T> Self;

Node* _node;//指针成员变量

list_iterator(Node* node)

:_node(node)

{}

T& operator*()

{

return _node->_data;

}

T* operator->()

{

return &(_node->_data);

}

//操作符重载前置++ 与后置++的区别是参数是否带（int）

// ++it

Self& operator++()

{

_node = _node->_next;

return *this;

}

// it++

Self& operator++(int x)

{

Self tmp(*this);//浅拷贝

_node = _node->_next;

return tmp;

}

//--it

Self& operator--()

{

_node = _node->_prev;

return *this;

}

//it--

Self& operator--(int x)

{

Self tmp(*this);

_node = _node->_prev;

return tmp;

}

bool operator!=(const Self& s)const { return _node != s._node; }

bool operator==(const Self& s)const { return _node == s._node; }

};

有必要注意的是重载 -> 是为了适配T为自定义类型的情况

list<AA>lta;

lta.push_back(AA());

auto ita = lta.begin();

while (ita != lta.end())

{

//cout << *ita << ' '; //编译不通过结构体并没有重载流插入

//cout << (*ita)._a1 << ' ';

//cout << ita->_a1 << ' '; //为了可读性省去了一个箭头

cout << ita.operator->()->_a1 << ' ';

++ita;

}

调用了 operator ->后 AA* 结构体指针再用->调用了_a1

这样迭代器大致实现了应该有的功能，我们还需要实现一个const 迭代器，如何封装const 迭代器呢？不能修改内容，只需要重载的 * 和 -> 返回类型加上const 修饰即可

但是注意到其他重载的运算符都是一样的，如果重新定义一个const 迭代器是否过于冗余呢？

观察一下STL库里是如何实现的

显然并不是冗余的复制一份迭代器，而是同一个类模板实现的，实例化两个不同的类，本质上与冗余的写法是一个道理

那么我们开始优化一下迭代器

将类模板修改一下

<code>//reference 引用 pointer 指针

template<class T , class Ref ,class Ptr>

有差异的返回值也改变一下

Ref operator*() //现在返回const类型还是普通类型是通过编译器推导的

{

return _node->_data;

}

Ptr operator->()

{

return &(_node->_data);

}

那么类实例化的时候传入对应参数编译器就会推导出对应的类：

typedef list_iterator<T,T&,T*> iterator;

typedef list_iterator<T,const T&,const T*> const_iterator;

测试一下

那么就实现成功迭代器类模板

3.2功能接口

迭代器接口

<code>iterator begin()//第一个结点指针

{

//iterator it(_head->_next);//构造函数

//return it; 优化一下

return _head->_next; //走的隐式类型转换

}

// const 修饰begin 可以兼容拷贝构造否则出现权限放大这是不允许的

const_iterator begin()const //前面的const 迭代器是指向元素或引用不可以改变内容后面的const是修饰this 对象不可以改变

{// 隐含的this指针由 list * const this 变为 const list* const this 前者是指针不可以更改指向

return _head->_next;

}

const_iterator cbegin()const

{

return _head->_next;

}

iterator end()

{

return _head; // 头节点左闭右开

}

const_iterator end()const

{

return _head;

}

const_iterator cend()const

{

return _head;

}

const 修饰begin 是为了防止权限放大的错误出现

因为拷贝构造中参数是 const 对象

插入删除

由于双向循环，插入删除相对比较简单，就是注意链接的顺序性即可

<code>void push_back(const T& x)

{

//Node* newnode = new Node(x); //没有写Node 构造报错

//_head->_prev->_next = newnode;

//newnode->_next = _head;

//newnode->_prev = _head->_prev;

//_head->_prev = newnode;

//++_size;

insert(end(), x);//复用 insert

}

void push_front(const T& x)

{

insert(begin(), x);

}

iterator insert(iterator pos, const T& x)

{

Node* cur = pos._node;

Node* prev = cur->_prev;

Node* newnode = new Node(x);

// prev newnode cur

newnode->_next = cur;

cur->_prev = newnode;

newnode->_prev = prev;

prev->_next = newnode;

++_size;

return newnode;

}

实现了 insert 我们可以根据迭代器复用 insert 实现尾插和头插

TIp：新节点将位于插入点的前一个位置这是STL对于“插入操作”的标准规范。

删除操作，与 insert 一样使用指针操作，来达到删除的效果。注意要对删除的节点进行释放空间操作（delete），不然会发生内存泄漏！！！

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;

}

需要注意的是，任意位置删除因为使用了迭代器，删除后会造成迭代器失效，所以需要更新迭代器，返回被删除节点的下一个节点的迭代器即可。

拷贝赋值析构函数

//lt1(lt)

list( const list<T>& lt)

{

empty_init();

for (auto& e : lt)

{

push_back(e);

}

void swap(list<T>& lt)

{

std::swap(_head, lt._head);

std::swap(_size, lt._size);

}

//lt1=lt3

list<T>& operator=(list<T> lt)

{

swap(lt);

return *this;

}

~list()

{

clear();

delete _head;

_head = nullptr;

}

void clear()

{

auto it = begin();

while (it!=end())

{

//erase(it++);//可以这样写可以理解为先进行了 it++后再执行 erase 代码块里的内容

it=erase(it);

}

_size = 0;

}

拷贝构造我们只需要范围 for 遍历依次尾插即可，这里空初始化是为了创捷头结点，赋值重载只需要交换头节点就可以

4、list与vector 区别对比

vector 与 list 都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不同，其主要不同如下：

上一篇： C语言经典100题目（满足所有C程序基础）

下一篇： C++和OpenGL实现3D游戏编程【连载15】——着色器初步

本文标签

【C++】——list 容器的解析与极致实现

声明

本文内容仅代表作者观点，或转载于其他网站，本站不以此文作为商业用途
如有涉及侵权，请联系本站进行删除
转载本站原创文章，请注明来源及作者。