用map做优先级队列

Aquester

先说说STL的容器一些常见的注意问题:有网友说,为什么用了STL,程序的效率反而下降了呢?是的,如果用不好,你编程是方便了,可是效率下降了.
1:     Vector,这个是基于线性数组的容器   
        注意事项: 在声明一个vector的时候,尽量指明大小,如果输入数据不超过10^6,那就声明一个10^6大小的vector,否则,vector的默认大小是10.(太小了),但是vector的大小可以自动扩大,不要以为仅仅是在已经分配的空间后面再多申请一块,而是新开辟一块空间,把原来的复制过去.想一下,如果你的vector不断的扩容,不断的复制,效率能不低吗?这就是有的网友问为什么STL的vector没有数组的效率高的原因.
2:     Set, Map, 都是基于RB-Tree的容器,所以有自动排序功能
        插入删除，查找效率都很高，查找1000个记录，最多查找10次，查找1000000个记录，最多查找20次
        注意事项: 许多人喜欢用,但是如果频繁的插入,删除,不建议使用.因为每插入一次或者删除一次,都要对RB-tree进行一次调整,n次插入,时间复杂度nlgn. 但是如果插入,删除不频繁的情况下是首选.
3:     hash_set, hash_map, 都是基于hash_table的,没有自动排序功能
       注意事项: 在声明的时候也要尽量指明大小,否则哈希表的容量达到thresh_hold的时候要自动扩容,所有元素再哈希一次.时间不容忽视. hash_table默认初始大小53, 然后扩容至97,193,389,故意是质数.默认的是朴素哈希函数:比如"apple"的hash code: 5*(5*5*(5*'a'+'p')+'p')+'l')+'e'   % 53 = 78066%53 = 50
       目前hash_set hash_map都已经不再是标准的容器,namespace也从std move to stdext. Linux下名字空间是__gnu_cxx. (不推荐使用)
4:   list: 双向链表,内存空间不连续
       只能用remove,remove_if, erase来删除,inset插入,不可以直接修改pre,next.插入删除效率比较高
5:   deque 双端队列
      分段连续内存空间,可以遍历(提供iterator)
6:   stack,queue
       栈和队列,唯一注意的是选择底层容器,默认是deque,可以选择list,vector,根据插入,删除情况选择合适的容器.(不同的底层容器扩容时带来的效率影响), 二者均不提供iterator
7:    priority_queue 优先级队列 (STL里面最笨拙的容器)
       基于堆,默认是大根堆,可以在构造函数里面提供自己的比较函数实现小根堆.
       不提供遍历,不能查找,不能修改里面的元素,只提供top,push,pop
       用A*搜索的朋友注意了,添加新的子节点到openlist时,要判断是否有重复节点,修改F值,这时才能体会到这个容器的笨拙之处.
8: Algorithm里面提供了make_heap, push_heap, pop_heap, 如果单纯做搜索,能不用就不用了吧,pop_heap并没有把元素弹出,而是放到了末尾. 适合对一个未排序的数组进行堆排序使用.
其实我想说的是如果我们真的需要一个优先级队列,前提是我们能对这个优先级队列查找,遍历,修改(当然修改优先级之后能自动排序),那就用map或者set来做吧.(取决于你要存储的数据,前者是key,value对,后者只有key).
举例如下:
    map> m; //最小的永远处于前面
    m[8] = 10;
    m[3] = 9;
    m[9] = 8;
    m[1] = 22;
    for(map>::const_iterator itor = m.begin();itor != m.end();itor++)
        printf("%d\n",itor->first);
   //输出 1 3 8 9
    m[5] = 100;
    for(map>::const_iterator itor = m.begin();itor != m.end();itor++)
        printf("%d\n",itor->first);
   
    //输出 1 3 5 8 9
    如果要修改优先级怎么办呢? 反正修改之后也要对RB_tree进行调整,那就先remove掉,再放进一个新的,比如上面的例子我要把m[5]的优先级改为10,可以如下方式:
(注意,不可以直接修改key,map的iterator提供的key是只读的,也就是说itor->first是const的)
    int value = m[5];
    m.erase(5);
    m[10] = value;
    for(map>::const_iterator itor = m.begin();itor != m.end();itor++)
        printf("%d\n",itor->first);
    //输出 1 3 8 9 10   
以上是自己对STL做个小小的总结。

本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u2/64804/showart_1716941.html