原文地址：Objective-C封裝std::priority_queue<>實現(xiàn)優(yōu)先隊列
最近項目中需要用到優(yōu)先隊列，google了半天谋梭，發(fā)現(xiàn)Cocoa Foundation中竟然木有現(xiàn)成的好用的輪子可以拿來用。找了半天，也只有Core Foundation的CFBinaryHeap算是滿足需求孽椰，但是CFBinaryHeap需要自己管理釋放對象，而且不能實時更新heap中的值茎辐，再一看文檔中提供的方法叫挟，辣么多回調(diào)列在那里，做為一個前C++開發(fā)者昼激，我想我還不如用我熟悉一點的std::priority_queue來實現(xiàn)我的需求吧庇绽。
回憶下什么是優(yōu)先隊列###
講到隊列一般人都知道，先進先出嘛橙困，就和排隊買東西一樣瞧掺，先來的人排在前面，買完就從隊列里出去了凡傅。那什么是優(yōu)先隊列呢辟狈，假設(shè)我們生活在一個特別尊老愛幼的社會，每次排隊買東西的時候，都要按照年齡作為優(yōu)先級比較的參照哼转，年紀大的在最前面明未，年紀小的在其次，青壯年排在后面壹蔓，老爺爺老奶奶買完了趟妥，才輪到小孩兒，小孩兒們正買著辣條呢呢佣蓉，忽然又來了個老奶奶披摄，大家于是很懂禮貌的讓老奶奶排到了第一個，等老奶奶搶完了超市里的土雞蛋離開隊伍后偏螺，才輪到剛剛正準備買辣條的小孩子繼續(xù)買行疏。
用OC封裝std::priority_queue###
STL中的priority_queue是C++基于heap實現(xiàn)的優(yōu)先隊列模板類，其魯棒性和性能已經(jīng)經(jīng)過了無數(shù)開發(fā)者的考驗套像。所以我們放心大膽的用吧酿联。
首先定義一下std::priority_queue<>的包裝類:
----PriorityQueue.h----
@interface QueueIntNodeObject : NSObject
@property (nonatomic, assign) NSUInteger compareValue;
@end
@interface PriorityQueue : NSObject
@property (nonatomic, readonly) QueueIntNodeObject *topObject;
@property (nonatomic, readonly) NSUInteger count;
- (void)pushObject:(QueueNodeObject *)myObject;
- (void)popObject;
- (void)popAllObjects;
QueueIntNodeObject是優(yōu)先隊列中所要管理的對象的基類，目前先實現(xiàn)以NSUInteger做為比較優(yōu)先級的類型夺巩，有需要的可以擴展其他的基類出來贞让。
PriorityQueue是用來包裝std::priority_queue的wrapper。定義幾個常用的屬性和方法柳譬。
----PriorityQueue.mm----
#import "PriorityQueue.h"
#include <queue>
class QueueCompare {
public:
bool operator()(QueueIntNodeObject *l, QueueIntNodeObject *r) const {
if (l.compareValue < r.compareValue) {
return true;
}else {
return false;
}
}
};
typedef std::priority_queue<QueueIntNodeObject *, std::vector<QueueIntNodeObject *>, QueueCompare> Queue;
#pragma mark - QueueIntNodeObject
@implementation QueueIntNodeObject
@end
#pragma mark - PriorityQueue
@interface PriorityQueue ()
@property (nonatomic) Queue *priority_queue;
@end
@implementation PriorityQueue
- (instancetype)init {
self = [super init];
if (self) {
_priority_queue = new Queue();
}
return self;
}
- (void)dealloc {
delete _priority_queue;
_priority_queue = NULL;
}
- (QueueIntNodeObject *)topObject {
return !self.priority_queue->empty() ? self.priority_queue->top() : nil;
}
- (NSUInteger)count {
return (NSUInteger)self.priority_queue->size();
}
- (void)popObject {
if (!self.priority_queue->empty()) {
self.priority_queue->pop();
}
}
- (void)pushObject:(QueueIntNodeObject *)myObject {
self.priority_queue->push(myObject);
}
- (void)popAllObjects {
if (!self.priority_queue->empty()) {
delete _priority_queue;
_priority_queue = new Queue();
}
}
@end
QueueCompare定義一個C++類喳张，用來重載()運算符，實現(xiàn)兩個QueueIntNodeObject對象的比較美澳。
typedef std::priority_queue<QueueIntNodeObject *, std::vector<QueueIntNodeObject *>, QueueCompare> Queue;
給priority_queue另外定義個名字销部，這個實在太長了。
下面就是實現(xiàn)PriorityQueue的幾個方法制跟，每個方法對應(yīng)的即是操作std::priority_queue的方法舅桩。當然別忘了再不使用std::priority_queue的時候delete掉，否則會有內(nèi)存泄漏雨膨。
我們再來看段實例代碼擂涛，以前面舉的排隊的例子，先定義一個排隊的人的對象聊记，對象有兩個屬性撒妈，名稱和年紀：
@interface Person : QueueIntNodeObject
@property (nonatomic, copy) NSString *name;
- (instancetype)initWithName:(NSString *)name age:(NSUInteger)age;
@end
@implementation SeatInfo
- (instancetype)initWithName:(NSString *)name age:(NSUInteger)age {
if (self = [super init]) {
self.name = name;
self.compareValue = age;
}
return self;
}
@end
然后再創(chuàng)建幾個Person對象，放到隊列管理去排监。
Person *s1 = [[Person alloc] initWithName:@"賈母" age:70];
NSLog(@"Retain count is %ld", CFGetRetainCount((__bridge CFTypeRef)s1));
Person *s2 = [[Person alloc] initWithName:@"寶玉" age:16];
Person *s3 = [[Person alloc] initWithName:@"黛玉" age:15];
Person *s4 = [[Person alloc] initWithName:@"寶釵" age:17];
Person *s5 = [[Person alloc] initWithName:@"妙玉" age:18];
Person *s6 = [[Person alloc] initWithName:@"賈政" age:40];
Person *s7 = [[Person alloc] initWithName:@"鳳姐兒" age:20];
Person *s8 = [[Person alloc] initWithName:@"平兒" age:19];
PriorityQueue *queue = [[PriorityQueue alloc] init];
[queue pushObject:s1];
[queue pushObject:s2];
[queue pushObject:s3];
[queue pushObject:s4];
[queue pushObject:s5];
[queue pushObject:s6];
[queue pushObject:s7];
[queue pushObject:s8];
NSLog(@"Retain count is %ld", CFGetRetainCount((__bridge CFTypeRef)s1));
while (queue.count) {
Person *person = (Person *)[queue topObject];
NSLog(@"%@", person.name);
[queue popObject];
}
NSLog(@"Retain count is %ld", CFGetRetainCount((__bridge CFTypeRef)s1));
這段代碼執(zhí)行后狰右，會按年齡從大到小輸出person對象，達到了我們想要的按照年紀作為優(yōu)先級參照輸出的效果舆床。
并且棋蚌，我在其中加入了輸出person對象引用計數(shù)的log,運行后發(fā)現(xiàn)，priority_queue在ARC下也很好的管理了計數(shù)，person對象在被push到queue中后附鸽，queue對其持強引用，引用計數(shù)加1瞒瘸，從queue中pop出來后坷备，引用計數(shù)減1。所以我們依舊不用擔心如何在ARC中管理內(nèi)存情臭。
如果想實現(xiàn)更復雜的優(yōu)先級的控制省撑，只需要實現(xiàn)一個類似于QueueIntNodeObject的類和一個用于比較優(yōu)先級的類即可。
是不是很簡單啦啦啦~~~
文中代碼都提交到 github 啦：https://github.com/LicoC/PriorityQueue 俯在， 歡迎star ??
