c ++ std :: sort неожиданное поведение (Runtime Error)

Question

Может кто-нибудь сказать мне, почему std :: sort показывает это неожиданное поведение.

Этот код дает ошибку времени выполнения

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

inline bool compare(string a, string b){
    return a.size() <= b.size();
}

int main(){

        int n = 100;

        string a = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";

        vector<string>v;
        for(int i=0; i<n; i++){
            v.push_back(a);
        }

        sort(v.begin(), v.end(), compare);

}

, но когдая заменяю return a.size() <= b.size(); на return a.size() < b.size();, он работает совершенно нормально.

Answer 1

Типичная реализация std :: sort использует некоторую вариацию быстрой сортировки, возможно, схему разделения, подобную Hoare, которая сканирует массив с левой стороны, пока значения стержень.Эта схема полагается на значение == pivot для завершения сканирования.Если пользовательское сравнение возвращает true при равных значениях, любое сканирование может выйти за границы массива, что приведет к ошибке доступа к памяти.

В отладочной сборке может быть проверка пользовательского сравнения,и если он возвращает true при равенстве, он может выдать исключение вместо получения ошибки доступа к памяти.

Answer 2

Функция сравнения не соответствует требованиям для заказа объектов с использованием std::sort.Измените его на

inline bool compare(string a, string b){
    return a.size() < b.size(); // Not <= just <
}

Почему использование <= не работает?

Все элементы вашего вектора являются строками одинакового размера.Следовательно, наша сортировка почти идентична сортировке списка чисел.

Для двух чисел std::sort должен определить, является ли одно меньше другого, больше другого или они равны.

Учитывая n1 и n2,

1. Если comp(n1, n2) возвращает true, то n1 меньше n2.
2. Если comp(n1, n2) возвращает false и comp(n2, n1) возвращает false, тогда n1 равно n2.
3. Если comp(n1, n2) возвращает false и comp(n2, n1) возвращает true, тогдаn1 больше n2.

Если вы используете <= в функции сравнения, comp(n1, n2) возвращает true и comp(n2, n1) возвращает true.Учитывая это, алгоритм сортировки просто не может сортировать ваши объекты, и при попытке сделать это происходит бесконечная рекурсия.