什么是最好的数据结构来支持优先级，更新，推送和弹出 [英] What would best data structure to support priority, updating , push and pop

问题描述

编写应用程序：
在哪里需要维护一个数据结构X-Files，它存储了多个对象并支持以下功能：

Writing an application: Where in I need to maintain an data structure 'X-Files' which stores a number of objects and supports following functionalities:

1. 弹出 - 删除具有最小值的对象（名为Area51的对象属性之一）


2. 推送 - 将对象插入数据结构


3. 检查 - 给定对象是否在数据结构X-Files中


4. 更新 - 更新对象的内容'Area51'，并保证更新将严格地比当前值更低的值）

1. Pop - Remove the object with the least value (one of the object attributes named - 'Area51' )
2. Push - Insert the object into the data structure
3. Check - Whether the given object is in the Data structure 'X-Files'
4. Update - Update the contents of the object (Involves updating the attribute 'Area51' and its guaranteed that update will be strictly to lower value than current value)

什么是最合适的数据结构支持这些要求？

What would be most appropriate data structure to support these requirements?

推荐答案

A std :: set 应该做这项工作。

A std::set should do the job.

虽然你的问题可能类似使用 std :: priority_queue ，不会陷入陷阱，因为一个香草 priority_queue 不支持更新现有元素（头部除外），也不检查元素是否有效存在。

While your problem might resembles using a std::priority_queue, don't fall into the trap, since a vanilla priority_queue does not support updating existing elements (other than the head), nor checking if an element exists in it efficiently.

这篇关于什么是最好的数据结构来支持优先级，更新，推送和弹出的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！