Сортировка списка векторов лексикографически по приоритетам
Скажем, у меня есть список векторов строк:
[«а», «с», «утка»] [«a», «a», «f»] [«Пчела», «S», «XY»] [«b», «a», «a»]Я хочу отсортировать векторы следующим образом:
сначала выполняется лексикографическая сортировка по элементу с индексом 0, и, если есть связь, она будет определяться лексикографически по элементу с индексом 1, а если есть другая связь, она будет определяться лексикографически по элементу с индексом 2.
Таким образом, список после сортировки будет выглядеть следующим образом:
[«a», «a», «f»] [«а», «с», «утка»] [«b», «a», «a»] [«Пчела», «S», «XY»]Как реализовать стандартную библиотечную функцию sort (), чтобы написать метод для сортировки списка векторов в соответствии с приведенным выше описанием? Я использую C ++.
Благодарю.
Нетрудно написать функцию сравнения, если известна длина каждого вектора. Но что, если я не знаю длину векторов (но я всегда знаю, что они имеют одинаковую длину)?
Функция сравнения для векторов длины 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() )
Будет ли это работать? Благодарю.
Решение
Просто звоню 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
Другие решения
Это будет пример реализации:
#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;
}
Очень просто. Вам нужно создать виртуальную массу символов, и вам нужно установить для каждого символа их номера индексов, сформировать от 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
}
}
}
Также вам нужен временный магазин.