链表的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. 核心逻辑
- 操作过程:
- 遍历[first, last)区间
- 将满足谓词p的元素移到区间前部
- 返回第一个不满足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;
}
三、关键特性与注意事项
高效性:
- 仅修改指针,时间复杂度 O(1)
- 不触发元素的构造、析构或赋值操作
所有权转移:
- 元素从源列表移除,成为目标列表的一部分
- 源列表的大小减少,目标列表的大小相应增加
迭代器有效性:
- 转移后,元素在目标列表中的迭代器仍然有效
- 源列表的迭代器、引用和指针仍指向元素,但可能不再属于源列表
自引用限制:
- 不能将元素从一个列表转移到自身的不同位置(标准未定义行为)
四、简单示例:使用 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;
}
五、典型应用场景
高效合并列表:
list1.splice(list1.end(), list2); // O(1)时间合并两个列表
元素位置调整:
// 将元素从尾部移到头部 if (!my_list.empty()) { my_list.splice(my_list.begin(), my_list, --my_list.end()); }
实现优先队列:
// 将元素按顺序插入到已排序的列表中 auto it = std::lower_bound(my_list.begin(), my_list.end(), value); my_list.splice(it, another_list, another_list.begin());
六、总结
splice
是 std::list
最强大的特性之一,通过指针操作实现了元素的零拷贝转移。其核心优势在于:
- O(1) 时间复杂度:远优于复制或移动元素
- 内存高效:无需额外空间存储临时元素
- 迭代器稳定性:转移后迭代器仍然有效
在需要频繁调整元素顺序或合并列表的场景中,合理使用 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);
else
upper.push_back(*it);
}
lower = quick_sort(std::move(lower));
upper = quick_sort(std::move(upper));
// 拼接 lower + equal + upper
lower.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;
}