469,903 Members | 1,580 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 469,903 developers. It's quick & easy.

STL Sort

Is the STL sort() algorithm implemented genericly over all the
containers or once for each container? And in which file is it implemented?
Jul 22 '05 #1
5 6958
Li even 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 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
Jul 22 '05 #2
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
Jul 22 '05 #3
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?


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
kb******@gascad.at
Jul 22 '05 #4
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;
}

Jul 22 '05 #5

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
Jul 22 '05 #6

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

2 posts views Thread by Thomas Philips | last post: by
1 post views Thread by Kamilche | last post: by
4 posts views Thread by its me | last post: by
40 posts views Thread by Elijah Bailey | last post: by
7 posts views Thread by Stuart | last post: by
7 posts views Thread by DC Gringo | last post: by
48 posts views Thread by Alex Chudnovsky | last post: by
1 post views Thread by Waqarahmed | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.