1/* 2 * 3 * Copyright (c) 1994 4 * Hewlett-Packard Company 5 * 6 * Copyright (c) 1996,1997 7 * Silicon Graphics Computer Systems, Inc. 8 * 9 * Copyright (c) 1997 10 * Moscow Center for SPARC Technology 11 * 12 * Copyright (c) 1999 13 * Boris Fomitchev 14 * 15 * This material is provided "as is", with absolutely no warranty expressed 16 * or implied. Any use is at your own risk. 17 * 18 * Permission to use or copy this software for any purpose is hereby granted 19 * without fee, provided the above notices are retained on all copies. 20 * Permission to modify the code and to distribute modified code is granted, 21 * provided the above notices are retained, and a notice that the code was 22 * modified is included with the above copyright notice. 23 * 24 */ 25 26/* NOTE: This is an internal header file, included by other STL headers. 27 * You should not attempt to use it directly. 28 */ 29 30#ifndef _STLP_INTERNAL_SET_H 31#define _STLP_INTERNAL_SET_H 32 33#ifndef _STLP_INTERNAL_TREE_H 34# include <stl/_tree.h> 35#endif 36 37#if !defined (_STLP_USE_PTR_SPECIALIZATIONS) 38 39_STLP_BEGIN_NAMESPACE 40 41//Specific iterator traits creation 42_STLP_CREATE_ITERATOR_TRAITS(SetTraitsT, Const_traits) 43 44template <class _Key, _STLP_DFL_TMPL_PARAM(_Compare, less<_Key>), 45 _STLP_DFL_TMPL_PARAM(_Alloc, allocator<_Key>) > 46class set 47#if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) 48 : public __stlport_class<set<_Key, _Compare, _Alloc> > 49#endif 50{ 51 typedef set<_Key, _Compare, _Alloc> _Self; 52public: 53// typedefs: 54 typedef _Key key_type; 55 typedef _Key value_type; 56 typedef _Compare key_compare; 57 typedef _Compare value_compare; 58 59private: 60 //Specific iterator traits creation 61 typedef _STLP_PRIV _SetTraitsT<value_type> _SetTraits; 62 63public: 64 //Following typedef have to be public for __move_traits specialization. 65 typedef _STLP_PRIV _Rb_tree<key_type, key_compare, 66 value_type, _STLP_PRIV _Identity<value_type>, 67 _SetTraits, _Alloc> _Rep_type; 68 69 typedef typename _Rep_type::pointer pointer; 70 typedef typename _Rep_type::const_pointer const_pointer; 71 typedef typename _Rep_type::reference reference; 72 typedef typename _Rep_type::const_reference const_reference; 73 typedef typename _Rep_type::iterator iterator; 74 typedef typename _Rep_type::const_iterator const_iterator; 75 typedef typename _Rep_type::reverse_iterator reverse_iterator; 76 typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator; 77 typedef typename _Rep_type::size_type size_type; 78 typedef typename _Rep_type::difference_type difference_type; 79 typedef typename _Rep_type::allocator_type allocator_type; 80 81private: 82 _Rep_type _M_t; // red-black tree representing set 83 _STLP_KEY_TYPE_FOR_CONT_EXT(key_type) 84 85public: 86 87 // allocation/deallocation 88#if !defined (_STLP_DONT_SUP_DFLT_PARAM) 89 explicit set(const _Compare& __comp = _Compare(), 90 const allocator_type& __a = allocator_type()) 91#else 92 set() 93 : _M_t(_Compare(), allocator_type()) {} 94 explicit set(const _Compare& __comp) 95 : _M_t(__comp, allocator_type()) {} 96 set(const _Compare& __comp, const allocator_type& __a) 97#endif 98 : _M_t(__comp, __a) {} 99 100#if defined (_STLP_MEMBER_TEMPLATES) 101 template <class _InputIterator> 102 set(_InputIterator __first, _InputIterator __last) 103 : _M_t(_Compare(), allocator_type()) 104 { _M_t.insert_unique(__first, __last); } 105 106# if defined (_STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS) 107 template <class _InputIterator> 108 set(_InputIterator __first, _InputIterator __last, const _Compare& __comp) 109 : _M_t(__comp, allocator_type()) { _M_t.insert_unique(__first, __last); } 110# endif 111 template <class _InputIterator> 112 set(_InputIterator __first, _InputIterator __last, const _Compare& __comp, 113 const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL) 114 : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); } 115#else 116 set(const value_type* __first, const value_type* __last) 117 : _M_t(_Compare(), allocator_type()) 118 { _M_t.insert_unique(__first, __last); } 119 120 set(const value_type* __first, 121 const value_type* __last, const _Compare& __comp, 122 const allocator_type& __a = allocator_type()) 123 : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); } 124 125 set(const_iterator __first, const_iterator __last) 126 : _M_t(_Compare(), allocator_type()) 127 { _M_t.insert_unique(__first, __last); } 128 129 set(const_iterator __first, const_iterator __last, const _Compare& __comp, 130 const allocator_type& __a = allocator_type()) 131 : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); } 132#endif /* _STLP_MEMBER_TEMPLATES */ 133 134 set(const _Self& __x) : _M_t(__x._M_t) {} 135 136#if !defined (_STLP_NO_MOVE_SEMANTIC) 137 set(__move_source<_Self> src) 138 : _M_t(__move_source<_Rep_type>(src.get()._M_t)) {} 139#endif 140 141 _Self& operator=(const _Self& __x) { 142 _M_t = __x._M_t; 143 return *this; 144 } 145 146 // accessors: 147 key_compare key_comp() const { return _M_t.key_comp(); } 148 value_compare value_comp() const { return _M_t.key_comp(); } 149 allocator_type get_allocator() const { return _M_t.get_allocator(); } 150 151 iterator begin() { return _M_t.begin(); } 152 iterator end() { return _M_t.end(); } 153 const_iterator begin() const { return _M_t.begin(); } 154 const_iterator end() const { return _M_t.end(); } 155 reverse_iterator rbegin() { return _M_t.rbegin(); } 156 reverse_iterator rend() { return _M_t.rend(); } 157 const_reverse_iterator rbegin() const { return _M_t.rbegin(); } 158 const_reverse_iterator rend() const { return _M_t.rend(); } 159 bool empty() const { return _M_t.empty(); } 160 size_type size() const { return _M_t.size(); } 161 size_type max_size() const { return _M_t.max_size(); } 162 void swap(_Self& __x) { _M_t.swap(__x._M_t); } 163#if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER) 164 void _M_swap_workaround(_Self& __x) { swap(__x); } 165#endif 166 167 // insert/erase 168 pair<iterator,bool> insert(const value_type& __x) 169 { return _M_t.insert_unique(__x); } 170 iterator insert(iterator __pos, const value_type& __x) 171 { return _M_t.insert_unique( __pos , __x); } 172#if defined (_STLP_MEMBER_TEMPLATES) 173 template <class _InputIterator> 174 void insert(_InputIterator __first, _InputIterator __last) 175 { _M_t.insert_unique(__first, __last); } 176#else 177 void insert(const_iterator __first, const_iterator __last) 178 { _M_t.insert_unique(__first, __last); } 179 void insert(const value_type* __first, const value_type* __last) 180 { _M_t.insert_unique(__first, __last); } 181#endif /* _STLP_MEMBER_TEMPLATES */ 182 void erase(iterator __pos) { _M_t.erase( __pos ); } 183 size_type erase(const key_type& __x) { return _M_t.erase_unique(__x); } 184 void erase(iterator __first, iterator __last) { _M_t.erase(__first, __last ); } 185 void clear() { _M_t.clear(); } 186 187 // set operations: 188 _STLP_TEMPLATE_FOR_CONT_EXT 189 const_iterator find(const _KT& __x) const { return _M_t.find(__x); } 190 _STLP_TEMPLATE_FOR_CONT_EXT 191 iterator find(const _KT& __x) { return _M_t.find(__x); } 192 _STLP_TEMPLATE_FOR_CONT_EXT 193 size_type count(const _KT& __x) const 194 { return _M_t.find(__x) == _M_t.end() ? 0 : 1 ; } 195 _STLP_TEMPLATE_FOR_CONT_EXT 196 iterator lower_bound(const _KT& __x) { return _M_t.lower_bound(__x); } 197 _STLP_TEMPLATE_FOR_CONT_EXT 198 const_iterator lower_bound(const _KT& __x) const { return _M_t.lower_bound(__x); } 199 _STLP_TEMPLATE_FOR_CONT_EXT 200 iterator upper_bound(const _KT& __x) { return _M_t.upper_bound(__x); } 201 _STLP_TEMPLATE_FOR_CONT_EXT 202 const_iterator upper_bound(const _KT& __x) const { return _M_t.upper_bound(__x); } 203 _STLP_TEMPLATE_FOR_CONT_EXT 204 pair<iterator, iterator> equal_range(const _KT& __x) 205 { return _M_t.equal_range_unique(__x); } 206 _STLP_TEMPLATE_FOR_CONT_EXT 207 pair<const_iterator, const_iterator> equal_range(const _KT& __x) const 208 { return _M_t.equal_range_unique(__x); } 209}; 210 211//Specific iterator traits creation 212_STLP_CREATE_ITERATOR_TRAITS(MultisetTraitsT, Const_traits) 213 214template <class _Key, _STLP_DFL_TMPL_PARAM(_Compare, less<_Key>), 215 _STLP_DFL_TMPL_PARAM(_Alloc, allocator<_Key>) > 216class multiset 217#if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) 218 : public __stlport_class<multiset<_Key, _Compare, _Alloc> > 219#endif 220{ 221 typedef multiset<_Key, _Compare, _Alloc> _Self; 222public: 223 // typedefs: 224 225 typedef _Key key_type; 226 typedef _Key value_type; 227 typedef _Compare key_compare; 228 typedef _Compare value_compare; 229 230private: 231 //Specific iterator traits creation 232 typedef _STLP_PRIV _MultisetTraitsT<value_type> _MultisetTraits; 233 234public: 235 //Following typedef have to be public for __move_traits specialization. 236 typedef _STLP_PRIV _Rb_tree<key_type, key_compare, 237 value_type, _STLP_PRIV _Identity<value_type>, 238 _MultisetTraits, _Alloc> _Rep_type; 239 240 typedef typename _Rep_type::pointer pointer; 241 typedef typename _Rep_type::const_pointer const_pointer; 242 typedef typename _Rep_type::reference reference; 243 typedef typename _Rep_type::const_reference const_reference; 244 typedef typename _Rep_type::iterator iterator; 245 typedef typename _Rep_type::const_iterator const_iterator; 246 typedef typename _Rep_type::reverse_iterator reverse_iterator; 247 typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator; 248 typedef typename _Rep_type::size_type size_type; 249 typedef typename _Rep_type::difference_type difference_type; 250 typedef typename _Rep_type::allocator_type allocator_type; 251 252private: 253 _Rep_type _M_t; // red-black tree representing multiset 254 _STLP_KEY_TYPE_FOR_CONT_EXT(key_type) 255 256public: 257#if !defined (_STLP_DONT_SUP_DFLT_PARAM) 258 explicit multiset(const _Compare& __comp = _Compare(), 259 const allocator_type& __a = allocator_type()) 260#else 261 multiset() 262 : _M_t(_Compare(), allocator_type()) {} 263 explicit multiset(const _Compare& __comp) 264 : _M_t(__comp, allocator_type()) {} 265 multiset(const _Compare& __comp, const allocator_type& __a) 266#endif 267 : _M_t(__comp, __a) {} 268 269#if defined (_STLP_MEMBER_TEMPLATES) 270 template <class _InputIterator> 271 multiset(_InputIterator __first, _InputIterator __last) 272 : _M_t(_Compare(), allocator_type()) 273 { _M_t.insert_equal(__first, __last); } 274 275 template <class _InputIterator> 276 multiset(_InputIterator __first, _InputIterator __last, 277 const _Compare& __comp, 278 const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL) 279 : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); } 280# if defined (_STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS) 281 template <class _InputIterator> 282 multiset(_InputIterator __first, _InputIterator __last, 283 const _Compare& __comp) 284 : _M_t(__comp, allocator_type()) { _M_t.insert_equal(__first, __last); } 285# endif 286#else 287 multiset(const value_type* __first, const value_type* __last) 288 : _M_t(_Compare(), allocator_type()) 289 { _M_t.insert_equal(__first, __last); } 290 291 multiset(const value_type* __first, const value_type* __last, 292 const _Compare& __comp, 293 const allocator_type& __a = allocator_type()) 294 : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); } 295 296 multiset(const_iterator __first, const_iterator __last) 297 : _M_t(_Compare(), allocator_type()) 298 { _M_t.insert_equal(__first, __last); } 299 300 multiset(const_iterator __first, const_iterator __last, 301 const _Compare& __comp, 302 const allocator_type& __a = allocator_type()) 303 : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); } 304#endif /* _STLP_MEMBER_TEMPLATES */ 305 306 multiset(const _Self& __x) : _M_t(__x._M_t) {} 307 _Self& operator=(const _Self& __x) { 308 _M_t = __x._M_t; 309 return *this; 310 } 311 312#if !defined (_STLP_NO_MOVE_SEMANTIC) 313 multiset(__move_source<_Self> src) 314 : _M_t(__move_source<_Rep_type>(src.get()._M_t)) {} 315#endif 316 317 // accessors: 318 key_compare key_comp() const { return _M_t.key_comp(); } 319 value_compare value_comp() const { return _M_t.key_comp(); } 320 allocator_type get_allocator() const { return _M_t.get_allocator(); } 321 322 iterator begin() { return _M_t.begin(); } 323 iterator end() { return _M_t.end(); } 324 const_iterator begin() const { return _M_t.begin(); } 325 const_iterator end() const { return _M_t.end(); } 326 reverse_iterator rbegin() { return _M_t.rbegin(); } 327 reverse_iterator rend() { return _M_t.rend(); } 328 const_reverse_iterator rbegin() const { return _M_t.rbegin(); } 329 const_reverse_iterator rend() const { return _M_t.rend(); } 330 bool empty() const { return _M_t.empty(); } 331 size_type size() const { return _M_t.size(); } 332 size_type max_size() const { return _M_t.max_size(); } 333 void swap(_Self& __x) { _M_t.swap(__x._M_t); } 334#if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER) 335 void _M_swap_workaround(_Self& __x) { swap(__x); } 336#endif 337 338 // insert/erase 339 iterator insert(const value_type& __x) 340 { return _M_t.insert_equal(__x); } 341 iterator insert(iterator __pos, const value_type& __x) 342 { return _M_t.insert_equal(__pos, __x); } 343 344#if defined (_STLP_MEMBER_TEMPLATES) 345 template <class _InputIterator> 346 void insert(_InputIterator __first, _InputIterator __last) 347 { _M_t.insert_equal(__first, __last); } 348#else 349 void insert(const value_type* __first, const value_type* __last) 350 { _M_t.insert_equal(__first, __last); } 351 void insert(const_iterator __first, const_iterator __last) 352 { _M_t.insert_equal(__first, __last); } 353#endif /* _STLP_MEMBER_TEMPLATES */ 354 void erase(iterator __pos) { _M_t.erase( __pos ); } 355 size_type erase(const key_type& __x) { return _M_t.erase(__x); } 356 void erase(iterator __first, iterator __last) { _M_t.erase( __first, __last ); } 357 void clear() { _M_t.clear(); } 358 359 // multiset operations: 360 _STLP_TEMPLATE_FOR_CONT_EXT 361 iterator find(const _KT& __x) { return _M_t.find(__x); } 362 _STLP_TEMPLATE_FOR_CONT_EXT 363 const_iterator find(const _KT& __x) const { return _M_t.find(__x); } 364 _STLP_TEMPLATE_FOR_CONT_EXT 365 size_type count(const _KT& __x) const { return _M_t.count(__x); } 366 _STLP_TEMPLATE_FOR_CONT_EXT 367 iterator lower_bound(const _KT& __x) { return _M_t.lower_bound(__x); } 368 _STLP_TEMPLATE_FOR_CONT_EXT 369 const_iterator lower_bound(const _KT& __x) const { return _M_t.lower_bound(__x); } 370 _STLP_TEMPLATE_FOR_CONT_EXT 371 iterator upper_bound(const _KT& __x) { return _M_t.upper_bound(__x); } 372 _STLP_TEMPLATE_FOR_CONT_EXT 373 const_iterator upper_bound(const _KT& __x) const { return _M_t.upper_bound(__x); } 374 _STLP_TEMPLATE_FOR_CONT_EXT 375 pair<iterator, iterator> equal_range(const _KT& __x) { return _M_t.equal_range(__x); } 376 _STLP_TEMPLATE_FOR_CONT_EXT 377 pair<const_iterator, const_iterator> equal_range(const _KT& __x) const { return _M_t.equal_range(__x); } 378}; 379 380#else 381# include <stl/pointers/_set.h> 382_STLP_BEGIN_NAMESPACE 383#endif /* _STLP_USE_PTR_SPECIALIZATIONS */ 384 385#define _STLP_TEMPLATE_HEADER template <class _Key, class _Compare, class _Alloc> 386#define _STLP_TEMPLATE_CONTAINER set<_Key,_Compare,_Alloc> 387#include <stl/_relops_cont.h> 388#undef _STLP_TEMPLATE_CONTAINER 389#define _STLP_TEMPLATE_CONTAINER multiset<_Key,_Compare,_Alloc> 390#include <stl/_relops_cont.h> 391#undef _STLP_TEMPLATE_CONTAINER 392#undef _STLP_TEMPLATE_HEADER 393 394#if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) && !defined (_STLP_NO_MOVE_SEMANTIC) 395template <class _Key, class _Compare, class _Alloc> 396struct __move_traits<set<_Key,_Compare,_Alloc> > : 397 _STLP_PRIV __move_traits_aux<typename set<_Key,_Compare,_Alloc>::_Rep_type> 398{}; 399 400template <class _Key, class _Compare, class _Alloc> 401struct __move_traits<multiset<_Key,_Compare,_Alloc> > : 402 _STLP_PRIV __move_traits_aux<typename multiset<_Key,_Compare,_Alloc>::_Rep_type> 403{}; 404#endif 405 406_STLP_END_NAMESPACE 407 408#endif /* _STLP_INTERNAL_SET_H */ 409 410// Local Variables: 411// mode:C++ 412// End: 413