Сортировка списка векторов лексикографически в соответствии с приоритетами

Скажем, у меня есть список векторов строк:

["а", "в", "утка"]

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

["пчела", "с", "ху"]

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

Я хочу отсортировать векторы таким образом:

первая сортировка лексикографически по элементу с индексом 0, и если есть ничья, она будет определена лексикографически по отношению к элементу с индексом 1, а если есть другая связь, она будет определена лексикографически по отношению к элементу с индексом 2.

Таким образом, приведенный выше список после сортировки будет выглядеть следующим образом:

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

["а", "в", "утка"]

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

["пчела", "с", "ху"]

Как я могу реализовать функцию sort() из стандартной библиотеки, чтобы написать метод для сортировки списка векторов в соответствии с приведенным выше описанием? Я использую С++. Спасибо.

Нетрудно написать функцию сравнения, когда известна длина каждого вектора. Но что, если я не знаю длины векторов (но я всегда знаю, что они имеют одинаковую длину)? Сравните функцию для векторов длины 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;

}

Таким образом, для векторов длины n будет n операторов if. Но как я могу оставить количество операторов if переменной?

Как насчет этого:

 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;

}

Затем я могу вызвать стандартную функцию сортировки:

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

Будет ли это работать? Спасибо.


c++ list sorting vector lexicographic
person user3213711    schedule 03.03.2014    source источник
comment
Прежде всего, вам понадобится компаратор естественной сортировки для std::string. Тогда это легко.   -  person Violet Giraffe    schedule 03.03.2014
comment
Я имею в виду, что я не хочу переписывать алгоритм сортировки, скажем, сортировку слиянием, так как он уже встроен. Но как-то я хочу реализовать его в своем методе.   -  person user3213711    schedule 03.03.2014
comment
Я имею в виду, что мне, вероятно, нужно определить порядок векторов. Затем я могу вызвать функцию sort() из стандартной библиотеки, передав порядок. Но как я могу определить порядок в коде? Длина векторов не всегда должна быть равна 3. Но все векторы будут иметь одинаковую длину.   -  person user3213711    schedule 03.03.2014

Ответы (3)


arrow_upward
7
arrow_downward

Простой вызов std::sort будет правильным решением. Он выполняет лексикографическое сравнение каждого элемента вектора, и это рекурсивно.

#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;
}

Выход:

a a f 
a c duck 
b a a 
bee s xy
person juanchopanza    schedule 03.03.2014
comment
Очень хорошее использование auto и нового для итератора. Я также должен обновить свой пример с этими функциями. - person Flovdis; 03.03.2014
comment
Можете ли вы объяснить мне, как работает нижний цикл for и печатает элементы вектора - person Arif Ali Shaik; 26.02.2018

arrow_upward
0
arrow_downward

Это будет пример реализации:

#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;
}
person Flovdis    schedule 03.03.2014

arrow_upward
0
arrow_downward

Очень простой. Вам нужно создать виртуальную массу символов, и вам нужно установить для каждого символа их порядковые номера, от 1 до N, и сравнить эти порядковые номера. Как это:

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
       }
   }
}

Кроме того, вам нужен временный магазин.

person Ivan    schedule 03.03.2014