multithreaded mergesort

Question

mergesort 알고리즘을 작성했는데 정상적으로 작동합니다. 그리고 난 함수의 재귀 호출 댓글을 달았습니다,이 같은 일부 부스트 : : 스레드를 사용하는 것을 시도했다 :

#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 누군가가이 코드에 어떤 문제가 있는지 말해 줄 수 있다면 고맙겠습니다.

Answer 1

실제로 보일지도 모르지만 참조로 서브 벡터에 실제로 벡터를 전달하지는 않습니다. 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]; 

(또한주의이 코드가 잘 될 수 있다는 : 또한 버퍼는 현재 작업중인 부분만큼 큰이어야주의, 전체 벡터 모든 시간을 복사 아무 문제가 없다 iterator와 표준 알고리즘을 사용했다면 좀 더 깨끗한 것이지만, 단순화를 위해, 나는 구조를 유지했다.)