C++自定义结构体的排序规则详解

C++自定义结构体的排序规则详解

引用

CSDN

1.

https://m.blog.csdn.net/m0_62128476/article/details/145293176

本文将详细介绍C++中自定义结构体的排序规则。通过重载小于号运算符和编写比较函数两种方法，你可以灵活地定义结构体的排序逻辑。此外，文章还将讨论在使用priority_queue和set等容器存储结构体时可能遇到的问题，帮助你避免常见的陷阱。

1. 准备工作

假设现在有一个名为 node 的结构体：

struct node {
    int x;
    int y;
};

2. 通过重载小于号来自定义结构体的排序规则

通过重载小于号运算符，可以自定义结构体的排序规则。例如，我们可以按照 x 的升序排序，如果 x 相同，则按照 y 的升序排序：

struct node {
    int x;
    int y;
    bool operator<(const node &anotherNode) const {
        if (x != anotherNode.x) {
            return x < anotherNode.x;
        }
        return y < anotherNode.y;
    }
};

重载运算符后，就可以通过 sort 函数直接对结构体数组排序了：

node nodes[N];
for (int i = 0; i < N; i++) {
    nodes[i].x = i;
    nodes[i].y = N - i;
}
sort(nodes, nodes + N);

3. 通过编写比较函数来自定义结构体的排序规则

如果结构体重载了小于号，但 sort 函数又指定了比较函数，则以比较函数中的排序规则为准。例如：

bool sortByXAscAndYAsc(const node &front, const node &back) {
    if (front.x != back.x) {
        return front.x < back.x;
    }
    return front.y < back.y;
}

将函数名作为第三个参数传递给 sort 函数，就可以通过 sort 函数直接对结构体数组排序了：

node nodes[N];
for (int i = 0; i < N; i++) {
    nodes[i].x = i;
    nodes[i].y = N - i;
}
sort(nodes, nodes + N, sortByXAscAndYAsc);

4. 在使用priority_queue和set等容器存储结构体时可能遇到的问题

如果结构体在重载小于号时函数没有添加 const 关键字，但又使用了 priority_queue 和 set 等容器存储结构体，编译器会给出以下错误：

错误信息显示：

In template: invalid operands to binary expression (‘const node’ and ‘const node’)
error occurred here in instantiation of member function ‘std::less::operator()’
requested here in instantiation of member function ‘std::_Rb_tree<node, node, std::_Identity, std::less>::_M_get_insert_unique_pos’
requested here in instantiation of function template specialization ‘std::_Rb_tree<node, node, std::_Identity, std::less>::_M_insert_unique’
requested here in instantiation of member function ‘std::set::insert’
requested here
candidate template ignored: could not match ‘const reverse_iterator<_Iterator>’ against ‘const node’
candidate template ignored: could not match ‘const reverse_iterator<_IteratorL>’ against ‘const node’
candidate template ignored: could not match ‘const move_iterator<_IteratorL>’ against ‘const node’
candidate template ignored: could not match ‘const move_iterator<_Iterator>’ against ‘const node’
candidate function not viable: ‘this’ argument has type ‘const node’, but method is not marked const

这个错误的原因是结构体的重载小于号函数没有添加 const 关键字。在C++中，const 关键字用于指定一个变量、对象的属性或成员函数不会改变。当一个函数被 const 关键字修饰时，该函数被称为常函数，常函数不能修改对象的属性（每个结构体的实例都可以看做是一个对象）。

试想一下，如果重载小于号的函数没有使用 const 关键字修饰，那么函数内就可以修改结构体中某个变量的值。这也是为什么在使用 priority_queue、set 等容器存储结构体变量时，结构体必须已经实现了用 const 修饰的重载小于号的函数。因为一旦在重载小于号的函数修改了结构体中某个变量的值，就有可能导致排序结果是错误的。