1 // Set implementation -*- C++ -*- 2 3 // Copyright (C) 2001 Free Software Foundation, Inc. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the 7 // terms of the GNU General Public License as published by the 8 // Free Software Foundation; either version 2, or (at your option) 9 // any later version. 10 11 // This library is distributed in the hope that it will be useful, 12 // but WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 // GNU General Public License for more details. 15 16 // You should have received a copy of the GNU General Public License along 17 // with this library; see the file COPYING. If not, write to the Free 18 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 19 // USA. 20 21 // As a special exception, you may use this file as part of a free software 22 // library without restriction. Specifically, if other files instantiate 23 // templates or use macros or inline functions from this file, or you compile 24 // this file and link it with other files to produce an executable, this 25 // file does not by itself cause the resulting executable to be covered by 26 // the GNU General Public License. This exception does not however 27 // invalidate any other reasons why the executable file might be covered by 28 // the GNU General Public License. 29 30 /* 31 * 32 * Copyright (c) 1994 33 * Hewlett-Packard Company 34 * 35 * Permission to use, copy, modify, distribute and sell this software 36 * and its documentation for any purpose is hereby granted without fee, 37 * provided that the above copyright notice appear in all copies and 38 * that both that copyright notice and this permission notice appear 39 * in supporting documentation. Hewlett-Packard Company makes no 40 * representations about the suitability of this software for any 41 * purpose. It is provided "as is" without express or implied warranty. 42 * 43 * 44 * Copyright (c) 1996,1997 45 * Silicon Graphics Computer Systems, Inc. 46 * 47 * Permission to use, copy, modify, distribute and sell this software 48 * and its documentation for any purpose is hereby granted without fee, 49 * provided that the above copyright notice appear in all copies and 50 * that both that copyright notice and this permission notice appear 51 * in supporting documentation. Silicon Graphics makes no 52 * representations about the suitability of this software for any 53 * purpose. It is provided "as is" without express or implied warranty. 54 */ 55 56 /** @file stl_set.h 57 * This is an internal header file, included by other library headers. 58 * You should not attempt to use it directly. 59 */ 60 61 #ifndef __GLIBCPP_INTERNAL_SET_H 62 #define __GLIBCPP_INTERNAL_SET_H 63 64 #include <bits/concept_check.h> 65 66 namespace std 67 { 68 69 // Forward declarations of operators < and ==, needed for friend declaration. 70 71 template <class _Key, class _Compare = less<_Key>, 72 class _Alloc = allocator<_Key> > 73 class set; 74 75 template <class _Key, class _Compare, class _Alloc> 76 inline bool operator==(const set<_Key,_Compare,_Alloc>& __x, 77 const set<_Key,_Compare,_Alloc>& __y); 78 79 template <class _Key, class _Compare, class _Alloc> 80 inline bool operator<(const set<_Key,_Compare,_Alloc>& __x, 81 const set<_Key,_Compare,_Alloc>& __y); 82 83 84 template <class _Key, class _Compare, class _Alloc> 85 class set 86 { 87 // concept requirements 88 __glibcpp_class_requires(_Key, _SGIAssignableConcept) 89 __glibcpp_class_requires4(_Compare, bool, _Key, _Key, _BinaryFunctionConcept); 90 91 public: 92 // typedefs: 93 typedef _Key key_type; 94 typedef _Key value_type; 95 typedef _Compare key_compare; 96 typedef _Compare value_compare; 97 private: 98 typedef _Rb_tree<key_type, value_type, 99 _Identity<value_type>, key_compare, _Alloc> _Rep_type; 100 _Rep_type _M_t; // red-black tree representing set 101 public: 102 typedef typename _Rep_type::const_pointer pointer; 103 typedef typename _Rep_type::const_pointer const_pointer; 104 typedef typename _Rep_type::const_reference reference; 105 typedef typename _Rep_type::const_reference const_reference; 106 typedef typename _Rep_type::const_iterator iterator; 107 typedef typename _Rep_type::const_iterator const_iterator; 108 typedef typename _Rep_type::const_reverse_iterator reverse_iterator; 109 typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator; 110 typedef typename _Rep_type::size_type size_type; 111 typedef typename _Rep_type::difference_type difference_type; 112 typedef typename _Rep_type::allocator_type allocator_type; 113 114 // allocation/deallocation 115 116 set() : _M_t(_Compare(), allocator_type()) {} 117 explicit set(const _Compare& __comp, 118 const allocator_type& __a = allocator_type()) 119 : _M_t(__comp, __a) {} 120 121 template <class _InputIterator> 122 set(_InputIterator __first, _InputIterator __last) 123 : _M_t(_Compare(), allocator_type()) 124 { _M_t.insert_unique(__first, __last); } 125 126 template <class _InputIterator> 127 set(_InputIterator __first, _InputIterator __last, const _Compare& __comp, 128 const allocator_type& __a = allocator_type()) 129 : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); } 130 131 set(const set<_Key,_Compare,_Alloc>& __x) : _M_t(__x._M_t) {} 132 set<_Key,_Compare,_Alloc>& operator=(const set<_Key, _Compare, _Alloc>& __x) 133 { 134 _M_t = __x._M_t; 135 return *this; 136 } 137 138 // accessors: 139 140 key_compare key_comp() const { return _M_t.key_comp(); } 141 value_compare value_comp() const { return _M_t.key_comp(); } 142 allocator_type get_allocator() const { return _M_t.get_allocator(); } 143 144 iterator begin() const { return _M_t.begin(); } 145 iterator end() const { return _M_t.end(); } 146 reverse_iterator rbegin() const { return _M_t.rbegin(); } 147 reverse_iterator rend() const { return _M_t.rend(); } 148 bool empty() const { return _M_t.empty(); } 149 size_type size() const { return _M_t.size(); } 150 size_type max_size() const { return _M_t.max_size(); } 151 void swap(set<_Key,_Compare,_Alloc>& __x) { _M_t.swap(__x._M_t); } 152 153 // insert/erase 154 pair<iterator,bool> insert(const value_type& __x) { 155 pair<typename _Rep_type::iterator, bool> __p = _M_t.insert_unique(__x); 156 return pair<iterator, bool>(__p.first, __p.second); 157 } 158 iterator insert(iterator __position, const value_type& __x) { 159 typedef typename _Rep_type::iterator _Rep_iterator; 160 return _M_t.insert_unique((_Rep_iterator&)__position, __x); 161 } 162 template <class _InputIterator> 163 void insert(_InputIterator __first, _InputIterator __last) { 164 _M_t.insert_unique(__first, __last); 165 } 166 void erase(iterator __position) { 167 typedef typename _Rep_type::iterator _Rep_iterator; 168 _M_t.erase((_Rep_iterator&)__position); 169 } 170 size_type erase(const key_type& __x) { 171 return _M_t.erase(__x); 172 } 173 void erase(iterator __first, iterator __last) { 174 typedef typename _Rep_type::iterator _Rep_iterator; 175 _M_t.erase((_Rep_iterator&)__first, (_Rep_iterator&)__last); 176 } 177 void clear() { _M_t.clear(); } 178 179 // set operations: 180 181 size_type count(const key_type& __x) const { 182 return _M_t.find(__x) == _M_t.end() ? 0 : 1; 183 } 184 185 #ifdef _GLIBCPP_RESOLVE_LIB_DEFECTS 186 //214. set::find() missing const overload 187 iterator find(const key_type& __x) { return _M_t.find(__x); } 188 const_iterator find(const key_type& __x) const { return _M_t.find(__x); } 189 iterator lower_bound(const key_type& __x) { 190 return _M_t.lower_bound(__x); 191 } 192 const_iterator lower_bound(const key_type& __x) const { 193 return _M_t.lower_bound(__x); 194 } 195 iterator upper_bound(const key_type& __x) { 196 return _M_t.upper_bound(__x); 197 } 198 const_iterator upper_bound(const key_type& __x) const { 199 return _M_t.upper_bound(__x); 200 } 201 pair<iterator,iterator> equal_range(const key_type& __x) { 202 return _M_t.equal_range(__x); 203 } 204 pair<const_iterator,const_iterator> equal_range(const key_type& __x) const { 205 return _M_t.equal_range(__x); 206 } 207 #else 208 iterator find(const key_type& __x) const { return _M_t.find(__x); } 209 iterator lower_bound(const key_type& __x) const { 210 return _M_t.lower_bound(__x); 211 } 212 iterator upper_bound(const key_type& __x) const { 213 return _M_t.upper_bound(__x); 214 } 215 pair<iterator,iterator> equal_range(const key_type& __x) const { 216 return _M_t.equal_range(__x); 217 } 218 #endif 219 220 template <class _K1, class _C1, class _A1> 221 friend bool operator== (const set<_K1,_C1,_A1>&, const set<_K1,_C1,_A1>&); 222 template <class _K1, class _C1, class _A1> 223 friend bool operator< (const set<_K1,_C1,_A1>&, const set<_K1,_C1,_A1>&); 224 }; 225 226 template <class _Key, class _Compare, class _Alloc> 227 inline bool operator==(const set<_Key,_Compare,_Alloc>& __x, 228 const set<_Key,_Compare,_Alloc>& __y) { 229 return __x._M_t == __y._M_t; 230 } 231 232 template <class _Key, class _Compare, class _Alloc> 233 inline bool operator<(const set<_Key,_Compare,_Alloc>& __x, 234 const set<_Key,_Compare,_Alloc>& __y) { 235 return __x._M_t < __y._M_t; 236 } 237 238 template <class _Key, class _Compare, class _Alloc> 239 inline bool operator!=(const set<_Key,_Compare,_Alloc>& __x, 240 const set<_Key,_Compare,_Alloc>& __y) { 241 return !(__x == __y); 242 } 243 244 template <class _Key, class _Compare, class _Alloc> 245 inline bool operator>(const set<_Key,_Compare,_Alloc>& __x, 246 const set<_Key,_Compare,_Alloc>& __y) { 247 return __y < __x; 248 } 249 250 template <class _Key, class _Compare, class _Alloc> 251 inline bool operator<=(const set<_Key,_Compare,_Alloc>& __x, 252 const set<_Key,_Compare,_Alloc>& __y) { 253 return !(__y < __x); 254 } 255 256 template <class _Key, class _Compare, class _Alloc> 257 inline bool operator>=(const set<_Key,_Compare,_Alloc>& __x, 258 const set<_Key,_Compare,_Alloc>& __y) { 259 return !(__x < __y); 260 } 261 262 template <class _Key, class _Compare, class _Alloc> 263 inline void swap(set<_Key,_Compare,_Alloc>& __x, 264 set<_Key,_Compare,_Alloc>& __y) { 265 __x.swap(__y); 266 } 267 268 } // namespace std 269 270 #endif /* __GLIBCPP_INTERNAL_SET_H */ 271 272 // Local Variables: 273 // mode:C++ 274 // End: 275