2

I have a vector of unsigned variables of the type:

vector<unsigned> a;
a.push_back(5); a.push_back(3); a.push_back(2); a.push_back(1);
a.push_back(12); a.push_back(4); a.push_back(20); a.push_back(11);
a.push_back(13); a.push_back(7); a.push_back(23); a.push_back(21);

Now I want to create 3 threads such that each thread sorts 4 values in the vector. E.g. 

Thread 1: a[0],a[1],a[2],a[3]. After sorting their values become: 1,2,3,5
Thread 2: a[4],a[5],a[6],a[7]. After sorting their values become: 4,11,12,20
Thread 3: a[8],a[9],a[10],a[11]. After sorting their values become: 7,13,21,23

After all the threads have finished sorting, I intend to notify that the values are now sorted. Is it possible to do the same in c++ using pthread if yes then how. I am using gcc 4.4. I know it is possible to do the same sequentially but I am curious to know if it is possible to sort these threads in a multi-threaded way?

EDIT: I can not use std::async as I am working with gcc version 4.4. and I am trying to include this logic in an old code which has been coded before c++11. Therefore, I can not use c++11.

Jannat Arora
  • 2,759
  • 8
  • 44
  • 70
  • The regions provided to the threads are overlapping, is that intentional? – Arun Apr 21 '15 at 23:26
  • You are asking an XY problem. See http://meta.stackexchange.com/questions/66377/what-is-the-xy-problem When you have figured out what question you're really trying to ask, be sure to edit your question, and update it. – Sam Varshavchik Apr 21 '15 at 23:26
  • @Arun Thanks for your comment. The regions provided to the threads will be non overlapping e.g. a[0],a[1],a[2],a[3] belong to the first thread and their sorted order is 1,2,3,5. Similarly a[4],a[5],a[6],a[7] belong to the second thread and their sorted order is 4,11,12,20. So the regions are non-overlapping – Jannat Arora Apr 21 '15 at 23:30

1 Answers1

1

The sorting algorithm, std::sort, work on iterators. It takes two iterators, say begin and end, and sort the elements in the half open range [begin, end).

So, we can try this for problem decomposition.

thread 0: sort(a, a+4);
thread 1: sort(a+4, a+8);
thread 2: sort(a+8, a+12);

Now, regarding work allocation to threads and waiting for their completion, we can try std::async. If C++11 is not an option (as mentioned in the comment), then you can create a thread pool solution, see for example How to create a thread pool using boost in C++?

Community
  • 1
  • 1
Arun
  • 19,750
  • 10
  • 51
  • 60
  • Thanks I can not use async as I have gcc version 4.4. Can you please suggest some workaround which may work with versions lesser than c++11. As I can not use C++11. – Jannat Arora Apr 21 '15 at 23:41
  • Ok. Thank you but I am not able to understand how are they notifying that all the threads have finished operation. Also the code is giving me the error: ‘threadpool’ does not name a type – Jannat Arora Apr 21 '15 at 23:52