multithreaded mergesort

Question

Я написал алгоритм слияния, и он отлично работает. Тогда я прокомментировал рекурсивные вызовы функции, и пытался использовать некоторые подталкивании :: тему так:

#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]; 

(Также обратите внимание, что этот код может также быть бит, если вы использовали итераторы и стандартные алгоритмы, но для простоты я сохранил вашу структуру.)