基于多线程实现链表快排

链表的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;

三、对比与应用场景

四、注意事项

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);
        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;
}