Hi,

I have a std::vector of std:: pair<int, int> elements. How can I create a predicate function for the stl partition algorithm in this vector, using the "first" value in the pair to compare, and passing as a parameter the pivot value.

I want elements greater than the pivot value to be on left side, and elements less than or equal to the pivot value to be the right. The pivot value might not actually be in the vector.

I'd appreciate your help in this.

thanks

If you had a boolean function whose return value depends on whether the first element of a pair is less than or equal to a particular number, it would be easy, right? (I changed the problem statement a little.)


Now, however you need a predicate with two arguments.

Well the function is easy enough:

But the predicate for std::partition must be a pointer to a function that takes one argument (a pair<int,int> in this case), and there is no way to send a second argument.

Or is there???

Well, yes. Yes there is...

There is an "adapter" function named bind2nd() that takes a pointer to a function with two parameters, and binds the second argument of the function being pointed to with the argument that you give to bind2nd. In other words, it wraps a single-argument function around a two-argument function. I am always amazed when I run across little things like this in C++. I mean, my flabber is gasted. Totally.

Here's how you can use it:


This calls the function firstLEn, with its second argument equal to pivot

The pointer has to be cast to a ptr_fun type since bind2nd is a template function and you have to tell the compiler that you are feeding it a pointer to a function---rather than, say an operator---so that the proper function can be generated.

Regards,

Dave

This seems to be a quick sort algorithm.

The topic of the thread is an illustration of a way to use the std::partition algorithm in a way that some textbooks and other reference materials (apparently) don't exactly spell out.

The std::partition function used this way might be helpful if you wanted to show how to implement a quicksort algorithm or other function that uses partitioning based on size of elements relative to some variable. This might be for teaching purposes or for any other reason that you didn't want to use the std::sort algorithm.

In fact, there are many problems other than sorting that need some kind of partitioning. The std::partition algorithm is one of those things in the C++ STL toolbox that doesn't mean much to beginners (and not-so-beginners also) unless you get to the point where you need it.

Regards,

Dave

Thanks for your explanation.