Сортировка строкового вектора в C ++ со специальным значением для размещения в конце

Question

Я пытаюсь создать функцию, которая сортирует вектор строк по следующим критериям:

Все строки = "NULL" должны идти до конца вектора и уменьшаться оттуда.Остальные строки должны сохранять свой порядок.

Например, учитывая:

{"Potato", "NULL", "NULL", "Charmander" , "Spaghetti", "NULL"}

вывод должен быть:

{"Potato","Charmander","Spaghetti","NULL","NULL","NULL"}

Я пытался с этим, но это не совсем работало:

bool comp(string i, string j){
    if(i=="NULL"){return i>j;}
     if (j=="NULL") {return i<j;}

Заранее спасибо

Answer 1

Вы можете сделать одну из двух вещей:

1. Сначала позаботьтесь о "NULL", а затем отсортируйте другие строки наивным способом, которым мы регулярно будем
2. Сортировать всю строкуиспользуя более сложный порядок, который вы определили

Обработка «NULL» вначале

Стандартная библиотека имеет алгоритм «разбиения» , который будет перемещать все элементы, соответствующиеопределенный критерий конца строки.

std::vector<string> vec {
    "Potato", "NULL", "NULL", "Charmander" , "Spaghetti", "NULL"
};
auto is_not_null = [](const std::string& s) { return s != "NULL"; } 
auto nulls_start = std::partition(vec.begin(), vec.end(), is_not_null);
auto non_nulls_end = nulls_start;
std::sort(vec.begin(), non_nulls_end);

Сортировка с комплексным сравнением

std::vector<string> vec {
    "Potato", "NULL", "NULL", "Charmander" , "Spaghetti", "NULL"
};
auto comparator = 
    [](const std::string& lhs, const std::string& rhs)
    {
        return rhs == "NULL" or lhs <= rhs; 
    };
std::sort(vec.begin(), vec.end(), comparator);

Обратите внимание на разницу между сравнением здесь и вашей comp() функцией.Компаратор отвечает на вопрос "должна ли первая полученная строка предшествовать второй?"- и ваша comp() функция просто не дает ответа, соответствующего вашему требованию.

Answer 2

Вы можете использовать алгоритм разбиения:

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

using namespace std;

int main(int argc, const char * argv[]) {

    vector<string> vec {
        "Potato", "NULL", "NULL", "Charmander" , "Spaghetti", "NULL"
    };

    partition(begin(vec), end(vec), // Partition the values
               [](const string& s) { return s != "NULL"; });


    copy(begin(vec), end(vec), ostream_iterator<string>{cout, " "});
    cout << endl;

    return 0;
}
// RESULT: Potato Spaghetti Charmander NULL NULL NULL 

ПРИМЕЧАНИЕ. Если вам нужно поддерживать относительный порядок, используйте вместо него stable_partition.

Answer 3

Вы можете написать свою собственную версию функции, которая ставит некоторые строки в конец, т.е.:

namespace myAlgo {
        template<typename ForwardIter, class T >
        ForwardIter moveToEnd(ForwardIter first, ForwardIter last, const T& value) {
            if (first == last) {
                return first;
            }
            ForwardIter fasterFirst = first;
            //Shift strings that do not match value to the left in stable manner
            while (++fasterFirst != last) {
                if (*fasterFirst != value) {
                    *++first = *fasterFirst;
                }
            }
            ForwardIter pivot = first;
            //Fill rest with value
            while (first != last) {
                *++first = value;
            }
    return pivot;
    }
}

Тогда просто:

myAlgo::moveToEnd(vec.begin(), vec.end(), "NULL");