chris wrote:

Lieven De Keyzer wrote: Is the STL sort() algorithm implemented genericly over all the

containers or once for each container? And in which file is it

implemented?

It's defined in <algorithm>. The file in which the actual implementation

lives is library specific, but it will be included by algorithm, and is

very frequently called stl_algo.h, in a directory called "bits" (you of

course can't assume that).

It is implemented generically over two random-access iterators. The

definition of a random access iterator can be looked up in the standard,

but in essence it generalises the idea of a pointer, so you can assume

you can do things like * to derefence, ++ and -- to go back and forth,

and add and subtract constants to go back and forth in larger steps,

assuming of course you don't leave the range [start,end], and you only

use * on either start or items between start and end (not end of course).

Any container whose iterators are random-access can therefore have

exactly the same sort algorithm applied to them.

Chris

The thing is, we have to parallelize an sort algorithm and meet the speedup

against the normal algorithm. I chose Quicksort. One of the requirements

for this, is that it is generic over STL containers. So I wrote my own

Quicksort template, working with random-access iterators but also with

bi-directional, for the list. What I want to know is: is there a way I can

also sort the associative containers with adjustments to my algorithm. Here

is the code:

//quicksort

template<typename ContainerIterator>

void quicksort(ContainerIterator begin, ContainerIterator end){

if (begin != end){

ContainerIterator newPivot(partition(begin, end));

quicksort(begin, newPivot);

quicksort(++newPivot, end);

}

}

//partition function

template<typename ContainerIterator>

ContainerIterator partition(ContainerIterator begin, ContainerIterator end){

typedef typename std::iterator_traits<ContainerIterator>::value_typ e

ValueType;

ValueType endValue(*((--end)++));

ContainerIterator front((--begin)++);

for(ContainerIterator it(begin); (it != (--end)++); it++)

if (*it <= endValue){

++front;

std::iter_swap(front, it);

}

std::iter_swap(++front,(--end)++);

return front;

}