c++ - 优先队列 Objective-C++？

Question

我正在研究一种路径查找算法，并希望实现一个优先级队列来加快速度。

我正在根据属性 fScore 将我的 Node 对象添加到队列中。最小的 fScore 总是被添加到队列的顶部。

我对此有哪些选择？最好使用 STL 实现 c++ 优先级队列吗？如果是这样，我将如何设置它以接收我的 objective-c 对象 Node 以及我将如何指定列表的排序依据 (Node.fScore)。

谢谢

Answer 1

对于 std::priority_queue，如果您使用的是 ARC，那么您应该已经完成​​了 90%。 STL 容器会自动存储强引用。赢了!

您需要创建一个自定义比较类。

typedef std::priority_queue<MyClass *, std::vector<MyClass *>, MyClassCompare> MyPriorityQueue;

我不确定您将如何实现您的比较类。它看起来像:

class MyClassCompare {
    bool operator()(MyClass *lhs, MyClass *rhs) const {
        // magic!!! Be sure to return a bool.
    }
};

---

示例包装器类

MyClassQueue.h

@interface MyClassQueue : NSObject
@property (nonatomic, readonly) MyClass *topObject;
@property (nonatomic, readonly) NSUInteger count;
- (void)pushObject:(MyClass *)myObject;
- (void)popObject;
- (void)popAllObjects;
@end

MyClassQueue.mm

#import "MyClassQueue.h"
#include <queue>
#import "MyClass.h"

class MyClassCompare {
    bool operator()(MyClass *lhs, MyClass *rhs) const {
        // magic!!! Be sure to return a bool.
    }
};

typedef std::priority_queue<MyClass *, std::vector<MyClass *>, MyClassCompare> MyPriorityQueue;

@interface MyClassQueue ()
@property (nonatomic) MyPriorityQueue *queue;
@end
@implementation MyClassQueue

- (MyClass *)topObject {
    return !self.queue->empty() ? self.queue->top() : nil;
}

- (NSUInteger)count {
    return (NSUInteger)self.queue->size();
}

- (void)pushObject:(MyClass *)myObject {
    self.queue->push(myObject);
}

- (void)popObject {
    if (!self.queue->empty()) {
        self.queue->pop();
    }
}

- (void)popAllObjects {
    if (!self.queue->empty()) {
        delete _queue;
        _queue = new MyPriorityQueue();
    }
}

- (instancetype)init {
    self = [super init];
    if (self != nil) {
        _queue = new MyPriorityQueue();
    }
    return self;
}

- (void)dealloc {
    delete _queue;
    _queue = NULL;
}    
@end