making min heap

hi!
to make a minheap out of a vector "cont" the function is make_heap(cont.begin(),cont.end(),greater<int>)

now this works if the contents of the vector "cont" are single integers what do we do if it is a pair of int ie: cont<pair<int,int> >

what change do I make to function operator greater<int>.

thanks a lot.

You would need to create an operator> for pair<int, int>. A better solution would probably be to write an comparison function or object that does the same thing and specifying it instead of greater<int> (or rather greater<pair<int, int> >).

Make a struct with the following function:

Code:

---

bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) const

---

Then just implement that to return the ordering you want for your pair. Give the struct a name appropriate to the comparing you are doing (e.g. IntPairGreaterThan). Then pass that to the make_heap function as the third parameter.

Thanx a lot man that was really useful.
Could you give me some reference from where I could learn about function objects?

Regards!
Eklavya

There is very little to learn about function objects. :) They are basically a struct (or class) with an overloaded operator() and may optionally have member variables to store state.

Const correctness is important and to work with all std algorithms they need certain typedefs,which your function object gains if you inherit them from std::unary_function or std::binary_function (the references tell you which algorithms requires which predicates).

For example, a function object to compare two pair<int, int>'s might look like this:

Code:

---

struct less_pair:
    public std::binary_function<std::pair<int, int>, std::pair<int, int>, bool>
//template arguments for binary_function are: left argument type, right argument type, return type
{
    bool operator() (const std::pair<int, int>& lhv, const std::pair<int, int>& rhv) const
    {
        return lhv.first < rhv.first || lhv.first == rhv.first && lhv.second < rhv.second;
    }
};

//usage
    std::vector<std::pair<int, int> > vec;
    //...
    std::sort(vec.begin(), vec.end(), less_pair());

---

It might also be useful to familiarize yourself with the function objects that <functional> provides (they may save you the trouble of writing your own function objects in simpler cases).

Another quite cool thing that may save you from having to write a separate functor - especially if you're just going to use it once - and may sometimes be the most readable option as well is the lambda header in boost.
In this particular case (since we need to access members of pair a lot), it is probably not that helpful though :)

Code:

---

    std::sort(vec.begin(), vec.end(),
        bind(&std::pair<int, int>::first, _1) < bind(&std::pair<int, int>::first, _2)
        || bind(&std::pair<int, int>::first, _1) == bind(&std::pair<int, int>::first, _2)
        && bind(&std::pair<int, int>::second, _1) < bind(&std::pair<int, int>::second, _2)
    );

---

>> Could you give me some reference from where I could learn about function objects?
The C++ Standard Library by Josuttis is my reference for that stuff (and occasionally other books like The C++ Programming Language by Stroustrup and Effective STL by Meyers).

std::pair already has a less-than operator. If you want to define a greater-than comparison function, then I'd suggest simply calling the operator less-than operator of the pair with the arguments reversed. It'll probably be more efficient, and will certainly be less likely to have a bug.

Are you sure that's standard? I see dinkumware (meaning VC++) has it. In fact it has operator> already, so the original code would work with one minor change:

Code:

---

make_heap(cont.begin(),cont.end(),greater<pair<int, int> >);

---

I just don't know if that's in the standard or just a VC++ extension.

Wow! Good to know.

This discussion still applies if you want to compare pairs in any other ways (only first or only second, etc).

Quote:

---

Originally Posted by anon

an overloaded operator() and may optionally have member variables to store state.

---

You should be careful with this though, because if the function object is intended to be used as a predicate to be passed to an STL function, it must be a stateless object.
See Chapter 87. Make predicates pure functions for an explaination of why.

Right.

They may quite safely store unchanged data though, such as for example std::binder1st and std::binder2nd.

Stuffing too much data in them might not be wise for performance reasons as it may be copied a lot?

And then, not all function objects are predicates...

Quote:

---

Originally Posted by anon

There is very little to learn about function objects. :) They are basically a struct (or class) with an overloaded operator() and may optionally have member variables to store state.

Const correctness is important and to work with all std algorithms they need certain typedefs,which your function object gains if you inherit them from std::unary_function or std::binary_function (the references tell you which algorithms requires which predicates).

For example, a function object to compare two pair<int, int>'s might look like this:

Code:

---

struct less_pair:
    public std::binary_function<std::pair<int, int>, std::pair<int, int>, bool>
//template arguments for binary_function are: left argument type, right argument type, return type
{
    bool operator() (const std::pair<int, int>& lhv, const std::pair<int, int>& rhv) const
    {
        return lhv.first < rhv.first || lhv.first == rhv.first && lhv.second < rhv.second;
    }
};

//usage
    std::vector<std::pair<int, int> > vec;
    //...
    std::sort(vec.begin(), vec.end(), less_pair());

---

It might also be useful to familiarize yourself with the function objects that <functional> provides (they may save you the trouble of writing your own function objects in simpler cases).

Another quite cool thing that may save you from having to write a separate functor - especially if you're just going to use it once - and may sometimes be the most readable option as well is the lambda header in boost.
In this particular case (since we need to access members of pair a lot), it is probably not that helpful though :)

Code:

---

    std::sort(vec.begin(), vec.end(),
        bind(&std::pair<int, int>::first, _1) < bind(&std::pair<int, int>::first, _2)
        || bind(&std::pair<int, int>::first, _1) == bind(&std::pair<int, int>::first, _2)
        && bind(&std::pair<int, int>::second, _1) < bind(&std::pair<int, int>::second, _2)
    );

---

---

thanks a lot man really descriptive.

Quote:

---

Originally Posted by Daved

Are you sure that's standard? I see dinkumware (meaning VC++) has it. In fact it has operator> already, so the original code would work with one minor change:

Code:

---

make_heap(cont.begin(),cont.end(),greater<pair<int, int> >);

---

I just don't know if that's in the standard or just a VC++ extension.

---

i had tried this method but it seems to be giving huge "STL style" errors.