比较器 return 在 C++ 中的真正含义是什么

Question

我正在尝试用 C++ 进行稳定排序，我的数组是这样的

{{first = "art zero", second = "let3 "}, {first = "own kit dig", second = "let2 "}, {first = "art can", second = "let1 "}}

sort(let.begin(), let.end(),
[](pair<string,string>& a, pair<string,string>& b) {
    int comp = a.first.compare(b.first);
    if(!comp) {
        return a.second.compare(b.second);
    } else {
        return comp;
    }
});

为什么不按第一个值的字典顺序排序？ return 值在 C++ 比较器中的真正含义是什么？谢谢

Answer 1

std::pair and std::string 已默认提供字典顺序，因此您无需为此任务编写比较函数。

如果您确实想编写一个比较函数，它必须满足 Compare 要求。它必须提供严格的弱排序。这意味着如果第一个值出现在第二个之前 returns true，否则 false。

您可以修改您的代码，使其 returns true 表示“小于”，false 否则。

sort(let.begin(), let.end(), [](const pair<string,string> &a, const pair<string,string> &b){
    int comp = a.first.compare(b.first);
    if (comp == 0) {
        return a.second.compare(b.second) < 0; // less than (ascending order)
    } else
        return comp < 0; // less than (ascending order)
});

Answer 2

如果您简单地选择 std::map 作为您的容器，则默认排序以词法排序顺序提供存储，例如

#include <iostream>
#include <string>
#include <map>

int main (void) {
    
    std::map<std::string, std::string> let {{"art zero", "let3 "}, 
                                            {"own kit dig", "let2 "},
                                            {"art can", "let1 "}};
    for (const auto& p : let)
        std::cout << p.first << ", " << p.second << '\n';
}

例子Use/Output

$ ./bin/map_sort_lex
art can, let1
art zero, let3
own kit dig, let2

不能同时使用map/mutimap

如果您必须对 .first 和 .second 都进行电报排序，则不能使用 std::map/std::multimap。它们仅限于在 .first 上排序以进行存储。另一种方法是 std::vector<std::pair<>> 和你的字符串对。

您可以通过编写一个简单的 bool Compare 函数来实现自定义比较，如下所示：

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

bool lexcmp (const std::pair<std::string, std::string>& lhs, 
             const std::pair<std::string, std::string>& rhs)
{
    if (lhs.first != rhs.first)
        return lhs.first < rhs.first;
    
    return lhs.second < rhs.second;
}

int main (void) {
    
    std::vector<std::pair<std::string, std::string>> let {{"art zero", "let3 "}, 
                                                          {"art zero", "let2 "},
                                                          {"own kit dig", "let2 "},
                                                          {"art can", "let1 "}};
    
    std::sort (let.begin(), let.end(), lexcmp);
    
    for (const auto& p : let)
        std::cout << p.first << ", " << p.second << '\n';
}

例子Use/Output

添加额外的 "art zero", "let2 " 对以强制对 .second 进行排序后，您将拥有：

$ ./bin/vector_sort_lex
art can, let1
art zero, let2
art zero, let3
own kit dig, let2

如果您可以只在 .first 上排序，那么 std::map（或 std::multimap）会为您处理排序。对 .first 和 .second 进行排序，那么上面的解决方案也不错。

比较器 return 在 C++ 中的真正含义是什么

What does comparator return really mean in C++

c++

sorting

stable-sort