Sort multi-dimensional vector in c++ lexicographically

Question

Assuming I have this 2-dimensional vector arr which is 5X3:

3, 4, 1
1, 7, 2
5, 2, 8
1, 3, 1
5, 0, 0

and I want to sort it lexicographically, like so:

1, 3, 1
1, 7, 2
3, 4, 1
5, 0, 0
5, 2, 8

in other words, I want the rows be sorted primarily according to the first elements, and then if two rows have equal first elements, the rows be sorted according to the second elements, I don't want any sorting relative to the third elements.

Here is the code that I wrote:

bool compare (vector<float> ar1, vector<float> ar2) {

if (ar1[0]<ar2[0]) return 1;
if (ar1[0]>ar2[0]) return 0;
if (ar1[1]<ar2[1]) return 1;
if (ar1[1]>ar2[1]) return 0;
return 0;
}

stable_sort(arr.begin(), arr.end(), compare);

the code seems to give the desired results for the above vector. However, in an actual project where I have a 4506X3 vector of floats it doesn't sort the second column! Can the big size of this vector be a problem? In that case, what is the solution? Should I sort the first column, then divide the array based on rows with the same first elements, sort the second columns of the smaller arrays and then merge them? Is there a better solution?

I appreciate any suggestions.

juanchopanza juanchopanza · Accepted Answer · 2014-05-19T21:55:15

You don't need your own comparator. The default will work out of the box because there is already an operator< for std::vector which performs a lexicographical comparison.

std::stable_sort(arr.begin(), arr.end());

Sort multi-dimensional vector in c++ lexicographically

2 Answers