Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > quicksort template

Reply
Thread Tools

quicksort template

 
 
Andrew Koenig
Guest
Posts: n/a
 
      11-03-2004
"Lieven" <(E-Mail Removed)> wrote in message
news:41882eec$0$1418$(E-Mail Removed)...

> pivotValue(*pivot);
> }
>
>
> Problem is I don't know the type of this value at this stage.
> Should I include it in the templateparameters?


No need. If T is an iterator type, then std::iterator_traits<T>::value_type
is the type that is obtained by dereferencing T.


 
Reply With Quote
 
 
 
 
John Harrison
Guest
Posts: n/a
 
      11-03-2004

"Andrew Koenig" <(E-Mail Removed)> wrote in message
news:ViYhd.829348$(E-Mail Removed)...
> "Lieven" <(E-Mail Removed)> wrote in message
> news:41882eec$0$1418$(E-Mail Removed)...
>
>> pivotValue(*pivot);
>> }
>>
>>
>> Problem is I don't know the type of this value at this stage.
>> Should I include it in the templateparameters?

>
> No need. If T is an iterator type, then
> std::iterator_traits<T>::value_type is the type that is obtained by
> dereferencing T.
>


And 'iterator type' includes pointers.

john


 
Reply With Quote
 
 
 
 
Lieven
Guest
Posts: n/a
 
      11-03-2004
I want to write a generic quicksort over STL containers. We have to
parallelize this algorithm afterwards. This is what I've got for now:


template<typename containerIterator>
void quicksort(containerIterator begin, containerIterator end){

┬*┬*┬*┬*┬*┬*┬*┬*if┬*(end┬*>┬*begin){
┬*┬*┬*┬*┬*┬*┬*┬*┬*┬*┬*┬*┬*┬*┬*┬*containerIterator┬*pivot(begin);
┬*┬*┬*┬*┬*┬*┬*┬*┬*┬*┬*┬*┬*┬*┬*┬*containerIterator┬*newPivot(partition(begin,┬*end,┬*pivot));
┬*┬*┬*┬*┬*┬*┬*┬*┬*┬*┬*┬*┬*┬*┬*┬*quicksort(begin,┬*--newPivot);
┬*┬*┬*┬*┬*┬*┬*┬*┬*┬*┬*┬*┬*┬*┬*┬*quicksort(++newPivot,┬*end);
┬*┬*┬*┬*┬*┬*┬*┬*}
}


template<typename containerIterator>
containerIterator partition(containerIterator begin, containerIterator end,
containerIterator pivot){

┬*┬*┬*┬*┬*┬*┬*┬*//what┬*I┬*want┬*here┬*is┬*to┬*store┬*the┬*value┬*of┬*the┬*pivot,
┬*┬*┬*┬*┬*┬*┬*┬*//so┬*something┬*like:┬*
┬*┬*┬*┬*┬*┬*┬*┬*pivotValue(*pivot);
}


Problem is I don't know the type of this value at this stage.
Should I include it in the templateparameters?
 
Reply With Quote
 
Lieven
Guest
Posts: n/a
 
      11-04-2004
Lieven wrote:

> I want to write a generic quicksort over STL containers. We have to
> parallelize this algorithm afterwards. This is what I've got for now:
>
>
> template<typename containerIterator>
> void quicksort(containerIterator begin, containerIterator end){
>
> if┬*(end┬*>┬*begin){


> containerIterator┬*pivot(begin);
> containerIterator┬*newPivot(partition(begin,┬*end,┬*pivot));


/*I realize I made a mistake here. When I do --newPivot, this is a
destructive operation. The iterator now points to the element in front of
the pivotelement. So the ++newPivot afterwards just points to the
pivotelement again.*/

> quicksort(begin,┬*--newPivot);
> quicksort(++newPivot,┬*end);
> }
> }
>
>
> template<typename containerIterator>
> containerIterator partition(containerIterator begin, containerIterator
> end, containerIterator pivot){
>
> //what┬*I┬*want┬*here┬*is┬*to┬*store┬*the┬*value┬*of┬*the┬*pivot,
> //so┬*something┬*like:
> pivotValue(*pivot);
> }
>
>
> Problem is I don't know the type of this value at this stage.
> Should I include it in the templateparameters?


What is the best way to solve this? something like using --newPivot++ in the
first expression? Or is there another way?
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Gosling's quicksort freezes hiwa Java 4 03-29-2005 08:59 AM
Bentley-Sedgewick ternary QuickSort: C++/C implementation? Alex Vinokur C++ 0 08-30-2004 05:45 AM
Tabelle mit quicksort alphabetisch sortieren Sarah Java 2 10-23-2003 08:18 PM
c++ and quicksort Exekute C++ 6 09-28-2003 09:28 AM
Re: c++ and quicksort David Sachs C++ 1 09-28-2003 02:13 AM



Advertisments