我应该如何比较指针对（用于排序谓词）

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 进行比较。

不幸的是，std::pair 的 operator< 是根据组件上的 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));
 }

在您可以命名的几乎任何系统上，这应该编译为与 相同的代码返回 lhs < rhs;，但这在形式上并不正确。如果指针的引用对象都是同一对象的子对象（例如，如果您有一个巨大的数组，并且所有对都指向该数组的元素），则对于指针来说，operator< 是可以的因此对于 std::pair 来说是可以的。

如果您希望配对落在相同的排序位置，当且仅当它们指向的对象排序相同时，那么您需要添加额外的取消引用：

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<< /code> 对于 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 时都会执行一些重复的空检查。如果您很关心，请看看编译器如何处理它。

Answer 2

假设您的类有比较运算符：

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

如果您只想比较指针地址，请使用 std::greater：

sort(container.begin(), container.end(), std::greater<SomeClass *>());

编辑：好的，我真的不知道您现在要做什么，与您最近的编辑。如果您只想查找重复项，为什么不直接使用默认排序呢？

Answer 3

如果我理解正确，您的谓词应该具有以下签名，

bool sortPredicate(pair<SomeClass*, SomeClass*>& lhs, pair<SomeClass*, SomeClass*>& rhs);

我对您的类一无所知，也不知道它是否有任何自然顺序，因此很难猜测您想要如何对其进行排序。在评论中，您写道最大的项目应该放在第一位。我假设有 <类的运算符。这个怎么样？

bool sortPredicate(pair<SomeClass*, SomeClass*>& lhs, pair<SomeClass*, SomeClass*>& rhs)
{
    if(!(*(lhs.first) < *(rhs.first) || *(rhs.first) < *(lhs.first))) // If there is == operator use it.
    {
        return *(rhs.second) < *(lhs.second);
    }
    else
    {
        return *(rhs.first) < *(lhs.first);
    }

}

编辑：好的，谢谢您的澄清。这个怎么样？

bool sortPredicate(pair<SomeClass*, SomeClass*>& lhs, pair<SomeClass*, SomeClass*>& rhs)
{
    if(lhs.first == rhs.first)
    {
        return rhs.second < lhs.second;
    }
    else
    {
        return rhs.first < lhs.first;
    }
}

Answer 4

您应该在您的pair类上定义一个operator<。我假设您的配对包含 item1 和 item2。因此：

template <class T>
class pair{
private:
  T item1;
  T item2
public:
  // [...] other stuff goes here
  // here the comparing
  bool operator<(pair p){
    return (item1 < p.item1 || (item1 == p.item1 && item2 < p.item2));
  }
};

此解决方案假设项目已定义 < 和 == 运算符。

我想我没有满足您正在寻找的内容，但我建议重载 <、> 和 ==你的pair类中的运算符。