C++ boost - 是否有一个像队列一样工作的容器，可以直接进行键访问？
我想知道一个类似队列的容器，但它有按键访问，就像地图一样。 我的目标很简单：我想要一个 FIFO 队列，但是，如果我插入一个元素并且具有给定键的元素已在队列中，我希望它的新元素替换已经存在的元素队列。例如，按插入时间排序的地图就可以。
如果没有这样的容器，你认为可以同时使用队列和映射来实现吗？
I was wonndering about a queue-like container but which has key-access, like a map.
My goal is simple : I want a FIFO queue, but, if I insert an element and an element with a given key is already in the queue, I want it the new element to replaced the one already in the queue. For example, a map ordered by insertion time would work .
If there is no container like that, do you think it can be implemented by using both a queue and a map ?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
Boost multi-index提供了这种容器。
为了自己实现它，我可能会选择一个
map，其值由链表节点和有效负载组成。列表节点可以是手动滚动的，也可以是 Boost 侵入式< /a>.请注意，队列适配器的要点是隐藏 Sequence 的大部分接口，但您想弄乱它隐藏的细节。因此，我认为您应该致力于重现
queue的接口（稍微修改一下push的语义），而不是实际使用它。Boost multi-index provides this kind of container.
To implement it myself, I'd probably go for a
mapwhose values consist of a linked list node plus a payload. The list node could be hand-rolled, or could be Boost intrusive.Note that the main point of the
queueadaptor is to hide most of the interface of Sequence, but you want to mess with the details it hides. So I think you should aim to reproduce the interface ofqueue(slightly modified with your altered semantics forpush) rather than actually use it.显然，您可以简单地使用类似队列的容器来完成您想要的操作，但是您必须在每次插入时花费
O(n)时间来确定元素是否已经存在。如果您基于std::vector之类的东西实现队列，您可以使用二分搜索并基本上加快插入O(log n)（即当内存重新分配完成时，仍然需要O(n)操作）。如果这样没问题，就坚持下去。 带有附加容器的变体可能会可以提高性能，但编写起来也很容易出错，如果第一个解决方案足够了，就使用它。
在第二种情况下，您可能希望将元素存储在不同的容器中两次 - 原始队列和诸如映射之类的东西（或者有时哈希映射可能表现更好）。该映射仅用于确定该元素是否已存在于容器中 - 如果是，您将必须在队列中更新它。
基本上，这为我们提供了
O(1)哈希映射查找的复杂性（在现实世界中，由于冲突，这可能会变得更难看 - 哈希映射并不真正适合确定元素存在）不需要更新的情况的O(1)插入时间和需要更新的情况的O(n)插入时间。根据实际更新操作的百分比，实际插入性能可能从
O(1)到O(n)不等，但此方案肯定会优于第一种方案如果更新的数量足够小。不过，您必须同时将元素插入两个容器中，如果删除该元素，也应该执行相同的操作，并且我会三思而行“我真的需要性能提升吗？”。
Obviously what you want can be done simply with the queue-like container, but you would have to spend
O(n)time on every insertion to determine if the element is already present. If you implement your queue based on something likestd::vectoryou could use the binary search and basically speed up your insertion toO(log n)(that would still requireO(n)operations when the memory reallocation is done).If this is fine, just stick to it. The variant with additional container might give you a performance boost, but it's also likely to be error-prone to write and if the first solution is sufficient, just use it.
In the second scenario you might want to store your elements twice in different containers - the original queue and something like a map (or sometimes a hashmap may perform better). The map is used only to determine if the element is already present in the container or not - and if YES, you will have to update it in your queue.
Basically that gives us
O(1)complexity for hashmap lookups (in real world this might get uglier because of the collisions - hashmaps aren't really good for determining element existence) andO(1)insertion time for the case when no update is required andO(n)insertion time for the case update is needed.Based on the percentage of the actual update operations, the actual insertion performance may vary from
O(1)toO(n), but this scheme will definitely outperform the first one if the number of updates is small enough.Still, you have to insert your elements in two containers simultaneosly and the same should be done if the element is deleted and I would think twice "do I really need that performance boost?".
我看到使用队列和可选的地图来完成此操作的简单方法。
为您的元素定义某种 == 运算符。
然后只需建立一个队列，并在每次要插入元素时搜索它。
您可以通过元素位置到元素的映射来优化这一点，而不是每次都搜索队列。
I see easy way of doing this with a queue and optionally a map.
Define some sort of == operator for your elements.
Then simply have a queue and search for your element every time you want to insert it.
You could optimize this by having a map of element locations to elements instead of searching the queue every time.