Is the STL sort() algorithm implemented genericly over all the
containers or once for each container? And in which file is it implemented?
containers or once for each container? And in which file is it implemented?
-
-
Re: STL Sort
Li even De Keyzer wrote:[color=blue]
> Is the STL sort() algorithm implemented genericly over all the
> containers or once for each container? And in which file is it implemented?[/color]
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
-
Re: STL Sort
Lieven De Keyzer wrote:[color=blue]
> Is the STL sort() algorithm implemented genericly over all the
> containers or once for each container? And in which file is it implemented?[/color]
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
Comment
-
Re: STL Sort
Lieven De Keyzer wrote:[color=blue]
>
> Is the STL sort() algorithm implemented genericly over all the
> containers or once for each container? And in which file is it implemented?[/color]
AFAIK it is a generic sort algorithm with the exception of std::list. std::list
has its own sort implemented.
#include <algorithm>
--
Karl Heinz Buchegger
kbuchegg@gascad .at
Comment
-
Re: STL Sort
chris wrote:
[color=blue]
> Lieven De Keyzer wrote:[color=green]
>> Is the STL sort() algorithm implemented genericly over all the
>> containers or once for each container? And in which file is it
>> implemented?[/color]
>
> 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[/color]
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<typena me ContainerIterat or>
void quicksort(Conta inerIterator begin, ContainerIterat or end){
if (begin != end){
ContainerIterat or newPivot(partit ion(begin, end));
quicksort(begin , newPivot);
quicksort(++new Pivot, end);
}
}
//partition function
template<typena me ContainerIterat or>
ContainerIterat or partition(Conta inerIterator begin, ContainerIterat or end){
typedef typename std::iterator_t raits<Container Iterator>::valu e_type
ValueType;
ValueType endValue(*((--end)++));
ContainerIterat or front((--begin)++);
for(ContainerIt erator it(begin); (it != (--end)++); it++)
if (*it <= endValue){
++front;
std::iter_swap( front, it);
}
std::iter_swap( ++front,(--end)++);
return front;
}
Comment
-
Re: STL Sort
[color=blue]
>
> The thing is, we have to parallelize an sort algorithm and meet the[/color]
speedup[color=blue]
> 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.[/color]
Here[color=blue]
> is the code:
>[/color]
Associative containers are already sorted, you cannot change the order.
john
Comment
Comment