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 // uset.h 7 // 8 9 #ifndef USET_H_45543F516E02A87A3FCEA5024052A6F5 10 #define USET_H_45543F516E02A87A3FCEA5024052A6F5 11 12 #include "uassert.h" 13 #include "uvector.h" 14 15 namespace ustl { 16 17 /// \class set uset.h ustl.h 18 /// \ingroup Sequences 19 /// 20 /// \brief Unique sorted container. Sorted vector with all values unique. 21 /// 22 template <typename T> 23 class set : public vector<T> { 24 public: 25 typedef const set<T>& rcself_t; 26 typedef vector<T> base_class; 27 typedef typename base_class::value_type key_type; 28 typedef typename base_class::value_type data_type; 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 set (void) : vector<T> () { } 41 explicit inline set (size_type n) : vector<T> (n) { } 42 inline set (rcself_t v) : vector<T> (v) { } 43 inline set (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) { clear(); insert (i1, i2); } 51 inline void push_back (const_reference v) { insert (v); } 52 inline const_iterator find (const_reference v) const { return (binary_search (begin(), end(), v)); } 53 inline iterator find (const_reference v) { return (const_cast<iterator>(const_cast<rcself_t>(*this).find (v))); } 54 iterator insert (const_reference v); 55 inline void insert (const_iterator i1, const_iterator i2); 56 inline void erase (const_reference v); 57 inline iterator erase (iterator ep) { return (base_class::erase (ep)); } 58 inline iterator erase (iterator ep1, iterator ep2) { return (base_class::erase (ep1, ep2)); } 59 inline void clear (void) { base_class::clear(); } 60 }; 61 62 /// Inserts \p v into the container, maintaining the sort order. 63 template <typename T> 64 typename set<T>::iterator set<T>::insert (const_reference v) 65 { 66 iterator ip = lower_bound (begin(), end(), v); 67 if (ip == end() || v < *ip) 68 ip = base_class::insert (ip, v); 69 else 70 *ip = v; 71 return (ip); 72 } 73 74 /// Inserts the contents of range [i1,i2) 75 template <typename T> 76 void set<T>::insert (const_iterator i1, const_iterator i2) 77 { 78 assert (i1 <= i2); 79 reserve (size() + distance (i1, i2)); 80 for (; i1 < i2; ++i1) 81 push_back (*i1); 82 } 83 84 /// Erases the element with value \p v. 85 template <typename T> 86 inline void set<T>::erase (const_reference v) 87 { 88 iterator ip = find (v); 89 if (ip != end()) 90 erase (ip); 91 } 92 93 94 } // namespace ustl 95 96 #endif 97 98
