Code

2010年9月25日星期六

有关自己写常用的数据类型

这两天为了一个vsc++ priority queue 的bug浪费了不少时间。我的pqueue是用来储存struct的pointers。我用下面这种方法创建:

priority_queue<CellNode*, vector<CellNode*>, M_compare> openq;
M_compare也是用常规方法写的,跟官网上完全一样的格式。但我run程序的时候总是给我invalid heap的错误。网上搜一下后好象是说queue里的东西没有initialize或者是queue里的container access invalid address。然后我用vs debugger trace stack,发现在call了好几次我的comparator之后comparator的parameter会变成一个很大的负数,我觉得非常奇怪。看ms debugger源码里的那些程序感觉也不是很对,就很是抓狂。

最后觉悟了,我要的无非是一个简单的priority queue,我不需要很有效率的检索,因为我的数据集不是很大,完全没有必要用heap这么复杂的structure来实现。我也不需要通用,因为就只有我一个人用。 然后我就花10分钟写了一个很简单的pqueue。我用list来做container因为他的insert和remove比较快。在pop()里面我就用了一个linear search来找我的head,这样的complexity也就只有O(n)而已。push()和empty()也就是list自己的push_back和empty。额,感觉这个太简单了。用了一下,run without any error!

用vsc++里面的data structure,好处是不用自己写。但是出问题了是很难debug的。所以今后小的data structure可以先考虑自己写,也许节省的就不只两天的时间了。

没有评论: