在编程的世界里,容器是数据存储与管理的基石。其中,list作为一种灵活且功能强大的数据结构,扮演着举足轻重的角色。它不仅能够动态地调整大小,还允许我们在任意位置插入和删除元素,为开发者提供了极大的便利。本文将深入探讨list的奥秘,从其底层实现机制到实际应用场景,全面剖析这一容器的独特魅力。无论您是编程初学者,还是经验丰富的开发者,相信都能从中获得宝贵的启示与收获。让我们一同踏上这段探索之旅,揭开list的神秘面纱。
在 list
的实现中,底层是通过双向链表结构来存储数据。双向链表中的每个节点不仅包含数据,还包含指向前一个节点和后一个节点的两个指针。以下是节点结构的定义:
template <class T>
struct list_node
{
// 指向下一个节点的指针
list_node<T>* _next;
// 指向前一个节点的指针
list_node<T>* _prev;
// 存储节点的值
T _val;
// 构造函数,用于初始化节点
list_node(const T& val = T())
:_next(nullptr) // 将_next初始化为nullptr,表示当前节点没有下一个节点
,_prev(nullptr) // 将_prev初始化为nullptr,表示当前节点没有前一个节点
,_val(val) // 使用给定的值初始化_val
{}
};
【注意】:
template <class T>
表示 list_node
是一个模板结构体,可以接受任何类型 T
作为其节点的值类型。
:_next(nullptr), _prev(nullptr), _val(val)
)来初始化成员变量。这是一种更高效的初始化方式,特别是对于引用和指针类型。
const T& val = T()
是一个带有默认参数的构造函数。如果调用构造函数时没有提供参数,它将使用类型 T
的默认构造函数来创建一个临时对象,并用这个临时对象来初始化 _val
。
template <class T>
class list
{
typedef list_node<T> Node;
public:
// 迭代器iterator的设计"......"
// 返回指向链表第一个节点的迭代器
iterator begin();
// 返回指向链表末尾之后位置的迭代器
iterator end();
// 构造函数
list();
// 拷贝构造函数
list(const list<T>& lt);
// 赋值运算符重载
list<T>& operator=(list<T> lt);
// 析构函数
~list();
// 清空
void clear();
// 尾插
void push_back(const T& x);
// 头插
void push_front(const T& x);
// 尾删
void pop_back();
// 头删
void pop_front();
// 指定位置插入
iterator insert(iterator pos, const T& x);
// 指定位置删除
iterator erase(iterator pos);
// 返回list的大小
size_t size();
private:
Node* _head; // 指向链表的头节点
size_t _size; // 链表大小
};
【注意】:
namespace xny
{
template <class T>
struct list_node
{//...};
template <class T>
class list
{//...};
}
我们就vector与list来比较一下:
std::list
(在C++标准库中通常是双向链表或循环双向链表的实现)和std::vector
在底层实现和内存布局上有很大的不同,这导致了它们在迭代器使用上的区别。
std::vector
是一个动态数组,它在内存中连续存储元素。这意味着std::vector
的迭代器可以简单地通过指针(或指针的封装)来实现,因为元素之间的地址是连续的。std::list
则是一个链表,其元素在内存中不必连续存储。每个元素(节点)包含数据和指向下一个(以及前一个,对于双向链表)节点的指针。因此,std::list
的迭代器需要包含更多信息,通常是一个指向当前节点的指针。std::vector
的迭代器在插入或删除元素时可能会失效(如果操作导致内存重新分配),但在读取元素时通常是稳定的。std::list
的迭代器在插入或删除节点时通常不会失效(除非删除的是迭代器当前指向的节点),因为链表操作不需要移动其他元素。然而,如果迭代器指向了一个已被删除的节点(例如,通过保留一个已删除节点的迭代器),则使用该迭代器是未定义行为。std::vector
的迭代器通常是随机访问迭代器,支持高效的元素访问(通过索引)和迭代器算术(如加减整数)。std::list
的迭代器是双向迭代器(对于双向链表)或前向迭代器(对于单向链表),它们不支持随机访问,但支持顺序遍历。template <class T>
struct list_iterator
{
typedef list_node<T> Node; // 更换名称,方便使用
typedef list_iterator self;
Node* _node;
// 构造函数
list_iterator(Node* node)
:_node(node)
{}
/*各种函数重载...*/
};
*
和->
操作符的重载1.解引用*操作符
T& operator*()
{
return _node->_val;
}
_val
)的引用。由于返回的是引用类型 T&
,调用者可以直接修改该值。这里的 _node
是指向链表节点的指针,而 _val
是节点中存储的数据。2.**成员访问->**操作符:
T* operator->()
{
return &_node->_val;
}
T
类型的指针。这使得调用者能够使用指针的箭头操作符(->
)来访问节点中存储的对象的成员。需要注意的是,这里返回的是值的地址,而不是节点本身的地址。++
和--
操作符的重载1.**前置++**操作符
**【注意】:**之前我们已经声明typedef list_iterator self;
self& operator++()
{
_node = _node->_next;
}
++++it
(尽管这种写法并不常见且可能引发误解)。2.**后置++**操作符
self operator++(int)
{
self tmp(*this);
_node = _node->_next;
return tmp;
}
tmp
,该副本保存了递增前的状态,然后更新当前迭代器指向下一个节点,并返回之前保存的副本。这里的int
参数实际上并未使用,它仅作为区分前置与后置递增的语法糖。3.**前置–**操作符
self operator--()
{
_node = _node->_prev;
}
4.**后置–**操作符
self& operator--(int)
{
self tmp(*this);
_node = _node->_prev;
return tmp;
}
!=
和==
操作符的重载1.!= 操作符
bool operator!=(const self& it) const
{
return _node != it._node;
}
2.**==**操作符
bool operator==(const self& it) const
{
return _node == it._node;
}
const
? lt.end()
时,end()
函数通常会返回一个迭代器对象,这个对象是作为临时值返回的。在C++中,临时对象具有常量性,即你不能通过它们调用非const
成员函数。因此,为了使比较操作符能够接受lt.end()
返回的临时迭代器作为参数,这些操作符必须是const
的。const
成员函数也会允许调用者通过非常量的迭代器对象调用它们。这可能会引发权限放大的问题,因为调用者可能会错误地假设这些函数能够修改对象的状态。通过将比较操作符声明为const
,你明确地表明这些函数不会修改它们的参数,这有助于防止潜在的错误。const
是一种良好的编程习惯。这有助于保持代码的一致性和可预测性,使得其他开发者能够更容易地理解和使用你的类。template <class T>
class list
{
typedef list_node<T> Node;
public:
typedef list_iterator<T> iterator;
/*
...各种函数
*/
private:
Node* _head;
size_t _size;
};
list()
{
_head = new Node;
_head->next = nullptr;
_head->prev = nullptr;
_size = 0;
}
注意:
iterator begin()
{
return _head->next;
// return iterator(_head->next);
// 单参数会隐式类型转换
}
iterator end()
{
return _head;
// return iterator(_head);
}
// 那常对象呢?
vector
一样:typedef const_list_iterator<T> const_iterator;
在 vector 中,const_iterator 通过 const 修饰符即可实现不可修改的迭代器,这是因为 vector 的底层存储是连续的内存块,通过 const 限制访问的值即可。而 list 的底层是双向链表,迭代器不仅需要访问链表节点的值,还需要操作链表的前驱和后继节点(即 _prev 和 _next 指针)。直接使用 const 修饰迭代器无法满足这些需求,因为 const 限制了对链表结构的必要修改。
const
修饰?
const
修饰的迭代器会限制所有成员的修改,包括迭代器内部的_node
指针。如果我们对const
迭代器执行++
或--
操作,这些操作会修改_node
,而const
禁止这种修改。
【解决方案】:
这里我们可以模仿库里面的操作,将模板改为以下方式:
template <class T, class Ref, class Ptr>
并在list类中声明:
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;
【解释】:
iterator:
T
是迭代器将要操作的元素类型。T&
是对元素的非 const 引用类型,允许通过迭代器修改元素的值。T*
是指向元素的指针类型,用于迭代器的内部实现,以便能够访问链表中的下一个节点。const_iterator:
T
同样是迭代器将要操作的元素类型。const T&
是对元素的 const 引用类型,通过迭代器不能修改元素的值。const T*
是指向 const 元素的指针类型,确保迭代器不会修改链表中的元素。template <class T, class Ref, class Ptr>
struct list_iterator
{
typedef list_node<T> Node;
typedef list_iterator self;
Node* _node;
list_iterator(Node* node)
:_node(node)
{}
Ref operator*()
{
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)
{
list_iterator 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;
}
};
insert
这个函数接受一个迭代器 pos
,该迭代器指向链表中的一个位置,以及一个要插入的值 x
。函数应该返回指向新插入节点的迭代器。
步骤 1: 获取当前节点和前一个节点
pos
获取当前节点 cur
。prev
。如果 cur
是头节点,则 prev
应该是 nullptr
(但在这个函数中,pos
不应该指向头节点本身,而是指向链表中的一个有效位置)。然而,为了简化逻辑,我们可以假设头节点是一个哑节点,或者我们有一个特殊的处理方式。在这个例子中,我们将不处理哑节点的情况,而是假设 pos
指向一个有效的数据节点或链表末尾之后的位置(在这种情况下,cur
将是 nullptr
的下一个节点,即实际插入位置的前一个节点的 next
)。步骤 2: 创建新节点
x
创建一个新节点 newnode
。步骤 3: 插入新节点
cur
是 nullptr
(意味着 pos
指向链表末尾之后的位置),则将新节点插入到链表末尾。这通常意味着将新节点的 _next
设置为 nullptr
,并将其 _prev
设置为链表的最后一个节点。但由于我们假设 pos
是一个有效的插入位置,这种情况不太可能发生(除非在 end()
之后调用 insert
,这通常是不允许的)。然而,为了完整性,我们可以检查这一点,并相应地调整逻辑。prev
和 cur
之间。这涉及更新 prev
的 _next
、newnode
的 _next
和 _prev
、以及 cur
的 _prev
。步骤 4: 更新链表大小
_size
以反映新插入的节点。步骤 5: 返回迭代器
iterator insert(iterator pos, const T& x)
{
// 1.获取当前节点和前一个节点
Node* cur = pos._node;
Node* prev = cur->_prev;
// 2.创建新节点
Node* newnode = new Node(x);
// 3.插入新节点
prev->_next = newnode;
newnode->_prev = prev;
cur->_prev = newnode;
newnode->_next = cur;
// 4.更新链表大小
++_size;
// 5.返回迭代器
return newnode;
}
erase
这个函数接受一个迭代器 pos
,该迭代器指向链表中的一个位置函数应该返回指向删除节点之后节点的迭代器。
步骤 1: 检查节点有效性
assert
断言来确保传递给 erase
函数的迭代器 pos
是有效的,即它不等于 end()
迭代器。这是因为 end()
迭代器通常指向链表末尾的下一个位置(一个不存在的节点),因此不能从中删除任何元素。步骤 2: 获取当前节点及其邻居
pos
获取当前要删除的节点 cur
。prev
和后一个节点 next
。步骤 3: 更新链表连接
prev
的 _next
指针指向当前节点的后一个节点 next
。next
的 _prev
指针指向当前节点的前一个节点 prev
。这样,您就从链表中移除了当前节点 cur
,因为它不再被前一个和后一个节点所引用。
步骤 4: 释放内存
delete
操作符释放当前节点 cur
所占用的内存。这是非常重要的,因为如果不这样做,将会导致内存泄漏。步骤 5: 更新链表大小
_size
减一,以反映已经删除了一个节点。步骤 6: 返回新的迭代器位置
erase
函数会返回一个指向被删除节点之后节点的迭代器。在这个实现中,我们返回了指向 next
节点的迭代器。这是因为 next
节点现在是删除操作后当前位置的有效节点。next
是 nullptr
(意味着被删除的节点是链表的最后一个节点),则根据需求,您可能希望返回一个特殊的迭代器,比如 end()
,或者抛出一个异常来表示这种特殊情况。然而,在这个实现中,我们假设调用者知道他们是否在删除链表的最后一个节点,并相应地处理返回的迭代器。iterator erase(iterator pos)
{
// 1.检查节点有效性,记得包含头文件:#include<cassert>
assert(pos != end());
// 2.获取当前节点及其邻居
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
// 3.更新链表连接
prev->_next = next;
next->_prev = prev;
// 4.释放内存
delete cur;
// 5.更新链表大小
--_size;
// 6.返回新的迭代器位置
return next;
}
push_back
void push_back(const T& x)
{
// 1.获取尾节点
Node* tail = _head->_prev;
// 2.创建新节点
Node* newnode = new Node(x);
// 3.更新链表连接
tail->_next = newnode;
newnode->_prev = tail;
newnode->_next = _head;
_head->_prev = newnode;
}
【思考】: 在我们已经实现了insert函数之后,再这么写会不会有点冗余呢?
void push_back(const T& x)
{
// 很经典的类似于运算符重载的复用操作
insert(end(), x);
}
push_front
,尾删pop_back
,头删pop_front
// 头插
void push_front(const T& x)
{
insert(begin(), x);
}
// 尾删
void pop_back()
{
erase(--end());
}
// 头删
void pop_front()
{
erase(begin());
}
size_t size()
{
return _size;
}
没想到吧!如此简单是为什么呢?原因就是我们每次执行插入删除操作的时候都进行了链表大小的更改,所以不需要进行任何其他操作我们就能得到链表的大小啦!
#pragma once
#include <cassert>
namespace xny
{
template <class T>
struct list_node
{
list_node<T>* _next;
list_node<T>* _prev;
T _val;
list_node(const T& val = T())
:_next(nullptr)
,_prev(nullptr)
,_val(val)
{}
};
// typedef list_iterator<T, T&, T*> iterator;
// typedef list_iterator<T, const T&, const T*> const_iterator;
template <class T, class Ref, class Ptr>
struct list_iterator
{
typedef list_node<T> Node;
typedef list_iterator self;
Node* _node;
list_iterator(Node* node)
:_node(node)
{}
Ref operator*()
{
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)
{
list_iterator tmp(*this);
_node = _node->_prev;
return tmp;
}
bool operator!=(const self& it) const // 为什么加const?原因:在调用测试样例时,有it != lt.end(),此时传入的参数是lt.end(),而end()是传值返回一个拷贝的临时变量,出作用域就会销毁,而临时变量具有常性,所以加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;
// 如何设计const迭代器?
// typedef const_list_iterator<T> const_iterator;(T* const ptr1)
// 这样设计const迭代器是不行的,因为const迭代器期望指向内容不能修改
// 这样设计是迭代器本身不能修改
// 应该是const T* ptr2
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;
_size = 0;
}
list()
{
empty_init();
}
// lt2(lt1)
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);
}
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it); // 相当于it++
}
_size = 0;
}
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)
{
insert(begin(), x);
}
void pop_back()
{
erase(--end());
}
void pop_front()
{
erase(begin());
}
iterator insert(iterator pos, const T& x)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* newnode = new Node(x);
prev->_next = newnode;
newnode->_prev = prev;
cur->_prev = newnode;
newnode->_next = cur;
++_size;
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;
--_size;
return next;
}
size_t size()
{
/*size_t sz = 0;
iterator it = begin();
while (it != end())
{
++sz;
++it;
}
return sz;*/
return _size;
}
private:
Node* _head;
size_t _size;
};
void test_list1()
{
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;
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
}
struct A {
A(int a1 = 0, int a2 = 0)
:_a1(a1)
,_a2(a2)
{}
int _a1;
int _a2;
};
void test_list2()
{
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));
auto it = lt.begin();
while (it != lt.end())
{
// cout << *(it)._a1 << " " << *(it)._a2 << endl;
cout << it->_a1 << " " << it->_a2 << endl;
++it;
}
// 严格来说,it->->_a1才是符合语法的,由于it.operator->()返回的是A*,再调用*的重载,里面又包含了一个->,所以严格来说有两个->
// 但是因为运算符重载要求可读性,那么编译器特殊处理,省略了一个->
}
void test_list3()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_front(5);
lt.push_front(6);
lt.push_front(7);
lt.push_front(8);
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);
lt.push_back(30);
lt.push_back(40);
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
cout << lt.size() << endl;
}
void test_list4()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
list<int> lt1(lt);
for (auto e : lt1)
{
cout << e << " ";
}
cout << endl;
list<int> lt2;
lt2.push_back(10);
lt2.push_back(20);
lt2.push_back(30);
lt2.push_back(40);
for (auto e : lt2)
{
cout << e << " ";
}
cout << endl;
lt1 = lt2;
for (auto e : lt1)
{
cout << e << " ";
}
cout << endl;
}
}
#include <iostream>
using namespace std;
#include "list.h"
int main()
{
xny::test_list1();
cout << endl << endl;
xny::test_list2();
cout << endl << endl;
xny::test_list3();
cout << endl << endl;
xny::test_list4();
return 0;
}
通过深入理解C++中双向链表的设计与实现,我们可以更高效地管理数据,尤其是在动态场景下。无论是增加、删除还是遍历元素,链表都展现出它的灵活性与高效性。掌握这一数据结构不仅能帮助我们编写更高性能的代码,还能为解决复杂问题提供坚实的技术基础。在实际应用中,灵活运用链表将带来更优的解决方案,让我们的程序更加健壮和高效。
今天的分享到这里就结束啦!如果觉得文章还不错的话,可以三连支持一下,17的主页还有很多有趣的文章,欢迎小伙伴们前去点评,您的支持就是17前进的动力!