c++ - Parallelized quicksort in C++11 randomly crashes -


i writing quicksort in c++ , works fine, when try make use multiple threads (with c++11 threading) randomly crashes. says "terminate called without active exception" or "pure virtual method called" or crashes without error message. more threads use more crashes.

could tell me did wrong? using mingw x64-4.8.1-release-posix-seh-rev5 -ofast optimization flag.

template<class t> t partition(t begin, t end, t pivot){     t result_pivot;     std::swap(*pivot, *(end - 1)); /* puts pivot end */     pivot = end - 1;     t it_right = end - 1;     /* starts searching item left bigger pivot */     for(t it_left = begin; it_left < it_right; ++it_left){          if(*pivot <= *it_left){             while(*(--it_right) > *pivot && it_right != it_left)                  /* empty - searches item smallar pivot right */ ;             if(it_right != it_left){ /* if such item found , pointers not meet swap them */                 std::swap(*it_right, *it_left);             }             else break; /* if pointers meet, stop */         }     }     /* puts pivot , returns pivot */     std::swap(*pivot, *it_right);     return it_right; }  struct running_threads {     int max_threads = 8;//std::thread::hardware_concurrency();     std::mutex mutex;     int num_of_threads = 1;     void operator++(){          mutex.lock();         ++num_of_threads;         mutex.unlock();     }     void operator--(){          mutex.lock();         --num_of_threads;         mutex.unlock();     } } thr;  template<class t> void swap_quick_sort(t begin, t end){     size_t size = end - begin;     /* stopping criteria */     if(size <= 3){         if(size == 3)             order3(begin[0], begin[1], begin[2]);         else if(size == 2 && begin[0] > begin[1])             std::swap(begin[0], begin[1]);         return;     }     /* pivot median of first, middle , last item */     t pivot = median(begin, begin + size/2, begin + size - 1);      t result_pivot = partition(begin, end, pivot);     /* since creating/joining threads slow,         create new thread when array big enough */     if(size > 30000 && thr.num_of_threads < thr.max_threads){         std::thread a(swap_quick_sort<t>, begin, result_pivot);         ++thr;         swap_quick_sort(result_pivot + 1, end);         a.join();         --thr;     }     else {         swap_quick_sort(begin, result_pivot);         swap_quick_sort(result_pivot + 1, end);     } }  template<class t> void order3(t& a, t& b, t& c){     if (a <= b && <= c){         if (b > c)             std::swap(c, b);     }     else if(b <= && b <= c)          if (a <= c)                          std::swap(a, b);         else {                          std::swap(a, b);             std::swap(b, c);         }     else                                    if (a <= b){                std::swap(a, c);             std::swap(b, c);          }         else                                     std::swap(a, c);  }  template<class t> t median(t a, t b, t c){     if (*a <= *b && *a <= *c){         if (*b <= *c)             return b;         else             return c;     }     else if(*b <= *a && *b <= *c){         if (*a <= *c)                          return a;         else             return c;     }     else if(*a <= *b)                           return a;         else             return b; } 

in main function call vector of random elements.


Comments

Popular posts from this blog

java.util.scanner - How to read and add only numbers to array from a text file -

rewrite - Trouble with Wordpress multiple custom querystrings -