нестандартный условный алгоритм сортировки STL C++

Question

Я изучаю STL и нашел this очень интересный PDF из Стэнфорда с заданиями. Одна из задач - сортировать список песен, но таким образом, чтобы песни, помеченные как «Моя песня», всегда были первыми в списке.

Таким образом, если мы имеем:

vector <string> song{ "Viva", "Pompeii", "My song", "We remain", "My song", "It is time" }; 

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

My song, My song ... (in ascending or descending order); 

Я решил эту проблему с помощью iter_swap

Вот мой код:

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


    void print(vector <string> song) { 
     for (vector <string> ::iterator it = song.begin(), end = song.end(); it != end; ++it) { 
      cout << *it << " "; 
     } 
    } 

    int main() { 
     vector <string> song{ "Viva", "Pompeii", "My song", "We remain", "My song", "It is time" }; 
     vector <string> ::iterator start = song.begin(); 

     for (vector <string> ::iterator begin = song.begin(), end = song.end(); begin != end; ++begin){ 
      if (*begin == "My song") { 
       iter_swap(start, begin); 
       ++start; 
      } 
     } 
     sort(start, song.end()); 
     print(song); 
     cin.get(); 
     } 

Но до этого я некоторое время боролся за решение проблемы, используя только алгоритм sort. К сожалению, я не придумал решение. Не могли бы вы сказать, можно ли написать функцию сортировки compare, которая решила бы задачу? Я не уверен, если это возможно, так как sort просто делает простой заказ. Я прав?

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

bool compare(string x, string y) { 
    // What to write here? 
} 

void print(vector <string> song) { 
    for (vector <string> ::iterator it = song.begin(), end = song.end(); it != end; ++it) { 
     cout << *it << " "; 
    } 
} 

int main() { 
    vector <string> song{ "Viva", "Pompeii", "My song", "We remain", "My song", "It is time" }; 

    sort(start, song.end(), compare); 
    print(song); 
    cin.get(); 
    } 

Answer 1

Да, это возможно. Вам просто нужно убедиться, что строка "My song" сравнивает меньше, чем любая другая строка.

bool compare(std::string const& x, std::string const& y) 
{ 
    // if y == "My Song", then x can't come before it 
    if (y == "My song") return false; 

    // we already know y != "My Song", so if x does, then we know it should come before y 
    if (x == "My song") return true; 

    // neither x nor y == "My Song", so just fall back to a normal comparison. 
    return x < y;  
} 

Кстати, ваша оригинальная идея была прекрасной. Но то, что вы делали, было разделом. Для этого есть и алгоритм в стандартной библиотеке.

auto start = std::partition(song.begin(), song.end(), 
    [](std::string const& s) { return s == "My song"; }); 
std::sort(start, song.end());