我应该如何比较指针对(对于排序谓词)

Question

我有一个装满数十亿以下物品的STL容器

pair<SomeClass*, SomeClass*>

我需要以下形式的一些功能

/*returns items sorted biggest first */

bool sortPredicate (pair<SomeClass*, SomeClass*>two,  pair<SomeClass*, SomeClass*> one)
{
  return ???;
}

有没有一些技巧可以用来快速比较指针对？

编辑1:澄清

最后,我只想对指针对列表进行排序,使所有重复项彼此相邻.假设SomeClass中没有明确的方法可用于此目的 - 我只有指针对,我想找到所有相同的对(并行).我认为有一种方法可以解决这个问题,但如果你能想到更好的并行方法,请告诉我.

编辑2:澄清

修复了我的代码(排序谓词的参数是错误的 - 它们应该是对的).

Answer 1

这是C++的一个怪癖,相同类型的任意指针不一定(必然)与<,但可比较std::less.

不幸的是,operator<for std::pair是根据operator<组件定义的,而不是std::less.

因此,假设您希望两个对落在同一个排序位置,当且仅当它们指向相同的两个对象时,您需要:

// "less than"
template<typename T>
bool lt(const T &lhs, const T &rhs) {
    return std::less<T>()(lhs, rhs);
}

typedef std::pair<SomeClass*, SomeClass*> mypair;

bool sortPredicate(const mypair &lhs, const mypair &rhs) {
    return lt(lhs.first, rhs.first) 
        || (!lt(rhs.first, lhs.first) && lt(lhs.second, rhs.second));
 }

几乎任何你可以命名的系统,这应该编译成相同的代码return lhs < rhs;,但这不正式.如果指针的referands是同一个对象的所有子对象(例如,如果你有一个巨大的数组,并且所有对都指向那个数组的元素),那么operator<指针就可以了,因此可以std::pair<pointer,pointer>.

如果你想要成对并且只有当他们指向的对象排序相同时才会在相同的排序位置,那么你需要添加额外的解引用:

bool sortPredicate(const mypair &lhs, const mypair &rhs) {
    return lt(*lhs.first, *rhs.first) 
        || (!lt(*rhs.first, *lhs.first) && lt(*lhs.second, *rhs.second));
 }

如果允许的话,你也可以添加对空指针的检查.当然如果您知道SomeClass确实是类类型而不是指针类型,那么您不需要std::less在上面的版本中使用,只需operator<为SomeClass 定义并且:

inline bool lessptr(const SomeClass *lhs, const SomeClass *rhs) {
    if (lhs == 0) return rhs != 0;
    if (rhs == 0) return false;
    return *lhs < *rhs;
}

bool sortPredicate(const mypair &lhs, const mypair &rhs) {
    return lessptr(lhs.first, rhs.first) 
        || (!lessptr(rhs.first, lhs.first) && lessptr(lhs.second, rhs.second));
 }

您可能会或可能不会优化那一点,因为在第一次和第二次调用lessPtr时都会执行一些重复的空值检查.如果您非常关心,请查看编译器使用它做什么.