Sorting a list of vectors lexicographically according to priorities

Question

Say I have a list of vectors of strings:

["a", "c", "duck"]

["a", "a", "f"]

["bee", "s", "xy"]

["b", "a", "a"]

I want to sort the vectors in this way:

first sorting lexicographically with respect to the element at index 0, and if there's a tie, it will be determined lexicographically with respect to the element at index 1, and if there's another tie, it will be determined lexicographically with respect to the element at index 2.

So the list above will be as follows after being sorted:

["a", "a", "f"]

["a", "c", "duck"]

["b", "a", "a"]

["bee", "s", "xy"]

How can I implement the standard library sort() function to write a method to sort a list of vectors according to the above description? I'm using C++. Thanks.

It's not hard to write the compare function once the length of each vector is known. But what if I don't know the length of the vectors (but I always know they are of the same length)? Compare function for vectors of length 3:

bool CompareVector(vector<string>  first, vector<string>  second){
    if (first[0] < second[0])
       return true;
    if (first[1] < second[1])
       return true;
    if (first[2] < second[2])
       return true;
    return false;

}

So for vectors of length n, there will be n if statements. But how can I keep the number of if statements a variable?

How about this:

 bool CompareVector(vector<string>  first, vector<string>  second){
    for (int i=0; i< first.size(); i++)
       if (first[i] < second[i])
         return true;
    return false;

}

Then I can call the standard sort function:

sort(vector<vector<string> >input.begin(), vector<vector<string> >input.end(), CompareVector() )

Would this work? Thanks.

Solution

Simply calling std::sort will do the right thing. It performs a lexicographical comparison of each element of the vector, and this is recursive.

#include <vector>
#include <string>
#include <iostream>
#include <algorithm>

int main()
{
  std::vector<std::vector<std::string>> v{{"a", "c", "duck"},
                                          {"a", "a", "f"},
                                          {"bee", "s", "xy"},
                                          {"b", "a", "a"}};
  std::sort(v.begin(), v.end());

  for (const auto& v_: v)
  {
    for (const auto& s : v_)
      std::cout << s << " ";
    std::cout << std::endl;
  }
  std::cout << std::endl;
}

Output:

a a f 
a c duck 
b a a 
bee s xy 

Comments

[Violet Giraffe]

First of all, you're going to need a natural sort comparator for std::string. Then it's easy.

[user3213711]

I mean I don't want to rewrite a sorting algorithm, say, merge sort, since it's already built in. But somehow I want to implement it in my method.

[user3213711]

I mean, I probably need to define an ordering of the vectors. Then I can call the sort() function from the standard library by passing in the ordering. But how can I define the ordering in code? The length of the vectors doesn't always have to be 3. But all the vectors will be of the same length.

[Flovdis]

A very nice use of auto and the new for iterator. I should update my example with these features as well.

[Arif Ali Shaik]

Can you explain me, how the bottom for loop is working and printing the elements of the vector