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