4 * Hewlett-Packard Company
6 * Copyright (c) 1996,1997
7 * Silicon Graphics Computer Systems, Inc.
10 * Moscow Center for SPARC Technology
15 * This material is provided "as is", with absolutely no warranty expressed
16 * or implied. Any use is at your own risk.
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.
26 /* NOTE: This is an internal header file, included by other STL headers.
27 * You should not attempt to use it directly.
30 #ifndef _STLP_INTERNAL_SET_H
31 #define _STLP_INTERNAL_SET_H
33 #ifndef _STLP_INTERNAL_TREE_H
34 # include <stl/_tree.h>
37 #if !defined (_STLP_USE_PTR_SPECIALIZATIONS)
41 //Specific iterator traits creation
42 _STLP_CREATE_ITERATOR_TRAITS(SetTraitsT, Const_traits)
44 template <class _Key, _STLP_DFL_TMPL_PARAM(_Compare, less<_Key>),
45 _STLP_DEFAULT_ALLOCATOR_SELECT(_Key) >
47 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND)
48 : public __stlport_class<set<_Key, _Compare, _Alloc> >
51 typedef set<_Key, _Compare, _Alloc> _Self;
54 typedef _Key key_type;
55 typedef _Key value_type;
56 typedef _Compare key_compare;
57 typedef _Compare value_compare;
60 //Specific iterator traits creation
61 typedef _STLP_PRIV _SetTraitsT<value_type> _SetTraits;
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;
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;
82 _Rep_type _M_t; // red-black tree representing set
83 _STLP_KEY_TYPE_FOR_CONT_EXT(key_type)
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())
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)
98 : _M_t(__comp, __a) {}
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); }
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); }
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); }
116 set(const value_type* __first, const value_type* __last)
117 : _M_t(_Compare(), allocator_type())
118 { _M_t.insert_unique(__first, __last); }
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); }
125 set(const_iterator __first, const_iterator __last)
126 : _M_t(_Compare(), allocator_type())
127 { _M_t.insert_unique(__first, __last); }
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 */
134 set(const _Self& __x) : _M_t(__x._M_t) {}
136 set(__move_source<_Self> src)
137 : _M_t(__move_source<_Rep_type>(src.get()._M_t)) {}
139 _Self& operator=(const _Self& __x) {
145 key_compare key_comp() const { return _M_t.key_comp(); }
146 value_compare value_comp() const { return _M_t.key_comp(); }
147 allocator_type get_allocator() const { return _M_t.get_allocator(); }
149 iterator begin() { return _M_t.begin(); }
150 iterator end() { return _M_t.end(); }
151 const_iterator begin() const { return _M_t.begin(); }
152 const_iterator end() const { return _M_t.end(); }
153 reverse_iterator rbegin() { return _M_t.rbegin(); }
154 reverse_iterator rend() { return _M_t.rend(); }
155 const_reverse_iterator rbegin() const { return _M_t.rbegin(); }
156 const_reverse_iterator rend() const { return _M_t.rend(); }
157 bool empty() const { return _M_t.empty(); }
158 size_type size() const { return _M_t.size(); }
159 size_type max_size() const { return _M_t.max_size(); }
160 void swap(_Self& __x) { _M_t.swap(__x._M_t); }
163 pair<iterator,bool> insert(const value_type& __x)
164 { return _M_t.insert_unique(__x); }
165 iterator insert(iterator __pos, const value_type& __x)
166 { return _M_t.insert_unique( __pos , __x); }
167 #if defined (_STLP_MEMBER_TEMPLATES)
168 template <class _InputIterator>
169 void insert(_InputIterator __first, _InputIterator __last)
170 { _M_t.insert_unique(__first, __last); }
172 void insert(const_iterator __first, const_iterator __last)
173 { _M_t.insert_unique(__first, __last); }
174 void insert(const value_type* __first, const value_type* __last)
175 { _M_t.insert_unique(__first, __last); }
176 #endif /* _STLP_MEMBER_TEMPLATES */
177 void erase(iterator __pos) { _M_t.erase( __pos ); }
178 size_type erase(const key_type& __x) { return _M_t.erase_unique(__x); }
179 void erase(iterator __first, iterator __last) { _M_t.erase(__first, __last ); }
180 void clear() { _M_t.clear(); }
183 _STLP_TEMPLATE_FOR_CONT_EXT
184 const_iterator find(const _KT& __x) const { return _M_t.find(__x); }
185 _STLP_TEMPLATE_FOR_CONT_EXT
186 iterator find(const _KT& __x) { return _M_t.find(__x); }
187 _STLP_TEMPLATE_FOR_CONT_EXT
188 size_type count(const _KT& __x) const
189 { return _M_t.find(__x) == _M_t.end() ? 0 : 1 ; }
190 _STLP_TEMPLATE_FOR_CONT_EXT
191 iterator lower_bound(const _KT& __x) { return _M_t.lower_bound(__x); }
192 _STLP_TEMPLATE_FOR_CONT_EXT
193 const_iterator lower_bound(const _KT& __x) const { return _M_t.lower_bound(__x); }
194 _STLP_TEMPLATE_FOR_CONT_EXT
195 iterator upper_bound(const _KT& __x) { return _M_t.upper_bound(__x); }
196 _STLP_TEMPLATE_FOR_CONT_EXT
197 const_iterator upper_bound(const _KT& __x) const { return _M_t.upper_bound(__x); }
198 _STLP_TEMPLATE_FOR_CONT_EXT
199 pair<iterator, iterator> equal_range(const _KT& __x)
200 { return _M_t.equal_range_unique(__x); }
201 _STLP_TEMPLATE_FOR_CONT_EXT
202 pair<const_iterator, const_iterator> equal_range(const _KT& __x) const
203 { return _M_t.equal_range_unique(__x); }
206 //Specific iterator traits creation
207 _STLP_CREATE_ITERATOR_TRAITS(MultisetTraitsT, Const_traits)
209 template <class _Key, _STLP_DFL_TMPL_PARAM(_Compare, less<_Key>),
210 _STLP_DEFAULT_ALLOCATOR_SELECT(_Key) >
212 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND)
213 : public __stlport_class<multiset<_Key, _Compare, _Alloc> >
216 typedef multiset<_Key, _Compare, _Alloc> _Self;
220 typedef _Key key_type;
221 typedef _Key value_type;
222 typedef _Compare key_compare;
223 typedef _Compare value_compare;
226 //Specific iterator traits creation
227 typedef _STLP_PRIV _MultisetTraitsT<value_type> _MultisetTraits;
230 //Following typedef have to be public for __move_traits specialization.
231 typedef _STLP_PRIV _Rb_tree<key_type, key_compare,
232 value_type, _STLP_PRIV _Identity<value_type>,
233 _MultisetTraits, _Alloc> _Rep_type;
235 typedef typename _Rep_type::pointer pointer;
236 typedef typename _Rep_type::const_pointer const_pointer;
237 typedef typename _Rep_type::reference reference;
238 typedef typename _Rep_type::const_reference const_reference;
239 typedef typename _Rep_type::iterator iterator;
240 typedef typename _Rep_type::const_iterator const_iterator;
241 typedef typename _Rep_type::reverse_iterator reverse_iterator;
242 typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
243 typedef typename _Rep_type::size_type size_type;
244 typedef typename _Rep_type::difference_type difference_type;
245 typedef typename _Rep_type::allocator_type allocator_type;
248 _Rep_type _M_t; // red-black tree representing multiset
249 _STLP_KEY_TYPE_FOR_CONT_EXT(key_type)
252 #if !defined (_STLP_DONT_SUP_DFLT_PARAM)
253 explicit multiset(const _Compare& __comp = _Compare(),
254 const allocator_type& __a = allocator_type())
257 : _M_t(_Compare(), allocator_type()) {}
258 explicit multiset(const _Compare& __comp)
259 : _M_t(__comp, allocator_type()) {}
260 multiset(const _Compare& __comp, const allocator_type& __a)
262 : _M_t(__comp, __a) {}
264 #if defined (_STLP_MEMBER_TEMPLATES)
265 template <class _InputIterator>
266 multiset(_InputIterator __first, _InputIterator __last)
267 : _M_t(_Compare(), allocator_type())
268 { _M_t.insert_equal(__first, __last); }
270 template <class _InputIterator>
271 multiset(_InputIterator __first, _InputIterator __last,
272 const _Compare& __comp,
273 const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL)
274 : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); }
275 # if defined (_STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS)
276 template <class _InputIterator>
277 multiset(_InputIterator __first, _InputIterator __last,
278 const _Compare& __comp)
279 : _M_t(__comp, allocator_type()) { _M_t.insert_equal(__first, __last); }
282 multiset(const value_type* __first, const value_type* __last)
283 : _M_t(_Compare(), allocator_type())
284 { _M_t.insert_equal(__first, __last); }
286 multiset(const value_type* __first, const value_type* __last,
287 const _Compare& __comp,
288 const allocator_type& __a = allocator_type())
289 : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); }
291 multiset(const_iterator __first, const_iterator __last)
292 : _M_t(_Compare(), allocator_type())
293 { _M_t.insert_equal(__first, __last); }
295 multiset(const_iterator __first, const_iterator __last,
296 const _Compare& __comp,
297 const allocator_type& __a = allocator_type())
298 : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); }
299 #endif /* _STLP_MEMBER_TEMPLATES */
301 multiset(const _Self& __x) : _M_t(__x._M_t) {}
302 _Self& operator=(const _Self& __x) {
307 multiset(__move_source<_Self> src)
308 : _M_t(__move_source<_Rep_type>(src.get()._M_t)) {}
311 key_compare key_comp() const { return _M_t.key_comp(); }
312 value_compare value_comp() const { return _M_t.key_comp(); }
313 allocator_type get_allocator() const { return _M_t.get_allocator(); }
315 iterator begin() { return _M_t.begin(); }
316 iterator end() { return _M_t.end(); }
317 const_iterator begin() const { return _M_t.begin(); }
318 const_iterator end() const { return _M_t.end(); }
319 reverse_iterator rbegin() { return _M_t.rbegin(); }
320 reverse_iterator rend() { return _M_t.rend(); }
321 const_reverse_iterator rbegin() const { return _M_t.rbegin(); }
322 const_reverse_iterator rend() const { return _M_t.rend(); }
323 bool empty() const { return _M_t.empty(); }
324 size_type size() const { return _M_t.size(); }
325 size_type max_size() const { return _M_t.max_size(); }
326 void swap(_Self& __x) { _M_t.swap(__x._M_t); }
329 iterator insert(const value_type& __x)
330 { return _M_t.insert_equal(__x); }
331 iterator insert(iterator __pos, const value_type& __x)
332 { return _M_t.insert_equal(__pos, __x); }
334 #if defined (_STLP_MEMBER_TEMPLATES)
335 template <class _InputIterator>
336 void insert(_InputIterator __first, _InputIterator __last)
337 { _M_t.insert_equal(__first, __last); }
339 void insert(const value_type* __first, const value_type* __last)
340 { _M_t.insert_equal(__first, __last); }
341 void insert(const_iterator __first, const_iterator __last)
342 { _M_t.insert_equal(__first, __last); }
343 #endif /* _STLP_MEMBER_TEMPLATES */
344 void erase(iterator __pos) { _M_t.erase( __pos ); }
345 size_type erase(const key_type& __x) { return _M_t.erase(__x); }
346 void erase(iterator __first, iterator __last) { _M_t.erase( __first, __last ); }
347 void clear() { _M_t.clear(); }
349 // multiset operations:
350 _STLP_TEMPLATE_FOR_CONT_EXT
351 iterator find(const _KT& __x) { return _M_t.find(__x); }
352 _STLP_TEMPLATE_FOR_CONT_EXT
353 const_iterator find(const _KT& __x) const { return _M_t.find(__x); }
354 _STLP_TEMPLATE_FOR_CONT_EXT
355 size_type count(const _KT& __x) const { return _M_t.count(__x); }
356 _STLP_TEMPLATE_FOR_CONT_EXT
357 iterator lower_bound(const _KT& __x) { return _M_t.lower_bound(__x); }
358 _STLP_TEMPLATE_FOR_CONT_EXT
359 const_iterator lower_bound(const _KT& __x) const { return _M_t.lower_bound(__x); }
360 _STLP_TEMPLATE_FOR_CONT_EXT
361 iterator upper_bound(const _KT& __x) { return _M_t.upper_bound(__x); }
362 _STLP_TEMPLATE_FOR_CONT_EXT
363 const_iterator upper_bound(const _KT& __x) const { return _M_t.upper_bound(__x); }
364 _STLP_TEMPLATE_FOR_CONT_EXT
365 pair<iterator, iterator> equal_range(const _KT& __x) { return _M_t.equal_range(__x); }
366 _STLP_TEMPLATE_FOR_CONT_EXT
367 pair<const_iterator, const_iterator> equal_range(const _KT& __x) const { return _M_t.equal_range(__x); }
371 # include <stl/pointers/_set.h>
372 _STLP_BEGIN_NAMESPACE
373 #endif /* _STLP_USE_PTR_SPECIALIZATIONS */
375 #define _STLP_TEMPLATE_HEADER template <class _Key, class _Compare, class _Alloc>
376 #define _STLP_TEMPLATE_CONTAINER set<_Key,_Compare,_Alloc>
377 #include <stl/_relops_cont.h>
378 #undef _STLP_TEMPLATE_CONTAINER
379 #define _STLP_TEMPLATE_CONTAINER multiset<_Key,_Compare,_Alloc>
380 #include <stl/_relops_cont.h>
381 #undef _STLP_TEMPLATE_CONTAINER
382 #undef _STLP_TEMPLATE_HEADER
384 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
385 template <class _Key, class _Compare, class _Alloc>
386 struct __move_traits<set<_Key,_Compare,_Alloc> > :
387 _STLP_PRIV __move_traits_aux<typename set<_Key,_Compare,_Alloc>::_Rep_type>
390 template <class _Key, class _Compare, class _Alloc>
391 struct __move_traits<multiset<_Key,_Compare,_Alloc> > :
392 _STLP_PRIV __move_traits_aux<typename multiset<_Key,_Compare,_Alloc>::_Rep_type>
394 #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
398 #endif /* _STLP_INTERNAL_SET_H */