我有一个事件的优先级队列,但有时事件优先级会改变,所以我想将事件请求者的迭代器维护到堆中.如果优先级发生变化,我希望在log(n)时间内调整堆.我将始终只有一个指向堆中每个元素的迭代器.
我正在寻找一个在Delphi中实现的优先级队列,它在多线程环境中运行良好.
理想情况下无锁,或设计用于多线程插入/删除,其中包含比单线程实现(我已经拥有)的锁定包装更好的东西.
特殊性在于,在正常操作中,当顶部(最高优先级项)改变时,将仅存在添加,删除和通知,而最高优先级项的"弹出"操作应该非常罕见.
它将用于监视/超时线程监视任务,在其他线程中执行,这些任务预计在大多数时间内正常终止,因此它们只是从队列中添加/删除.超时线程基本上会等待下一个超时事件,因此在最高优先级事件发生更改时需要通知.
任务由脚本处理,可以随时安全地终止.
如果有比这更好的算法而不是优先级队列,它们也可能是很好的答案!
编辑:在Martin James的评论之后,另一个特点是相对较少的不同超时值,并且对于每个超时值,问题变成FIFO队列的问题.
std :: priority_queue :: top返回一个常量值.但是,我想从优先级队列中删除顶部元素,并能够在其他地方修改它.
priority_queue<SomeClass, vector<SomeClass>, SomeClassCompare > pQueue;
...
SomeClass *toBeModified = &(pQueue.top());
pQueue.pop();
toBeModified->setMember(3); // I would like to do this
有没有办法可以从优先级队列中获取顶级元素(并从队列中删除)并按照我的意愿修改它？
有没有理由让std::priority_queue构造函数通过常量引用接受比较器？如果比较器超出范围怎么办？
在@LightnessRacesInOrbit指出的可能移动比较器的情况下,我正在考虑这个问题!
如果已有关于此事的帖子,我很抱歉.我一直都找不到它!
最相似的容器有会员类型,如key_compare或value_compare但有没有为priority_queue.
是因为priority_queue是适配器吗？或者这是错误的标准？
这不是作业.
我正在使用一个小的"优先级队列"(目前实现为数组)来存储具有最小值的最后N个项目.这有点慢 - O(N)项目插入时间.当前实现跟踪数组中的最大项并丢弃任何不适合数组的项,但我仍希望进一步减少操作数.
寻找符合以下要求的优先级队列算法:
我最初考虑使用二进制堆(它们可以通过数组轻松实现),但显然当数组不能再增长时它们表现不佳.链接列表和数组将需要额外的时间来移动东西.stl优先级队列增长并使用动态分配(尽管我可能错了).
那么,还有其他想法吗？
--EDIT--
我对STL实现不感兴趣.由于大量的函数调用,STL实现(由少数人建议)比当前使用的线性阵列慢一点.
我对优先级队列算法感兴趣,而不是实现.
我猜它不是,我只想确定.意思是2个线程使用相同的 std :: deque std::deque::push_back或push_front同时使用.
同样的问题std::priority_queue和功能std::priority_queue::push和std::priority_queue::pop..
这些容器是否是线程安全的？或者我应该亲自编程它是线程安全的？
Tnx很多.
std::vector,std::list并且std::deque有std::back_inserter和std::set有std::inserter.
对于std::stack和std::priority_queue我会假设等效的插入器将是一个,push()但我似乎无法找到正确的函数来调用.
我的意图是能够使用以下函数和正确的插入迭代器:
#include <string>
#include <queue>
#include <iterator>
template<typename outiter>
void foo(outiter oitr)
{
static const std::string s1 ("abcdefghji");
static const std::string s2 ("1234567890");
*oitr++ = s1;
*oitr++ = s2;
}
int main()
{
std::priority_queue<std::string> spq;
std::stack<std::string> stk;
foo(std::inserter(spq));
foo(std::inserter(stk));
return 0;
}
我有以下结构
struct node{
float val;
int count;
}
我有这个结构的几个对象.现在,我想将这些对象插入到STL的优先级队列中,以便优先级队列按计数对项目进行排序.有关如何这样做的任何想法？优选地,最小堆是优选的.我知道如何对原始数据类型而不是结构进行上述操作
对于我的项目，我从 GCC 5 切换到 GCC 9，发现性能变得更差。我做了一些调查并提出了一个简单的源代码来重现该行为。
我在同一台机器上使用不同的 GCC 版本（g++-5 和 g++-9）编译代码
#include <queue>
int main()
{
std::priority_queue<int> q;
for (int j = 0; j < 2000; j ++) {
for (int i = 0; i < 20000; i ++) {
q.emplace(i);
}
for (int i = 0; i < 20000; i ++) {
q.pop();
}
}
return 0;
}
当我使用 GCC 5 编译它时，我得到以下计时：
# g++-5 -std=c++14 -O3 main.cpp
# time ./a.out
real 0m1.580s
user 0m1.578s
sys 0m0.001s
对 GCC 9 …