Sorting a vector of pairs

Question

I have a question about sorting a vector of pairs:

std::vector<std::pair<double,Processor*>> baryProc;

this vector is already filled up with the pairs. Now I wanted to sort the pairs inside the vector based on the double value inside the pair

EXAMPLE:

suppose I have 3 pairs inside the vector. pair1 is at front and pair 3 is at end. pair2 is in the middle:

pair1(1, proc1) 
pair2(3, proc2)
pair3(2.5, proc3)

now i want to sort the pairs based on the double value. So that the order inside the vector is:

pair1(1, proc1) 
pair3(2.5, proc3)
pair2(3, proc2)

How could I do this? I am quite stuck.

Solution 1

In C++, you can have custom comparator functions that specify how to decide whether one element goes before another when sorting. In your case, given 2 pairs, you want the one with the lower value for the first element to go before the other one. You can write a comparator function like so:

// This function returns true if the first pair is "less"
// than the second one according to some metric
// In this case, we say the first pair is "less" if the first element of the first pair
// is less than the first element of the second pair
bool pairCompare(const std::pair<double, Processor*>& firstElem, const std::pair<double, Processor*>& secondElem) {
  return firstElem.first < secondElem.first;

}

Now, pass this function into your sort method:

//The sort function will use your custom comparator function 
std::sort(baryProc.begin(), baryProc.end(), pairCompare);

Solution 2

#include <algorithm>

int main(){

    std::vector<std::pair<double,Processor*>> baryProc;

    std::sort(baryProc.begin(),baryProc.end());
}

Note that you do not need a custom comparator because the default comparator of pair does the thing you want. It first compares by the first element and if they are identical, it compares the second element in the pair.

Comments

[WhozCraig]

This will work if the double values are guaranteed unique (effectively a "set"). But without such a guarantee (by force if needed) you need to write a comparator. The default comparator for pair typically does a return (a.first < b.first || (a.first == b.first && a.second < b.second; The latter is the pointer-comparison that will bite you with non-unique values for first.

[WhozCraig]

+1 a good example of eliminating the .second comparison from the normal less-operator of std::pair. I would prefer a functor for this (more likely to inline), but a functional solution works none-the-less.

[Hossein Nasr]

we have no condition to help us what to do when the first elements are the same. so what happen if we use default comparator?

[Kevin]

Why did you specify std::vector and std::pair but not std::sort? If you did that, you could get rid of the using namespace std bit entirely.

[WhozCraig]

@hoosssein See my comment. the default less-than operator (invoked by std::less<> for std::pair<> can, and will, hit both values if needed (typically as i described). The solution is to provide a custom comparator, as maditya has demonstrated.

[Hossein Nasr]

no reason. i just copy variable declaration form question. thanks for your note.

[WhozCraig]

So long as you understand that for identical double values the less-than state now rests on comparing two pointers, which is most-assuredly what you do NOT want to happen (it rarely is, in fact, so).

[Hossein Nasr]

so, as I understand, this my cause inconsistency in sorting? or you just worry about simple comparison between 2 pointer that cause at most 5 clock of CPU?

[user2633791]

Thanks for this good explanation. i guess the standard comparator will work fine. Would standart oparator sort right if double values are often the same? e.g.: (1,proc1), (1,proc2), (2,proc3), (3,proc4), (3,proc5),....

[maditya]

@user2633791 What you're asking is whether the sort is stable. A sorting algorithm is stable if two elements with the same value remain in the same order relative to one another at the end of the sort as they were at the beginning. The default sort algorithm is not stable, but STL provides a stable sort which should suit your purposes.

[Blastfurnace]

Unless two pointers point into or one-past-the-end of the same array the comparison is undefined. If the user wants to order the pairs by the first element then they should only compare the first elements in this case.

[user2633791]

why does the standard comparator here take the double values of the pair?

[juanchopanza]

@user2633791 the standard comparator compares lexicographically, using first first and second second. Why? Because it makes sense.

[Hossein Nasr]

as is said, at first it use first element(pair.first) then it use second element in pare (pair.second) to compare to pairs of any type.

[user2633791]

thanks. works fine now with standard comparator if you use my own comparator my compiler says: this function call misses the list of arguments this pointers will ruin me :)

[user2633791]

@maditya any idea why my compiler would say so? Missing arguments for this function call. use "&pairCompare" instead of "pairCompare" to get a pointer on this member. but doing so doesnt help

[maditya]

@user2633791 There were extra '>' characters in the arguments to the function, I've removed them now. I think that was probably the problem. (Should be std::pair<double, Processor*> rather than std::pair<double, Processor*>>)

[user2633791]

yeah i noticed this before... unfortunately not the mistake :(

[maditya]

@user2633791 Not sure then sorry ... it compiles for me