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 に答える