c++ - 试图理解 libstdc++ 对 std::multiset 的实现

Question

我试图查看 libstdc++ 对 std::multiset 的实现(只是因为我很好奇)，我发现了这一行 https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_multiset.h#L118 ，并且不知道该怎么做。按照我的理解，_Rb_tree class是一个单一的元素树，那条线是如何把它变成一个多重集的？

按照我的理解，该行只是为另一种类型调整分配器。还是我误解得很厉害？

---

这是链接代码

private:
  /// This turns a red-black tree into a [multi]set.
  typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
rebind<_Key>::other _Key_alloc_type;

  typedef _Rb_tree<key_type, value_type, _Identity<value_type>,
           key_compare, _Key_alloc_type> _Rep_type;
  /// The actual tree structure.
  _Rep_type _M_t;

Answer 1

_Rb_tree 不决定是否允许重复值；它甚至不知道它是否只有一个值或一个单独的键和值(当用作 map 时，它从 pair 中派生出一个键)。该评论仅表示正在选择模板参数，这使得 _Rb_tree 可用作集合或多重集。文件前面的评论指出

The private tree data is declared exactly the same way for set and
multiset; the distinction is made entirely in how the tree functions are
called (*_unique versus *_equal, same as the standard).