umultiset.h

   1 // This file is part of the ustl library, an STL implementation.
   2 //
   3 // Copyright (C) 2005 by Mike Sharov <msharov@users.sourceforge.net>
   4 // This file is free software, distributed under the MIT License.
   5 //
   6 // umultiset.h
   7 //
   8
   9 #ifndef UMULTISET_H_446AEDBB7F61C6994DC228C25D5FA3A1
  10 #define UMULTISET_H_446AEDBB7F61C6994DC228C25D5FA3A1
  11
  12 #include "uvector.h"
  13 #include "ualgo.h"
  14
  15 namespace ustl {
  16
  17 /// \class multiset umultiset.h ustl.h
  18 /// \ingroup AssociativeContainers
  19 ///
  20 /// \brief Multiple sorted container.
  21 /// Unlike set, it may contain multiple copies of each element.
  22 ///
  23 template <typename T>
  24 class multiset : public vector<T> {
  25 public:
  26     typedef const multiset<T>&                          rcself_t;
  27     typedef vector<T>                                   base_class;
  28     typedef typename base_class::value_type             value_type;
  29     typedef typename base_class::size_type              size_type;
  30     typedef typename base_class::pointer                pointer;
  31     typedef typename base_class::const_pointer          const_pointer;
  32     typedef typename base_class::reference              reference;
  33     typedef typename base_class::const_reference        const_reference;
  34     typedef typename base_class::const_iterator         const_iterator;
  35     typedef typename base_class::iterator               iterator;
  36     typedef typename base_class::reverse_iterator       reverse_iterator;
  37     typedef typename base_class::const_reverse_iterator const_reverse_iterator;
  38 public:
  39     inline                      multiset (void)         : vector<T> () {}
  40     explicit inline             multiset (size_type n)  : vector<T> (n) {}
  41     inline                      multiset (rcself_t v)   : vector<T> (v) {}
  42     inline                      multiset (const_iterator i1, const_iterator i2) : vector<T> () { insert (i1, i2); }
  43     inline rcself_t             operator= (rcself_t v)  { base_class::operator= (v); return (*this); }
  44     inline size_type            size (void) const       { return (base_class::size()); }
  45     inline iterator             begin (void)            { return (base_class::begin()); }
  46     inline const_iterator       begin (void) const      { return (base_class::begin()); }
  47     inline iterator             end (void)              { return (base_class::end()); }
  48     inline const_iterator       end (void) const        { return (base_class::end()); }
  49     inline void                 assign (const_iterator i1, const_iterator i2);
  50     size_type                   count (const_reference v) const;
  51     inline void                 push_back (const_reference v)   { insert (v); }
  52     inline iterator             insert (const_reference v);
  53     void                        insert (const_iterator i1, const_iterator i2);
  54     void                        erase (const_reference v);
  55     inline iterator             erase (iterator ep)     { return (base_class::erase (ep)); }
  56     inline iterator             erase (iterator ep1, iterator ep2) { return (base_class::erase (ep1, ep2)); }
  57     inline void                 clear (void)            { base_class::clear(); }
  58 };
  59
  60 /// Copies contents of range [i1,i2)
  61 template <typename T>
  62 inline void multiset<T>::assign (const_iterator i1, const_iterator i2)
  63 {
  64     base_class::clear();
  65     insert (i1, i2);
  66 }
  67
  68 /// Returns the number of elements of value \p v.
  69 template <typename T>
  70 typename multiset<T>::size_type multiset<T>::count (const_reference v) const
  71 {
  72     const pair<const_iterator,const_iterator> fr = equal_range (begin(), end(), v);
  73     return (distance (fr.first, fr.second));
  74 }
  75
  76 /// Inserts \p v.
  77 template <typename T>
  78 inline typename multiset<T>::iterator multiset<T>::insert (const_reference v)
  79 {
  80     iterator ip = upper_bound (begin(), end(), v);
  81     return (base_class::insert (ip, v));
  82 }
  83
  84 /// Inserts all elements from range [i1,i2).
  85 template <typename T>
  86 void multiset<T>::insert (const_iterator i1, const_iterator i2)
  87 {
  88     assert (i1 <= i2);
  89     reserve (size() + distance (i1, i2));
  90     for (; i1 < i2; ++i1)
  91         push_back (*i1);
  92 }
  93
  94 /// Erases all elements with value \p v.
  95 template <typename T>
  96 void multiset<T>::erase (const_reference v)
  97 {
  98     pair<iterator,iterator> epr = equal_range (begin(), end(), v);
  99     erase (epr.first, epr.second);
 100 }
 101
 102 } // namespace ustl
 103
 104 #endif
 105