Не удалось отсортировать мой массив с помощью std :: sort и пользовательского компаратора

Question

arr.push_back("1"); 
arr.push_back("34"); 
arr.push_back("3"); 
arr.push_back("98"); 
arr.push_back("9"); 
arr.push_back("76"); 
arr.push_back("45"); 
arr.push_back("4"); 

sort(arr.begin(), arr.end(), myCompare); 

//Here is the compare function
int myCompare(string X, string Y) 
{ 
  string XY = X.append(Y); 

  string YX = Y.append(X); 
  return XY.compare(YX) > 0 ? 1: 0; 
} 
//output should be 998764543431

У меня возникла путаница относительно сортировки, например.у нас есть номера {"1","34","3","98","9","76","45","4"}.Когда мы впервые сравниваем 2 строки, у нас есть 2 варианта 134 и 341, так что 341 больше, мы получим 341 в качестве возвращаемой строки.

Аналогично, мы получим 3341 вследующая итерация и 983341 в следующем и 9983341 в следующем, но когда приходит 76, его необходимо добавить либо в начале, либо в конце, либо он будет 998334176 или 769983341, что неверно.Я что-то упустил?

Answer 1

Есть несколько вопросов.Игнорируя вопросы, почему вы храните int как std::string?Это имеет смысл, только если в какой-то момент вы будете хранить нецелые данные в массиве.Целочисленное сравнение очень быстро.string Сравнение медленное и почти никогда не приводит к желаемому результату.

Сначала

std::string::append изменяет параметр.Итак, если у меня есть:

string x = "left";
string y = "right";
string xy = x.append(y);

x теперь равно «влево», как и xy.Ваша функция сравнения добавит x к y, затем y к результату.

Ваш метод, вызываемый с X = 1, Y = 34:

string XY = X.append(Y); 
// XY = "134", X = "134", Y = "34"
string YX = Y.append(X); 
// YX = 34134, Y = "34134", X = "134"

return XY.compare(YX) > 0 ? 1: 0; 

Таким образом, это можно выразить как

X = X + Y;
XY = X;
Y = Y + X;
YX = Y;

string::compare делает символсравнить.Итак, если бы ваш массив был отсортирован только с использованием string::compare, вы получите

1       3       34      4       45      76      9       98

Second,

Когда мы впервые сравниваем 2 строки, у нас есть 2 варианта 134 и 341так как 341 больше, мы получим 341 в качестве возвращаемой строки.

"341" на больше, чем "134".Однако вы не сравниваете «341» с «134» - вы сравниваете «134» с «3134».«3134» больше только потому, что начинается с 3 вместо «1».Если бы числа были «1341» и «341», «341» все равно было бы больше.

Если ваша цель - просто отсортировать список по целочисленному значению,

int myCompare(string X, string Y)
{
    return atoi(X.c_str()) < atoi(Y.c_str());
}

Или, что более разумно, использовать массив int вместо строк, и пусть sort использует его построенный-в функции сравнения.