Странное поведение std :: is_sorted - PullRequest
Новая
       10

Странное поведение std :: is_sorted

2 голосов
/ 20 июня 2019

Я изучаю утверждения в c ++, и я столкнулся со странным поведением std :: is_sorted.

Учитывая компаратор (c) и несортированный вектор (v) для std :: strings. Я использую std :: sort (v.begin (), v.end (), компаратор). и затем вызовите std :: is_sorted с теми же аргументами. И результат ложный, почему так? 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iterator>
#include <cassert>
int main(){
    auto comparator([](std::string a , std::string b) {return a.length() - b.length();} );
    std::vector<std::string> v {"y" , "yyyy" , "yy" ,
                                 "yy" , "yyyyyyy" , "yyy"};
    assert(false == std::is_sorted(v.begin() , v.end(),comparator));
    std::sort(v.begin(), v.end(),comparator);
    assert(true == std::is_sorted(v.begin() , v.end(),comparator));
}

Ответы [ 2 ]

6 голосов
/ 20 июня 2019

Ваш предикат не работает должным образом.Если вы хотите отсортировать по длине строки, вам нужно 

auto comparator([](std::string a , std::string b) {return a.length() < b.length();} );

Исходный предикат, который вы разместили, возвращает разницу длины строки, которая имеет целочисленный тип и может быть преобразована в bool при вызове с помощью std::sortи приводит к true для всего, что отличается от 0, false в противном случае.Следовательно, каждая неравная длина строки приводит к тому, что предикат оценивается как true, и элементы последовательности с различной длиной строки будут бесконечно заменяться из-за того, что предикат всегда "истинен".Это приводит к неопределенному поведению.

Терминология здесь заключается в том, что предикат должен реализовывать «строгий слабый порядок», который задокументирован, например, в cppreference .Спасибо @ FrançoisAndrieux и @Peter за комментарии по этому поводу.

Также рассмотрите возможность передачи аргументов const std::string& или std::string_view, чтобы избежать ненужных копий.

2 голосов
/ 20 июня 2019

Согласно стандарту C ++ ( 28,7 Сортировка и связанные с ней операции )

2 Сравнение - это тип функционального объекта (23.14). Возвращаемое значение Операция вызова функции применяется к объекту типа Compare, когда контекстно преобразуется в bool (раздел 7), возвращает true, если первый аргумент вызова меньше второго, и ложь в противном случае. Сравнение comp используется повсеместно для алгоритмов, предполагающих упорядочение связь. Предполагается, что комп не будет применять какие-либо непостоянные функция через разыменованный итератор.

Это лямбда-выражение 

auto comparator([](std::string a , std::string b) {return a.length() - b.length();} );

всегда возвращает (контекстно преобразованное значение) true, если длины двух строк неравны.

Так что для этого вектора 

std::vector<std::string> v {"y" , "yyyy" , "yy" ,
                             "yy" , "yyyyyyy" , "yyy"};

лямбда-выражение возвращает false для смежных элементов "yy" и "yy" в позиции 2 и 3.

Если, например, вы поместите промежуточное значение между позициями 2 и 3, как, например, 

std::vector<std::string> v {"y" , "yyyy" , "yy" , "y",
                             "yy" , "yyyyyyy" , "yyy"};

тогда первое утверждение 

assert(false == std::is_sorted(v.begin() , v.end(),comparator));

терпит неудачу.

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

auto comparator( []( const std::string &a , const std::string &b ) 
                 {
                     return a.length() < b.length(); 
                 } );

Также параметры лямбда-выражения должны быть константами.

Примите во внимание, что если ваш компилятор поддерживает C ++ 17, вы также можете переписать лямбда-выражение следующим образом 

auto comparator( []( const std::string &a , const std::string &b ) 
                 {
                     return std::size( a ) < std::size( b ); 
                 } );
...