标准库排序和用户定义类型

Question

如果我想通过UDT中的两种变量类型之一对向量进行排序，标准库sort能否完成此操作，还是我需要编写自己的排序函数。

例如，如果您有以下内容

struct MyType{
 int a;
 int b;
};

vector<MyType> moo;

// do stuff that pushes data back into moo

sort(moo.begin(), moo.end()) // but sort it by lowest to highest for a, not b

那么使用标准库的 sort 函数是否可以实现这个功能呢？谢谢。

- trikker

Answer 1

如果你的类型实现了"bool operator < (...) const"和一个拷贝构造函数（编译器生成或自定义），就可以使用标准函数。

struct MyType {
    int a;
    int b;
    bool operator < (const MyType& other) const {
        ... // a meaningful implementation for your type
    }
    // Copy constructor (unless it's a POD type).
    MyType(const MyType &other)
        : a(other.a), b(other.b) { }
    // Some other form of construction apart from copy constructor.
    MyType()
        : a(0), b(0) { }
};

相反地，您可以将排序函数（或函数对象）作为第三个参数传递给 sort()，而不是实现运算符 "<"。

bool type_is_less(const MyType& t1, const MyType& t2) { ... }
...
std::sort(c.begin(), c.end(), type_is_less);

以下情况下会很有用：

1. 由于某种原因，您不想实现运算符"<",
2. 您需要对无法重载运算符的内置类型或指针类型容器进行排序。
3. 您希望使用不同的排序方法对序列进行排序。例如：有时您希望按名字字典序升序排序一个具有名/姓成员的结构体，而其他时候则按姓氏字典序排序。两个不同的函数（或函数对象）可以轻松实现这种选择。

- Alex B

---

另一个选项是为您的类型专门化std::less。这样，您就不必每次传递函数对象（例如，因为确实有一个合理的定义），但是您的类型不会获得operator <。 - Pavel Minaev

type_is_less 也可以是一个“函数对象”（重载()运算符的对象）。 - newacct

这个程序有一个严重的缺陷，即 operator< 不是 const。这意味着它不能用于将比较左侧视为常量的代码。（顺便说一句，我经常看到这种错误，这就足以切换到使这些运算符成为全局的原因之一。这样做的人犯错更少。当然，还有其他原因。） - sbi

@sbi：笔误。操作符<应该是const，如上段所指定的。 - Alex B

@Checkers：好的，我撤回了我的反对票。 :) 不过，我仍然强烈倾向于将所有二元运算符实现为自由函数，同时对待它们的两个操作数（即不改变它们）。使用成员函数时，左操作数可能会被处理得不同。对于像比较这样的运算符，你永远不希望出现这种情况。 - sbi

Answer 2

有三种方法可以实现这个功能：

您可以为您的类重载 operator< ：

bool operator<(const MyType& lhs, const MyType& rhs) {return lhs.a<rhs.a;}

这种方法的缺点是，如果你想根据b来排序，就会遇到麻烦。

你也可以针对你的类型专门使用std::less。这样做可以使std::sort（以及其他一些操作，比如在map中使用该类型作为键）正常工作，而不是为了这个含义而劫持operator<。然而，在你的代码的其他地方，你可能会根据b来比较你的类型，这种方法仍然会劫持通用的比较语法。

或者你可以像这样编写自己的比较器：

struct compare_by_a {
  bool operator()(const MyType& lhs, const MyType& rhs) const
  {return lhs.a<rhs.a;}
};

（注：操作符后面的const并不是必需的，但我认为这是良好的编码风格。）这使得通用比较方法未定义；因此，如果某些代码想在你不知情的情况下使用它们，则编译器会发出错误并提醒你。您可以在需要比较的任何地方有选择地和明确地使用此或其他比较器。

- sbi

Answer 3

如今，使用C++ 20，您可以使用以下功能：

• 通用初始化器
• 指定初始化器
• 来自范围库的排序函数
• 投影
• 结构化绑定

这样，生活会更简单。

请参见：

#include <vector>
#include <algorithm>
namespace rng = std::ranges;

// Some demo type
struct MyType {
    int a{};
    int b{};
};

int main () {

    // Test data
    std::vector<MyType> data{ {.b = 5}, {.b = 4}, {.b = 3}, {.b = 2},  {.b = 1} };

    // Sort it for b
    rng::sort(data, {}, &MyType::b);

    // Debug output
    for (const auto& [a, b] : data) std::cout << a << '\t' << b << '\n';
}

- A M