16

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.

Brian Tompsett - 汤莱恩
  • 5,753
  • 72
  • 57
  • 129
user2633791
  • 185
  • 1
  • 2
  • 5

2 Answers2

31
#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.

Yeraze
  • 3,269
  • 4
  • 28
  • 42
Hossein Nasr
  • 1,436
  • 2
  • 20
  • 40
  • 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 Aug 07 '13 at 20:16
  • 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? – Hossein Nasr Aug 07 '13 at 20:19
  • 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. – Kevin Aug 07 '13 at 20:20
  • @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. – WhozCraig Aug 07 '13 at 20:22
  • no reason. i just copy variable declaration form question. thanks for your note. – Hossein Nasr Aug 07 '13 at 20:23
  • 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). – WhozCraig Aug 07 '13 at 20:25
  • 1
    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? – Hossein Nasr Aug 07 '13 at 20:30
  • 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. – Blastfurnace Aug 07 '13 at 20:43
  • why does the standard comparator here take the double values of the pair? – user2633791 Aug 07 '13 at 20:53
  • @user2633791 the standard comparator compares lexicographically, using `first` first and `second` second. Why? Because it makes sense. – juanchopanza Aug 07 '13 at 20:54
  • 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. – Hossein Nasr Aug 07 '13 at 20:55
28

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);
maditya
  • 8,626
  • 2
  • 28
  • 28
  • 1
    +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. – WhozCraig Aug 07 '13 at 20:19
  • 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),.... – user2633791 Aug 07 '13 at 20:37
  • 1
    @user2633791 What you're asking is whether the sort is [stable](http://en.wikipedia.org/wiki/Stable_sort#Stability). 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](http://www.cplusplus.com/reference/algorithm/stable_sort/) which should suit your purposes. – maditya Aug 07 '13 at 20:40
  • 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 Aug 07 '13 at 20:57
  • @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 – user2633791 Aug 07 '13 at 21:14
  • @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` rather than `std::pair>`) – maditya Aug 07 '13 at 22:56
  • yeah i noticed this before... unfortunately not the mistake :( – user2633791 Aug 07 '13 at 23:05
  • @user2633791 Not sure then sorry ... it compiles for me – maditya Aug 07 '13 at 23:07