1 // Debugging set implementation -*- C++ -*- 2 3 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2009 4 // Free Software Foundation, Inc. 5 // 6 // This file is part of the GNU ISO C++ Library. This library is free 7 // software; you can redistribute it and/or modify it under the 8 // terms of the GNU General Public License as published by the 9 // Free Software Foundation; either version 3, or (at your option) 10 // any later version. 11 12 // This library is distributed in the hope that it will be useful, 13 // but WITHOUT ANY WARRANTY; without even the implied warranty of 14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 // GNU General Public License for more details. 16 17 // Under Section 7 of GPL version 3, you are granted additional 18 // permissions described in the GCC Runtime Library Exception, version 19 // 3.1, as published by the Free Software Foundation. 20 21 // You should have received a copy of the GNU General Public License and 22 // a copy of the GCC Runtime Library Exception along with this program; 23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 24 // <http://www.gnu.org/licenses/>. 25 26 /** @file debug/set.h 27 * This file is a GNU debug extension to the Standard C++ Library. 28 */ 29 30 #ifndef _GLIBCXX_DEBUG_SET_H 31 #define _GLIBCXX_DEBUG_SET_H 1 32 33 #include <debug/safe_sequence.h> 34 #include <debug/safe_iterator.h> 35 #include <utility> 36 37 namespace std 38 { 39 namespace __debug 40 { 41 template<typename _Key, typename _Compare = std::less<_Key>, 42 typename _Allocator = std::allocator<_Key> > 43 class set 44 : public _GLIBCXX_STD_D::set<_Key,_Compare,_Allocator>, 45 public __gnu_debug::_Safe_sequence<set<_Key, _Compare, _Allocator> > 46 { 47 typedef _GLIBCXX_STD_D::set<_Key, _Compare, _Allocator> _Base; 48 typedef __gnu_debug::_Safe_sequence<set> _Safe_base; 49 50 public: 51 // types: 52 typedef _Key key_type; 53 typedef _Key value_type; 54 typedef _Compare key_compare; 55 typedef _Compare value_compare; 56 typedef _Allocator allocator_type; 57 typedef typename _Base::reference reference; 58 typedef typename _Base::const_reference const_reference; 59 60 typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, set> 61 iterator; 62 typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, set> 63 const_iterator; 64 65 typedef typename _Base::size_type size_type; 66 typedef typename _Base::difference_type difference_type; 67 typedef typename _Base::pointer pointer; 68 typedef typename _Base::const_pointer const_pointer; 69 typedef std::reverse_iterator<iterator> reverse_iterator; 70 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 71 72 // 23.3.3.1 construct/copy/destroy: 73 explicit set(const _Compare& __comp = _Compare(), 74 const _Allocator& __a = _Allocator()) 75 : _Base(__comp, __a) { } 76 77 template<typename _InputIterator> 78 set(_InputIterator __first, _InputIterator __last, 79 const _Compare& __comp = _Compare(), 80 const _Allocator& __a = _Allocator()) 81 : _Base(__gnu_debug::__check_valid_range(__first, __last), __last, 82 __comp, __a) { } 83 84 set(const set& __x) 85 : _Base(__x), _Safe_base() { } 86 87 set(const _Base& __x) 88 : _Base(__x), _Safe_base() { } 89 90 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 91 set(set&& __x) 92 : _Base(std::forward<set>(__x)), _Safe_base() 93 { this->_M_swap(__x); } 94 95 set(initializer_list<value_type> __l, 96 const _Compare& __comp = _Compare(), 97 const allocator_type& __a = allocator_type()) 98 : _Base(__l, __comp, __a), _Safe_base() { } 99 #endif 100 101 ~set() { } 102 103 set& 104 operator=(const set& __x) 105 { 106 *static_cast<_Base*>(this) = __x; 107 this->_M_invalidate_all(); 108 return *this; 109 } 110 111 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 112 set& 113 operator=(set&& __x) 114 { 115 // NB: DR 675. 116 clear(); 117 swap(__x); 118 return *this; 119 } 120 121 set& 122 operator=(initializer_list<value_type> __l) 123 { 124 this->clear(); 125 this->insert(__l); 126 return *this; 127 } 128 #endif 129 130 using _Base::get_allocator; 131 132 // iterators: 133 iterator 134 begin() 135 { return iterator(_Base::begin(), this); } 136 137 const_iterator 138 begin() const 139 { return const_iterator(_Base::begin(), this); } 140 141 iterator 142 end() 143 { return iterator(_Base::end(), this); } 144 145 const_iterator 146 end() const 147 { return const_iterator(_Base::end(), this); } 148 149 reverse_iterator 150 rbegin() 151 { return reverse_iterator(end()); } 152 153 const_reverse_iterator 154 rbegin() const 155 { return const_reverse_iterator(end()); } 156 157 reverse_iterator 158 rend() 159 { return reverse_iterator(begin()); } 160 161 const_reverse_iterator 162 rend() const 163 { return const_reverse_iterator(begin()); } 164 165 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 166 const_iterator 167 cbegin() const 168 { return const_iterator(_Base::begin(), this); } 169 170 const_iterator 171 cend() const 172 { return const_iterator(_Base::end(), this); } 173 174 const_reverse_iterator 175 crbegin() const 176 { return const_reverse_iterator(end()); } 177 178 const_reverse_iterator 179 crend() const 180 { return const_reverse_iterator(begin()); } 181 #endif 182 183 // capacity: 184 using _Base::empty; 185 using _Base::size; 186 using _Base::max_size; 187 188 // modifiers: 189 std::pair<iterator, bool> 190 insert(const value_type& __x) 191 { 192 typedef typename _Base::iterator _Base_iterator; 193 std::pair<_Base_iterator, bool> __res = _Base::insert(__x); 194 return std::pair<iterator, bool>(iterator(__res.first, this), 195 __res.second); 196 } 197 198 iterator 199 insert(iterator __position, const value_type& __x) 200 { 201 __glibcxx_check_insert(__position); 202 return iterator(_Base::insert(__position.base(), __x), this); 203 } 204 205 template <typename _InputIterator> 206 void 207 insert(_InputIterator __first, _InputIterator __last) 208 { 209 __glibcxx_check_valid_range(__first, __last); 210 _Base::insert(__first, __last); 211 } 212 213 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 214 void 215 insert(initializer_list<value_type> __l) 216 { _Base::insert(__l); } 217 #endif 218 219 void 220 erase(iterator __position) 221 { 222 __glibcxx_check_erase(__position); 223 __position._M_invalidate(); 224 _Base::erase(__position.base()); 225 } 226 227 size_type 228 erase(const key_type& __x) 229 { 230 iterator __victim = find(__x); 231 if (__victim == end()) 232 return 0; 233 else 234 { 235 __victim._M_invalidate(); 236 _Base::erase(__victim.base()); 237 return 1; 238 } 239 } 240 241 void 242 erase(iterator __first, iterator __last) 243 { 244 // _GLIBCXX_RESOLVE_LIB_DEFECTS 245 // 151. can't currently clear() empty container 246 __glibcxx_check_erase_range(__first, __last); 247 248 while (__first != __last) 249 this->erase(__first++); 250 } 251 252 void 253 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 254 swap(set&& __x) 255 #else 256 swap(set& __x) 257 #endif 258 { 259 _Base::swap(__x); 260 this->_M_swap(__x); 261 } 262 263 void 264 clear() 265 { this->erase(begin(), end()); } 266 267 // observers: 268 using _Base::key_comp; 269 using _Base::value_comp; 270 271 // set operations: 272 iterator 273 find(const key_type& __x) 274 { return iterator(_Base::find(__x), this); } 275 276 // _GLIBCXX_RESOLVE_LIB_DEFECTS 277 // 214. set::find() missing const overload 278 const_iterator 279 find(const key_type& __x) const 280 { return const_iterator(_Base::find(__x), this); } 281 282 using _Base::count; 283 284 iterator 285 lower_bound(const key_type& __x) 286 { return iterator(_Base::lower_bound(__x), this); } 287 288 // _GLIBCXX_RESOLVE_LIB_DEFECTS 289 // 214. set::find() missing const overload 290 const_iterator 291 lower_bound(const key_type& __x) const 292 { return const_iterator(_Base::lower_bound(__x), this); } 293 294 iterator 295 upper_bound(const key_type& __x) 296 { return iterator(_Base::upper_bound(__x), this); } 297 298 // _GLIBCXX_RESOLVE_LIB_DEFECTS 299 // 214. set::find() missing const overload 300 const_iterator 301 upper_bound(const key_type& __x) const 302 { return const_iterator(_Base::upper_bound(__x), this); } 303 304 std::pair<iterator,iterator> 305 equal_range(const key_type& __x) 306 { 307 typedef typename _Base::iterator _Base_iterator; 308 std::pair<_Base_iterator, _Base_iterator> __res = 309 _Base::equal_range(__x); 310 return std::make_pair(iterator(__res.first, this), 311 iterator(__res.second, this)); 312 } 313 314 // _GLIBCXX_RESOLVE_LIB_DEFECTS 315 // 214. set::find() missing const overload 316 std::pair<const_iterator,const_iterator> 317 equal_range(const key_type& __x) const 318 { 319 typedef typename _Base::const_iterator _Base_iterator; 320 std::pair<_Base_iterator, _Base_iterator> __res = 321 _Base::equal_range(__x); 322 return std::make_pair(const_iterator(__res.first, this), 323 const_iterator(__res.second, this)); 324 } 325 326 _Base& 327 _M_base() { return *this; } 328 329 const _Base& 330 _M_base() const { return *this; } 331 332 private: 333 void 334 _M_invalidate_all() 335 { 336 typedef typename _Base::const_iterator _Base_const_iterator; 337 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal; 338 this->_M_invalidate_if(_Not_equal(_M_base().end())); 339 } 340 }; 341 342 template<typename _Key, typename _Compare, typename _Allocator> 343 inline bool 344 operator==(const set<_Key, _Compare, _Allocator>& __lhs, 345 const set<_Key, _Compare, _Allocator>& __rhs) 346 { return __lhs._M_base() == __rhs._M_base(); } 347 348 template<typename _Key, typename _Compare, typename _Allocator> 349 inline bool 350 operator!=(const set<_Key, _Compare, _Allocator>& __lhs, 351 const set<_Key, _Compare, _Allocator>& __rhs) 352 { return __lhs._M_base() != __rhs._M_base(); } 353 354 template<typename _Key, typename _Compare, typename _Allocator> 355 inline bool 356 operator<(const set<_Key, _Compare, _Allocator>& __lhs, 357 const set<_Key, _Compare, _Allocator>& __rhs) 358 { return __lhs._M_base() < __rhs._M_base(); } 359 360 template<typename _Key, typename _Compare, typename _Allocator> 361 inline bool 362 operator<=(const set<_Key, _Compare, _Allocator>& __lhs, 363 const set<_Key, _Compare, _Allocator>& __rhs) 364 { return __lhs._M_base() <= __rhs._M_base(); } 365 366 template<typename _Key, typename _Compare, typename _Allocator> 367 inline bool 368 operator>=(const set<_Key, _Compare, _Allocator>& __lhs, 369 const set<_Key, _Compare, _Allocator>& __rhs) 370 { return __lhs._M_base() >= __rhs._M_base(); } 371 372 template<typename _Key, typename _Compare, typename _Allocator> 373 inline bool 374 operator>(const set<_Key, _Compare, _Allocator>& __lhs, 375 const set<_Key, _Compare, _Allocator>& __rhs) 376 { return __lhs._M_base() > __rhs._M_base(); } 377 378 template<typename _Key, typename _Compare, typename _Allocator> 379 void 380 swap(set<_Key, _Compare, _Allocator>& __x, 381 set<_Key, _Compare, _Allocator>& __y) 382 { return __x.swap(__y); } 383 384 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 385 template<typename _Key, typename _Compare, typename _Allocator> 386 void 387 swap(set<_Key, _Compare, _Allocator>&& __x, 388 set<_Key, _Compare, _Allocator>& __y) 389 { return __x.swap(__y); } 390 391 template<typename _Key, typename _Compare, typename _Allocator> 392 void 393 swap(set<_Key, _Compare, _Allocator>& __x, 394 set<_Key, _Compare, _Allocator>&& __y) 395 { return __x.swap(__y); } 396 #endif 397 398 } // namespace __debug 399 } // namespace std 400 401 #endif 402
