Перемещение элементов списка с определенным значением до конца списка

Question

У меня есть список строк, и я пытаюсь привести все строки с определенным значением в конец списка. В коде, который я написал, я пытаюсь использовать functor и сортировку списка, чтобы довести все строки, равные «Hello» до конца списка.

#include<iostream> 
#include<list> 
#include<string> 
using namespace std; 

struct DescendingFunctor 
{ 
private: 
    string StructString; 

public: 
    DescendingFunctor(string S) : StructString(S) {} 

    bool operator()(const string& LHS, const string& RHS) 
    { 
     return LHS > StructString; 
    } 
}; 

int main() 
{ 
    list<string> s; 
    s.push_back("C++"); 
    s.push_back("World"); 
    s.push_back("Hello"); 
    s.push_back("Hello"); 
    s.push_back("World"); 
    s.push_back("C++"); 

    DescendingFunctor d("Hello"); 
    s.sort(d); 

    return 0; 
} 

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

return LHS > StructString; 

Потому что, когда я заменить его

return LHS > RHS; 

Список отсортирован в порядке убывания. Есть ли способ, которым я могу использовать list :: sort, чтобы довести все строки до «Hello» до конца списка? Если бы не то, что было бы хорошим способом достичь этого?

Answer 1

попробуйте использовать эту логику

bool operator()(const string& LHS, const string& RHS) 
{ 
    return LHS != StructString && RHS == StructString; 
} 

Это дает вам то, что вы хотите.

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

В любом случае та же задача может быть выполнена с более низкой временной сложностью, которая равна O(n) вместо O(n * log(n)).

Answer 2

По ряду причин, вы должны предпочесть использовать std:partition для этого:

1. Как вы обратите внимание (в комментарии), вы используете только один из аргументов для вашего бинарного предиката. Это делает ваш бинарный предикат непоследовательным - он действительно не определяет relevant ordering. И наоборот, предикат в partition унарный, и вы можете семантически использовать его именно для того, что вы хотите.

2. С точки зрения сложности сортировки является излишним для того, что вам нужно, так как сложность Θ (п журнал (п);., Наоборот, сложность partition линейна

Возможно вы можете попробовать что-то вроде этого:

std::partition(
    std::begin(s), 
    std::end(s), 
    [](const string &w){return w != "hello";});