c++ - 我读了 map.erase(map.end());删除 map 的最后一个元素。但是最后一个元素是什么？它是基于元素的插入顺序吗？

Question

我是初学者。假设我创造了

 map<int, node*> mp;

节点在哪里

struct node{
node *previous;
int key; // I have no idea why there is a key variable in this node
int value;
node *next
};

所以map有int key，指向一个双向链表的节点。

假设我按顺序插入了以下元素。

<key,(let corresponding node.value element be)>  
<5, 1>
<10,2>
<8, 3>  

所以双向链表是这样的:

1<->2<->3

现在，如果我想在节点值为 2,3 的现有节点之间插入一个新节点。所以我创建了一个新的 map 元素。

<key,(let corresponding node.value element be)>  
<7, 4>  

并且(新调整的)双向链表看起来像:(根据我的要求)

1<->2<->4<->3

哪个元素将被 mp.erase(mp.end());删除，为什么？

我写了一个示例程序，其中删除了 map 元素<8,3>。为什么会这样？

仅供引用:我正在为 LRUcache 代码工作。

Answer 1

首先，map.end():

Returns an iterator referring to the past-the-end element in the map container.

past-the-end 元素是一个虚拟元素(也就是说，它实际上并不存在)。它代表 map 最后一个有效元素之后的元素。

如果您问，为什么是虚拟元素？ map.end() 不应该是最后一个元素吗？

这是因为大多数涉及 C++11 容器的操作，如 map、set、vector 等，都指定了它们的操作as [ ) 这意味着无论何时为任何操作提供范围，该范围都被解释为:包含第一个元素，不包含最后一个元素。

例如，[2,5) 表示必须对 2,3,4 执行操作。

其次，当您调用 mp.erase(element) 时，此 element 必须是有效且可取消引用的元素。但是您正在为其指定 map.end() 。

mp.erase(mp.end()) 不能工作。

回到你的问题，TL;DR:

map 不记录插入顺序。

所以从末尾删除意味着删除映射中存在的最后一个元素，按键排序。