<algorithm>排序自定义条件

Question

好的，我尝试使用排序来向量项目，所以两个形容词项目的大小是<= 2d。下面是我的尝试：

struct item{
    long number;
    long size;
};

// d is global variable.
bool check(const item& x, const item& y)
{
    return ((x.size + y.size) <= (2 * d));
}

// Items is a vector of item.
sort(items.begin(), items.end(), check); 

我做错了什么，甚至不可能使用那样的条件进行排序？

Answer 1

使用这样的条件进行排序是不可能的吗？

不是的。sort中的比较器必须满足strict weak ordering的标准，而这显然不是您的标准(例如，它不是无自反的)。

Answer 2

这个问题不可能在O(N log N)时间内解决。我不知道它是否是NP-难的，但它不是微不足道的。我确实认为可以肯定地说，一个解决问题的程序将需要指数级的时间。有这样的程序:我认为它可以随意摆弄，插入到线性优化器中。

任何标准库函数都不会让你得到一个通用的解决方案。没有比O(N log N)更慢的标准库函数，也没有解决可能难以解决的问题。

例如，如果每个size都等于10 * d，那么这个问题就很难解决。

Answer 3

您错误地使用了sort()方法。

STL排序用于对元素列表进行排序。对于一个“排序”，你需要满足如下条件：

1. 如果check( A，B) == false和A != B，则check( B，A)返回true。
2. 如果check( A，B) == false和check( B，C) == false和A，B，C是不同的，则check ( A，C)返回false。

在哪里可以使用STL的sort()的一个好主意是，给定项目S的列表和您希望项目的顺序：

1. 如果S中的项的顺序发生更改，则输出顺序应保持不变。
2. 输出是唯一的。
3. 输出顺序中的所有项都具有某种关系，即strict partial order关系。

如果是这种情况，那么您可能可以编写check函数来为您工作:)