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;
}
