Quicksort - compare function object

[Lieven]

I want to make a quicksort algorithm that can take both a vector and a list.
This is the code I've got. But I also want to give an argument that will be
used for comparing the elements. I am used to programming in Lisp/Scheme,
where I would just pass a lambda. Is a function object something like that
in C++? And in that case, how would I pass the function/operator < (lesser
then).

//quicksort
template<typename BidirectionalIterator>
void quicksort(BidirectionalIterator& begin, BidirectionalIterator& end){
....
}


//partition function
template<typename BidirectionalIterator>
BidirectionalIterator partition(BidirectionalIterator& begin,
BidirectionalIterator& end){
....
}

 

[Andre Kostur]

I want to make a quicksort algorithm that can take both a vector and a
list. This is the code I've got. But I also want to give an argument
that will be used for comparing the elements. I am used to programming
in Lisp/Scheme, where I would just pass a lambda. Is a function object
something like that in C++? And in that case, how would I pass the
function/operator < (lesser then).

Umm.. any particular reason why you want to make your own quicksort vs.
using std::sort ?

And note that std::sort has two signatures... one which takes two
RandomAccessInterators, and one which takes those iterators and a
BinaryPredicate.....

 

[Lieven]

Andre Kostur wrote:
 

Umm.. any particular reason why you want to make your own quicksort vs.
using std::sort ?

Yes, an excercise for school where we have to parallelize an algorithm. One
of the requirements if you have chosen a sort is that it is generic over
STL.

And note that std::sort has two signatures... one which takes two
RandomAccessInterators, and one which takes those iterators and a
BinaryPredicate.....

My algorithm works for vectors and lists, by using BidirectionalIterators.
But I wanted to know what is the best way to pass this predicate.

 

[Rob Williscroft]

Lieven wrote in in
comp.lang.c++:

Andre Kostur wrote:
 

Yes, an excercise for school where we have to parallelize an
algorithm. One of the requirements if you have chosen a sort is that
it is generic over STL.


My algorithm works for vectors and lists, by using
BidirectionalIterators. But I wanted to know what is the best way to
pass this predicate.

By (generic) value:

template< typename Bi, typename Comp >
void quicksort( Bi begin, Bi end, Comp comp )
{
// symantics: (bool)comp( *iter1, *iter2 ); with: Bi iter1, iter2;
}

Note that the iterators are also passed by value.

Example "Comp" aruguments for int:

std::less< int >(); // #include <functional>

bool f( int a, int b ) { return a < b; }

struct comp
{
typedef bool return_type;
bool operator( int a, int b ) const
{
return a < b;
}
};


int main()
{
std::vector< int > vi;
quicksort( vi.begin(), vi.end(), std::less< int >() );
quicksort( vi.begin(), vi.end(), f );
quicksort( vi.begin(), vi.end(), comp() );
}

Rob.