std::(unordered_)map 和 std::(unordered_)set 共享代码吗？

Question

假设我关心二进制大小，我已经使用了

std::map

，并且我需要一套。我可以使用

std::set<T>

，而不是使用

std::map<T, bool>

。这会有帮助吗，或者通用代码已经在幕后使用了吗？

我怀疑 C++ 标准是否说了有关共享代码的内容，因此不同实现之间可能会有所不同，但我认为有一些常见的做法。

Answer 1

这是你必须测量和观察的事情。你是对的，

std::map<T, std::monostate>

比

std::map<T, U>

更类似于

std::set<T>

，因为底层比较必须通过

value.first

，而不是直接

value

。

Afaik，主要实现确实使用一个基类模板实现所有关联容器，并且类似地使用一个类模板实现所有无序关联容器。然而，这些都是模板，因此会产生不同数量的目标代码重用。

Answer 2

正如您所观察到的，这取决于实施。

也就是说，是的，至少在一些广泛使用的编译器（例如 gcc）中，set 和 map 使用共享实现。

例如，这是 gcc 用于 set 和 map 的底层红/黑树实现：

https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_tree.h

这是地图标题的使用部分：

      typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,
               key_compare, _Pair_alloc_type> _Rep_type;

      /// The actual tree structure.
      _Rep_type _M_t;