9

我的优先队列声明为：

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

4 回答 4

11

给 que 比较函子 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;
于 2009-06-12T10:56:26.537 回答
4

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

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

于 2009-06-12T10:31:41.650 回答
4

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

于 2009-06-12T10:35:37.227 回答
3

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

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

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

于 2009-06-12T11:00:27.713 回答