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

基于多线程实现链表快排

news 2025/7/4 6:37:25

链表的splice函数与std::partition函数详解

一、链表的splice函数：高效的节点迁移操作

splice是std::list和std::forward_list特有的成员函数，用于在链表之间高效迁移节点，不涉及元素复制，仅修改指针连接。

1. std::list的splice函数重载形式
// 1. 移动单个节点到指定位置
void splice(iterator pos, list& other, iterator it);// 2. 移动[first, last)范围内的节点到指定位置
void splice(iterator pos, list& other, iterator first, iterator last);// 3. 移动另一个链表的所有节点到指定位置
void splice(iterator pos, list& other);
2. 核心特性
  • 零复制操作：仅修改节点的前驱后继指针，不涉及元素构造/析构
  • 迭代器有效性：被移动的节点在原链表中的迭代器失效，在新链表中有效
  • 复杂度：O(1)时间复杂度（仅修改指针，不遍历链表）
3. 使用示例
std::list<int> list1 = {1, 2, 3};
std::list<int> list2 = {4, 5, 6};// 从list2头部移动一个节点到list1尾部
list1.splice(list1.end(), list2, list2.begin());  // list1: [1,2,3,4], list2: [5,6]// 从list2移动多个节点到list1头部
list1.splice(list1.begin(), list2, list2.begin(), list2.end());  // list1: [5,6,1,2,3,4], list2: 空
二、std::partition函数：序列元素重排算法

std::partition是C++标准库算法，用于将序列分为满足和不满足条件的两部分，不保证元素顺序。

1. 函数签名
template<class ForwardIt, class UnaryPredicate>
ForwardIt partition(ForwardIt first, ForwardIt last, UnaryPredicate p);
2. 核心逻辑
  • 操作过程：
    1. 遍历[first, last)区间
    2. 将满足谓词p的元素移到区间前部
    3. 返回第一个不满足p的元素迭代器
  • 稳定性：不保证保留原序列中元素的相对顺序
  • 返回值：指向第一个不满足p的元素，或last（所有元素都满足）
3. 使用示例
std::vector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6};// 将偶数移到前部
auto it = std::partition(vec.begin(), vec.end(), [](int x) { return x % 2 == 0; });// 输出结果：[4, 2, 6, 3, 1, 1, 5, 9]
for (int i : vec) std::cout << i << " ";
std::cout << "分割点: " << *it << std::endl;
三、对比与应用场景
函数所属类别核心功能典型场景
list::splice容器成员函数链表节点迁移（零复制）快速排序、链表重组、队列操作
std::partition标准算法按条件重排序列元素快速排序分割、数据过滤
四、注意事项
1. splice的限制
  • 仅适用于std::list和std::forward_list
  • 被操作的链表必须属于同一类型
  • 移动后原链表的迭代器、引用、指针失效
2. partition的特性
  • 不保证稳定性（元素相对顺序可能改变）
  • 返回迭代器指向第一个不满足条件的元素
  • 对于链表，需配合iterator操作，避免随机访问
3. 性能优化
  • 在链表操作中，splice+partition组合比传统数组操作更高效
  • 利用链表的O(1)节点迁移特性，减少不必要的数据复制
总结

splice和partition是链表操作与序列分割的核心工具：

  • splice通过节点迁移实现链表的高效重组，是链表特有的性能优化手段
  • partition提供通用的序列分割能力，配合splice可实现链表上的高效分治算法（如快速排序）
  • 两者结合使用时，能在避免元素复制的同时完成复杂的数据处理任务，尤其适合对性能敏感的链表操作场景。

C++ std::list::splice 内部实现原理与示例

splice 是 C++ 标准库中 std::list 提供的核心操作，用于高效地在不同列表间转移元素。其核心优势是仅修改节点指针，无需复制或移动元素，时间复杂度为 O(1)。

一、splice 的功能与重载形式

std::list::splice 有三种重载形式：

// 1. 转移单个元素
void splice(const_iterator pos, list& other, const_iterator it);// 2. 转移另一个列表的全部元素
void splice(const_iterator pos, list& other);// 3. 转移另一个列表的元素范围 [first, last)
void splice(const_iterator pos, list& other, const_iterator first, const_iterator last);

参数说明：

  • pos：目标位置（将元素插入到该位置之前）
  • other：源列表
  • it/first/last：指定要转移的元素位置或范围

二、内部实现原理

std::list 是双向链表，每个节点包含前驱指针、后继指针和数据域。splice 的核心是调整这些指针的指向，步骤如下：

1. 转移单个元素
// 将other列表中it指向的元素转移到pos前
void list::splice(iterator pos, list& other, iterator it) {if (this == &other || pos == it) return;// 1. 从other中移除it节点it->prev->next = it->next;it->next->prev = it->prev;// 2. 将it插入到pos前it->prev = pos->prev;it->next = pos;pos->prev->next = it;pos->prev = it;
}
2. 转移元素范围
// 将other列表的[first, last)范围转移到pos前
void list::splice(iterator pos, list& other, iterator first, iterator last) {if (first == last || this == &other) return;// 1. 从other中移除[first, last)Node* first_node = first.node;Node* last_node = last.node;first_node->prev->next = last_node;last_node->prev = first_node->prev;// 2. 插入到pos前Node* pos_node = pos.node;first_node->prev = pos_node->prev;pos_node->prev->next = first_node;last_node->prev = pos_node;pos_node->prev = last_node;
}

三、关键特性与注意事项

  1. 高效性：

    • 仅修改指针，时间复杂度 O(1)
    • 不触发元素的构造、析构或赋值操作

  2. 所有权转移：

    • 元素从源列表移除，成为目标列表的一部分
    • 源列表的大小减少，目标列表的大小相应增加

  3. 迭代器有效性：

    • 转移后，元素在目标列表中的迭代器仍然有效
    • 源列表的迭代器、引用和指针仍指向元素，但可能不再属于源列表

  4. 自引用限制：

    • 不能将元素从一个列表转移到自身的不同位置（标准未定义行为）

四、简单示例：使用 splice 操作链表

#include <iostream>
#include <list>int main() {// 创建两个列表std::list<int> list1 = {1, 2, 3};std::list<int> list2 = {4, 5, 6};// 1. 转移单个元素：将list2的第一个元素移到list1开头list1.splice(list1.begin(), list2, list2.begin());// list1: {4, 1, 2, 3}// list2: {5, 6}// 2. 转移范围：将list2的全部元素移到list1末尾list1.splice(list1.end(), list2, list2.begin(), list2.end());// list1: {4, 1, 2, 3, 5, 6}// list2: {}// 3. 转移整个列表std::list<int> list3 = {7, 8, 9};list1.splice(list1.begin(), list3);// list1: {7, 8, 9, 4, 1, 2, 3, 5, 6}// list3: {}// 输出结果for (int num : list1) {std::cout << num << " ";}std::cout << std::endl;return 0;
}

五、典型应用场景

  1. 高效合并列表：

    list1.splice(list1.end(), list2);  // O(1)时间合并两个列表

  2. 元素位置调整：

    // 将元素从尾部移到头部
if (!my_list.empty()) {my_list.splice(my_list.begin(), my_list, --my_list.end());
}

  3. 实现优先队列：

    // 将元素按顺序插入到已排序的列表中
auto it = std::lower_bound(my_list.begin(), my_list.end(), value);
my_list.splice(it, another_list, another_list.begin());

六、总结

splice 是 std::list 最强大的特性之一，通过指针操作实现了元素的零拷贝转移。其核心优势在于：

  1. O(1) 时间复杂度：远优于复制或移动元素
  2. 内存高效：无需额外空间存储临时元素
  3. 迭代器稳定性：转移后迭代器仍然有效

在需要频繁调整元素顺序或合并列表的场景中，合理使用 splice 可以显著提升性能。

代码示例

使用向量实现快排
void quick_sort(std::vector<int>& vector, int left, int right)
{if (left < right){int pivot = vector[right];int i = left - 1;for (int j = left; j < right; j++){if (vector[j] <= pivot){i++;std::swap(vector[i], vector[j]);}}std::swap(vector[i + 1], vector[right]);int partitionIndex = i + 1;quick_sort(vector, left, partitionIndex - 1);quick_sort(vector, partitionIndex + 1, right);}
}

如果使用并发的会存在访问公共数据，不一定安全。

使用链表实现快排
#include<iostream>
#include<list>
#include<algorithm>// 问题分析：
// 1. std::partition 不能用于 std::list 的迭代器，因为它要求随机访问迭代器，而 std::list 只提供双向迭代器。
// 2. quick_sort 的拼接顺序有误，应该先拼接 lower，再拼接 pivot，再拼接 upper。
// 3. pivot 只应出现一次。// 修正后的 quick_sort 实现如下：
std::list<int> quick_sort(std::list<int> input)
{if (input.size() <= 1) return input;std::list<int> lower, equal, upper;int pivot = input.front();for (auto it = input.begin(); it != input.end(); ++it){if (*it < pivot)lower.push_back(*it);else if (*it == pivot)equal.push_back(*it);elseupper.push_back(*it);}lower = quick_sort(std::move(lower));upper = quick_sort(std::move(upper));// 拼接 lower + equal + upperlower.splice(lower.end(), equal);lower.splice(lower.end(), upper);return lower;
}int main()
{std::list<int> list{ 5, 2, 8, 3, 1, 6, 4, 7 };std::cout << "Original list: ";for (auto i : list) std::cout << i << " ";std::cout << std::endl;auto sorted_list = quick_sort(std::move(list));std::cout << "Sorted list: ";for (auto i : sorted_list) std::cout << i << " ";std::cout << std::endl;return 0;
}

替代方案

template<typename T>
std::list<T> quick_sort(std::list<T> input) {// 基准情况：空列表直接返回if (input.empty()) {return input;}std::list<T> result;// 1. 选择枢轴：取输入列表的第一个元素result.splice(result.begin(), input, input.begin());T const& pivot = *result.begin();// 2. 分割：将列表分为小于枢轴和不小于枢轴两部分auto divide_point = std::partition(input.begin(), input.end(),[&](T const& t) { return t < pivot; });// 3. 递归排序两部分std::list<T> lower_part;lower_part.splice(lower_part.end(), input, input.begin(), divide_point);auto new_lower = quick_sort(std::move(lower_part));auto new_higher = quick_sort(std::move(input));// 4. 合并结果：[左半部分 + 枢轴 + 右半部分]result.splice(result.end(), new_higher);result.splice(result.begin(), new_lower);return result;
}
基于future的链表快排
template<typename T>
std::list<T> parallel_quick_sort(std::list<T> input) {if (input.empty()) {return input;}std::list<T> result;result.splice(result.begin(), input, input.begin());T const& pivot = *result.begin();auto divide_point = std::partition(input.begin(), input.end(),[&](T const& t) { return t < pivot; });std::list<T> lower_part;lower_part.splice(lower_part.end(), input, input.begin(), divide_point);// 并行化关键：异步处理右半部分std::future<std::list<T>> new_higher_future = std::async(std::launch::async, parallel_quick_sort<T>, std::move(input));// 同步处理左半部分auto new_lower = parallel_quick_sort(std::move(lower_part));// 等待右半部分排序完成并合并结果auto new_higher = new_higher_future.get();result.splice(result.end(), new_higher);result.splice(result.begin(), new_lower);return result;
}
http://www.lryc.cn/news/579352.html

相关文章：

  • 如何有效的开展接口自动化测试?
  • Linux之Socket 编程 UDP
  • C++ 项目实践：如何用对象池优化内存管理、解决 MISRA 报警
  • 制作一款打飞机游戏76：分数显示
  • CentOS系统高效部署fastGPT全攻略
  • Android音视频探索之旅 | CMake基础语法 创建支持Ffmpeg的Android项目
  • 电脑CPU使用率占用100%怎么办 解决步骤指南
  • 按键精灵 安卓脚本开发：游戏实战之自动切换账号辅助工具
  • 需要scl来指定编译器的clangd+cmake在vscode/cursor开发环境下的配置
  • reactnative页面适配UI设计尺寸px转dp的完美解决方案px2dp
  • 9.Docker的容器数据卷使用（挂载）
  • CAD2018，矩形设计，新增文字，块新增与打散
  • snail-job的oracle sql（oracle 11g）
  • OFD|WPS|PDF 文档在线预览-高级功能
  • 前置代理重构网络访问的「中转站」
  • AI大模型的技术演进、流程重构、行业影响三个维度的系统性分析
  • 嵌入式系统中实现串口重定向
  • DMN方式的特点
  • 《P2572 [SCOI2010] 序列操作》
  • maker-pdf 文档文字识别，并用python实现
  • 专题：2025即时零售与各类人群消费行为洞察报告|附400+份报告PDF、原数据表汇总下载
  • 2025年6月：技术探索与生活平衡的协奏曲
  • 从零开始构建Airbyte数据管道：PostgreSQL到BigQuery实战指南
  • 基于定制开发开源AI智能名片与S2B2C商城小程序的搜索区用户需求洞察与精准服务研究
  • WebRTC 安全性分析研究
  • C# 线程同步（一）同步概念介绍
  • 网络安全的未来趋势与挑战
  • 好用的自带AI功能的国产IDE
  • Java-63 深入浅出 分布式服务 网络通信 RPC 与 RMI 详解
  • Spring 为何需要三级缓存解决循环依赖，而不是二级缓存