当前位置：首页 > news >正文

C++ list类

news 来源：原创 2025/8/10 7:39:44

C++ list类

引言

在C++标准库中，list是一个非常重要的容器类，它实现了双向链表的数据结构。本文将详细介绍C++中list的使用方法，包括其构造函数、迭代器、容量操作、元素访问以及修改操作等。此外，我们还将探讨list的迭代器失效问题，并通过模拟实现一个简单的list类来深入理解其底层工作原理。最后，我们将对比list与vector的优缺点，帮助读者在实际开发中根据需求选择合适的容器。

list的文档介绍

1.list的使用

1.1 list的构造

constructor构造函数	接口说明
list (size_type n, const value_type& val =value_type())	构造的list中包含n个值为val的元素
list()	构造空的list
list (const list& x)	拷贝构造函数
list (InputIterator first, InputIterator last)	用`[first, last)`区间中的元素构造list

1.2 list的iterator的使用

可以先将迭代器理解为一个指针，该指针指向list中的某个节点

函数声明	接口说明
begin+end	返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器
rbegin+rend	返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一个位置的reverse_iterator,即begin位置

注意：

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

迭代器的分类

从功能可以分为四种 iterator,reverse_iterator,const_iterator,const_reverse_iterator。

从性质上又可以分为三种

性质	使用的类	可用操作符
单向 (ForwardIterator)	forward_list / unordered_map …	++
双向 (BidirectionalIterator)	list / map / set…	++ / –
随机 (RandomAccessIterator)	vector / string / deque…	++ / – / + / -

由迭代器的底层结构决定可以使用哪些算法

1.3 list capacity

函数声明	接口说明
empty	检测list是否为空，是返回true，否则返回false
size	返回list中有效节点的个数

1.4 list element acess

函数声明	接口说明
front	返回list的第一个节点中值的引用
back	返回list的最后一个节点中值的引用

1.5 list modifiers

函数声明	接口说明
push front	在list首元素前插入值为val的元素
pop front	删除list中第一个元素
push back	在list尾部插入值为val的元素
pop back	删除list中最后一个元素
insert	在list position位置中插入值为val的元素
erase	删除list position位置的元素
swap	交换两个list中的元素
clear	清空list中的有效元素

2. list的迭代器失效

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

代码示例

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;}
}
// 改正
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);}
}

3. list的模拟实现

3.1 List.h文件

#pragma once
#include<assert.h>namespace jason
{template<class T>struct list_node{T _data;                // 节点存储的数据list_node<T>* _next;    // 指向下一个节点的指针list_node<T>* _prev;    // 指向前一个节点的指针// 构造函数，初始化节点的数据和指针list_node(const T& data = T()):_data(data)        // 初始化数据, _next(nullptr)   // 初始化下一个节点指针为空, _prev(nullptr)    // 初始化前一个节点指针为空{}};template<class T, class Ref, class Ptr>struct list_iterator{typedef list_node<T> Node;  // 定义节点类型typedef list_iterator<T, Ref, Ptr> Self;  // 定义迭代器自身类型Node* _node;  // 当前迭代器指向的节点// 构造函数，初始化迭代器指向的节点list_iterator(Node* node):_node(node){}// 解引用操作符，返回当前节点的数据引用Ref operator*(){return _node->_data;}// 箭头操作符，返回当前节点数据的指针Ptr operator->(){return &_node->_data;}// 前置++操作符，迭代器指向下一个节点Self& operator++(){_node = _node->_next;return *this;}// 前置--操作符，迭代器指向前一个节点Self& operator--(){_node = _node->_prev;return *this;}// 后置++操作符，迭代器指向下一个节点，但返回自增前的迭代器Self operator++(int){Self tmp(*this);  // 保存当前迭代器_node = _node->_next;  // 指向下一个节点return tmp;  // 返回自增前的迭代器}// 后置--操作符，迭代器指向前一个节点，但返回自减前的迭代器Self operator--(int){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;}};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;// 返回指向链表第一个元素的迭代器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 Node;  // 创建哨兵节点_head->_next = _head;  // 哨兵节点的下一个节点指向自己_head->_prev = _head;  // 哨兵节点的前一个节点指向自己_size = 0;  // 初始化链表大小为0}// 默认构造函数，初始化空链表list(){empty_init();}// 使用初始化列表构造链表list(initializer_list<T> il){empty_init();for (auto& e : il){push_back(e);  // 将初始化列表中的元素逐个插入链表}}// 拷贝构造函数list(const list<T>& lt){empty_init();for (auto& e : lt){push_back(e);  // 将另一个链表中的元素逐个插入当前链表}}// 赋值操作符list<T>& operator=(list<T> lt){swap(lt);  // 交换当前链表和传入链表的内容return *this;}// 析构函数，释放链表内存~list(){clear();  // 清空链表delete _head;  // 删除哨兵节点_head = nullptr;}// 清空链表void clear(){auto it = begin();while (it != end()){it = erase(it);  // 逐个删除链表中的节点}}// 交换两个链表的内容void swap(list<T>& lt){std::swap(_head, lt._head);  // 交换哨兵节点std::swap(_size, lt._size);  // 交换链表大小}// 在链表末尾插入元素void push_back(const T& x){insert(end(), x);  // 在链表末尾插入元素}// 在链表头部插入元素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);  // 创建新节点// 将新节点插入到前一个节点和当前节点之间newnode->_next = cur;cur->_prev = newnode;newnode->_prev = prev;prev->_next = newnode;++_size;  // 链表大小加1return newnode;  // 返回指向新节点的迭代器}// 删除链表末尾的元素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;  // 链表大小减1return next;  // 返回指向下一个节点的迭代器}// 返回链表的大小size_t size() const{return _size;}// 判断链表是否为空bool empty() const{return _size == 0;}private:Node* _head;  // 哨兵节点size_t _size;  // 链表大小};struct AA{int _a1 = 1;int _a2 = 1;};// 按需实例化// T* const ptr1// const T* ptr2template<class Container>void print_container(const Container& con){// const iterator -> 迭代器本身不能修改// const_iterator -> 指向内容不能修改typename Container::const_iterator it = con.begin();//auto it = con.begin();while (it != con.end()){//*it += 10;cout << *it << " ";++it;}cout << endl;for (auto e : con){cout << e << " ";}cout << endl;}}

3.2 List的反向迭代器

由于反向迭代器的++就是正向迭代器的- -，反向迭代器的- -就是正向迭代器的++，因此反向迭代器的实现可以借助正向迭代器，即：反向迭代器内部可以包含一个正向迭代器，对正向迭代器的接口进行包装即可。

template<class Iterator>
class ReverseListIterator
{// 注意：此处typename的作用是明确告诉编译器，Ref是Iterator类中的类型，而不是静态成员变量// 否则编译器编译时就不知道Ref是Iterator中的类型还是静态成员变量// 因为静态成员变量也是按照 类名::静态成员变量名 的方式访问的
public:typedef typename Iterator::Ref Ref;typedef typename Iterator::Ptr Ptr;typedef ReverseListIterator<Iterator> Self;
public://// 构造ReverseListIterator(Iterator it): _it(it){}//// 具有指针类似行为Ref operator*(){Iterator temp(_it);--temp;return *temp;}Ptr operator->(){ return &(operator*());}//// 迭代器支持移动Self& operator++(){--_it;return *this;}Self operator++(int){Self temp(*this);--_it;return temp;}Self& operator--(){++_it;return *this;}Self operator--(int){Self temp(*this);++_it;return temp;}//// 迭代器支持比较bool operator!=(const Self& l)const{ return _it != l._it;}bool operator==(const Self& l)const{ return _it != l._it;}Iterator _it;
};

4.list与vector的对比

	vector	list
底层结构	动态顺序表，一段连续空间	带头结点的双向循环链表
随机访问	支持随机访问，访问某个元素效率`O(1)`	不支持随机访问，访问某个元素效率`O(N)`
插入和删除	任意位置插入和删除效率低，需要搬移元素，时间复杂度为`O(N)`，插入时有可能需要增容，增容：开辟新空间，拷贝元素，释放旧空间，导致效率更低	任意位置插入和删除效率高，不需要搬移元素，时间复杂度为`O(1)`
空间利用率	底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高	底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低
迭代器	原生态指针	对原生态指针(节点指针)进行封装
迭代器失效	在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效	插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响
使用场景	需要高效存储，支持随机访问，不关心插入删除效率	大量插入和删除操作，不关心随机访问

C++ list类

目录

引言

1.list的使用

1.1 list的构造

1.2 list的iterator的使用

1.3 list capacity

1.4 list element acess

1.5 list modifiers

2. list的迭代器失效

3. list的模拟实现

3.1 List.h文件

3.2 List的反向迭代器

4.list与vector的对比

相关文章：