【C++闯关笔记】STL：list 的学习和使用

发布于：2025-09-07 ⋅ 阅读:(18) ⋅ 点赞:(0)

系列文章目录

第零篇：从C到C++入门：C++有而C语言没有的基础知识总结-CSDN博客

第一篇：【C++闯关笔记】封装①：类与对象-CSDN博客

第二篇：【C++闯关笔记】封装②：友元与模板-CSDN博客

第三篇：【C++闯关笔记】STL：string的学习和使用（万字精讲）-CSDN博客

第四篇：【C++闯关笔记】STL：vector的学习与使用-CSDN博客

第五篇：【C++闯关笔记】STL：list 的学习和使用-CSDN博客

前言

为什么要引入list？——“你是否曾因为需要在数组中间插入1000个新数据，而导致程序运行缓慢？”

list 的引入，目的就是解决某些情况下由于vector的局限性：中间插入/删除效率低（O(n)），所导致的效率低下问题。

一、list 是什么？

1.list 引入

什么是 std::list？—— 一个直观的比喻：

将 std::list 比作一列火车或一条珍珠项链。

解释：每节车厢（或每颗珍珠）就是一个“节点”，里面装着你的数据。车厢之间通过“挂钩”（指针）连接起来。不像数组那样所有车厢都挤在一条固定的轨道上，火车可以在任何地方轻松地加上或去掉一节车厢，完全不影响其他车厢。

所以std::list 是一个双向链表容器。

如果你学习过数据结构——链表，那么list对你而言就是个“老熟人”了，因为list本质就是一个“封装，添加了新元素的”链表。

2.list 概要介绍

① list 是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代；

② list 的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向 其前一个元素和后一个元素；

③ 与其他的序列式容器相比(vector，deque)，list 通常在任意位置进行插入、移除元素的执行效率更好。 

二、熟悉 list 的使用

1.包含头文件与命名空间

#include <list>
using namespace std; // 或者在具体代码中使用 std::list

2.声明和初始化

std::list<int> myList;              // 一个空的int链表
std::list<int> myList2(5, 100);     // 包含5个值为100的节点
std::list<int> myList3 = {1, 2, 3}; // C++11 列表初始化

list 的常用操作

以下为list中一些常见的重要接口。

添加元素

①push_back：在尾部添加新数据。对应链表的append操作。

②push_front：在头部添加新数据。

③insert( itertor pos, value )：在迭代器指向的位置之前插入新元素。这是与链表最大的不同，也是需要重点理解的地方！

std::list<int>myList;
myList.push_back(1);
myList.push_front(2);
mylist.insert(myList.begin(),3);

访问元素

①front：访问第一个元素。

②back：访问最后一个元素。

注意：相较于vector，list没有[]运算符！ 因为它不是连续存储，随机访问效率极低（O(n)复杂度）。

std::list<int>myList;
myList.push_back(1);
myList.push_front(2);

int first = myList.front();
int end = myList.back();

删除元素

①pop_back：删除尾部元素。

②pop_front：删除头部元素。

③erase：删除迭代器指向的元素。

④remove：删除所有值等于value的元素（这是一个很方便的成员函数）。

⑤clear：清空所有元素。

std::list<int>myList(5,5);
myList.pop_back();
myList.pop_front(2);
mylist.erase(myList.begin());
myList.remove(5);
myList.clear();

大小、判断空和交换

①size：返回 list 中元素个数。

②empty：检测 list 是否为空，是返回true，不是返回false。

③swap：交换两个 list 中的元素。

std::list<int>myList;
myList.push_back(1);
myList.push_front(2);

size_t size = myList.size();
bool jug = myList.empty();

std::list<int>myList2={1,2,3};
myList.swap(myList2);

迭代器的使用

可暂时将迭代器理解成一个指针，该指针指向list中的某个节点。掌握迭代器的用法，理解它为何是STL容器通用的“指针”。

①begin+end：返回第一个元素的迭代器iterator + 返回最后一个元素下一个位置的迭代器iterator。

②rbegin+rend：返回第一个元素的reverse_iterator，即end位置 + 返回最后一个元素下一个位置的 reverse_iterator,即begin位置。

rbegin是begin的相反，rend是end的相反。

注意：list 迭代器是一个双向迭代器，支持++和--操作，但不支持 +n（随机访问）。

迭代器的一个重要用途就是遍历：

std::list<int>myList;
myList.push_back(1);
myList.push_front(2);
mylist.insert(myList.begin(),3);

//正向遍历
list<int>::iterator  it = myList.begin();
while(it!=myList.end())
{
    std::cout<<*it<<' ';
    it++;
}

//逆向遍历
list<int>::reverse_iterator rit =myList.rbegin();
while(rit!=myList.rend())
{
    std::cout<<*rit<<' ';
    rit++;
}

什么是迭代器失效？

  • 场景： 当你对容器进行插入（insert） 或删除（erase） 操作后，指向容器元素的迭代器可能会变得“无效”（即不能再使用它）。

  • 对于std::list：

    • 插入操作： 所有迭代器不会失效。因为你只是在两个现有节点之间新增了一个节点，不影响其他节点的地址。

    • 删除操作： 只有指向被删除节点的那个迭代器会失效，其他迭代器仍然有效。

错误使用示范

std::list<int> myList = {1, 2, 3, 4, 5};
auto it = myList.begin();
++it; // 现在 it 指向 2
myList.erase(it); // 删除 it 指向的元素（2）
std::cout << *it; // 错误！it 已经失效，行为未定义（程序可能崩溃）！

正确使用示范

std::list<int> myList = {1, 2, 3, 4, 5};
auto it = myList.begin();
++it; // 指向 2
it = myList.erase(it); // 删除2，it现在指向3，是安全的
std::cout << *it; // 输出 3

erase函数会返回一个指向被删除元素的下一个元素的迭代器，应该用它来更新你的迭代器。（insert函数同理）

三、list 的模拟实现示例

在知道如何使用 list 后，可以考虑自己模拟实现 list ，这有两个好处：

一是可以熟练 list 各种接口的使用；二是可以深度理解 list 的特性，在之后使用 list 时扬长避短，提高程序运行效率。

1.list 类成员变量

正如前文所说，list 是封装过后的链表（带头双向循环链表） ，结合链表的特性，我们可以推测 list 类大致为：

class list
{

private:
    node*_head;
    size_t _size;
};

其中的节点node，本身就是一个封装过后的结构体或者类，所以推测完整的 list 类应如：

template<typename T>
typedef struct ListNode
{
    T _val;
    struct ListNode* _next;
    struct ListNode* _prev;

    Init_List(T& x)
        :_val(x) _next(nullptr), _prev(nullptr)
    {}

}node;


template<typename T>
class list
{

private:
    node*_head;
    size_t _size;
};

2.构造函数

在数据结构链表中，头节点一般是不存储数据的，list 同样如此。

①默认构造函数

void Init_List()
{
	_head = new node(T());
    _head->_next = _head;
    _head->_prev = _head;
	_size = 0;
}

list()
{
	Init_List();
}

②重载构造函数

初始化形如：std::list<T> 对象名(n, x);

list(const size_t n, T x)
{
    Init_List(); 
    node*cur = _head;   
    for(size_t i = 0;i < n;++i)
    {
        T*newNode=new node(T(x));
        cur->_next = newNode;
        newNode->_prev = cur;
        cur = newNode;
    }

	cur->_next = _head;
	_head->_prev = cur;

    _size = n;
}

通过传入另一个 list 对象的迭代器构造：

//通过模板，实现两种迭代器构造
template<typename Iterator>
list(const Iterator begin, const Iterator end)
{
    Iterator first = begin;
    while(first!=end)
    {
        Init_List();
        push_back(*first);
        first++;
        _size++;
    }

}

这其中逻辑与push_back如出一辙，所以直接使用了push_back，push_back的实现在下文。

④拷贝构造函数

list(const list<T>& l)
{
    Init_List(); 
    list<T> temp(l.begin(),l.end());
    swap(temp);
}

解释：

在函数中临时创建一个对象，用赋值拷贝将目标对象的值赋值给这个临时对象，然后将该临时对象与已经初始化的本对象swap。当该函数运行完毕后，临时对象被析构，目标对象的值则被交换至本对象。

swap的实现在下文。

3.析构函数

在list ，析构函数的主要作用是释放空间。

~list()
{
    if (_head)
	{
		node* cur = _head->_next;
		while (cur != _head)
		{
			node* next = cur->_next;
			delete cur;
			cur = next;
		}
		delete _head;
		_head = cur = nullptr;
		_size = 0;
	}
    
    free(_head);
    _head=nullptr;
}

或者

~list()
{
	clear();
	delete _head;
	_head = nullptr;
}

clear的实现在下文。

4.模拟实现迭代器

迭代器最根本的设计理念是：它要表现得像一个指针。指针最核心的两个操作是什么？

①解引用：通过* ptr来获取它指向的对象。

②成员访问：通过ptr->member来访问所指向对象的成员。

所以，模拟实现迭代器实际上就是模拟实现上面两个功能。

正向迭代器

	template<typename T,typename Ref,typename Ptr>
	struct _list_iterator
	{
		typedef struct listNode<T> node;
		typedef struct _list_iterator<T, Ref , Ptr> Self;

		node* _pnode;

		_list_iterator(node* pnode):_pnode(pnode)
		{}

		Ref operator*()
		{
			return _pnode->_data;
		}

		Ptr operator ->()
		{
			return &_pnode->_data;
		}
		//没有参数的是前置运算符，有int参数的是后置运算符。
		Self& operator++()
		{
			_pnode = _pnode->_next;
			return *this;
		}

		Self& operator--()
		{
			_pnode = _pnode->_prev;
			return *this;
		}

		Self operator++(T)
		{
			Self temp(*this);
			_pnode = _pnode->_next;
			return temp;
		}

		Self operator--(T)
		{
			Self temp(*this);
			_pnode = _pnode->_prev;
			return temp;
		}

		bool operator!=(const Self& n)
		{
			return _pnode != n._pnode;
		}

		bool operator==(const Self& n)
		{
			return _pnode == n._pnode;
		}

	};

解释：template<typename T,typename Ref,typename Ptr>

①T：即链表节点值_val的类型；Ref：实际传入的是T&，用于重载 ‘*’ ；Ptr：实际传入的是T *，用于重载 ‘->’;

②通过使用模板，以达到一套代码同时实现普通iterator迭代器和const iterator迭代器的目的；

反向迭代器

反向迭代器的设计遵循一个重要的对称原则：反向迭代器的位置与对应的正向迭代器位置是错位的。

所以我们可以利用已经设计好的正向迭代器：

	template<typename _list_iterator>
	struct Reverse_Iterator
	{
		_list_iterator _it;

		typedef typename _list_iterator::Ref Ref;
		typedef typename _list_iterator::T T;
		typedef typename _list_iterator::Ptr Ptr;
		typedef Reverse_Iterator<_list_iterator> Self;

		Reverse_Iterator(_list_iterator it):_it(it)
		{}

		Ref operator*()
		{
			_list_iterator temp(_it);
			--temp;
			return *temp;
		}

		Ptr operator ->()
		{
			_list_iterator temp(_it);
			--temp;
			//return temp;是错误的，要的是temp存储的变量的地址
			//_list_iterator的变量成员是个node*指针，这里temp相当于二级指针。
			return &(*temp);
		}

		//没有参数的是前置运算符，有参数的是后置运算符。
		Self& operator++()
		{
			--_it;
			return *this;
		}

		Self& operator--()
		{
			++_it;
			return *this;
		}

		Self operator++(T)
		{
			Self temp(*this);
			--_it;
			return temp;
		}

		Self operator--(T)
		{
			Self temp(*this);
			++_it;
			return temp;
		}

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

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

解释：为什么在 ‘*’ 与 ‘->’ 中需要--temp？

让我们通过一个例子来理解：

假设有一个包含元素的链表：[A, B, C, D]

  • 正向迭代器：

    • begin() 指向 A

    • end() 指向 D 之后的位置

  • 反向迭代器：

    • rbegin() 内部存储的迭代器指向 end()（即 D 之后）

    • 但对 rbegin() 解引用时，我们希望得到 D

    • rend() 内部存储的迭代器指向 begin()（即 A）

    • 但对 rend() 解引用时，我们希望得到 A 之前的位置（实际上不应该解引用 rend()）

所以，当反向迭代器内部存储的迭代器 _it 指向某个位置时，解引用操作应该返回的是 _it 前一个位置的元素。

将封装好的迭代器加入到上述 list 类中，如下：

	template<typename T>
	class list
	{
		typedef listNode<T> node;
		typedef _list_iterator<T, T&,T*> iterator;
		typedef _list_iterator<T, const T& ,const T*> const_iterator;
		typedef Reverse_Iterator<iterator> reverse_iterator;
		typedef Reverse_Iterator<const_iterator> const_reverse_iterator;

     private:
        node*_head;
        size_t _size;
    };

模拟实现迭代器相关函数

包括begin、end，rbegin、rend，以及它们的const类型重载。

		iterator begin()
		{
			return iterator(_head->_next);
		}

		const_iterator begin()const
		{
			return const_iterator(_head->_next);
		}

		iterator end()
		{
			return iterator(_head);
		}

		const_iterator end()const
		{
			return const_iterator(_head);
		}

		reverse_iterator rbegin()
		{
			return reverse_iterator(end());
		}

		reverse_iterator rend()
		{
			return reverse_iterator(begin());
		}

		const_reverse_iterator rbegin()const
		{
			return reverse_iterator(end());
		}

		const_reverse_iterator rend()const
		{
			return reverse_iterator(begin());
		}

5.添加元素模拟实现

push_front

在 list 链表头头节点后插入新元素。

push_front可以用与push_back同理的方式实现。

但实际上push_front与push_back有更简单的方式实现：

		void push_front(const T& x)
		{
			insert(begin(), x);
		}

 push_back

在 list 链表末尾插入新元素。

		void push_back(const T& x)
		{
			node* end = _head->_prev;
			node* newNode = new node(T(x));

			end->_next = newNode;
			newNode->_prev = end;
			newNode->_next = _head;
			_head->_prev = newNode;

			_size++;
		}

insert

在传入迭代器之后插入一个新元素，并返回新的迭代器。

		iterator insert(iterator w, const T& x)
		{
			node* newNode = new node(T(x));
			node* cur = w._pnode;
			node* prev = cur->_prev;

			prev->_next = newNode;
			newNode->_prev = prev;
			newNode->_next = cur;
			cur->_prev = newNode;
			_size++;
			return iterator(newNode);
		}

6.访问元素模拟实现

front

返回 list 首元素的值；

		T& front()
		{
			if (!empty())return (_head->_next)->_data;
		}

back

返回 list 末尾元素的值；

		T& back()
		{
			if (!empty())return (_head->_prev)->_data;
		}

7.删除元素模拟实现

erase

删除迭代器指向的元素，并返回变化后的迭代器。

		iterator erase(iterator pos)
		{
			node* cur = pos._pnode;
			node* prev = cur->_prev;
			node* next = cur->_next;

			delete cur;
			prev->_next = next;
			next->_prev = prev;
			_size--;
			return iterator(next);
		}

pop_front

删除链表非头节点的第一位元素。

与push_front/back可以利用insert同理，pop_front/back依旧可以利用erase。

		void pop_front()
		{
			/*erase(begin());*/
			if (!empty())
			{
				node* first = _head->_next;
				node* newFirst = first->_next;

				delete first;
				_head->_next = newFirst;
				newFirst->_prev = _head;
			}
		}

pop_back

删除链表的最后一位元素。


		void pop_back()
		{
			erase(end());
		}

clear

清空链表。这里使用了迭代器遍历

		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it=erase(it);
			}
		}

remove

批量删除链表中，节点值与传入参数相同的节点。

		void remove(const T& x)
		{
			iterator it = begin();
			while (it != end())
			{
				if(*it == x)it = erase(it);
			}
		}

8.大小、判断空和交换模拟实现

包括，size 返回链表有效数据个数，empty 判断链表是否为空，swap 交换两个链表中的数据。


		size_t size()
		{
			return _size;
		}

		bool empty()
		{
			return _size == 0;
		}

		void swap(list<T>& x)
		{
			std::swap(x._head, _head);
			std::swap(x._size, _size);
		}

swap函数不必挨个交换两个链表中节点的数据，只需要将头节点与_size交换即可。

三、完整 list 模拟代码展示

将上面的各个函数和数据结构的代码合起来，就组成了一个简易的 list 类。

为了防止模拟实现的 list 代码与std::list发生冲突，下面将代码放在一个命名空间里：

#pragma once
#include<iostream>

using std::cout;
using std::endl;
namespace karsen
{
	template<typename T>
	struct listNode
	{
		T _data;
		listNode* _next;
		listNode* _prev;

		listNode(const T& x)
			:_data(x), _next(nullptr), _prev(nullptr)
		{}
	};

	template<typename T,typename Ref,typename Ptr>
	struct _list_iterator
	{

		typedef struct listNode<T> node;
		typedef struct _list_iterator<T, Ref , Ptr> Self;
		//下面三个声明用于反向迭代器中
		typedef T T;
		typedef Ref  Ref;
		typedef Ptr Ptr;

		node* _pnode;

		_list_iterator(node* pnode):_pnode(pnode)
		{}

		Ref operator*()
		{
			return _pnode->_data;
		}

		Ptr operator ->()
		{
			return &_pnode->_data;
		}
		//没有参数的是前置运算符，有int参数的是后置运算符。
		Self& operator++()
		{
			_pnode = _pnode->_next;
			return *this;
		}

		Self& operator--()
		{
			_pnode = _pnode->_prev;
			return *this;
		}

		Self operator++(T)
		{
			Self temp(*this);
			_pnode = _pnode->_next;
			return temp;
		}

		Self operator--(T)
		{
			Self temp(*this);
			_pnode = _pnode->_prev;
			return temp;
		}

		//参数类型错误：迭代器的比较运算符 != 和 ==，
		//其参数应该是另一个迭代器 (const Self&)，而不是一个节点 (const node&)。
		bool operator!=(const Self& n)
		{
			return _pnode != n._pnode;
		}

		bool operator==(const Self& n)
		{
			return _pnode == n._pnode;
		}

	};



	//反向迭代器的设计遵循一个重要的对称原则：反向迭代器的位置与对应的正向迭代器位置是错位的。
	template<typename _list_iterator>
	struct Reverse_Iterator
	{
		_list_iterator _it;

		typedef typename _list_iterator::Ref Ref;
		typedef typename _list_iterator::T T;
		typedef typename _list_iterator::Ptr Ptr;
		typedef Reverse_Iterator<_list_iterator> Self;

		Reverse_Iterator(_list_iterator it):_it(it)
		{}

		Ref operator*()
		{
			_list_iterator temp(_it);
			--temp;
			return *temp;
		}

		Ptr operator ->()
		{
			_list_iterator temp(_it);
			--temp;
			//return temp;是错误的，要的是temp存储的变量的地址
			//_list_iterator的变量成员是个node*指针，这里temp相当于二级指针。
			return &(*temp);
		}

		//没有参数的是前置运算符，有参数的是后置运算符。
		Self& operator++()
		{
			--_it;
			return *this;
		}

		Self& operator--()
		{
			++_it;
			return *this;
		}

		Self operator++(T)
		{
			Self temp(*this);
			--_it;
			return temp;
		}

		Self operator--(T)
		{
			Self temp(*this);
			++_it;
			return temp;
		}

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

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


	template<typename T>
	class list
	{
		typedef listNode<T> node;
	public:
		typedef _list_iterator<T, T&, T*> iterator;
		typedef _list_iterator<T, const T&, const T*> const_iterator;
		typedef Reverse_Iterator<iterator> reverse_iterator;
		typedef Reverse_Iterator<const_iterator> const_reverse_iterator;

		iterator begin()
		{
			return iterator(_head->_next);
		}

		const_iterator begin()const
		{
			return const_iterator(_head->_next);
		}

		iterator end()
		{
			return iterator(_head);
		}

		const_iterator end()const
		{
			return const_iterator(_head);
		}

		reverse_iterator rbegin()
		{
			return reverse_iterator(end());
		}

		reverse_iterator rend()
		{
			return reverse_iterator(begin());
		}

		const_reverse_iterator rbegin()const
		{
			return reverse_iterator(end());
		}

		const_reverse_iterator rend()const
		{
			return reverse_iterator(begin());
		}


		void empty_InitList()
		{
			_head = new node(T());
			_head->_next = _head;
			_head->_prev = _head;
			_size = 0;
		}

		list()
		{
			empty_InitList();
		}

		list(int n, const T& x)
		{
			if (n < 0)return;
			empty_InitList();

			node* cur = _head;
			for (int i = 0; i < n; i++)
			{
				node* temp = new node(T(x));
				temp->_prev = cur;
				cur->_next = temp;
				cur = cur->_next;
			}
			cur->_next = _head;
			_head->_prev = cur;

			_size = (size_t)n;
		}

		//用以区分是否是const迭代器
		template<typename InputIterator>
		list(InputIterator first, InputIterator last)
		{
			empty_InitList();
			while (first != last)
			{
				push_back(*first);
				first++;
				_size++;
			}
		}
		
		list(const list<T>& l)
		{
			empty_InitList();

			list<T>temp(l.begin(), l.end());
			swap(temp);

		}

		list<T>& operator=(list<T> other)
		{
			swap(other);
			return *this;
		}


		~list()
		{
			/*if (_head)
			{
				node* cur = _head->_next;
				while (cur != _head)
				{
					node* next = cur->_next;
					delete cur;
					cur = next;
				}
				delete _head;
				_head = cur = nullptr;
				_size = 0;
			}*/

			clear();
			delete _head;
			_head = nullptr;
		}


		void swap(list<T>& x)
		{
			std::swap(x._head, _head);
			std::swap(x._size, _size);
		}

		size_t size()
		{
			return _size;
		}

		bool empty()
		{
			return _size == 0;
		}

		T& front()
		{
			if (!empty())return (_head->_next)->_data;
		}

		T& back()
		{
			if (!empty())return (_head->_prev)->_data;
		}

		iterator insert(iterator w, const T& x)
		{
			node* newNode = new node(T(x));
			node* cur = w._pnode;
			node* prev = cur->_prev;

			prev->_next = newNode;
			newNode->_prev = prev;
			newNode->_next = cur;
			cur->_prev = newNode;
			_size++;
			return iterator(newNode);
		}

		void push_front(const T& x)
		{
			insert(begin(), x);
		}

		void push_back(const T& x)
		{
			//node* end = _head->_prev;
			//node* newNode = new node(T(x));
			//end->_next = newNode;
			//newNode->_prev = end;
			//newNode->_next = _head;
			//_head->_prev = newNode;
			//_size++;

			insert(end(), x);
		}

		iterator erase(iterator pos)
		{
			node* cur = pos._pnode;
			node* prev = cur->_prev;
			node* next = cur->_next;

			delete cur;
			prev->_next = next;
			next->_prev = prev;
			_size--;
			return iterator(next);
		}

		void pop_front()
		{
			/*erase(begin());*/
			if (!empty())
			{
				node* first = _head->_next;
				node* newFirst = first->_next;

				delete first;
				_head->_next = newFirst;
				newFirst->_prev = _head;
			}
		}

		void pop_back()
		{
			erase(end());
		}

		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it=erase(it);
			}
		}

		void remove(const T& x)
		{
			iterator it = begin();
			while (it != end())
			{
				if(*it == x)it = erase(it);
			}
		}
			
	private:
		node* _head;
		size_t _size;
	};
}

以上就是 list 有关介绍的全部内容了。

总结

本文先是详细介绍了什么是 list ，紧接着是如何使用 list ，最后尝试模拟实现list 。

本文是【C++闯关笔记】系列之一，若对本系列感兴趣，欢迎关注博主。一起学习，共同进步。

整理不易，希望对你有所帮助。

读完点赞，手留余香~

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布