c++ - 如何实现尺寸有限的 map

Question

我想实现一个元素数量永远不会超过特定限制的 map L。当插入第 L+1 个元素时，应该从映射中删除最旧的条目以清空空间。

我发现了类似的东西:Data Structure for Queue using Map Implementations in Java with Size limit of 5 .那里建议使用链接的 HashMap ，即也保留所有元素的链接列表的 HashMap 。不幸的是，那是针对 java 的，我需要一个针对 C++ 的解决方案。我在标准库和 boost 库中都找不到这样的东西。

同样的故事在这里:Add and remove from MAP with limited size

这里给出了 C++ 的可能解决方案，但它没有解决我下面的问题:C++ how to mix a map with a circular buffer?

我会以与此处描述的方式非常相似的方式实现它。用于存储键值对的 HashMap 和用于保存条目索引的键的链表或双端队列。要插入一个新值，我会将其添加到 HashMap 中，并将其键添加到索引的末尾；如果此时 has 的大小超过限制，我将弹出索引的第一个元素并从 has 中删除具有该键的条目。简单，与添加到 HashMap 相同的复杂性。

删除条目需要对索引进行迭代以从那里删除键，这对于链表和双端队列都具有线性复杂度。 (双端队列也有一个缺点，即删除元素本身具有线性复杂性。)所以看起来对这种数据结构的删除操作不会保留复杂性，因为底层有映射。

问题是:这种复杂性的增加是否必要，或者有一些巧妙的方法来实现有限的 map 数据结构，以便插入和删除都保持相同的复杂性？

---

哎呀，刚刚发布并立即意识到一些重要的事情。索引的大小也是有限的。如果该限制是常数，则迭代它的复杂度也可以认为是常数。

好吧，这个限制给出了移除操作成本的上限。

如果限制非常高，人们可能仍然更喜欢一种不涉及对索引进行线性迭代的解决方案。

Answer 1

我仍然会使用关联容器来直接访问，并使用顺序容器来轻松移除旧项目。让我们看看所需的访问方法:

• 在给定键的情况下访问元素 => 好的，关联容器允许直接访问
• 添加一个新的键值对
  • 如果 map 未满，很容易:push_back在序列容器上，并简单地添加到关联容器上
  • 如果 map 已满，则必须执行上述操作，但必须删除最旧的元素=> front在序列容器上将给出该元素，并且 pop_front和 erase将删除它，前提是 key 包含在序列容器中
• 删除由其键给定的元素 => 从关联容器中删除很简单，但仅限于 list允许恒定时间删除一个元素前提是你有一个迭代器。好消息是，在列表中删除或插入元素不会使指向其他元素的迭代器失效。

由于您没有给出任何保持键排序的要求，我会使用 unordered_map用于关联容器和 list对于序列一。附加要求是 list必须包含 key ，并且 unordered_map必须包含指向其在 list 中对应元素的迭代器.该值可以在任一容器中。由于我假设主要访问将是直接访问，因此我会将值存储在映射中。

归结为:

• 一个list<K>允许识别最旧的 key
• 一个unordered_map<K, pair<V, list<K>::iterator>>

它将 key 的存储空间加倍并添加了一个额外的迭代器。但预计 key 不会太大并且 list::iterator通常只包含一个指针:这会改变少量内存以提高速度。

这应该足以提供恒定时间

• key 访问
• 插入新项目
• 删除一个项目的关键