如何实现c++的排序方法 带指针的priority_queue

Question

我的优先级队列声明为：

std::priority_queue<*MyClass> queue;

class MyClass {
    bool operator<( const MyClass* m ) const;
}

不对队列中的项目进行排序。

怎么了？ 我不想实现不同的（比较）类。

答案摘要：

问题是，指针地址是排序的。 避免这种情况的唯一方法是使用“比较指针”的类。

现在实现为：

std::priority_queue<*MyClass, vector<*MyClass>, MyClass::CompStr > queue;

class MyClass {
    struct CompStr {
        bool operator()(MyClass* m1, MyClass* m2);
    }
}

Answer 1

为 que 提供 Compare 函子 ptr_less。

如果您希望 ptr_less 与 std 库的其余部分（活页夹、作曲家等）兼容：

template<class T>
struct ptr_less
    : public binary_function<T, T, bool> {  
        bool operator()(const T& left, const T& right) const{
            return ((*left) <( *right));
        }
};

std::priority_queue<MyClass*, vector<MyClass*>, ptr_less<MyClass*> > que; 

否则您可以使用简化版本：

struct ptr_less {
    template<class T>
    bool operator()(const T& left, const T& right) const {
        return ((*left) <( *right));
    }
};

std::priority_queue<MyClass*, vector<MyClass*>, ptr_less > que; 

Answer 2

由于您的priority_queue仅包含指针值，因此它将使用指针的默认比较运算符 - 这将按地址对它们进行排序，这显然不是您想要的。 如果您更改 priority_queue 以按值存储类实例，它将使用您定义的运算符。 或者，您必须提供比较功能。

Answer 3

您提供的运算符 <() 会将 MyClass 对象与指向 MyClass 对象的指针进行比较。 但你的队列只包含指针（我认为）。 您需要一个以两个指针作为参数的比较函数。

所有这些都是基于一些假设 - 请使用复制和粘贴来发布您的实际代码。

Answer 4

不确定优先级队列的东西，因为我从未使用过它，但要进行直接排序，您可以这样做：

class A
{
    friend struct ComparePtrToA;
public:
    A( int v=0 ):a(v){}
private:
    int a;
};

struct ComparePtrToA
{
    bool operator()(A* a1, A* a2) {return a1->a < a2->a;}
};

#include <vector>
#include <algorithm>
int _tmain(int argc, _TCHAR* argv[])
{
    vector<A*> someAs;
    someAs.push_back(new A(1));
    someAs.push_back(new A(3));
    someAs.push_back(new A(2));
    sort( someAs.begin(), someAs.end(), ComparePtrToA() );
}

注意内存泄漏，这只是一个示例......

进一步注意：这并不是一个实现优先队列！ 该向量只是使用我创建的函子通过指针比较两个对象的示例。 尽管我知道什么是优先级队列以及它的大致工作原理，但我从未使用过实现它们的 STL 功能。

更新：我认为 TimW 提出了一些有效的观点。 我不知道为什么他的票数这么低。 我认为我的答案可以改进如下：

class A
{
public:
    A( int v=0 ):a(v){}
    bool operator<( const A& rhs ) { return a < rhs.a; }
private:
    int a;
};

struct ComparePtrToA
{
    bool operator()(A* a1, A* a2) {return *a1 < *a2;}
};

这更干净（特别是如果您考虑使用值容器而不是指针 - 不需要进一步的工作）。