STL priority_queue与multiset

2009从-1开始

想用优先级队列，应用场景为：有大量的数据会进入到队列中等待后续操作，这时候来了高优先级的数据，要能插对到最前面
数据基本元素为Class，在比较函数中增加了计数器
priority_queue：这个就叫优先级队列，但是测试发现，采用vector<Class>时，入队执行的Class之间的比较操作非常多，非常耗时，出队也是一样问题。
multiset，入队的比较操作还好，大概平均入队一个，比较30次的样子，出队只取最大的元素，不会执行任何比较操作
想问下：
1、我这个场景，还有没其他的数据结构可供选择？
2、priority_queue应用场景在哪？感觉数据几千就非常慢了

bruceteen

这得看具体库的实现，要不你试试 deque

2009从-1开始

试了，也是一样问题。我是用VS2008测试的
因为基本元素是类，比较在意比较操作的次数。

bruceteen 发表于 2014-09-18 16:09
这得看具体库的实现，要不你试试 deque

linux_c_py_php

priority_queue是堆, 问题就是不支持随机查找删除.

2009从-1开始

我的场景不会用到随机查询
刚测试了下压入10w数据，multiset：
初始化数据耗时毫秒：1408
总共执行了2821561次比较操作
priority_queue<Node,vector<Node>,cmp> 10w数据没出来，改为1万：
初始化数据耗时毫秒：25746
总共执行了50004816次比较操作

linux_c_py_php 发表于 2014-09-18 16:15
priority_queue是堆, 问题就是不支持随机查找删除.

jwj070524

建议用multiset，存储指针类型的数据（避免无意义的拷贝构造），然后自定义比较函数。仔细测试一下到底是不是比较很耗时。

2009从-1开始

各位，刚刚到Unix下测试了下，priority_queue速度很快，跟multiset没明显差异
难道被微软的实现坑到了？ 回复 1# 2009从-1开始