为何std::set/std::map未高效利用三路比较运算符operator<=>？

核心原因 #

• 历史兼容包袱重：std::set自C++98起的底层实现逻辑就基于严格弱序的二元比较规则，默认使用std::less<T>作为比较器，元素等价性判断固定为!(a < b) && !(b < a)，底层红黑树的插入、查找、平衡逻辑全部围绕二元比较设计，这套逻辑已经沿用了二十余年，现有大量存量代码依赖该行为。如果要重构为三路比较逻辑，需要全量重写关联容器底层实现，还要保证旧代码行为完全一致，改动成本和风险都极高，标准委员会和标准库厂商都没有动力做这种量级的改造。
• C++标准无强制要求：C20引入三路比较运算符时，仅补充了语法层面的默认比较支持，并未修改关联容器的比较器要求，也没有强制规定标准库必须针对三路比较做性能优化。目前主流的STL实现（libstdc、libc++、MSVC STL）均未针对支持三路比较的类型单独优化set的操作逻辑，所以运行时还是按照旧的二元比较逻辑执行，自然会产生冗余的operator<=>调用。

测试用例说明 #

测试代码如下：

#include <iostream>
#include <set>

struct foo {
    foo (int i) : i {i} {}
    auto operator<=> (const foo& other) const {
      std::cout << "Call (" << i << "," << other.i << ")" << std::endl;
      return i <=> other.i;
    }
    int i = 0;
};

int main () {
  auto m = std::set <foo> ();

  m.insert (3);
  std::cout << "Inserting 8" << std::endl;
  m.insert (8);
  std::cout << "Checking 3" << std::endl;
  m.contains (3);
  std::cout << "Checking 8" << std::endl;
  m.contains (8);
  std::cout << "Checking 5" << std::endl;
  m.contains (5);
}

运行输出结果：

Inserting 8
Call (8,3)
Call (3,8)
Call (8,3)
Checking 3
Call (3,3)
Call (3,3)
Checking 8
Call (3,8)
Call (8,8)
Call (8,8)
Checking 5
Call (3,5)
Call (8,5)
Call (5,8)

你观察到的冗余调用完全符合现有STL的实现逻辑：比如插入8时，第一次比较判断大小确定插入方向，接下来两次比较是执行!(8 < 3) && !(3 < 8)判断元素是否重复，最后一次是红黑树平衡时的比较，所以总共3次调用。查找元素时的两次方向相反的比较，也是等价性判断的旧逻辑导致的。

内容的提问来源于stack exchange，提问作者Michaël