C++ 线程模板向量快速排序

Question

线程快速排序方法：

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include "MD5.h"
#include <thread>
using namespace std;

template<typename T>
void quickSort(vector<T> &arr, int left, int right) {
    int i = left, j = right; //Make local copys to modify
    T tmp; //Termorary variable to use for swaping.
    T pivot = arr[(left + right) / 2]; //Find the centerpoint. if 0.5 truncate.

    while (i <= j) {
        while (arr[i] < pivot) //is i < pivot?
            i++;
        while (arr[j] > pivot) //Is j > pivot?
            j--;
        if (i <= j) {          //Swap
            tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            i++;
            j--;
        }
    };

    thread left_t; //Left thread
    thread right_t; //Right thread
    if (left < j)
        left_t = thread(quickSort<T>, ref(arr), left, j);

    if (i < right)
        right_t = thread(quickSort<T>, ref(arr), i, right);

    if (left < j)
        left_t.join();
    if (left < j)
        right_t.join();
}


int main()
{
    vector<int> table;
    for (int i = 0; i < 100; i++)
    {
        table.push_back(rand() % 100);
    }
    cout << "Before" << endl;
    for each(int val in table)
    {
        cout << val << endl;
    }
    quickSort(table, 0, 99);
    cout << "After" << endl;
    for each(int val in table)
    {
        cout << val << endl;
    }
    char temp = cin.get();
    return 0;
}

上面的程序像疯了一样滞后，垃圾邮件 "abort()" 已被调用。

我认为它与向量有关并且它有线程问题

我看过 Daniel Makardich 提出的问题，他使用 Vector int 而我的使用 Vector T

Answer 1

快速排序没有任何问题，但将模板化函数传递给线程没有问题。没有函数quickSort。您需要显式指定类型，以实例化函数模板：

#include <thread>
#include <iostream>

template<typename T>
void f(T a) { std::cout << a << '\n'; }

int main () {
    std::thread t;
    int a;
    std::string b("b");
    t = std::thread(f, a); // Won't work
    t = std::thread(f<int>, a);
    t.join();
    t = std::thread(f<decltype(b)>, b); // a bit fancier, more dynamic way
    t.join();
    return 0;
}

我怀疑你的情况应该这样做：

left_t = thread(quickSort<T>, ref(arr), left, j);

right_t 也类似。此外，您在尝试使用 operator()() 而不是构造对象时犯了错误。这就是错误不同的原因。

虽然无法验证，因为没有最小的可验证示例=/

我不知道是否可以让编译器对作为参数传递的 f 使用自动类型推导，如果有人知道这可能会使它成为更好的答案。

Answer 2

问题出在线程连接和@luk32 所说的

需要将线程转换为指向线程的指针。

thread* left_t = nullptr; //Left thread
thread* right_t = nullptr; //Right thread
if (left < j)
    left_t = new thread(quickSort<T>, ref(arr), left, j);

if (i < right)
    right_t = new thread(quickSort<T>, ref(arr), i, right);

if (left_t)
{
    left_t->join();
    delete left_t;
}
if (right_t)
{
    right_t->join();
    delete right_t;
}

好像你创建了一个默认构造的线程对象。但是不要使用它，它仍然要加入。如果你加入它，它会抱怨。

C++ 线程模板向量快速排序

C++ Threaded Template Vector Quicksort

multithreading

vector

quicksort