非标准条件排序算法STL c++

Question

我正在研究 STL，并且发现 this 来自斯坦福大学的非常有趣的 PDF 任务。其中一项任务是对歌曲列表进行排序，但标签为 "My song" 的歌曲始终位于列表的第一位。

所以，如果我们有：

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());

非标准条件排序算法STL c++

non-standard conditional sort algorithm STL c++

c++

sorting

algorithm

stl