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

c++-list

news 2025/7/30 5:50:07

C++-list

std::list是C++标准模板库(STL)提供的双向链表容器，它提供了高效的插入和删除操作，特别适合频繁修改的序列。定义在 <list> 头文件中，属于 std 命名空间。该类的接口与常规容器接口基本一致。

模板原型：

template < class T, class Alloc = allocator<T> > class list;

allocator<T>：STL空间配置器（内存池）。

基本特性：

  • 实现方式：双向链表结构，每个元素包含指向前驱和后继的指针。

  • 内存分配：元素在内存中非连续存储的，通过指针链接。

  • 泛型容器：通过模板实现，可以存储任何类型的元素。

  • 迭代器：双向迭代器（支持++和–操作）。

1. 底层理解

list 底层是 带头双向循环链表。

template<typename T>
struct list_node{T val;list_node* prev;list_node* next;list_node(const T& data = T()) :val(data) , prev(nullptr) , next(nullptr) {}
};
template<typename T>
class list {private:list_node<T>* node;
}

在这里插入图片描述

2. 成员函数

2.1 成员类型

成员类型解释
value_type第一个模板参数（T）
allocator_type第二个模板参数（Alloc）
size_type无符号整数（size_t）
reference类型引用（T&）
const_referenceconst类型引用（const T&）

2.2 构造函数

序号函数原型说明
1️⃣explicit list (const allocator_type& alloc = allocator_type())默认构造
2️⃣list (const list& x)拷贝构造
3️⃣explicit list (size_type n, const value_type& val = value_type(), const allocator_type& alloc = allocator_type())使用 n 个 val 值初始化
4️⃣template <class InputIterator> list (InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type())使用一段迭代器区间初始化

2.3 赋值重载

序号函数原型说明
1️⃣list& operator= (const list& x)两个已存在的 list 对象的赋值

2.4 迭代器

序号函数原型说明
1️⃣iterator begin()返回指向 list 对象中第一个元素的迭代器
2️⃣const_iterator begin() const返回指向 list 对象中第一个元素的 const迭代器
3️⃣iterator end()返回指向 list 对象末尾元素之后位置的迭代器
4️⃣const_iterator end() const返回指向 list 对象末尾元素之后位置的 const迭代器
5️⃣reverse_iterator rbegin()返回指向 list 对象末尾元素的反向迭代器
6️⃣const_reverse_iterator rbegin() const返回指向 list 对象末尾元素的const反向迭代器
7️⃣reverse_iterator() rend()返回指向 list 对象起始元素之前位置的反向迭代器
8️⃣const_reverse_iterator() rend() const返回指向 list 对象起始元素之前位置的const反向迭代器

在这里插入图片描述

2.5 容量相关的接口

序号函数原型说明
1️⃣size_type size() const返回 list 对象中元素的数量
2️⃣bool empty() const判断当前 list 对象是否为空

2.6 元素的访问

序号函数原型说明
1️⃣reference front()返回 list 对象第一个元素的引用
2️⃣const_reference front() const返回 const list 对象第一个元素的 const引用
3️⃣reference back()返回 list 对象最后一个元素的引用
4️⃣const_reference back() const返回 const list 对象最后一个元素的引用

2.7 修改相关的接口

序号函数原型说明
1️⃣template <class InputIterator> void assign (InputIterator first, InputIterator last)使用一段迭代器区间赋值给 list 对象（通常使用其他容器）
2️⃣void push_front (const value_type& val)在 list 对象头部插入 val 元素
3️⃣void pop_front()在 list 对象头部删除一个元素
4️⃣void push_back (const value_type& val)在 list 对象尾部插入 val 元素
5️⃣void pop_back()在 list 对象尾部删除一个元素
6️⃣iterator insert (iterator pos, const value_type& val);在 list 对象的 pos 位置迭代器插入 val 元素，返回新插入元素的迭代器
7️⃣iterator erase (iterator pos);删除 list 对象的 pos 位置迭代器元素，返回删除位置元素的下一个迭代器
8️⃣void clear();清空 list 对象中所有元素

2.8 其他操作

序号函数原型说明
1️⃣void reverse()逆置 list 对象中的元素
2️⃣void sort()排序 list 对象中的元素（默认升序）
3️⃣void merge (list& x)合并两个有序的 list，将 x 对象中的所有元素合并到当前 list 中，合并完后 x 将变为空链表
4️⃣void unique()去重，但前提需要 list 对象有序
5️⃣void remove (const value_type& val)移除所有 val 元素
6️⃣void splice (iterator position, list& x)将x链表中的所有元素移动到当前链表的 position迭代器之前，移动后 x 变为空链表
7️⃣void splice (iterator position, list& x, iterator i)将x链表中 i 位置迭代器元素移动到当前链表的 position迭代器之前
8️⃣void splice (iterator position, list& x, iterator first, iterator last);将x链表一段迭代器区间移动到当前链表的 position迭代器之前
  1. reverse

在这里插入图片描述

  1. sort

在这里插入图片描述

  1. merge

在这里插入图片描述

  1. unique

在这里插入图片描述

  1. remove

在这里插入图片描述

6.splice

在这里插入图片描述

3. list迭代器失效

C++中，list 与 vector 迭代器失效有所不同，list迭代器失效主要发生在 元素被删除时

迭代器失效的情况：

  • erase 时被删除位置元素迭代器失效。

    • 解决方式：通过 erase 返回值重新获取迭代器（erase返回删除元素的下一个位置迭代器）

  • 整个 list 被销毁或赋值时，所有迭代器都会失效。

4. list模拟实现

// list.hpp
#pragma once#include <iostream>
#include <cassert>namespace simulate_list {template<typename T>struct list_node{T val;list_node* prev;list_node* next;list_node(const T& data = T()) :val(data) , prev(nullptr) , next(nullptr) {}};template<typename T , typename Ref , typename Ptr>struct __list_iterator {typedef list_node<T> node;typedef __list_iterator<T , Ref , Ptr> self;__list_iterator(node* nodeptr) :cur(nodeptr) {}self& operator++() {cur = cur->next;return *this;}self operator++(int) {self temp(cur);cur = cur->next;return temp;}self& operator--() {cur = cur->prev;return *this;}self operator--(int) {self temp(cur);cur = cur->prev;return temp;}Ref operator*() {return cur->val;}Ptr operator->() {return &(operator*());}bool operator==(const self& s) {return cur == s.cur;}bool operator!=(const self& s) {return cur != s.cur;}node* cur;};template<typename 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 iterator(head->next); }iterator end() { return iterator(head); }const_iterator begin() const { return const_iterator(head->next); }const_iterator end() const { return const_iterator(head); }bool empty() const { return head->next == head; }T& front() { assert(!empty()); return head->next->val; }T& back() { assert(!empty()); return head->prev->val; }const T& front() const { assert(!empty()); return head->next->val; }const T& back() const { assert(!empty()); return head->prev->val; }size_t size() const {size_t count = 0;for (auto& a : *this) count++;return count; }void clear() {auto it = begin();while (it != end())it = erase(it);}void initializer_list() {head = new node;head->prev = head;head->next = head;}list<T>() {initializer_list();}list<T>(const list<T>& l) {initializer_list();for (auto& node : l)push_back(node);}list<T>& operator=(list<T> l) {std::swap(head , l.head);return *this;}~list<T>() {clear();delete head;head = nullptr;}iterator insert(iterator position , const T& val);iterator erase(iterator position);void push_front(const T& val) { insert(begin() , val); }void pop_front() { assert(!empty()); erase(begin()); }void push_back(const T& val) { insert(end() , val); }void pop_back() { assert(!empty()); erase(--end()); }  private:node* head = nullptr;}; template<typename T>typename list<T>::iterator list<T>::insert(list<T>::iterator position , const T& val) {node* prev = position.cur->prev;node* newnode = new node(val);prev->next = newnode;newnode->prev = prev;newnode->next = position.cur;position.cur->prev = newnode;return iterator(newnode);   // 返回新插入节点的迭代器}template<typename T>typename list<T>::iterator list<T>::erase(list<T>::iterator position) {node* prev = position.cur->prev;node* next = position.cur->next;prev->next = next;next->prev = prev;delete position.cur;return iterator(next);  // 返回删除元素的下一个元素}} // namespace simulate_list end
http://www.lryc.cn/news/603198.html

相关文章：

  • 【VOS虚拟操作系统】未来之窗打包工具在前端资源优化中的应用与优势分析——仙盟创梦IDE
  • Redis内存使用耗尽情况分析
  • 40+个常用的Linux指令——下
  • 艾利特机器人：光伏机器人如何重塑清洁能源制造新格局
  • 【CDH】CDH环境中升级ZooKeeper的实战记录
  • 基于KMeans、AgglomerativeClustering、DBSCAN、PCA的聚类分析的区域经济差异研究
  • 【Linux知识】Linux Shell 脚本中的 `set -ex` 命令深度解析
  • 复现cacti的RCE（CVE-2022-46169）
  • Go 客户端玩转 ES|QL API 直连与 Mapping Helpers 实战详解
  • upload-labs靶场通关（1-12）
  • 服务器之光：Nginx--反向代理模块详解及演练
  • 图论：Bellman_ford算法
  • 《汇编语言：基于X86处理器》第10章 结构和宏（3）
  • 【WRF-Chem 实例1】namelist.input 详解- 模拟CO2
  • 鸿蒙Harmony-自定义List组件，解决List组件手势滑动点击卡住问题
  • 【图像噪点消除】——图像预处理（OpenCV）
  • 创建型设计模式-工厂方法模式和抽象工厂方法模式
  • 社区老人健康信息管理系统|基于springboot社区老人健康信息管理系统设计与实现(源码+数据库+文档)
  • Gartner发布CTEM指南：使用持续威胁暴露管理来减少网络攻击
  • 智能体安全与可信AI：防护机制与伦理考量
  • 利用 C# 实现 Word 文档多维度统计（字数、字符数、页数、段落数、行数）
  • macOS “Sploitlight“漏洞曝光：攻击者可窃取Apple Intelligence缓存数据
  • FreeRTOS在中断上下文中设置事件组，调度很慢的的解决方法
  • JavaWeb 入门：CSS 基础与实战详解（Java 开发者视角）
  • 如何在在NPM发布一个React组件
  • pycharm中安装pythonocc
  • 队列算法之【用队列实现栈】
  • 【Android】三种弹窗 Fragment弹窗管理
  • 人工智能技术革命：AI工具与大模型如何重塑开发者工作模式与行业格局
  • Sentinel实现限流和熔断降级