how to use list in parallel_sort

[reeba]

can anyone tell me how to sort a list using parallel_sort???
Thanks in advance

[robert-reed]

The simple answer is: you can't get there from here.

The documentation for parallel_sort makes it clear: it has the same requirements for the sequences it sorts as std::sort, namely, the iterator by which you access the sequence must be at least a random access iterator, which is not usuallytrue of iterators attachable to lists. In particular, the algorithm underlying both std::sort and tbb::parallel_sort is based on Hoare's Quicksort algorithm, which needs to be able to partition subsequences and exchange elements of the sequence.

[nagy]

From the reference document.

The requirementson the iterator and sequence are the same as for std::sort. Specifically,

RandomAccessIterator must be a random access iterator, ...

Which I believebasicallymeans that the container must have a random access iterator, which is not the case for std::list. The only solution I can think of is to copy the entire list into an std::vector, sort it and then copy it back, which could be very inefficient. I think your better of either using std::vector from the beginning or using the std::list::sort function.

EDIT: Updated accordingly to the next post

[ARCH_R_Intel]

Even for sequential code, it might actually be faster to copy to a std::vector, apply std::sort, and copy back to the list. Vectors are much friendly to caches than lists, and a cache miss is on the order of at least a hundred clock cycles. I tried a quick experiment with list of length 100,0000 and 1,000,000 on Linux with gcc 4.3.2. The sequence, where the input x is a std::list:

    {
        vector tmp( x.begin(), x.end() );
        sort(tmp.begin(),tmp.end());
        x.assign(tmp.begin(),tmp.end());
    }

was about twices as fast as x.sort().

Of course if the list is short or there is a large overhead for copying list items, then the results will not be as good. But perhapssorting avector of pointers to the items might work well (I did not try this).

[reeba]

thanks for all the replies :)