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.

Answer 1

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 

Answer 2

This would be an example implementation:

#include <iostream>
#include <vector>

typedef std::vector<std::string> StringTuple;
typedef std::vector<StringTuple> MyList;

bool mySort(const StringTuple &a, const StringTuple &b)
{
    if (a[0]==b[0]) {
        if (a[1]==b[1]) {
            return a[2] < b[2];
        } else {
            return a[1] < b[1];
        }
    } else {
        return a[0] < b[0];
    }
}

void showList(const std::vector<StringTuple> &list)
{
    for (MyList::const_iterator it = list.begin(); it != list.end(); ++it) {
        const StringTuple &tuple = *it;
        for (StringTuple::const_iterator it2 = tuple.begin(); it2 != tuple.end(); ++it2) {
            std::cout << "\t\"" << *it2 << "\"";
        }
        std::cout << std::endl;
    }
}


int main(int argc, const char * argv[])
{
    MyList listToSort;

    listToSort.push_back({"a", "c", "duck"});
    listToSort.push_back({"a", "a", "f"});
    listToSort.push_back({"bee", "s", "xy"});
    listToSort.push_back({"b", "a", "a"});

    std::cout << "Before sort:" << std::endl;
    showList(listToSort);
    std::sort(listToSort.begin(), listToSort.end(), mySort);
    std::cout << "After sort:" << std::endl;
    showList(listToSort);
    return 0;
}

Answer 3

Very simple. You need create virtual mass of symbols, and you need to set for each symbols their index numbers, form 1 to N, and compare this indices. Like this:

std::vector<std::string> m_vector;
std::string abc = "abcde....."; // this variable have an alphabet

void f()
{
   for(int i = 0; i < m_vector.size(); i++)
   {
       int symbol = 0;
       for(int j = 0; j < abc.length(); j++)
       {
           //second index zero because we need to get a first symbol
           if(m_vector[i][0] == abc[j]) 
           {
               symbol = j;
               break;
           }
       }

       //here your comparison, as you need
       //like this
       if(prevItem > symbol)
       {
           //to move forward
       }
   }
}

As well, you need temporary store.