How does multiset store duplicate elements?

Question

I know that in c++, the Set template stores the elements as a balanced red black tree. But I would like to know how would multiset store duplicate element. For example, it could store 1,1,2,3 as the following

or as

The internals of map and set are not fixed, but the traditional implementation is a balanced red-black tree. — Gem Taylor, Jun 22 '18 at 11:33
@Ron But that would make the implementation of the iterator much more difficult than allowing multiples. — Gem Taylor, Jun 22 '18 at 11:36
@Ron I think they are stored as trees. https://stackoverflow.com/questions/1237361/how-sets-multisets-maps-and-multimaps-work-internally — Himanshu Kumar, Jun 22 '18 at 11:36
@Ron `unordered_multiset` is not a tree, but `multiset` (probably) is — Caleth, Jun 22 '18 at 11:37
Hint: one of those diagrams is not a *balanced* tree, and the other *is* — Caleth, Jun 22 '18 at 11:40
@Caleth This is what I would like to know, is multiset stored as a balanced binary tree or just as a BST? — Himanshu Kumar, Jun 22 '18 at 11:44
Probably a red-black tree for unique elements with a list attached to any node that has duplicates. But as long as the time constraints are met implementations are allowed to do what they like. You need to look at the source for your implementation. — Richard Critten, Jun 22 '18 at 11:46
@RichardCritten I think this is the most probable solution. Thanks — Himanshu Kumar, Jun 22 '18 at 11:50

score 4 · Accepted Answer · answered Jun 22 '18 at 12:06

A sensible implementation of the standard library will have one data-structure implementing all four of map, multimap, set and multiset. The differences in public members boil down to "how do we compare value_type instances?" "what is the result of a duplicate insert?"

Because of the complexity requirements, it is generally a balanced binary tree.

As a sketch of how to adapt a BalancedTree:

template <typename Value, typename Compare, typename Allocator>
class BalancedTree { ... };

template<
    class Key,
    class T,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<std::pair<const Key, T> >
> class map
{
public:
  using value_type = std::pair<const Key, T>;
  class value_compare 
  { 
    value_compare(Compare c) : c(c) {}
    bool operator()( const value_type& lhs, const value_type& rhs ) const
    {
      return c(lhs.first, rhs.first);
    }
    Compare c;
  }

  std::pair<iterator, bool> insert(value_type vt)
  {
    node n(vt);
    auto pos = bt.insert_point(n);
    if (value_comp()(*pos, vt))
      return { bt.splice(pos, n), true };
    return { pos, false };
  }

private:
  BalancedTree<value_type, value_compare, Allocator> bt;
}

template<
    class T,
    class Compare = std::less<T>,
    class Allocator = std::allocator<T>
> class multi_set
{
public:
  using value_type = T;
  iterator insert(value_type vt)
  {
    node n(vt);
    auto pos = bt.insert_point(n);
    return bt.splice(pos, n);
  }

private:
  BalancedTree<T, Compare, Allocator> bt;
}

How does multiset store duplicate elements?

1 Answers1