By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,214 Members | 1,195 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 446,214 IT Pros & Developers. It's quick & easy.

Quicksort - compare function object

P: n/a
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){
....
}
Jul 22 '05 #1
Share this Question
Share on Google+
3 Replies


P: n/a
Lieven <li*************@hotmail.com> wrote in
news:41***********************@news.skynet.be:
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.....
Jul 22 '05 #2

P: n/a
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.
Jul 22 '05 #3

P: n/a
Lieven wrote in news:41***********************@news.skynet.be in
comp.lang.c++:
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.


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.
--
http://www.victim-prime.dsl.pipex.com/
Jul 22 '05 #4

This discussion thread is closed

Replies have been disabled for this discussion.