Непонятный результат возвращаемого значения функции сравнения std :: sort (stable_sort) - PullRequest
0 голосов
/ 12 ноября 2018

У меня есть следующая простая программа. В 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 он действительно отсортирован в порядке убывания.

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

Ответы [ 2 ]

0 голосов
/ 12 ноября 2018

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

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

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

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

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

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

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

0 голосов
/ 12 ноября 2018

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

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

...