GCC中std::set基于stl_tree.h的节点键存储及重复存储疑问

答案很明确：std::set并不会存储两次相同的键，GCC的_Rb_tree通过模板参数的巧妙设计实现了无冗余的复用。

核心原理：_KeyOfValue适配器的作用 #

GCC的_Rb_tree类的模板参数里，除了_Key（键类型）和_Val（节点存储的值类型），还有一个关键参数_KeyOfValue——这是一个函数对象，负责从_Val中提取出用于比较、查找的_Key。

• 对于std::set：
  set的value_type直接就是key_type，所以实例化_Rb_tree时，_Val和_Key是同一个类型。此时_KeyOfValue用的是_Identity<_Key>，这个适配器的作用就是直接返回传入的_Val本身（也就是键）。所以红黑树的节点里只存储一份_Key，完全没有冗余。

• 对于std::map：
  map的value_type是std::pair<const Key, T>，此时_Key是Key，_Val是这个键值对。_KeyOfValue则使用_Select1st<std::pair<const Key, T>>，它的作用是从键值对中提取第一个元素（也就是const Key部分）作为查找、比较用的键。节点里存储的是完整的键值对，但红黑树的核心逻辑（比如平衡、查找）只依赖提取出的键，不需要额外存储单独的_Key。

这种设计的优势 #

通过_KeyOfValue这个“策略”模板参数，_Rb_tree把红黑树的核心逻辑（插入、删除、旋转、查找等）和“如何从存储值中获取键”的逻辑解耦了。不管_Val是单纯的键，还是键值对，红黑树的核心代码都不需要修改，只需要更换_KeyOfValue的实现就能适配不同的容器需求。

对你自己实现STL容器的启发：不需要单独写两个红黑树（一个存键，一个存键值对），只需要给红黑树模板增加一个“键提取器”参数，让它能从存储的value_type中获取键，就能同时支持set和map的实现，既复用代码又避免冗余存储。

内容的提问来源于stack exchange，提问作者edugomez102