quicksort template

Discussion in 'C++' started by Andrew Koenig, Nov 3, 2004.

  1. "Lieven" <> wrote in message
    news:41882eec$0$1418$...

    > 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.
     
    Andrew Koenig, Nov 3, 2004
    #1
    1. Advertising

  2. "Andrew Koenig" <> wrote in message
    news:ViYhd.829348$...
    > "Lieven" <> wrote in message
    > news:41882eec$0$1418$...
    >
    >> 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
     
    John Harrison, Nov 3, 2004
    #2
    1. Advertising

  3. Andrew Koenig

    Lieven Guest

    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?
     
    Lieven, Nov 3, 2004
    #3
  4. Andrew Koenig

    Lieven Guest

    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?
     
    Lieven, Nov 4, 2004
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Sarah
    Replies:
    2
    Views:
    3,292
    Roedy Green
    Oct 23, 2003
  2. hiwa
    Replies:
    4
    Views:
    684
    Esmond Pitt
    Mar 29, 2005
  3. Exekute

    c++ and quicksort

    Exekute, Sep 27, 2003, in forum: C++
    Replies:
    6
    Views:
    9,082
    Jerry Coffin
    Sep 28, 2003
  4. David Sachs

    Re: c++ and quicksort

    David Sachs, Sep 28, 2003, in forum: C++
    Replies:
    1
    Views:
    486
    Gianni Mariani
    Sep 28, 2003
  5. Alex Vinokur
    Replies:
    0
    Views:
    996
    Alex Vinokur
    Aug 30, 2004
Loading...

Share This Page