最近项目中需要用到优先队列,google了半天,发现Cocoa Foundation中竟然木有现成的好用的轮子可以拿来用。找了半天,也只有Core Foundation的CFBinaryHeap算是满足需求,但是CFBinaryHeap需要自己管理释放对象,而且不能实时更新heap中的值,再一看文档中提供的方法,辣么多回调列在那里,做为一个前C++开发者,我想我还不如用我熟悉一点的std::priority_queue来实现我的需求吧。
回忆下什么是优先队列
讲到队列一般人都知道,先进先出嘛,就和排队买东西一样,先来的人排在前面,买完就从队列里出去了。那什么是优先队列呢,假设我们生活在一个特别尊老爱幼的社会,每次排队买东西的时候,都要按照年龄作为优先级比较的参照,年纪大的在最前面,年纪小的在其次,青壮年排在后面,老爷爷老奶奶买完了,才轮到小孩儿,小孩儿们正买着辣条呢呢,忽然又来了个老奶奶,大家于是很懂礼貌的让老奶奶排到了第一个,等老奶奶抢完了超市里的土鸡蛋离开队伍后,才轮到刚刚正准备买辣条的小孩子继续买。
用OC封装std::priority_queue
STL中的priority_queue是C++基于heap实现的优先队列模板类,其鲁棒性和性能已经经过了无数开发者的考验。所以我们放心大胆的用吧。
首先定义一下std::priority_queue<>的包装类:
|
|
QueueIntNodeObject是优先队列中所要管理的对象的基类,目前先实现以NSUInteger做为比较优先级的类型,有需要的可以扩展其他的基类出来。
PriorityQueue是用来包装std::priority_queue的wrapper。定义几个常用的属性和方法。
|
|
QueueCompare定义一个C++类,用来重载()运算符,实现两个QueueIntNodeObject对象的比较。
|
|
给priority_queue另外定义个名字,这个实在太长了。
下面就是实现PriorityQueue的几个方法,每个方法对应的即是操作std::priority_queue的方法。当然别忘了再不使用std::priority_queue的时候delete掉,否则会有内存泄漏。
我们再来看段实例代码,以前面举的排队的例子,先定义一个排队的人的对象,对象有两个属性,名称和年纪:
|
|
然后再创建几个Person对象,放到队列管理去。
|
|
这段代码执行后,会按年龄从大到小输出person对象,达到了我们想要的按照年纪作为优先级参照输出的效果。
并且,我在其中加入了输出person对象引用计数的log,运行后发现,priority_queue在ARC下也很好的管理了计数,person对象在被push到queue中后,queue对其持强引用,引用计数加1,从queue中pop出来后,引用计数减1。所以我们依旧不用担心如何在ARC中管理内存。
如果想实现更复杂的优先级的控制,只需要实现一个类似于QueueIntNodeObject的类和一个用于比较优先级的类即可。
是不是很简单啦啦啦~~~
文中代码都提交到 github 啦:https://github.com/LicoC/PriorityQueue , 欢迎star 😝