【C++初阶】5.C++ list类详解（含模拟实现及其代码）

用户11952558

发布于 2026-01-09 14:10:05

1350

一、底层结构：带头双向循环链表

为链表支持头插，删除等最优结构。

二、使用方法

1. 构造函数（与 vector 相似）

list<int> l1;                    // 无参构造
list<int> l2(5, 3);              // n个val
list<int> l3(l2.begin(), l2.end()); // 迭代器区间构造
list<int> l4 = l3;               // 拷贝构造

2. 迭代器遍历

由于链表的下标+[]的复杂度较高，因此没有重载，迭代器也只支持++，--，不支持+和-。

// 方式一：迭代器遍历
list<int>::iterator it = l1.begin();
while (it != l1.end()) {
    cout << *it << " ";
    it++;
}

// 方式二：范围for（有迭代器就支持范围for）
for (auto& e : l1) {
    cout << e << " ";
}

3. 迭代器种类

有些迭代器，如vector是支持下标+[]访问，可以加/减一个数，而list的迭代器，不行。

按照性质分：

随机迭代器：如string，vector：支持+/-/++/--
双向迭代器：如list，map，set：支持++/--
单向迭代器：如unordered_map，forward_list（单向链表）：支持++

它们的功能是递减的关系。

不同的函数支持的迭代器种类也不一样：

Sort：仅支持随机迭代器，因为快排可能要取随机的key，可能会转为堆排防止递归过深\

Reverse：支持双向迭代器（随机迭代器当然也支持）

Find：仅需遍历一遍即可，因此可以支持到单向

4. push_back与emplace_back

基本上两者功能相同，我们先弄一个类：

class A {
public:
    A(int a, int b)
        :_a(a)
        ,_b(b)
    {
        cout << "构造" << endl;
    }
    
    A(const A& a) {
        _a = a._a;
        _b = a._b;
        cout << "拷贝构造" << endl;
    }
    
private:
    int _a; int _b;
};

list<A> l1;
list<A> l2;
A a1(1, 2);

l1.push_back(a1);
l1.emplace_back(a1);
l1.push_back({ 1,2 });
l2.emplace_back(1, 2);

两者的区别在最后两行：

l1.push_back({ 1,2 });
l2.emplace_back(1, 2);

看似只差一个大括号，但实际是天壤之别：

l1.push_back({ 1,2 });：是构造+拷贝构造
l2.emplace_back(1, 2);：则是直接构造

因此，两者区别是emplace_back会直接看破你的意图，直接在尾部构造一个元素，而push_back则是中规中矩先构造，再传上去。因此，在这种情况下，emplace_back略优于push_back。

5. insert与erase

由于链表的迭代器只能++/--，因此虽然insert，erase理论上很快，但是用迭代器找到对应元素是比较慢的：

// 删除第三个元素
list<int>::iterator it = l1.begin();
int k = 3;
while (k--) {
    it++;
}
l1.erase(it);

// 插入100到第三个位置
it = l1.begin();
k = 3;
while (k--) {
    it++;
}
l1.insert(it, 100);

6. 替代算法库

6.1 Reverse

l1.reverse();  // 可以将链表元素翻转过来

但是，算法库里也有reverse，支持双向迭代器，因此没必要。

6.2 Sort

用于排序。由于上文讲到，算法库里的sort要随机迭代器，因此这不适用，list里支持了sort：

l1.sort();  // 用来排序链表

6.3 Merge

用来合并有序链表：

l1.merge(l2);  // 合并两个有序链表

6.4 Unique

去重有序链表：

l1.unique();  // 去重有序链表

6.5 Splice

剪切：

auto it = l1.begin();
it++;
l1.splice(it, l2);  // 在l1的it位置插l2，l2清空

三、模拟实现

1. 节点

由于链表区别于vector，它是一节一节构成的，不是连续的，因此我们先定义一个结构体，当作链表的一个节：

template<class T>
struct list_node {
    T _data;
    list_node* _next;
    list_node* _prev;
    
    list_node(const T& data = T())
        :_data(data)
        ,_next(nullptr)
        ,_prev(nullptr)
    { }
};

要注意，c++结构体也是可以加构造函数的，此外，由于我们在类外面需要不停访问里面的_data元素，因此弄成默认为公有的结构体。

2. 普通迭代器（重要）

由于节点不是连续的，因此不能直接用指针当迭代器，++后的结果一定不是下一个。因此，我们就需要一个链表节点为成员，顺藤摸瓜去到上下的节点。

成员+构造函数：

list_node<T>* _node;

list_iterator(list_node<T>* node)
    :_node(node)
{ }

我们就需要重载这个++/--，用运算符重载这把利器，表面上是++等运算，实际上是指针的顺藤摸瓜：

list_iterator& operator++() {
    _node = _node->_next;
    return *this;
}

list_iterator& operator--() {
    _node = _node->_prev;
    return *this;
}

==和!=： 只需要比较地址是否相同即可：

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

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

完整代码：

template<class T>
struct list_iterator {
    list_node<T>* _node;
    
    list_iterator(list_node<T>* node)
        :_node(node)
    { }
    
    T& operator*() {
        return _node->_data;
    }
    
    list_iterator& operator++() {
        _node = _node->_next;
        return *this;
    }
    
    list_iterator& operator--() {
        _node = _node->_prev;
        return *this;
    }
    
    bool operator !=(const list_iterator& s)const {
        return _node != s._node;
    }
    
    bool operator ==(const list_iterator& s)const {
        return _node == s._node;
    }
};

最后将他们统一装进一个struct大箱子里，用的时候就不用管了：

typedef list_iterator<T> iterator;

别忘了最后的重命名。

3. list成员

private:
    list_node<T>* _head;  // 需要一个头节点（哨兵位）
    size_t _size;         // 以及size，以便统计个数

4. 迭代器与构造函数

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

iterator end() {
    return _head;
}

list() {
    _head = new list_node<T>;
    _head->_next = _head;
    _head->_prev = _head;
    _size = 0;
}

由于迭代器是左闭右开，并且是循环的，因此end可以直接放到开头的哨兵位上。

5. insert和erase

只需要注意各个连线，不要连错：

void insert(iterator pos, const T& val) {
    list_node<T>* cur = pos._node;
    list_node<T>* prev = cur->_prev;
    list_node<T>* new_node = new list_node<T>(val);
    
    new_node->_next = cur;
    cur->_prev = new_node;
    new_node->_prev = prev;
    prev->_next = new_node;
    ++_size;
}

void erase(iterator pos) {
    assert(pos != end());
    
    list_node<T>* prev = pos._node->_prev;
    list_node<T>* next = pos._node->_next;
    prev->_next = next;
    next->_prev = prev;
    delete pos._node;
    --_size;
}

6. push_back

复用即可：

void push_back(const T& val) {
    //list_node<T>* new_node = new list_node(val);
    //list_node<T>* tail = _head->_prev;
    //tail->_next = new_node;
    //new_node->_next = _head;
    //_head->_prev = new_node;
    //++_size;
    //auto it = end();
    //--it;
    //insert(it, val);
    insert(end(), val);  // 直接复用insert
}

7. size，empty

size_t size() {
    return _size;
}

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

8. 后置++，--

list_iterator operator++(int) {
    list_iterator tmp = *this;
    _node = _node->_next;
    return tmp;
}

list_iterator operator--(int) {
    list_iterator tmp = *this;
    _node = _node->_prev;
    return tmp;
}

先预存一下原来的节点，再对原来节点操作，再返回原来存下的节点。

那list_iterator tmp = *this中不需要写拷贝构造吗？不用，因为我们要的就是浅拷贝。因为在链表++，--里就像缆车在索道上一样，缆车向前进，但依旧是在轨道上，绝对不能瞬移到其它地方。

但是注意，需要传值返回，不能传引用，因为tmp会析构。

9. ->重载

struct A {
    int _a = 1;
    int _b = 2;
};

对于装A类的链表，如何打印？

while(it != l1.end()) {
    std::cout << (*it)._a << std::endl;
    ++it;
}

我们可以直接解引用，再用.取出相关元素（注意，解引用*优先级低，要括号）。

但是，由于指针有类似->的用法，为了方便，可以重载一个->。

先看代码：

T* operator->() {
    return &_node->_data;
}

代码逻辑很绕，是因为省略了一些东西。不省略：

std::cout << it.operator->()->_a << std::endl;

it.operator->()返回了&_node->_data，即为A的一个地址
有了*A（A的地址），我们就能正常解引用找到_a了

因此，这个->重载和->正常情况都是用了，省略了一次，才不好懂。

10. const迭代器

首先，我们以前提到过const iterator和const_iterator区别。类比指针，就是const T*和T* const。更何况这个迭代器并不是简单的const，因此不是加一个const能解决的。

解决方法：

10.1 简单粗暴法

复制粘贴一份普通迭代器代码，再将*和->两个重载（即和模板的值接触的两个）加上const：

const T& operator*() {
    return _node->_data;
}

const T* operator->() {
    return &_node->_data;
}

但这个方法一点也不优雅，我们看一下库函数怎么实现的。

10.2 模板封装

库中只有一个结构体，但是模板有三个参数：T，Ref，Ptr。

分别对应两组：

普通迭代器：T，T&，T*
const迭代器：T，const T&，const T*

但是不管是T&还是const T&，经过Ref之后，统一叫作Ref。之后，再将Ref换一个名字，即typedef成reference，提高代码可读性，一致性。

本质即为让编译器统一生成。

我们的代码修改就变成了这样子：

template<class T, class Ref, class Ptr>
struct list_iterator {
    list_node<T>* _node;
    
    list_iterator(list_node<T>* node)
        :_node(node)
    { }
    
    Ref operator*() {
        return _node->_data;
    }
    
    list_iterator& operator++() {
        _node = _node->_next;
        return *this;
    }
    
    list_iterator& operator--() {
        _node = _node->_prev;
        return *this;
    }
    
    list_iterator operator++(int) {
        list_iterator tmp = *this;
        _node = _node->_next;
        return tmp;
    }
    
    list_iterator operator--(int) {
        list_iterator tmp = *this;
        _node = _node->_prev;
        return tmp;
    }
    
    bool operator !=(const list_iterator& s)const {
        return _node != s._node;
    }
    
    bool operator ==(const list_iterator& s)const {
        return _node == s._node;
    }
    
    Ptr operator->() {
        return &_node->_data;
    }
};

11. 迭代器失效

由于插入元素，地址不改变，因此，insert不会失效。但是erase由于原先的体制会被释放，因此会失效（野指针），因此就需要返回新迭代器：

iterator erase(iterator pos) {
    assert(pos != end());
    
    list_node<T>* prev = pos._node->_prev;
    list_node<T>* next = pos._node->_next;
    prev->_next = next;
    next->_prev = prev;
    delete pos._node;
    --_size;
    return next;  // 返回下一个位置的迭代器
}

12. clear和析构

Clear不清除头节点，但析构会。Clear只用遍历一次即可：

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

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

13. 拷贝构造

参考vector，我们可以用范围for遍历一次，再插入，但先要有头节点，因此加一个empty_init()，专门初始化头节点：

void empty_init() {
    _head = new list_node<T>;
    _head->_next = _head;
    _head->_prev = _head;
    _size = 0;
}

list() {
    empty_init();
}

构造函数可以直接复用：

list(list<T> li) {
    empty_init();
    for (auto& it : li) {
        push_back(it);
    }
}

14. swap和赋值运算符重载

用现代c++写法：

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

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

将原指针和要拷贝的交换，再去析构。

15. initializer_list构造（C++11）

在list中，可以list<int> l1 = { 1,2,3,4 };这样构造一个list，就是用了一个initializer_list的类。

先包头文件#include <initializer_list>，再写一个initializer的构造函数：

list(std::initializer_list<T> li) {
    empty_init();
    for (auto& it : li) {
        push_back(it);
    }
}

这样，list模拟实现完成。

四、完整代码

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<assert.h>
#include <initializer_list>

namespace bit
{
	template<class T>
	struct list_node
	{
		T _data;
		list_node* _next;
		list_node* _prev;
		list_node(const T& data=T())
			:_data(data)
			,_next(nullptr)
			,_prev(nullptr)
		{ }
	};
	template<class T,class Ref,class Ptr>
	struct list_iterator
	{
		list_node<T>* _node;
		list_iterator(list_node<T>* node)
			:_node(node)
		{ }
		Ref operator*()
		{
			return _node->_data;
		}
		list_iterator& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		list_iterator& operator--()
		{
			_node = _node->_prev;
			return *this;
		}
		list_iterator operator++(int)
		{
			list_iterator tmp = *this;
			_node = _node->_next;
			return tmp;
		}
		list_iterator operator--(int)
		{
			list_iterator tmp = *this;
			_node = _node->_prev;
			return tmp;
		}
		bool operator !=(const list_iterator& s)const
		{
			return _node != s._node;
		}
		bool operator ==(const list_iterator& s)const
		{
			return _node == s._node;
		}
		Ptr operator->()
		{
			return &_node->_data;
		}
	};
	/*template<class T>
	struct list_const_iterator
	{
		list_node<T>* _node;
		list_const_iterator(list_node<T>* node)
			:_node(node)
		{
		}
		const T& operator*()
		{
			return _node->_data;
		}
		list_const_iterator& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		list_const_iterator& operator--()
		{
			_node = _node->_prev;
			return *this;
		}
		list_const_iterator& operator++(int)
		{
			list_const_iterator tmp = *this;
			_node = _node->_next;
			return tmp;
		}
		list_const_iterator& operator--(int)
		{
			list_iterator tmp = *this;
			_node = _node->_prev;
			return tmp;
		}
		bool operator !=(const list_const_iterator& s)const
		{
			return _node != s._node;
		}
		bool operator ==(const list_const_iterator& s)const
		{
			return _node == s._node;
		}
		const T* operator->()
		{
			return &_node->_data;
		}
	};*/
	template<class T>
	class list
	{
	public:
		/*typedef list_iterator<T> iterator;
		typedef list_iterator<T> const_iterator;*/
		typedef list_iterator<T, T&, T*> iterator;
		typedef list_iterator<T, const T&, const T*> const_iterator;
		iterator begin()
		{
			return _head->_next;
		}
		iterator end()
		{
			return _head;
		}
		const_iterator begin() const
		{
			return _head->_next;
		}
		const_iterator end() const
		{
			return _head;
		}
		void empty_init()
		{
			_head = new list_node<T>;
			_head->_next = _head;
			_head->_prev = _head;
			_size = 0;
		}
		list()
		{
			empty_init();
		}
		list(const list<T>&li)
		{
			empty_init();
			for (auto&it : li)
			{
				push_back(it);
			}
		}
		list(std::initializer_list<T> li)
		{
			empty_init();
			for (auto& it : li)
			{
				push_back(it);
			}
		}
		void swap(list<T>&li)
		{
			std::swap(_head, li._head);
			std::swap(_size, li.size);
		}
		list<T>&operator=(const list<T>&li)
		{
			swap(li);
			return *this;
		}
		void push_back(const T& val)
		{
			//list_node<T>* new_node = new list_node(val);
			//list_node<T>* tail = _head->_prev;
			//tail->_next = new_node;
			//new_node->_next = _head;
			//_head->_prev = new_node;
			//++_size;
			//auto it = end();
			//--it;
			//insert(it, val);
			insert(end(), val);
		}
		void insert(iterator pos, const T&val)
		{
			list_node<T>* cur = pos._node;
			list_node<T>* prev = cur->_prev;
			list_node<T>* next = cur->_next;
			list_node<T>* new_node = new list_node<T>(val);
			new_node->_next = cur;
			cur->_prev = new_node;
			new_node->_prev = prev;
			prev->_next = new_node;
			++_size;
		}
		iterator erase(iterator pos)
		{
			assert(pos != end());
			list_node<T>* prev = pos._node->_prev;
			list_node<T>* next = pos._node->_next;
			prev->_next = next;
			next->_prev = prev;
			delete pos._node;
			--_size;
			return next;
		}
		size_t size()
		{
			return _size;
		}
		bool empty()
		{
			return size() == 0;
		}
		void clear()
		{
			auto it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}
		~list()
		{
			clear();
			delete _head;
			_head = nullptr;

		}

	private:
		list_node<T>* _head;
		size_t _size;
	};
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2026-01-09，如有侵权请联系 cloudcommunity@tencent.com 删除

return