c++，自定义对象的排序：比较函数的要求

问题描述 投票：0回答：1

我有一个自定义对象的指针向量

std::vector<MyObject*>
。该对象有一个索引、一个数字和一个时间戳（对象的创建时间）。时间戳是唯一的，数字可以是-1（对象尚未分配数字）或正值；如果对象的数字大于 0，则该数字是唯一的。

class MyObject {
private:
    int id;
    int number;
    time_t timestamp;
public:
    MyObject(int id, int number, time_t timestamp) : id(id), number(number), timestamp(timestamp) {}
};

我想使用自定义比较函数对向量进行排序：如果我的对象的两个实例有一个数字，我使用该数字（降序）进行排序，如果没有，我使用时间戳（降序）进行排序。

所以我将以下内容添加到 

MyObject
类中：

    static bool compareByDescendingNumberAndTimestamp(MyObject * a, MyObject * b) {
        if (a->number > 0 && b->number > 0) {
            return a->number > b->number;
        }
        return a->timestamp > b->timestamp;
    }

最后对向量进行排序：

std::vector<MyObject*> myObjects;
auto object1 = new MyObject(1, 24097, 1200);
auto object2 = new MyObject(2, 24096, 1100);
auto object3 = new MyObject(3, -1, 1000);
auto object4 = new MyObject(4, -1, 900);
auto object5 = new MyObject(5, 24099, 800);
auto object6 = new MyObject(6, 24095, 850);
myObjects.push_back(object1);
myObjects.push_back(object2);
myObjects.push_back(object3);
myObjects.push_back(object4);
myObjects.push_back(object5);
myObjects.push_back(object6);
std::sort(myObjects.begin(), myObjects.end(), MyObject::compareByDescendingNumberAndTimestamp);

我想要的顺序如下：

ID   Number  Timestamp
5    24099    800
1    24097   1200
2    24096   1100
3    -       1000
4    -        900
6    24095    850

但我实际得到的是：

ID   Number  Timestamp
1    24097   1200
2    24096   1100
3    -       1000
4    -        900
5    24099    800
6    24095    850

经过一番研究，我找到了此页面。据我了解，我的比较函数不满足Compare的要求。特别是 

comp(a, b)
没有建立严格的弱排序关系。

有没有办法编写一个比较函数来按我想要的方式排序我的向量？

注意：我一直在使用c++17。

编辑：

最小可重现示例（请注意，向量的初始顺序影响最终结果）：

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

class MyObject {
public:
    int id;
    int number;
    time_t timestamp;

    MyObject(int id, int number, time_t timestamp) : id(id), number(number), timestamp(timestamp) {}

    static bool compareByDescendingNumberAndTimestamp(MyObject * a, MyObject * b) {
        if (a->number > 0 && b->number > 0) {
            return a->number > b->number;
        }
        return a->timestamp > b->timestamp;
    }
};

int main() {
    std::vector<MyObject*> myObjects;
    auto object1 = new MyObject(1, 24097, 1200);
    auto object2 = new MyObject(2, 24096, 1100);
    auto object3 = new MyObject(3, -1, 1000);
    auto object4 = new MyObject(4, -1, 900);
    auto object5 = new MyObject(5, 24099, 800);
    auto object6 = new MyObject(6, 24095, 850);
    myObjects.push_back(object6);
    myObjects.push_back(object5);
    myObjects.push_back(object4);
    myObjects.push_back(object3);
    myObjects.push_back(object2);
    myObjects.push_back(object1);
    std::sort(myObjects.begin(), myObjects.end(), MyObject::compareByDescendingNumberAndTimestamp);

    std::cout << "ID\tNumber\tTimestamp" << std::endl;
    for (auto const & object: myObjects) {
        std::cout << std::to_string(object->id) << "\t" << std::to_string(object->number) << "\t"
        << std::to_string(object->timestamp) << std::endl;
    }

    return 0;
}
c++ sorting
1个回答
0
投票

您在问题中描述的排序函数的问题在于它实际上不是排序函数。

快速提醒顺序理论，顺序关系（记为

≤
）必须验证3个属性：

  • 自反性：a ≤ a
  • 反对称：如果 a ≤ b 且 b ≤ a 则 a = b
  • 传递性：如果 a ≤ b 且 b ≤ c 则 a ≤ c

当您具有这样的关系时，通过仅比较项目对，可以保证获得排序集，并且分而治之的排序算法在很大程度上依赖于这些属性的有效性。
如果你没有，你可能会遇到矛盾。

让我们拿 3 个项目，id 2、3 和 5（显示为 

(id    number    timestamp)
），看看你的函数说了什么：

  1. (5    24099    800)
    ≤ 
    (2    24096   1100)
    （通过数字比较）
  2. (2    24096   1100)
    ≤ 
    (3    -       1000)
    （通过比较它们的时间戳）
  3. (3    -       1000)
    ≤ 
    (5    24099    800)
    （通过比较它们的时间戳）
  4. (2    24096   1100)
    ≤ 
    (5    24099    800)
    （通过使用 2. 和 3. 传递性）
  5. (2    24096   1100)
    = 
    (5    24099    800)
    （使用 1. 和 4 通过反对称性。）

矛盾就在这里。您的程序不会检测到它，因为它相信您为其提供了正确的顺序关系。

结论：你必须改变你的函数，让它成为正确的顺序关系（实际上，C++需要严格的顺序关系，因此

a < a
一定是假的）。

现在理论已经不存在了，让我们看看如何对 

myObjects
向量进行排序。

一个有效的订购是：

  • 所有带有 
    number == -1
    的对象（实际上是所有带有 
    number < 0
    的对象）都位于末尾，并按 
    timestamp
    递减排序。
  • 所有带 
    number >= 0
    的对象均按 
    number
    降序排序。

这可以简化为*按数字、时间戳降序排序。

为了安全起见，我将测试是否在任何地方遇到

nullptr
（你没有这样做，但真的总是应该这样做）并将它们推到最后（我让你更改循环以打印对象）。

std::sort(myObjects.begin(), myObjects.end(), 
    [] (auto const a, auto const b) -> bool {
    if (!a)
        return false;
    if (!b)
        return true;
    return std::make_pair(a->number, a->timestamp) > std::make_pair(b->number, b->timestamp);
});

另一个有效的订购是：

  • 所有带有 
    number < 0
    的对象实际上都位于开头，并按 
    timestamp
    递减排序。
  • 所有带 
    number >= 0
    的对象均按 
    number
    降序排序。

在这种情况下，它不能像上面那样简化，你会得到：

std::sort(myObjects.begin(), myObjects.end(), 
    [] (auto const a, auto const b) -> bool {
    if (!a)
        return false;
    if (!b)
        return true;
    if (a->number > 0 && b->number > 0)
        return a->number > b->number;
    if (a->number < 0 && b->number < 0)
        return a->timestamp > b->timestamp;
    return (a->number < 0);
});

作为更灵活的替代方案，您可以分几个步骤进行排序，使用 

std::partition
将向量划分为可比较的子部分（它比 
std::sort
更有效）。
lambda 会更容易编写：

auto nonNullEnd = std::partition(myObjects.begin(), myObjects.end(),
    [](auto const o) -> bool {
    return static_cast<bool>(o);
});
auto negNumberedObjectEnd = std::partition(myObjects.begin(), nonNullEnd,
    [](auto const o) -> bool {
    return o->number < 0;
});

std::sort(myObjects.begin(), negNumberedObjectEnd,
    [] (auto const a, auto const b) -> bool {
        return a->timestamp > b->timestamp;
});
std::sort(negNumberedObjectEnd,nonNullEnd, 
    [] (auto const a, auto const b) -> bool {
    return a->number > b->number;
});

肯定还有其他方法来对事物进行排序，如果您想尝试的话，我建议您使用最后一种方法。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.