1 /* 2 * 3 * Copyright (c) 1994 4 * Hewlett-Packard Company 5 * 6 * Permission to use, copy, modify, distribute and sell this software 7 * and its documentation for any purpose is hereby granted without fee, 8 * provided that the above copyright notice appear in all copies and 9 * that both that copyright notice and this permission notice appear 10 * in supporting documentation. Hewlett-Packard Company makes no 11 * representations about the suitability of this software for any 12 * purpose. It is provided "as is" without express or implied warranty. 13 * 14 * 15 * Copyright (c) 1996,1997 16 * Silicon Graphics Computer Systems, Inc. 17 * 18 * Permission to use, copy, modify, distribute and sell this software 19 * and its documentation for any purpose is hereby granted without fee, 20 * provided that the above copyright notice appear in all copies and 21 * that both that copyright notice and this permission notice appear 22 * in supporting documentation. Silicon Graphics makes no 23 * representations about the suitability of this software for any 24 * purpose. It is provided "as is" without express or implied warranty. 25 */ 26 27 /* NOTE: This is an internal header file, included by other STL headers. 28 * You should not attempt to use it directly. 29 */ 30 31 #ifndef __SGI_STL_INTERNAL_SET_H 32 #define __SGI_STL_INTERNAL_SET_H 33 34 __STL_BEGIN_NAMESPACE 35 36 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) 37 #pragma set woff 1174 38 #pragma set woff 1375 39 #endif 40 41 #ifndef __STL_LIMITED_DEFAULT_TEMPLATES 42 template <class _Key, class _Compare = less<_Key>, 43 class _Alloc = __STL_DEFAULT_ALLOCATOR(_Key) > 44 #else 45 template <class _Key, class _Compare, 46 class _Alloc = __STL_DEFAULT_ALLOCATOR(_Key) > 47 #endif 48 class set { 49 public: 50 // typedefs: 51 52 typedef _Key key_type; 53 typedef _Key value_type; 54 typedef _Compare key_compare; 55 typedef _Compare value_compare; 56 private: 57 typedef _Rb_tree<key_type, value_type, 58 _Identity<value_type>, key_compare, _Alloc> _Rep_type; 59 _Rep_type _M_t; // red-black tree representing set 60 public: 61 typedef typename _Rep_type::const_pointer pointer; 62 typedef typename _Rep_type::const_pointer const_pointer; 63 typedef typename _Rep_type::const_reference reference; 64 typedef typename _Rep_type::const_reference const_reference; 65 typedef typename _Rep_type::const_iterator iterator; 66 typedef typename _Rep_type::const_iterator const_iterator; 67 typedef typename _Rep_type::const_reverse_iterator reverse_iterator; 68 typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator; 69 typedef typename _Rep_type::size_type size_type; 70 typedef typename _Rep_type::difference_type difference_type; 71 typedef typename _Rep_type::allocator_type allocator_type; 72 73 // allocation/deallocation 74 75 set() : _M_t(_Compare(), allocator_type()) {} 76 explicit set(const _Compare& __comp, 77 const allocator_type& __a = allocator_type()) 78 : _M_t(__comp, __a) {} 79 80 #ifdef __STL_MEMBER_TEMPLATES 81 template <class _InputIterator> 82 set(_InputIterator __first, _InputIterator __last) 83 : _M_t(_Compare(), allocator_type()) 84 { _M_t.insert_unique(__first, __last); } 85 86 template <class _InputIterator> 87 set(_InputIterator __first, _InputIterator __last, const _Compare& __comp, 88 const allocator_type& __a = allocator_type()) 89 : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); } 90 #else 91 set(const value_type* __first, const value_type* __last) 92 : _M_t(_Compare(), allocator_type()) 93 { _M_t.insert_unique(__first, __last); } 94 95 set(const value_type* __first, 96 const value_type* __last, const _Compare& __comp, 97 const allocator_type& __a = allocator_type()) 98 : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); } 99 100 set(const_iterator __first, const_iterator __last) 101 : _M_t(_Compare(), allocator_type()) 102 { _M_t.insert_unique(__first, __last); } 103 104 set(const_iterator __first, const_iterator __last, const _Compare& __comp, 105 const allocator_type& __a = allocator_type()) 106 : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); } 107 #endif /* __STL_MEMBER_TEMPLATES */ 108 109 set(const set<_Key,_Compare,_Alloc>& __x) : _M_t(__x._M_t) {} 110 set<_Key,_Compare,_Alloc>& operator=(const set<_Key, _Compare, _Alloc>& __x) 111 { 112 _M_t = __x._M_t; 113 return *this; 114 } 115 116 // accessors: 117 118 key_compare key_comp() const { return _M_t.key_comp(); } 119 value_compare value_comp() const { return _M_t.key_comp(); } 120 allocator_type get_allocator() const { return _M_t.get_allocator(); } 121 122 iterator begin() const { return _M_t.begin(); } 123 iterator end() const { return _M_t.end(); } 124 reverse_iterator rbegin() const { return _M_t.rbegin(); } 125 reverse_iterator rend() const { return _M_t.rend(); } 126 bool empty() const { return _M_t.empty(); } 127 size_type size() const { return _M_t.size(); } 128 size_type max_size() const { return _M_t.max_size(); } 129 void swap(set<_Key,_Compare,_Alloc>& __x) { _M_t.swap(__x._M_t); } 130 131 // insert/erase 132 pair<iterator,bool> insert(const value_type& __x) { 133 pair<typename _Rep_type::iterator, bool> __p = _M_t.insert_unique(__x); 134 return pair<iterator, bool>(__p.first, __p.second); 135 } 136 iterator insert(iterator __position, const value_type& __x) { 137 typedef typename _Rep_type::iterator _Rep_iterator; 138 return _M_t.insert_unique((_Rep_iterator&)__position, __x); 139 } 140 #ifdef __STL_MEMBER_TEMPLATES 141 template <class _InputIterator> 142 void insert(_InputIterator __first, _InputIterator __last) { 143 _M_t.insert_unique(__first, __last); 144 } 145 #else 146 void insert(const_iterator __first, const_iterator __last) { 147 _M_t.insert_unique(__first, __last); 148 } 149 void insert(const value_type* __first, const value_type* __last) { 150 _M_t.insert_unique(__first, __last); 151 } 152 #endif /* __STL_MEMBER_TEMPLATES */ 153 void erase(iterator __position) { 154 typedef typename _Rep_type::iterator _Rep_iterator; 155 _M_t.erase((_Rep_iterator&)__position); 156 } 157 size_type erase(const key_type& __x) { 158 return _M_t.erase(__x); 159 } 160 void erase(iterator __first, iterator __last) { 161 typedef typename _Rep_type::iterator _Rep_iterator; 162 _M_t.erase((_Rep_iterator&)__first, (_Rep_iterator&)__last); 163 } 164 void clear() { _M_t.clear(); } 165 166 // set operations: 167 168 iterator find(const key_type& __x) const { return _M_t.find(__x); } 169 size_type count(const key_type& __x) const { return _M_t.count(__x); } 170 iterator lower_bound(const key_type& __x) const { 171 return _M_t.lower_bound(__x); 172 } 173 iterator upper_bound(const key_type& __x) const { 174 return _M_t.upper_bound(__x); 175 } 176 pair<iterator,iterator> equal_range(const key_type& __x) const { 177 return _M_t.equal_range(__x); 178 } 179 friend bool operator== __STL_NULL_TMPL_ARGS (const set&, const set&); 180 friend bool operator< __STL_NULL_TMPL_ARGS (const set&, const set&); 181 }; 182 183 template <class _Key, class _Compare, class _Alloc> 184 inline bool operator==(const set<_Key,_Compare,_Alloc>& __x, 185 const set<_Key,_Compare,_Alloc>& __y) { 186 return __x._M_t == __y._M_t; 187 } 188 189 template <class _Key, class _Compare, class _Alloc> 190 inline bool operator<(const set<_Key,_Compare,_Alloc>& __x, 191 const set<_Key,_Compare,_Alloc>& __y) { 192 return __x._M_t < __y._M_t; 193 } 194 195 #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER 196 197 template <class _Key, class _Compare, class _Alloc> 198 inline void swap(set<_Key,_Compare,_Alloc>& __x, 199 set<_Key,_Compare,_Alloc>& __y) { 200 __x.swap(__y); 201 } 202 203 #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */ 204 205 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) 206 #pragma reset woff 1174 207 #pragma reset woff 1375 208 #endif 209 210 __STL_END_NAMESPACE 211 212 #endif /* __SGI_STL_INTERNAL_SET_H */ 213 214 // Local Variables: 215 // mode:C++ 216 // End: 217