CODEWITHSUNDEEP
c++c++11gcclibstdc++multiset
Curious
Curious

Reputation: 21510

Trying to understand libstdc++'s implementation of std::multiset

I was trying to peek into libstdc++'s implementation of std::multiset (just because I was curious) and I found this line https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_multiset.h#L118, and didn't know what to make of it. The way I understand it, the _Rb_tree class is a single element tree, how does that line turn that into a multiset?

The way I understand it, that line is just adapting the allocator for another type. Or am I misunderstanding this terribly?

This is the linked code

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;

Upvotes: 2

Views: 291

Answers (1)

Davis Herring
Davis Herring

Reputation: 39818

_Rb_tree doesn't decide whether duplicate values are allowed; it doesn't even know whether it has just a value or a separate key and value (it derives a key from the pair when used as a map). The comment is merely indicating that template arguments are being chosen which make _Rb_tree useful as a set or multiset. Comments earlier in the file point out that

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).

Upvotes: 2

Related Questions