为什么有三个比较来添加第二个地图元素？

Question

当我运行以下代码（注释掉一行）时，我没有得到任何输出（没有进行比较）。但是当我取消注释最后一行时，我得到了三行输出（进行了三次比较）。添加第二项时，进行1-2次比较可以理解，但为什么要添加第三项？

#include <map>
#include <iostream>

using namespace std;

class MyType
{
  public :
  int a;
  MyType():a(0){}
};

bool operator<(const MyType &lhs, const MyType &rhs)
{
  cout<<"operator < is called\n";
  return lhs.a < rhs.a;
}

int main()
{
  MyType T1,T2;
  T1.a = 100;
  T2.a = 33; 
  
  map<MyType,int> Test;

  Test[T1] = 10; 
  //Test[T2] = 20; --> #Uncomment this line for getting 3 lines of "operator < is called"

}

未注释行的输出：

operator < is called
operator < is called
operator < is called

它是如何在只添加一个额外的键的情况下从零开始打印三个字符串的？

MyCodeOnline

这里是lhs和rhs的地址：

0x56365ea45e90
0x7ffe3c4cd47c
operator < is called
0x7ffe3c4cd47c
0x56365ea45e90
operator < is called
0x56365ea462d0
0x56365ea45e90
operator < is called

Answer 1

在 visual studio 调试版本中，它会在标准库中生成大量额外代码以捕获各种错误。

在 std::map 的情况下，在插入新值后，它检查比较器是否正确 returns false for comp(key, key) 并因此实现所需的严格弱排序。

如果您切换到发布版本，如您所料只有 2 次比较。

我推测 libstdc++ 中发生的事情是 Test[T2] = 20 必须执行四个操作：

检查T2是否已经存在
为 T2
Return 对新元素的引用
将新元素的值赋给20

我猜 libstdc++ 没有优化步骤 1 和 2 以重用比较。如果您使用 insert 将元素插入地图，则只执行 2 次比较（这在所有标准库中应该更有效，即使它们设法不生成对比较器的额外调用）：

Test.insert(std::make_pair(T2, 20));

Answer 2

我的回答基于使用 RB 树作为底层存储的映射的 libstdc++ gcc 实现。

当使用 operator[] 插入到地图时，它会做两件事：首先，它会查看是否可以在地图中找到现有元素，其次 add/update 元素到新值。

查找操作是第一次使用operator<
下一次使用是在插入底层RB树的时候。同样，第一个操作是检查新节点值是否等于树中已有的节点。
第二个操作，然后是相对于前一个节点放置新节点的位置。

这与 map emplace 或 insert 操作形成对比，它们不会执行 find 操作，而是直接跳到将节点插入到底层树中。

为什么有三个比较来添加第二个地图元素？

Why are there three comparisons to add a second map element?

c++

insert

stdmap