我可以使用迭代器访问优先级队列的元素吗？ [英] Can I access elements of a Priority Que using an iterator?

问题描述

向量和链接列表

向量被连续存储在存储器中，因此任何元素都可以使用 operator [] ，就像在数组中一样。

链表包含不能连续存储在内存中的元素，因此必须通过以下方式访问随机元素

优先级队列的优点

< h1>

最近我发现了优先级队列，它的工作原理类似于堆栈，但元素 push（）并且这个函数根据与运算符进行比较的顺序将它们放在一个顺序中。我相信。

这完全适合我，因为我正在测试事件，并根据剩余的时间将它们放置在队列中，直到它们发生。当我 push（）和 pop（）元素时，队列会自动将它们排序。 （Popping不影响顺序。）我可以写一个运算符< ，所以这不是问题。

我无法解决的问题

我需要为这个事件队列做三件事：

1 :)搜索项目的事件队列。我假设这可以用标准库中的算法来完成？例如，find？如果不是，我可以自己实现一个，只要我可以做点2（见下文）。

2 :)迭代队列。我认为默认的底层容器是 std :: vector ...有没有办法访问底层向量中的随机元素？如果我选择使用 std :: deque 怎么办？我需要这样做来修改某些事件参数。 （事件放在队列中。）例如，我可能需要处理一个事件，然后从每个剩余事件的'time_to_event'参数中减去一个固定的时间。我怀疑这个问题无法完成。

3 :)从队列中删除一个元素。有时在处理事件时，其他事件会失效，因此需要删除。

可以点1-3吗？我在 std :: priority_queue 上的所有信息来自 cplusplus .com ，所以我的默认答案是no，没有办法做任何这些事情。如果我不能做所有的三件事，那么我想我必须写我自己的优先级队列封装。 （哦无聊）

解决方案

不，你不能迭代 std :: priority_queue 。它支持的是插入项，并删除最高优先级的项。

当你想要更多的灵活性，你可能想使用 std :: make_heap 以将堆结构构建到容器中， std :: push_heap 可添加项目， std :: pop_heap 删除一个项目。

由于这些是应用于容器的算法，您仍然可以使用容器的迭代器。根据您如何修改堆中的数据，您可能需要先重新构建堆（如果您以堆属性不再适用的方式修改堆）。你可以用 std :: is_heap 来测试，如果你有任何问题。

Aside： a href =http://www.cppreference.com> http://www.cppreference.com 比您链接的网站更实用和准确。

Vectors and Linked Lists

Vectors are stored in memory serially, and therefore any element may be accessed using the operator[], just as in an array.

A linked list contains elements which may not be stored continuously in memory, and therefore a random element must be accessed by following pointers, using an iterator.

(You probably already knew this.)

Advantage of Priority Que

Recently I discovered the 'priority queue', which works kind of like a stack, but elements are push()-ed into the container, and this function places them in an order according to comparisons made with the operator<, I believe.

This suits me perfectly, as I am testing for events and placing them in the queue according to the time remaining until they occur. The queue automatically sorts them for me as I push() and pop() elements. (Popping does not affect the order.) I can write an operator< so this isn't a problem.

Issues I have not been able to resolve

There are three things which I need to be able to do with this event queue:

1:) Search the event queue for an item. I assume this can be done with an algorithm in the standard library? For example, 'find'? If not I can implement one myself, provided I can do point 2. (See below)

2:) Iterate over the queue. I think the default underlying container is std::vector... Is there a way to access random elements within the underlying vector? What if I choose to use std::deque instead? I need to do this to modify certain event parameters. (Events are placed in the queue.) As an example, I may need to process an event and then subtract a constant amount of time from each remaining event's 'time_to_event' parameter. I suspect this cannot be done due to this question.

3:) Remove an element from the queue. Sometimes when processing events, other events become invalidated, and therefore need to be removed.

Can points 1-3 be done? All the information I have on std::priority_queue has come from cplusplus.com, and so my default answer would be "no", there is no way to do any of these things. If I can't do all three things, then I guess I will have to write my own Priority Queue wrapper. (Oh boring)

解决方案

No, you can't iterate over items in an std::priority_queue. All it supports is inserting items, and removing the highest priority item.

When you want more flexibility, you probably want to use std::make_heap to build the heap structure into your container, std::push_heap to add an item, and std::pop_heap to remove an item.

Since these are algorithms you apply to a container, you can still use the container's iterators as you see fit. Depending on how you modify the data in the heap, you may need to re-build the heap afterwards -- if you modify it in a way that the heap property no longer applies. You can test that with std::is_heap if you have any question.

Aside: many of us find http://www.cppreference.com more useful and accurate than the site you've linked.

这篇关于我可以使用迭代器访问优先级队列的元素吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！