目录
🌈前言
本篇文章进行STL中list（双向链表）序列容器的学习！！！
🌸 list
🌷1、list的介绍及使用
🌸1.1、list的介绍
- list是可以在常数范围内在任意位置进行插入和删除的序列容器，并且该容器可以前后双向迭代
- list的底层是双向链表结构，双向链表中每个元素存储在互不关联的独立节点中，在节点中听过指针指向其前一个元素和后一个元素来进行链接
- list与forward_list非常相似：最主要的不同在于fowward_list是单链表，只能往前进行迭代，已让其简单高效，而list可以往前和往后进行迭代
- list与其他容器相比（array、vector、deque），list通常在任意位置进行插入、移除元素的执行效率更好，尾插尾删效率慢，需要迭代一遍
- list与其他序列容器相比，list和forward_list最大的缺陷是不支持任意位置的访问
比如：
- 要访问list的第n个元素，必须从已知的位置（头结点或尾节点）迭代到该位置，在这段位置上迭代需要线性时间的开销
- list还需要一些额外的空间，以保持每个节点的相关信息（对于存储类型较小元素的大list来说这可能是一个重要的因素）
list底层原理图(双向链表)：
🌹1.2、list的使用
list中的接口比较多，此处类似，只需要掌握如何正确的使用，然后再去深入研究背后的原理，已达到可扩展的能力。以下为list中一些常见的重要接口
🌹1.2.1、list容器常见的构造函数
| （constructor）构造函数 | 接口说明 |
|---|---|
| list() （重点） | 构造空的list |
| list（size_type n, const value_type& val = value_type()） | 构造list中包含n个值尾val的元素 |
| list (const listr& l) （重点） | 拷贝构造函数 |
| list (InputIterator first, InputIterator last) | 使用区间[first, last)中的元素来构造list |
举个栗子🌰：
void TestList()
{
list<int> l1; // 构造空的list
list<int> l2(5, 100); // 构造5个值为100的list
list<int> l3(l2); // 拷贝构造函数
list<int> l4(l3.begin(), l3.end()); // 使用迭代器来构造list
int Array[] = { 1, 2, 3, 4 };
// 以数组为迭代器区间来构造list[Array, Array + 4)
list<int> l5(Array, Array + sizeof(Array) / sizeof(int));
// 使用迭代器进行遍历输出
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;
}
🌺1.2.2、list iterator（迭代器的使用）
| 函数声明 | 接口说明 |
|---|---|
| begin + end | 返回第一个元素的迭代器 + 返回最后一个元素的下一个位置的迭代器 |
| rbegin + rend | 返回第一个元素的reverse_iterator，即end位置，返回最后一个元素下一个位置的reserve_iterator，及begin位置 |
【注意】
- begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
- rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动
举个栗子🌰：
void print_list(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; 编译不通过 --- 被const修饰不能修改
}
cout << endl;
}
int main()
{
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
list<int> l(array, array + sizeof(array) / sizeof(array[0]));
// 使用正向迭代器正向list中的元素
for (list<int>::iterator it = l.begin(); it != l.end(); ++it)
cout << *it << " ";
cout << endl;
// 使用反向迭代器逆向打印list中的元素
for (list<int>::reverse_iterator it = l.rbegin(); it != l.rend(); ++it)
cout << *it << " ";
cout << endl;
return 0;
}
🌻1.2.3、list capacity
| 函数声明 | 接口说明 |
|---|---|
| empty | 检测list是否为空，是返回true，否返回false |
| size | 返回list节点的有效个数 |
举个栗子🌰：
void TestListCapacity()
{
list<int> v1;
list<int> v2{ 1, 2, 3, 4 };
cout << "v1的有效节点个数为: " << v1.size() << '\t'
<< "v1是否为空: " << v1.empty() << endl;
cout << "v2的有效节点个数为: " << v2.size() << '\t'
<< "v是否为空: " << v2.empty() << endl;
}
int main()
{
TestListCapacity();
return 0;
}
🌼1.2.4、list element access
| 函数声明 | 接口说明 |
|---|---|
| front | 返回list第一个节点中值（val）的引用 |
| back | 返回list最后一个节点中值（val）的引用 |
举个栗子🌰：
void TestList()
{
list<int> v{ 1, 2, 3, 4, 5 };
// 输出list中第一个节点的数据
cout << v.front() << endl;
// 输出list中最后一个节点的数据
cout << v.back() << endl;
// 将list第一个节点数据修改成100
v.front() = 100;
for (auto It = v.begin(); It != v.end(); ++It)
cout << *It << ' ';
cout << endl;
// 将list最后一个节点数据修改成200
v.back() = 200;
for (auto It = v.begin(); It != v.end(); ++It)
cout << *It << ' ';
cout << endl;
}
int main()
{
TestList();
return 0;
}
注意：二个接口返回的是这个数据的引用，引用可以充当左值…
🌿1.2.5、list modifiers
| 函数声明 | 接口说明 |
|---|---|
| push_back | 在list尾部插入值为val的元素 |
| pop_back | 删除list中最后一个元素 |
| push_front | 在list首元素前插入值为val的元素 |
| pop_front | 删除list中第一个元素 |
| insert | 在list position位置前插入值为val的元素 |
| erase | 删除list position位置的元素 |
| swap | 交换二个list中的元素 |
| clear | 清空list中的有效元素 |
举个栗子🌰1??：
void PrintList(list<int>& l)
{
for (auto& e : l)
cout << e << " ";
cout << endl;
}
void TestList1()
{
// 测试push_back、pop_back、pusk_front、pop_front
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);
}
举个栗子🌰2??：
// 测试insert、erase接口
void TestList2()
{
int Array1[] = { 1, 2, 3 };
list<int> L(Array1, Array1 + sizeof(Array1) / sizeof(Array1[0]));
// 获取list中第二个节点
auto pos = ++L.begin();
cout << *pos << endl;
// 在pos前插入值为4的元素
L.insert(pos, 4);
PrintList(L);
// 在pos前插入5个值为5的元素
L.insert(pos, 5, 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);
}
举个栗子🌰3??：
void PrintList(list<int>& l)
{
for (auto& e : l)
cout << e << " ";
cout << endl;
}
void TestList3()
{
// 测试swap、clear接口
// 用数组来构造list
int array1[] = { 1, 2, 3 };
list<int> l1(array1, array1 + sizeof(array1) / sizeof(array1[0]));
PrintList(l1);
list<int> l2{ 3, 2, 1 };
PrintList(l2);
// 交换l1和l2中的元素
l1.swap(l2);
PrintList(l1);
PrintList(l2);
// 将l2中的元素清空
l2.clear();
cout << l2.size() << endl;
}
🍀1.2.5、list迭代器失效问题
迭代器失效：
- 前面说过，大家可以将迭代器暂时理解成原生态指针，迭代器失效即所指向的节点已被销毁或释放，即该节点被删除了。
- list的底层结构为双向链表，因此在list中进行插入时，是不会导致list迭代器失效的（list底层存储空间不连续
- 只有在删除节点时才会失效，并且失效的知识指向被删除节点的迭代器，其他迭代器不受影响
举个栗子🌰：
// 错误写法
void TestListIterator1()
{
int Array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
list<int> l(Array, Array + sizeof(Array) / sizeof(int));
auto It = l.begin();
while (It != l.end())
{
// erase()接口被执行后，It所指向的节点已被删除，导致It迭代器无效，在下一次使用时，必须重新赋值
l.erase(It);
++It;
}
}
// 正确写法
void TestListIterator2()
{
int Array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
list<int> l(Array, Array + sizeof(Array) / sizeof(int));
auto It = l.begin();
while (It != l.end())
{
// erase()接口被执行后，对It重新赋值
l.erase(It++); // It = l.erase(It)
}
}
🍁2、list模拟实现
🍂2.1、模拟实现list（vs2022）
list.h
#ifndef LIST_H_
#define LIST_H_
#include <iostream>
#include <new>
#include <cassert>
namespace mylist
{
// 首先，构造节点模板类
template <typename T>
struct ListNode
{
ListNode<T>* _Pre; // 前驱指针域
ListNode<T>* _Next; // 后驱指针域
T _val; // 数据
//构造函数
ListNode(const T& val = T())
: _Pre(nullptr)
, _Next(nullptr)
, _val(val)
{}
};
/*
List 的迭代器
迭代器有两种实现方式，具体应根据容器底层数据结构实现:
1、原生态指针，比如：vector
2、将原生态指针进行封装，因迭代器使用形式与指针完全相同，因此自定义的类中必须实现以下
方法：
1、指针可以解引用，迭代器的类必须重载operator*()
2、指针可以通过->访问其所指向的空间成员，也必须重载operator->()
3、指针可以++向后移动，迭代器类必须重载operator++()与operator++(int)
至于operator--()和operator--(int)释放需要重载，根据具体结构来抉择
list可以向后查找，所以需要重载，如果是forword_list(单链表)就不用重载
*/
// 封装一个迭代器
template <typename T, typename Ref, typename Ptr>
class ListIterator
{
// 类型重命名
typedef ListIterator<T, Ref, Ptr> Self; // 迭代器本身
typedef ListNode<T>* PNode;
public:
PNode _PNode; // 指向节点的指针
//--------------------------------------------------------------- constructor（构造）
ListIterator(PNode x = nullptr)
: _PNode(x)
{}
ListIterator(const Self& s)
: _PNode(s._PNode)
{}
// Compare operator
bool operator ==(const Self& s) { return _PNode == s._PNode; }
bool operator !=(const Self& s) { return _PNode != s._PNode; }
// ---------------------------------------------------------------- * -> operator
// *重载是对迭代器取值，取的是节点的数据值
T& operator*() { return _PNode->_val; }
T* operator->() { return &(operator*()); }
// ----------------------------------------------------------------- ++ -- operator
Self& operator++()
{
_PNode = _PNode->_Next;
return *this;
}
Self operator++(int)
{
Self tmp(*this);
_PNode = _PNode->_Next;
return tmp;
}
Self& operator--()
{
_PNode = _PNode->_Pre;
return *this;
}
Self operator--(int)
{
Self tmp(*this);
_PNode = _PNode->_Pre;
return tmp;
}
};
template <typename T>
class list
{
//------------------------------------------------------------------------- typedef
typedef ListNode<T>* PNode;
typedef ListIterator<T, T*, T&> iterator; // 普通迭代器
typedef ListIterator<T, const T&, const T&> const_iterator; // 常量迭代器
public:
//-------------------------------------------------------------------------- iterator
iterator begin() { return iterator(_pHead->_Next); }
iterator end() { return iterator(_pHead); }
const_iterator cbegin() { return const_iterator(_pHead->_Next); }
const_iterator cend() { return const_iterator(_pHead); }
//-------------------------------------------------------------------------- constuctor(构造)
list() { CreatNode(); } // 构造空list
list(size_t n, const T& val = T())
{
CreatNode();
for (int i = 0; i < n; ++i)
push_back(val);
}
list(const list<T>& l)
{
CreatNode();
/*list<T> temp(l.cbegin(), l.cend());
this->swap(temp);*/
PNode cur = l._pHead->_Next;
while (cur != l._pHead)
{
push_back(cur->_val);
cur = cur->_Next;
}
}
template<typename iterator>
list(iterator* first, iterator* last)
{
CreatNode();
while (first != last)
{
push_back(*first);
++first;
}
}
list<T>& operator=(list<T> l)
{
this->swap(l);
return *this;
}
~list()
{
clear();
delete _pHead;
_pHead = nullptr;
}
//-------------------------------------------------------------------------- list capacity
size_t size()
{
size_t size = 0;
PNode cur = _pHead->_Next;
while (cur != _pHead)
{
++size;
cur = cur->_Next;
}
return size;
}
bool empty() { return _pHead->_Next == nullptr; }
//-------------------------------------------------------------------------- list Moidfy
// 增删查改 随机插入 随机删除
void push_back(const T& val)
{
PNode newNode = new ListNode<T>(val);
PNode tailPrev = _pHead->_Pre;
tailPrev->_Next = newNode;
newNode->_Pre = tailPrev;
newNode->_Next = _pHead;
_pHead->_Pre = newNode;
}
void pop_back()
{
// 存储尾节点后一个节点
PNode tailprev = _pHead->_Pre->_Pre;
// 当只有一个节点时，需要独自进行处理
if (_pHead->_Next->_Next == nullptr)
{
delete _pHead->_Next;
_pHead->_Next = _pHead;
_pHead->_Pre = _pHead;
}
else
{
delete _pHead->_Pre;
tailprev->_Next = _pHead;
_pHead->_Pre = tailprev;
}
}
void push_front(const T& val)
{
PNode newNode = new ListNode<T>(val);
PNode next = _pHead->_Next;
_pHead->_Next = newNode;
newNode->_Pre = _pHead;
newNode->_Next = next;
next->_Pre = newNode;
}
void pop_front()
{
PNode next = _pHead->_Next->_Next;
if (next == nullptr)
{
delete _pHead->_Next;
_pHead->_Next = _pHead;
_pHead->_Pre = _pHead;
}
else
{
PNode nextnode = _pHead->_Next;
_pHead->_Next = next;
next->_Pre = _pHead;
delete nextnode;
}
}
PNode find(const T& val)
{
PNode cur = _pHead->_Next;
while (cur != _pHead->_Pre)
{
if (cur->_val == val)
return cur;
cur = cur->_Next;
}
return nullptr;
}
iterator insert(iterator pos, const T& val)
{
PNode newNode = new ListNode<T>(val);
PNode Posprev = pos._PNode->_Pre;
Posprev->_Next = newNode;
newNode->_Pre = Posprev;
newNode->_Next = pos._PNode;
pos._PNode->_Pre = newNode;
return iterator(newNode);
}
iterator erase(iterator pos)
{
PNode Posnext = pos._PNode->_Next;
PNode Posprev = pos._PNode->_Pre;
Posprev->_Next = Posnext;
Posnext->_Pre = Posprev;
delete pos._PNode;
return iterator(Posnext);
}
//-------------------------------------------------------------------------- list Access
T& front() { return _pHead->_Next->_val; }
const T& front()const { return _pHead->_Next->_val; }
T& back() { return _pHead->_Pre->_val; }
const T& back()const { return _pHead->_Pre->_val; }
//-------------------------------------------------------------------------- 其他辅助接口
void clear()
{
PNode cur = _pHead->_Next;
while (cur != _pHead)
{
PNode curNext = cur->_Next;
delete cur;
cur = curNext;
}
_pHead->_Next = _pHead;
_pHead->_Pre = _pHead;
}
void swap(list<T>& l)
{
std::swap(_pHead, l._pHead);
}
private:
void CreatNode()
{
// 带头双向循环链表为空时一开始前后驱指针都指向自己
_pHead = new ListNode<T>;
_pHead->_Next = _pHead;
_pHead->_Pre = _pHead;
}
//--------------------------------------------------------------------------
private:
PNode _pHead;
};
}
#endif
🍃2.2、对mylist接口进行测试
list.cpp
#include "list.h"
using namespace std;
// 正向打印list
template <typename T>
void Printlist(mylist::list<T>& l)
{
auto It = l.cbegin();
while (It != l.cend())
{
cout << *It << ' ';
++It;
}
cout << endl;
}
// 测试list构造
void Test_list_constructor()
{
mylist::list<int> l1;
mylist::list<int> l2(10, 5);
Printlist<int>(l2);
int Array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
mylist::list<int> l3(Array, Array + sizeof(Array) / sizeof(int));
Printlist(l3);
mylist::list<int> l4(l3);
Printlist(l4);
l1 = l4;
Printlist(l1);
}
// 测试pusk_back、pop_back、pusk_front、pop_front
void Testlist2()
{
// 测试push_back、pop_back
mylist::list<int> l;
for (int i = 0; i < 5; ++i)
l.push_back(i);
Printlist(l);
for (int i = 0; i < 5; ++i)
l.pop_back();
cout << l.size() << endl;
// 测试pusk_front、pop_front
for (int i = 0; i < 5; ++i)
l.push_front(i);
Printlist(l);
for (int i = 0; i < 5; ++i)
l.pop_front();
cout << l.size() << endl;
}
void Testlist3()
{
int array[] = { 1, 2, 3, 4, 5 };
mylist::list<int> l(array, array + sizeof(array) / sizeof(array[0]));
auto pos = l.begin();
l.insert(l.begin(), 0);
Printlist(l);
++pos;
l.insert(pos, 2);
Printlist(l);
l.erase(l.begin());
l.erase(pos);
Printlist(l);
// pos指向的节点已经被删除，pos迭代器失效
cout << *pos << endl;
auto it = l.begin();
while (it != l.end())
it = l.erase(it);
cout << l.size() << endl;
}
int main()
{
Test_list_constructor();
Testlist2();
Testlist3();
return 0;
}
🍄 3、list与vector的对比
vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不同，其主要不同如下：
| vector | list | |
|---|---|---|
| 底层结构 | 动态顺序表，一段连续空间 | 带头节点的双向循环链表 |
| 随机访问 | 支持随机访问，访问某个元素效率O(1) | 不支持随机访问，访问某个元素效率O(N) |
| 插入和删除 | 任意位置插入和删除效率低，需要搬移元素，时间复杂度为O(N)，插入时可能需要增容。增容：开辟新空间，拷贝元素，释放旧空间，导致效率更低 | 任意位置插入和删除效率高，不需要搬移元素，时间复杂度为O(1)，不存在增容问题 |
| 空间利用率 | 底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高 | 底层节点随机动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低 |
| 迭代器 | 原生态指针 | 对原生态指针（节点指针）进行封装 |
| 迭代器失效 | 在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效 | 插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响 |
| 使用场景 | 需要高效存储，支持随机访问，不关心插入删除效率 | 大量插入删除操作，不关心随机访问 |