<algorithm>排序自定义条件

好吧，所以我尝试使用排序向量的项目，所以两个adjecant项目的大小是< = 2d。因此，这里是我的尝试：<algorithm>排序自定义条件

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);

我在做什么错，或使用条件类似的排序，它甚至是不可能的？

来源

2011-02-27 Marijus

1.您得到了什么错误（如果有？）2.排序函数通常具有整数返回值，因为它们至少需要三个条件：A < B, A > B，A == B – 2011-02-27 19:09:10

@Mike'sort'不。 – 2011-02-27 19:10:26

甚至不可能使用这样的条件进行排序？

号中sort的比较器必须满足strict weak ordering它你显然不（例如它不是漫反射）的标准。

来源

2011-02-27 19:08:17

您正在使用sort（）方法错误。

STL排序用于排序元素列表。对于'订购'，您需要满足如下条件：

如果检查（A，B）== false AND A！= B，则检查（B，A）返回true。（A，B）== false AND check（B，C）== false AND A，B，C是不同的，然后检查（A，C）返回false。

一个好主意，在那里你可以使用STL的sort（）时，给予你的项目S和你需要的产品是在顺序列表：

如果项目的顺序S变化，输出顺序应保持不变。
输出是唯一的。
输出顺序中的所有项都具有某种关系，即strict partial order关系。

如果是这样的话，那么你可能可以写检查功能来为你工作:)

来源

2011-02-27 19:10:07 Vanwaril

你的条件是错误的（当B == A？时会发生什么）。 – 2011-02-27 19:12:49

第二个条件实际上应该是：if（check（A，B）== true并且检查（B，C）== true然后检查（A，C）== true（这是_transitive_要求;条件之一是_asymmetric_要求） – MSalters 2011-02-28 10:47:09

这个问题不能在O解决（N日志N）的时间。我不知道这是否是NP难题，但它是非常重要的。我认为可以肯定地说，解决代码中表达的问题的程序需要指数时间。有这样的程序：我认为它可以摆弄并插入线性优化器。

任何标准库函数都不会让你获得通用解决方案的大部分方法。没有比O（N log N）慢的标准库函数，并且没有解决可能难以处理的问题。

如果例如每个size等于10 * d，则此问题是棘手的。

来源

2011-02-27 19:18:10 Potatoswatter

<algorithm>排序自定义条件

回答

相关问题