Сбивающий с толку результат сравнения функции std::sort (stable_sort) с возвращаемым значением

У меня есть следующая простая программа. В test1 и test2 я пытался отсортировать 2 строки "2" и "1", и в приведенном ниже примере функция compare всегда будет возвращать false.

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

static inline bool compare(const std::string& a, const std::string& b)
{
    if (isdigit(b[0]))
        return false;

    assert(isdigit(a[0]));
    return true;
}

static inline void test1()
{
    std::cout << "test1:\n";
    std::vector<std::string> arr = {
            "2", "1"
    };
    std::stable_sort(arr.begin(), arr.end(), compare);
    for (auto e: arr)
        std::cout << e << std::endl;
}

static inline void test2()
{
    std::cout << "test2:\n";
    std::vector<std::string> arr = {
            "1", "2"
    };
    std::stable_sort(arr.begin(), arr.end(), compare);
    for (auto e: arr)
        std::cout << e << std::endl;
}

static inline bool compare_int(const int& a, const int& b)
{
    return a > b;
}

static inline void test3()
{
    std::cout << "test3:\n";
    std::vector<int> arr = {
            9, 3, 13, 7
    };
    std::stable_sort(arr.begin(), arr.end(), compare_int);
    for (auto e: arr)
        std::cout << e << ' ';
    std::cout << std::endl;
}

int main()
{
    test1();
    test2();
    test3();

    return 0;
}

Однако я получаю следующий вывод

test1:
2
1
test2:
1
2
test3:
13 9 7 3 

Я в замешательстве, потому что, насколько мне известно, функция compare в test1 и test2 вернет false, что указывает на то, что эти 2 элемента должны поменяться местами. Но очевидно, что они не меняются и остаются на прежнем месте.

Я неправильно истолковываю возвращаемое значение функции сравнения? Но в test3 он действительно отсортирован по убыванию.

Я не совсем понимаю его внутренности, обрабатывает ли он символы иначе, чем целые числа?


person Zihan    schedule 12.11.2018    source источник
comment
Я функция сортировки. Я звоню compare("2", "1"). Вы возвращаете false. Затем я звоню compare("1", "2"). Вы снова возвращаете false. Видите проблему? Ваша функция сравнения говорит, что 2 идет после 1, и в то же время 1 идет после 2. Это невозможно, но это то, что вы закодировали.   -  person PaulMcKenzie    schedule 12.11.2018
comment
Спасибо, но если я добавлю вывод в функцию сравнения std::cout << a << ' ' << b << std::endl;, я обнаружу, что она печатает 1 2 в обоих случаях, а не 2 1, почему функция сравнения будет вызываться дважды в одном и том же порядке? Для массива с двумя элементами разве не достаточно просто сравнить один раз?   -  person Zihan    schedule 12.11.2018
comment
Функция может быть вызвана миллион раз, если исполняющая библиотека захочет это сделать. Цель состоит в том, чтобы увидеть, является ли ваша функция сравнения фиктивной, и это так. Если вы утверждаете, что 2 предшествует 1, и в то же время 1 предшествует 2, звучит ли это так, как будто что-то пойдет не так? См. документы о функции сравнения и о том, что такое строгая-слабая -порядок означает.   -  person PaulMcKenzie    schedule 12.11.2018
comment
Забыл сказать, в std::sort он будет вызываться дважды, а в std::stable_sort будет вызываться только один раз с выводом 1 2   -  person Zihan    schedule 12.11.2018
comment
Кроме того, настоящий алгоритм вам нужен std::partition или std::stable_partition? Если первый символ — цифра, сгруппируйте ее в какую-нибудь стопку цифр, а все остальные строки группируются в стопку нецифр. Это настоящая цель?   -  person PaulMcKenzie    schedule 12.11.2018
comment
Большое спасибо, но документы не дают представления о строгом слабом порядке, я нахожу его в другом ответ из stackoverflow. Итак, проблема в том, что iut не оценивает 2 элемента, используя ==, а вместо этого !(a<b) && !(b<a), поэтому он будет сравниваться дважды в сортировке (я еще не изучал стабильную сортировку).   -  person Zihan    schedule 12.11.2018
comment
@PaulMcKenzie Да, этого можно добиться с помощью раздела, но я пытаюсь решить эту проблему, используя одну функцию сравнения, и столкнулся с этой проблемой, которую я пропустил в то время. Сейчас пересматриваю.   -  person Zihan    schedule 12.11.2018
comment
Так почему же вы используете неправильный алгоритм для выполнения работы? Вы видите, что это проблема разделения, а не проблема сортировки.   -  person PaulMcKenzie    schedule 12.11.2018
comment
Почему нельзя использовать sort? Идея заключается в порядке, если он имеет больший порядок, он попадает в правую половину массива. Я думаю, что если мы определим правильный порядок, мы сможем сгруппировать его и в правой половине. Я неправильно понимаю?   -  person Zihan    schedule 12.11.2018
comment
Да, вы неправильно понимаете. В том, что вы делаете, нет порядка. Вы делаете группировку. Заказ означает конкретно a < b. Если вы говорите и a < b, и b < a, это неоднозначно, а не порядок. Если вы хотите сохранить относительный порядок внутри каждой группы, для этого и предназначен std::stable_partition.   -  person PaulMcKenzie    schedule 12.11.2018
comment
@PaulMcKenzie Спасибо за разъяснение. Хотите организовать дискуссию в качестве ответа? Хотя Виктор Истомин дает хороший ответ, но я думаю, что дискуссия проясняет ситуацию. Если вы заняты, я могу позже ответить на свой вопрос, сославшись на ответ вас обоих.   -  person Zihan    schedule 12.11.2018
comment
Я думаю, вы должны ответить на свой вопрос. Похоже, вы хотели partition или что-то подобное, но я предоставляю вам указать на ваше неправильное представление и решение.   -  person PaulMcKenzie    schedule 12.11.2018


Ответы (2)


Я собираюсь ответить на свой вопрос, но большое спасибо PaulMckenzie за его помощь в обсуждении и ответ Виктора Истомина.

Оказывается, эта сортировка работает не так, как я думал. Он ожидает строгий-слабый-порядок, что означает, что a > b и b > a не могут быть истинными одновременно, иначе поведение не определено. Кроме того, его способ определить, равны ли 2 элемента, использует !(a < b) && !(b > a), потому что он использует только оператор < вместо оператора ==.

Ошибка в моем коде в том, что я всегда возвращаю false в этом случае, так что выражение !(a < b) && !(b > a) будет истинным, а sort считает их равными, тем самым не меняя их местами.

Правильным решением, как указывает Пол Маккензи, является использование stable_partiion (или partition, если относительный порядок не нужен). Принцип состоит в том, чтобы использовать сортировку только тогда, когда у нас есть четкое правило сравнения элементов, если мы просто хотим сгруппировать одинаковые элементы вместе, partition подходит.

Кажется, у меня были некоторые ложные заблуждения о функции сортировки, спасибо за указание.

----------------- обновление ----------------

Калет указывает в комментарии, что строгий-слабый-порядок не применяется, но поведение будет неопределенным, если оно будет нарушено. Обновил описание этой части. Спасибо.

person Zihan    schedule 12.11.2018
comment
Это не соблюдается. std::sort задокументировано как имеющее неопределенное поведение, если сравнение не реализует строгое слабое упорядочение данных. Это не означает, что результат может быть неправильным, это означает, что ваша программа больше не связана правилами C++, которые включают в себя такие возможности, которые кажутся работающими, но уничтожают несвязанные данные. - person Caleth; 12.11.2018
comment
@biggerfish Может быть, вас смутило слово «сортировка». В C++ и большинстве других языков sort имеет особое значение. В непринужденной английской речи sort может означать группировать вещи. Но это не непринужденный английский, это информатика. - person PaulMcKenzie; 13.11.2018
comment
@PaulMcKenzie Да, я так думаю. Спасибо. - person Zihan; 13.11.2018

Похоже, что «сравнить» работает именно так, как вы написали: возвращает false, если первый символ второй строки является цифрой.

Кстати, эта функция сравнения не будет работать должным образом (что вы от нее ожидаете, я понятия не имею) в общем случае. В C++ компаратор сортировки должен реализовывать строгое слабое упорядочение. Другими словами, не должно быть случая, когда 'a ‹ b' и 'b ‹ a' одновременно.

person Victor Istomin    schedule 12.11.2018