-3

If I have a vector<pair<int,int> > datatype, what is the accepted way to sort it by the first element of the pair and then by second if the firsts are equal? For instance maybe (1,10), (3,3), (7,13), (7,16), (8,1), (8,2), (15,2) etc.

Brian Tompsett - 汤莱恩
  • 5,753
  • 72
  • 57
  • 129
MyNameIsKhan
  • 2,594
  • 8
  • 36
  • 56

2 Answers2

11

pairs by default compare by first element, then second. So, if you don't care about preserving the order when the first elements compare equal, then you can just use std::sort:

std::sort(v.begin(), v.end());
nneonneo
  • 171,345
  • 36
  • 312
  • 383
  • This is what I was already using but it doesn't seem to work as intended – MyNameIsKhan Aug 03 '13 at 04:07
  • In what way? The big caveat is that it will sort by second element if the first elements are equal (instead of preserving their original order). – nneonneo Aug 03 '13 at 04:08
  • @AgainstASicilian You might be looking for `std::stable_sort`? – Rapptz Aug 03 '13 at 04:09
  • @nneonneo I do care about preserving order though – MyNameIsKhan Aug 03 '13 at 04:17
  • @Rapptz stable_sort and sort would result in the same result for pair's. – Jason C Aug 03 '13 at 04:19
  • 1
    @AgainstASicilian Don't put all the important info in comments, include it in your original question. – Jim Balter Aug 03 '13 at 04:21
  • @AgainstASicilian: Seeing your revision, you clearly don't care about the original order of the second element because you want to sort them. So `std::sort` is **exactly** what you need. If it ain't working, that's a different problem. – nneonneo Aug 03 '13 at 04:25
  • @AgainstASicilian Important info includes things like that you want a stable sort (and why ... it's not clear that you understand what a stable sort is), what you tried, what the result was and how it differed from what you want ... – Jim Balter Aug 03 '13 at 04:28
  • @nneonneo Maybe my English is off, but by preserve order I meant make sure it is in order. I think that's the wrong way though and I am sorry! I will be clearer next time – MyNameIsKhan Aug 03 '13 at 04:29
  • @neonneo If, say, the second elements were already sorted, then one might want to do a stable sort on just the first elements. – Jim Balter Aug 03 '13 at 04:30
  • @AgainstASicilian: "preserve" means to keep as it originally was; you want "ensure". – nneonneo Aug 03 '13 at 04:30
  • @AgainstASicilian A stable sort preserves (keeps) *the original order* of equal elements. Putting things in order is just sorting them. – Jim Balter Aug 03 '13 at 04:31
  • My mistake, sorry everyone. I mean that I want to sort by first and then sort by second when the firsts are equal – MyNameIsKhan Aug 03 '13 at 04:32
  • @AgainstASicilian As this answer says, std::sort does that. You said it doesn't seem to work as intended, but you have given no indication of what went wrong. – Jim Balter Aug 03 '13 at 04:34
1

std::pairs comparison operators compare pairs lexicographically, it first compares the first elements, then the second elements if the first elements are equal.

Here is an example of using std::vector<std::pair<int, int>> and std::sort.

Using std::sort that way uses std::pair's operator <, which, as said above, compares the pairs lexicographically.

UPDATE: Here is an example using std::stable_sort and a custom comparison function that compares only the first element.

By using std::stable_sort, you are guaranteed that the relative order of equal elements are preserved. That is, even if the first elements of the std::pairs are equal, the original relative order is still retained.

Mark Garcia
  • 17,424
  • 4
  • 58
  • 94