C++ 11 Multithread Merge Sort

Question

I am new in C++11 and I was trying to write an simple program using thread in C++11. I went for merge sort, and the following is my code:

#include <iostream>
#include <thread>
#include <vector>
using namespace std;

void merge(vector<int>& vec, int start, int mid, int end)
{
    vector<int> one (vec.begin() + start, vec.begin() + mid + 1);
    vector<int> two (vec.begin() + mid + 1, vec.begin() + end + 1);

    int a = 0;
    int b = 0;
    int index = start;
    while (a < one.size() && b < two.size())
    {
        if (one[a] < two[b])
            vec[index ++] = one[a ++];
        else 
            vec[index ++] = two[b ++];
    }

    // merge the left-over elements
    while (a < one.size())
        vec[index ++] = one[a ++];
    while (b < two.size())
        vec[index ++] = two[b ++];
}

void merge_sort(vector<int>& vec, int start, int end)
{
if (start >= end)
    return;

int mid = start + (end - start) / 2;

// multi-thread version
thread first(merge_sort, vec, start, mid);
thread second(merge_sort, vec, mid + 1, end);
first.join();
second.join();

/*
// single-thread version, testified.
merge_sort(vec, start, mid);
merge_sort(vec, mid + 1, end); 
*/

merge(vec, start, mid, end);
}


int main()
{
    int a[] = {4, 2, 5, 9, 7, 1, 3};
    vector<int> vec(a, a + 7);
    merge_sort(vec, 0, 6);
    for (int i = 0; i < 7; i ++)
        cout << vec[i] << endl;
    return 0;
}

The underlying algorithm is really simple: after an array is split into two subarrays, two threads were created to take care of the subarrays, one thread for one subarray. After joining the two threads, the two subarray are merged. When I tried to compiles it with clang++ 5.1 on MacOS 10.9.4, the following error came out:

Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../lib/c++/v1/thread:332:5:
error: attempt to use a deleted function
__invoke(_VSTD::move(_VSTD::get<0>(__t)), _VSTD::move(_VSTD::get<_Indices>(__t))...);

Then I went online and found a similar program that uses pthread, instead of C++11 thread, with almost the same underlying logic. I compiled and ran the program, and it worked. It looks like this:

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <iostream>
using namespace std;

#define N 2  /* # of thread */

int a[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};  /* target array */

/* structure for array index
 * used to keep low/high end of sub arrays
 */
typedef struct Arr {
    int low;
    int high;
} ArrayIndex;

void merge(int low, int high)
{
        int mid = (low+high)/2;
        int left = low;
        int right = mid+1;

        int b[high-low+1];
        int i, cur = 0;

        while(left <= mid && right <= high) {
                if (a[left] > a[right])
                        b[cur++] = a[right++];
                else
                        b[cur++] = a[right++];
        }

        while(left <= mid) b[cur++] = a[left++];
        while(right <= high) b[cur++] = a[left++];
        for (i = 0; i < (high-low+1) ; i++) a[low+i] = b[i];
}

void * mergesort(void *a)
{
        ArrayIndex *pa = (ArrayIndex *)a;
        int mid = (pa->low + pa->high)/2;

        ArrayIndex aIndex[N];
        pthread_t thread[N];

        aIndex[0].low = pa->low;
        aIndex[0].high = mid;

        aIndex[1].low = mid+1;
        aIndex[1].high = pa->high;

        if (pa->low >= pa->high) return 0;

        int i;
        for(i = 0; i < N; i++) pthread_create(&thread[i], NULL, mergesort, &aIndex[i]);
        for(i = 0; i < N; i++) pthread_join(thread[i], NULL);

        merge(pa->low, pa->high);

        //pthread_exit(NULL);
        return 0;
}

int main()
{
        ArrayIndex ai;
        ai.low = 0;
        ai.high = sizeof(a)/sizeof(a[0])-1;
        pthread_t thread;

        pthread_create(&thread, NULL, mergesort, &ai);
        pthread_join(thread, NULL);

        int i;
        for (i = 0; i < 10; i++) printf ("%d ", a[i]);
        cout << endl;

        return 0;
}

Does anybody know what was wrong with my program?

Answer 1

For better or worse, std::bind, std::async, and the std::thread constructor copy their arguments into separate storage to decouple their lifetime from the current scope. If you really want to pass a reference, you need to wrap it in a reference_wrapper with std::ref (or std::cref for a const reference):

thread first(merge_sort, std::ref(vec), start, mid);
thread second(merge_sort, std::ref(vec), mid + 1, end);