C++ 如何用指针实现c++ priority_queue的排序方法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/986021/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to implement sorting method for a c++ priority_queue with pointers
提问by Peter Smit
My priority queue declared as:
我的优先队列声明为：
std::priority_queue<*MyClass> queue;
class MyClass {
bool operator<( const MyClass* m ) const;
}
is not sorting the items in the queue.
不是对队列中的项目进行排序。
What is wrong? I would not like to implement a different (Compare) class.
怎么了？我不想实现不同的（比较）类。
Answer summary:
回答总结：
The problem is, the pointer addresses are sorted. The only way to avoid this is a class that 'compares the pointers'.
问题是，指针地址是排序的。避免这种情况的唯一方法是“比较指针”的类。
Now implemented as:
现在实现为：
std::priority_queue<*MyClass, vector<*MyClass>, MyClass::CompStr > queue;
class MyClass {
struct CompStr {
bool operator()(MyClass* m1, MyClass* m2);
}
}
回答by TimW
Give the que the Compare functor ptr_less.
给 que 比较函子 ptr_less。
If you want the ptr_less to be compatible with the rest of the std library (binders, composers, ... ):
如果您希望 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;
Otherwise you can get away with the simplified version:
否则，您可以使用简化版本：
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;
回答by Peter Smit
The operator <() you have provided will compare a MyClass object with a pointer to a MyClass object. But your queue contains only pointers (I think). You need a comparison function that takes two pointers as parameters.
您提供的运算符 <() 会将 MyClass 对象与指向 MyClass 对象的指针进行比较。但是你的队列只包含指针（我认为）。您需要一个将两个指针作为参数的比较函数。
All this is based on some suppositions - please post your actual code, using copy and paste.
所有这些都基于一些假设 - 请使用复制和粘贴发布您的实际代码。
回答by 1800 INFORMATION
Since your priority_queuecontains only pointer values, it will use the default comparison operator for the pointers - this will sort them by address which is obviously not what you want. If you change the priority_queueto store the class instances by value, it will use the operator you defined. Or, you will have to provide a comparison function.
由于您priority_queue仅包含指针值，因此它将使用指针的默认比较运算符 - 这将按地址对它们进行排序，这显然不是您想要的。如果您更改priority_queue以按值存储类实例，它将使用您定义的运算符。或者，您必须提供比较功能。
回答by markh44
Not sure about the priority queue stuff because I've never used it but to do a straight sort, you can do this:
不确定优先队列的内容，因为我从未使用过它，但要进行直接排序，您可以这样做：
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() );
}
Note the memory leaks, this is only an example...
注意内存泄漏，这只是一个例子......
Further note: This is not intended to be an implementation of priority queue! The vector is simply an example of using the functor I created to compare two objects via their pointers. Although I'm aware of what a priority queue is and roughly how it works, I have never used the STL features that implement them.
进一步注意：这不是优先队列的实现！向量只是使用我创建的函子通过指针比较两个对象的示例。尽管我知道优先级队列是什么以及它的工作原理，但我从未使用过实现它们的 STL 功能。
Update: I think TimW makes some valid points. I don't know why he was downvoted so much. I think my answer can be improved as follows:
更新：我认为 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;}
};
which is cleaner (especially if you consider having a container of values rather than pointers - no further work would be necessary).
这更干净（特别是如果您考虑使用值的容器而不是指针 - 不需要进一步的工作）。
