STL Sort

[Lieven De Keyzer]

Is the STL sort() algorithm implemented genericly over all the
containers or once for each container? And in which file is it implemented?

 

[Victor Bazarov]

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 implemented generically for the containers with random access
iterators (C++ arrays fall under that category). std::list has its
own sort (since its iterators aren't random-access).

It's declared in <algorithm>.

V

 

[chris]

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

 

[Karl Heinz Buchegger]

Is the STL sort() algorithm implemented genericly over all the
containers or once for each container? And in which file is it implemented?

AFAIK it is a generic sort algorithm with the exception of std::list. std::list
has its own sort implemented.

#include <algorithm>

 

[Lieven]

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

 

[John Harrison]

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:

Associative containers are already sorted, you cannot change the order.

john