1

我写了归并排序算法，它工作得很好。然后我评论了函数的递归调用，并尝试使用一些 boost::threads，如下所示：

#include <iostream>
#include <vector>
#include <boost/thread.hpp>

void merge_sort(std::vector <int> & tab, size_t beg, size_t end)
{
    if(beg < end)
    {
        size_t pivot = (beg + end) >> 1;

        boost::thread left(merge_sort, tab, beg, pivot);
        //merge_sort(tab, beg, pivot);
        boost::thread right(merge_sort, tab, pivot + 1, end);
        //merge_sort(tab, pivot + 1, end);
        left.join();
        right.join();

        std::vector <int> buf (tab);
        size_t i = beg, j = pivot + 1, q = beg;
        while (i <= pivot && j <= end)
        {
            if (buf[i] < buf[j])
                tab[q++] = buf[i++];
            else
                tab[q++] = buf[j++];
        }
        while (i <= pivot)
            tab[q++] = buf[i++];
    }
}

int main()
{

    const int myints[] = {30,29,28,27,26,25,1,2,3,4,5,6,7,24,23,22,21,20,19,18,8,9,10,11,17,16,15,13,45,12};
    std::vector <int> kontener (myints, myints + sizeof(myints) / sizeof(int) );

    merge_sort(kontener, 0, kontener.size() - 1);

    for(std::vector <int>::iterator it = kontener.begin(); it != kontener.end(); it++)
        std::cout << *it << " ";
    std::cout << std::endl;

    std::cin.sync();
    std::cin.get();
    return(0);
}

但是我对这个线程有错误的输出。:P 因此，如果有人能告诉我这段代码有什么问题，我将不胜感激。

4

1 回答 1

2

您实际上并没有将向量作为参考传递给子线程，即使看起来如此。您需要使用boost::ref或std::ref。另请注意，缓冲区只需与您当前正在处理的部分一样大，一直复制整个向量是没有意义的：

    boost::thread left(merge_sort, boost::ref(tab), beg, pivot);
    boost::thread right(merge_sort, boost::ref(tab), pivot + 1, end);
    left.join();
    right.join();

    std::vector <int> buf (tab.begin()+beg, tab.begin()+end+1);
    size_t i = beg, j = pivot + 1, q = beg;
    while (i <= pivot && j <= end)
    {
        if (buf[i-beg] < buf[j-beg])
            tab[q++] = buf[i++ - beg];
        else
            tab[q++] = buf[j++ - beg];
    }
    while (i <= pivot)
        tab[q++] = buf[i++ - beg];

（另请注意，如果您使用迭代器和标准算法，这段代码可能会更简洁一些，但为了简单起见，我保留了您的结构。）

于 2013-03-26T12:37:51.030 回答