代码之家 › 专栏 › 技术社区 › Spiros

如何实现有限大小的地图

limit hashmap data-structures memory c++

0

Spiros · 技术社区 · 8 年前

我想实现一个元素数量永远不会超过某个限制的映射 L .当 L+1 -插入元素后,应从地图中删除最旧的条目以清空空间。

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

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

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

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

删除条目需要在索引上进行迭代,以从索引中删除密钥,这对于链表和双端队列都具有线性复杂性。(双端队列还有一个缺点,即删除元素本身具有线性复杂性。)所以看起来 这种数据结构上的删除操作不会保留底层映射的复杂性 .

问题是: 这种复杂性的增加是必要的,还是有一些巧妙的方法来实现有限的地图数据结构,以便插入和删除保持相同的复杂性?

哎呀,刚刚发了帖子,立刻意识到了一些重要的事情。该指数的规模也有限。如果这个极限是常数,那么迭代它的复杂性也可以被认为是常数。

嗯,这个上限给出了搬迁成本的上限。

如果限制非常高,人们可能仍然倾向于不涉及指数的线性迭代的解决方案。

2 回复 | 直到 8 年前

1

Serge Ballesta 8 年前

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

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

由于您没有给出任何保持密钥排序的要求,我将使用 unordered_map 对于关联容器和 列表 对于序列一。附加要求是: 列表 必须包含密钥,并且 无序地图 必须包含一个迭代器到 列表 。该值可以在任一容器中。由于我假设主要访问将是直接访问,所以我会将值存储在地图中。

它归结为:

list<K> 允许识别最旧的密钥
一 unordered_map<K, pair<V, list<K>::iterator>>

它将密钥的存储空间增加了一倍,并添加了一个额外的迭代器。但是钥匙不要太大,也不要太大 list::iterator 通常只包含一个指针:这会改变少量内存以提高速度。

这应该足以提供恒定的时间

密钥访问
插入新项目
删除项的键

2

0

Joaquín M López Muñoz 8 年前

你可能想看看Boost。多索引 MRU example .