blob: 11ea9658bd6a5e93b72cf69cd04e7ff8223b3b64 [file] [log] [blame]
Howard Hinnantbc8d3f92010-05-11 19:42:161// -*- C++ -*-
2//===---------------------------- set -------------------------------------===//
3//
Howard Hinnantf5256e12010-05-11 21:36:014// The LLVM Compiler Infrastructure
Howard Hinnantbc8d3f92010-05-11 19:42:165//
Howard Hinnantb64f8b02010-11-16 22:09:026// This file is dual licensed under the MIT and the University of Illinois Open
7// Source Licenses. See LICENSE.TXT for details.
Howard Hinnantbc8d3f92010-05-11 19:42:168//
9//===----------------------------------------------------------------------===//
10
11#ifndef _LIBCPP_SET
12#define _LIBCPP_SET
13
14/*
15
16 set synopsis
17
18namespace std
19{
20
21template <class Key, class Compare = less<Key>,
22 class Allocator = allocator<Key>>
23class set
24{
25public:
26 // types:
27 typedef Key key_type;
28 typedef key_type value_type;
29 typedef Compare key_compare;
30 typedef key_compare value_compare;
31 typedef Allocator allocator_type;
32 typedef typename allocator_type::reference reference;
33 typedef typename allocator_type::const_reference const_reference;
34 typedef typename allocator_type::size_type size_type;
35 typedef typename allocator_type::difference_type difference_type;
36 typedef typename allocator_type::pointer pointer;
37 typedef typename allocator_type::const_pointer const_pointer;
38
39 typedef implementation-defined iterator;
40 typedef implementation-defined const_iterator;
41 typedef std::reverse_iterator<iterator> reverse_iterator;
42 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
43
44 // construct/copy/destroy:
Howard Hinnantb2e2a8f2011-06-04 15:22:3445 set()
46 noexcept(
47 is_nothrow_default_constructible<allocator_type>::value &&
48 is_nothrow_default_constructible<key_compare>::value &&
49 is_nothrow_copy_constructible<key_compare>::value);
50 explicit set(const value_compare& comp);
Howard Hinnantbc8d3f92010-05-11 19:42:1651 set(const value_compare& comp, const allocator_type& a);
52 template <class InputIterator>
53 set(InputIterator first, InputIterator last,
54 const value_compare& comp = value_compare());
55 template <class InputIterator>
56 set(InputIterator first, InputIterator last, const value_compare& comp,
57 const allocator_type& a);
58 set(const set& s);
Howard Hinnantb2e2a8f2011-06-04 15:22:3459 set(set&& s)
60 noexcept(
61 is_nothrow_move_constructible<allocator_type>::value &&
62 is_nothrow_move_constructible<key_compare>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:1663 explicit set(const allocator_type& a);
64 set(const set& s, const allocator_type& a);
65 set(set&& s, const allocator_type& a);
66 set(initializer_list<value_type> il, const value_compare& comp = value_compare());
67 set(initializer_list<value_type> il, const value_compare& comp,
68 const allocator_type& a);
69 ~set();
70
71 set& operator=(const set& s);
Howard Hinnantb2e2a8f2011-06-04 15:22:3472 set& operator=(set&& s)
73 noexcept(
74 allocator_type::propagate_on_container_move_assignment::value &&
75 is_nothrow_move_assignable<allocator_type>::value &&
76 is_nothrow_move_assignable<key_compare>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:1677 set& operator=(initializer_list<value_type> il);
78
79 // iterators:
Howard Hinnantb2e2a8f2011-06-04 15:22:3480 iterator begin() noexcept;
81 const_iterator begin() const noexcept;
82 iterator end() noexcept;
83 const_iterator end() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:1684
Howard Hinnantb2e2a8f2011-06-04 15:22:3485 reverse_iterator rbegin() noexcept;
86 const_reverse_iterator rbegin() const noexcept;
87 reverse_iterator rend() noexcept;
88 const_reverse_iterator rend() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:1689
Howard Hinnantb2e2a8f2011-06-04 15:22:3490 const_iterator cbegin() const noexcept;
91 const_iterator cend() const noexcept;
92 const_reverse_iterator crbegin() const noexcept;
93 const_reverse_iterator crend() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:1694
95 // capacity:
Howard Hinnantb2e2a8f2011-06-04 15:22:3496 bool empty() const noexcept;
97 size_type size() const noexcept;
98 size_type max_size() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:1699
100 // modifiers:
101 template <class... Args>
102 pair<iterator, bool> emplace(Args&&... args);
103 template <class... Args>
104 iterator emplace_hint(const_iterator position, Args&&... args);
105 pair<iterator,bool> insert(const value_type& v);
106 pair<iterator,bool> insert(value_type&& v);
107 iterator insert(const_iterator position, const value_type& v);
108 iterator insert(const_iterator position, value_type&& v);
109 template <class InputIterator>
110 void insert(InputIterator first, InputIterator last);
111 void insert(initializer_list<value_type> il);
112
113 iterator erase(const_iterator position);
114 size_type erase(const key_type& k);
115 iterator erase(const_iterator first, const_iterator last);
Howard Hinnantb2e2a8f2011-06-04 15:22:34116 void clear() noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16117
Howard Hinnantb2e2a8f2011-06-04 15:22:34118 void swap(set& s)
119 noexcept(
120 __is_nothrow_swappable<key_compare>::value &&
121 (!allocator_type::propagate_on_container_swap::value ||
122 __is_nothrow_swappable<allocator_type>::value));
Howard Hinnantbc8d3f92010-05-11 19:42:16123
124 // observers:
Howard Hinnantb2e2a8f2011-06-04 15:22:34125 allocator_type get_allocator() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16126 key_compare key_comp() const;
127 value_compare value_comp() const;
128
129 // set operations:
130 iterator find(const key_type& k);
131 const_iterator find(const key_type& k) const;
132 size_type count(const key_type& k) const;
133 iterator lower_bound(const key_type& k);
134 const_iterator lower_bound(const key_type& k) const;
135 iterator upper_bound(const key_type& k);
136 const_iterator upper_bound(const key_type& k) const;
137 pair<iterator,iterator> equal_range(const key_type& k);
138 pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
139};
140
141template <class Key, class Compare, class Allocator>
142bool
143operator==(const set<Key, Compare, Allocator>& x,
144 const set<Key, Compare, Allocator>& y);
145
146template <class Key, class Compare, class Allocator>
147bool
148operator< (const set<Key, Compare, Allocator>& x,
149 const set<Key, Compare, Allocator>& y);
150
151template <class Key, class Compare, class Allocator>
152bool
153operator!=(const set<Key, Compare, Allocator>& x,
154 const set<Key, Compare, Allocator>& y);
155
156template <class Key, class Compare, class Allocator>
157bool
158operator> (const set<Key, Compare, Allocator>& x,
159 const set<Key, Compare, Allocator>& y);
160
161template <class Key, class Compare, class Allocator>
162bool
163operator>=(const set<Key, Compare, Allocator>& x,
164 const set<Key, Compare, Allocator>& y);
165
166template <class Key, class Compare, class Allocator>
167bool
168operator<=(const set<Key, Compare, Allocator>& x,
169 const set<Key, Compare, Allocator>& y);
170
171// specialized algorithms:
172template <class Key, class Compare, class Allocator>
173void
Howard Hinnantb2e2a8f2011-06-04 15:22:34174swap(set<Key, Compare, Allocator>& x, set<Key, Compare, Allocator>& y)
175 noexcept(noexcept(x.swap(y)));
Howard Hinnantbc8d3f92010-05-11 19:42:16176
Howard Hinnantbc8d3f92010-05-11 19:42:16177template <class Key, class Compare = less<Key>,
178 class Allocator = allocator<Key>>
179class multiset
180{
181public:
182 // types:
183 typedef Key key_type;
184 typedef key_type value_type;
185 typedef Compare key_compare;
186 typedef key_compare value_compare;
187 typedef Allocator allocator_type;
188 typedef typename allocator_type::reference reference;
189 typedef typename allocator_type::const_reference const_reference;
190 typedef typename allocator_type::size_type size_type;
191 typedef typename allocator_type::difference_type difference_type;
192 typedef typename allocator_type::pointer pointer;
193 typedef typename allocator_type::const_pointer const_pointer;
194
195 typedef implementation-defined iterator;
196 typedef implementation-defined const_iterator;
197 typedef std::reverse_iterator<iterator> reverse_iterator;
198 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
199
200 // construct/copy/destroy:
Howard Hinnantb2e2a8f2011-06-04 15:22:34201 multiset()
202 noexcept(
203 is_nothrow_default_constructible<allocator_type>::value &&
204 is_nothrow_default_constructible<key_compare>::value &&
205 is_nothrow_copy_constructible<key_compare>::value);
206 explicit multiset(const value_compare& comp);
Howard Hinnantbc8d3f92010-05-11 19:42:16207 multiset(const value_compare& comp, const allocator_type& a);
208 template <class InputIterator>
209 multiset(InputIterator first, InputIterator last,
210 const value_compare& comp = value_compare());
211 template <class InputIterator>
212 multiset(InputIterator first, InputIterator last,
213 const value_compare& comp, const allocator_type& a);
214 multiset(const multiset& s);
Howard Hinnantb2e2a8f2011-06-04 15:22:34215 multiset(multiset&& s)
216 noexcept(
217 is_nothrow_move_constructible<allocator_type>::value &&
218 is_nothrow_move_constructible<key_compare>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16219 explicit multiset(const allocator_type& a);
220 multiset(const multiset& s, const allocator_type& a);
221 multiset(multiset&& s, const allocator_type& a);
222 multiset(initializer_list<value_type> il, const value_compare& comp = value_compare());
223 multiset(initializer_list<value_type> il, const value_compare& comp,
224 const allocator_type& a);
225 ~multiset();
226
227 multiset& operator=(const multiset& s);
Howard Hinnantb2e2a8f2011-06-04 15:22:34228 multiset& operator=(multiset&& s)
229 noexcept(
230 allocator_type::propagate_on_container_move_assignment::value &&
231 is_nothrow_move_assignable<allocator_type>::value &&
232 is_nothrow_move_assignable<key_compare>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16233 multiset& operator=(initializer_list<value_type> il);
234
235 // iterators:
Howard Hinnantb2e2a8f2011-06-04 15:22:34236 iterator begin() noexcept;
237 const_iterator begin() const noexcept;
238 iterator end() noexcept;
239 const_iterator end() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16240
Howard Hinnantb2e2a8f2011-06-04 15:22:34241 reverse_iterator rbegin() noexcept;
242 const_reverse_iterator rbegin() const noexcept;
243 reverse_iterator rend() noexcept;
244 const_reverse_iterator rend() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16245
Howard Hinnantb2e2a8f2011-06-04 15:22:34246 const_iterator cbegin() const noexcept;
247 const_iterator cend() const noexcept;
248 const_reverse_iterator crbegin() const noexcept;
249 const_reverse_iterator crend() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16250
251 // capacity:
Howard Hinnantb2e2a8f2011-06-04 15:22:34252 bool empty() const noexcept;
253 size_type size() const noexcept;
254 size_type max_size() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16255
256 // modifiers:
257 template <class... Args>
258 iterator emplace(Args&&... args);
259 template <class... Args>
260 iterator emplace_hint(const_iterator position, Args&&... args);
261 iterator insert(const value_type& v);
262 iterator insert(value_type&& v);
263 iterator insert(const_iterator position, const value_type& v);
264 iterator insert(const_iterator position, value_type&& v);
265 template <class InputIterator>
266 void insert(InputIterator first, InputIterator last);
267 void insert(initializer_list<value_type> il);
268
269 iterator erase(const_iterator position);
270 size_type erase(const key_type& k);
271 iterator erase(const_iterator first, const_iterator last);
Howard Hinnantb2e2a8f2011-06-04 15:22:34272 void clear() noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16273
Howard Hinnantb2e2a8f2011-06-04 15:22:34274 void swap(multiset& s)
275 noexcept(
276 __is_nothrow_swappable<key_compare>::value &&
277 (!allocator_type::propagate_on_container_swap::value ||
278 __is_nothrow_swappable<allocator_type>::value));
Howard Hinnantbc8d3f92010-05-11 19:42:16279
280 // observers:
Howard Hinnantb2e2a8f2011-06-04 15:22:34281 allocator_type get_allocator() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16282 key_compare key_comp() const;
283 value_compare value_comp() const;
284
285 // set operations:
286 iterator find(const key_type& k);
287 const_iterator find(const key_type& k) const;
288 size_type count(const key_type& k) const;
289 iterator lower_bound(const key_type& k);
290 const_iterator lower_bound(const key_type& k) const;
291 iterator upper_bound(const key_type& k);
292 const_iterator upper_bound(const key_type& k) const;
293 pair<iterator,iterator> equal_range(const key_type& k);
294 pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
295};
296
297template <class Key, class Compare, class Allocator>
298bool
299operator==(const multiset<Key, Compare, Allocator>& x,
300 const multiset<Key, Compare, Allocator>& y);
301
302template <class Key, class Compare, class Allocator>
303bool
304operator< (const multiset<Key, Compare, Allocator>& x,
305 const multiset<Key, Compare, Allocator>& y);
306
307template <class Key, class Compare, class Allocator>
308bool
309operator!=(const multiset<Key, Compare, Allocator>& x,
310 const multiset<Key, Compare, Allocator>& y);
311
312template <class Key, class Compare, class Allocator>
313bool
314operator> (const multiset<Key, Compare, Allocator>& x,
315 const multiset<Key, Compare, Allocator>& y);
316
317template <class Key, class Compare, class Allocator>
318bool
319operator>=(const multiset<Key, Compare, Allocator>& x,
320 const multiset<Key, Compare, Allocator>& y);
321
322template <class Key, class Compare, class Allocator>
323bool
324operator<=(const multiset<Key, Compare, Allocator>& x,
325 const multiset<Key, Compare, Allocator>& y);
326
327// specialized algorithms:
328template <class Key, class Compare, class Allocator>
329void
Howard Hinnantb2e2a8f2011-06-04 15:22:34330swap(multiset<Key, Compare, Allocator>& x, multiset<Key, Compare, Allocator>& y)
331 noexcept(noexcept(x.swap(y)));
Howard Hinnantbc8d3f92010-05-11 19:42:16332
333} // std
334
335*/
336
337#include <__config>
338#include <__tree>
339#include <functional>
340
Howard Hinnant08e17472011-10-17 20:05:10341#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
Howard Hinnantbc8d3f92010-05-11 19:42:16342#pragma GCC system_header
Howard Hinnant08e17472011-10-17 20:05:10343#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16344
345_LIBCPP_BEGIN_NAMESPACE_STD
346
347template <class _Key, class _Compare = less<_Key>,
348 class _Allocator = allocator<_Key> >
Howard Hinnant83eade62013-03-06 23:30:19349class _LIBCPP_TYPE_VIS set
Howard Hinnantbc8d3f92010-05-11 19:42:16350{
351public:
352 // types:
353 typedef _Key key_type;
354 typedef key_type value_type;
355 typedef _Compare key_compare;
356 typedef key_compare value_compare;
357 typedef _Allocator allocator_type;
358 typedef value_type& reference;
359 typedef const value_type& const_reference;
360
361private:
362 typedef __tree<value_type, value_compare, allocator_type> __base;
363 typedef allocator_traits<allocator_type> __alloc_traits;
364 typedef typename __base::__node_holder __node_holder;
365
366 __base __tree_;
367
368public:
369 typedef typename __base::pointer pointer;
370 typedef typename __base::const_pointer const_pointer;
371 typedef typename __base::size_type size_type;
372 typedef typename __base::difference_type difference_type;
373 typedef typename __base::const_iterator iterator;
374 typedef typename __base::const_iterator const_iterator;
Howard Hinnant0949eed2011-06-30 21:18:19375 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
376 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
Howard Hinnantbc8d3f92010-05-11 19:42:16377
Howard Hinnant28c97e62010-09-23 16:27:36378 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16379 explicit set(const value_compare& __comp = value_compare())
Howard Hinnantb2e2a8f2011-06-04 15:22:34380 _NOEXCEPT_(
381 is_nothrow_default_constructible<allocator_type>::value &&
382 is_nothrow_default_constructible<key_compare>::value &&
383 is_nothrow_copy_constructible<key_compare>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16384 : __tree_(__comp) {}
Howard Hinnant28c97e62010-09-23 16:27:36385 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16386 set(const value_compare& __comp, const allocator_type& __a)
387 : __tree_(__comp, __a) {}
388 template <class _InputIterator>
Howard Hinnant28c97e62010-09-23 16:27:36389 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16390 set(_InputIterator __f, _InputIterator __l,
391 const value_compare& __comp = value_compare())
392 : __tree_(__comp)
393 {
394 insert(__f, __l);
395 }
396
397 template <class _InputIterator>
Howard Hinnant28c97e62010-09-23 16:27:36398 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16399 set(_InputIterator __f, _InputIterator __l, const value_compare& __comp,
400 const allocator_type& __a)
401 : __tree_(__comp, __a)
402 {
403 insert(__f, __l);
404 }
405
Howard Hinnant28c97e62010-09-23 16:27:36406 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16407 set(const set& __s)
408 : __tree_(__s.__tree_)
409 {
410 insert(__s.begin(), __s.end());
411 }
412
Howard Hinnant61aa6012011-07-01 19:24:36413 _LIBCPP_INLINE_VISIBILITY
414 set& operator=(const set& __s)
415 {
416 __tree_ = __s.__tree_;
417 return *this;
418 }
419
Howard Hinnant73d21a42010-09-04 23:28:19420#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant28c97e62010-09-23 16:27:36421 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16422 set(set&& __s)
Howard Hinnantb2e2a8f2011-06-04 15:22:34423 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
Howard Hinnant0949eed2011-06-30 21:18:19424 : __tree_(_VSTD::move(__s.__tree_)) {}
Howard Hinnant73d21a42010-09-04 23:28:19425#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16426
Howard Hinnant28c97e62010-09-23 16:27:36427 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16428 explicit set(const allocator_type& __a)
429 : __tree_(__a) {}
430
Howard Hinnant28c97e62010-09-23 16:27:36431 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16432 set(const set& __s, const allocator_type& __a)
433 : __tree_(__s.__tree_.value_comp(), __a)
434 {
435 insert(__s.begin(), __s.end());
436 }
437
Howard Hinnant73d21a42010-09-04 23:28:19438#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16439 set(set&& __s, const allocator_type& __a);
440#endif
441
Howard Hinnante3e32912011-08-12 21:56:02442#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnant28c97e62010-09-23 16:27:36443 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16444 set(initializer_list<value_type> __il, const value_compare& __comp = value_compare())
445 : __tree_(__comp)
446 {
447 insert(__il.begin(), __il.end());
448 }
449
Howard Hinnant28c97e62010-09-23 16:27:36450 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16451 set(initializer_list<value_type> __il, const value_compare& __comp,
452 const allocator_type& __a)
453 : __tree_(__comp, __a)
454 {
455 insert(__il.begin(), __il.end());
456 }
457
Howard Hinnant28c97e62010-09-23 16:27:36458 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16459 set& operator=(initializer_list<value_type> __il)
460 {
461 __tree_.__assign_unique(__il.begin(), __il.end());
462 return *this;
463 }
Howard Hinnante3e32912011-08-12 21:56:02464#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16465
Howard Hinnant73d21a42010-09-04 23:28:19466#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant28c97e62010-09-23 16:27:36467 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16468 set& operator=(set&& __s)
Howard Hinnantb2e2a8f2011-06-04 15:22:34469 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16470 {
Howard Hinnant0949eed2011-06-30 21:18:19471 __tree_ = _VSTD::move(__s.__tree_);
Howard Hinnantbc8d3f92010-05-11 19:42:16472 return *this;
473 }
Howard Hinnant73d21a42010-09-04 23:28:19474#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16475
Howard Hinnant28c97e62010-09-23 16:27:36476 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantb2e2a8f2011-06-04 15:22:34477 iterator begin() _NOEXCEPT {return __tree_.begin();}
Howard Hinnant28c97e62010-09-23 16:27:36478 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantb2e2a8f2011-06-04 15:22:34479 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
Howard Hinnant28c97e62010-09-23 16:27:36480 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantb2e2a8f2011-06-04 15:22:34481 iterator end() _NOEXCEPT {return __tree_.end();}
Howard Hinnant28c97e62010-09-23 16:27:36482 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantb2e2a8f2011-06-04 15:22:34483 const_iterator end() const _NOEXCEPT {return __tree_.end();}
Howard Hinnantbc8d3f92010-05-11 19:42:16484
Howard Hinnant28c97e62010-09-23 16:27:36485 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantb2e2a8f2011-06-04 15:22:34486 reverse_iterator rbegin() _NOEXCEPT
487 {return reverse_iterator(end());}
Howard Hinnant28c97e62010-09-23 16:27:36488 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantb2e2a8f2011-06-04 15:22:34489 const_reverse_iterator rbegin() const _NOEXCEPT
490 {return const_reverse_iterator(end());}
Howard Hinnant28c97e62010-09-23 16:27:36491 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantb2e2a8f2011-06-04 15:22:34492 reverse_iterator rend() _NOEXCEPT
493 {return reverse_iterator(begin());}
Howard Hinnant28c97e62010-09-23 16:27:36494 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantb2e2a8f2011-06-04 15:22:34495 const_reverse_iterator rend() const _NOEXCEPT
496 {return const_reverse_iterator(begin());}
Howard Hinnantbc8d3f92010-05-11 19:42:16497
Howard Hinnant28c97e62010-09-23 16:27:36498 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantb2e2a8f2011-06-04 15:22:34499 const_iterator cbegin() const _NOEXCEPT {return begin();}
Howard Hinnant28c97e62010-09-23 16:27:36500 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantb2e2a8f2011-06-04 15:22:34501 const_iterator cend() const _NOEXCEPT {return end();}
Howard Hinnant28c97e62010-09-23 16:27:36502 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantb2e2a8f2011-06-04 15:22:34503 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
Howard Hinnant28c97e62010-09-23 16:27:36504 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantb2e2a8f2011-06-04 15:22:34505 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
Howard Hinnantbc8d3f92010-05-11 19:42:16506
Howard Hinnant28c97e62010-09-23 16:27:36507 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantb2e2a8f2011-06-04 15:22:34508 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
Howard Hinnant28c97e62010-09-23 16:27:36509 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantb2e2a8f2011-06-04 15:22:34510 size_type size() const _NOEXCEPT {return __tree_.size();}
Howard Hinnant28c97e62010-09-23 16:27:36511 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantb2e2a8f2011-06-04 15:22:34512 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
Howard Hinnantbc8d3f92010-05-11 19:42:16513
514 // modifiers:
Howard Hinnant73d21a42010-09-04 23:28:19515#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
Howard Hinnantbc8d3f92010-05-11 19:42:16516 template <class... _Args>
Howard Hinnant28c97e62010-09-23 16:27:36517 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16518 pair<iterator, bool> emplace(_Args&&... __args)
Howard Hinnant0949eed2011-06-30 21:18:19519 {return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...);}
Howard Hinnantbc8d3f92010-05-11 19:42:16520 template <class... _Args>
Howard Hinnant28c97e62010-09-23 16:27:36521 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16522 iterator emplace_hint(const_iterator __p, _Args&&... __args)
Howard Hinnant0949eed2011-06-30 21:18:19523 {return __tree_.__emplace_hint_unique(__p, _VSTD::forward<_Args>(__args)...);}
Howard Hinnant73d21a42010-09-04 23:28:19524#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
Howard Hinnant28c97e62010-09-23 16:27:36525 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16526 pair<iterator,bool> insert(const value_type& __v)
527 {return __tree_.__insert_unique(__v);}
Howard Hinnant73d21a42010-09-04 23:28:19528#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant28c97e62010-09-23 16:27:36529 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16530 pair<iterator,bool> insert(value_type&& __v)
Howard Hinnant0949eed2011-06-30 21:18:19531 {return __tree_.__insert_unique(_VSTD::move(__v));}
Howard Hinnant73d21a42010-09-04 23:28:19532#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant28c97e62010-09-23 16:27:36533 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16534 iterator insert(const_iterator __p, const value_type& __v)
535 {return __tree_.__insert_unique(__p, __v);}
Howard Hinnant73d21a42010-09-04 23:28:19536#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant28c97e62010-09-23 16:27:36537 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16538 iterator insert(const_iterator __p, value_type&& __v)
Howard Hinnant0949eed2011-06-30 21:18:19539 {return __tree_.__insert_unique(__p, _VSTD::move(__v));}
Howard Hinnant73d21a42010-09-04 23:28:19540#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16541 template <class _InputIterator>
Howard Hinnant28c97e62010-09-23 16:27:36542 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16543 void insert(_InputIterator __f, _InputIterator __l)
544 {
545 for (const_iterator __e = cend(); __f != __l; ++__f)
546 __tree_.__insert_unique(__e, *__f);
547 }
548
Howard Hinnante3e32912011-08-12 21:56:02549#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnant28c97e62010-09-23 16:27:36550 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16551 void insert(initializer_list<value_type> __il)
552 {insert(__il.begin(), __il.end());}
Howard Hinnante3e32912011-08-12 21:56:02553#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16554
Howard Hinnant28c97e62010-09-23 16:27:36555 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16556 iterator erase(const_iterator __p) {return __tree_.erase(__p);}
Howard Hinnant28c97e62010-09-23 16:27:36557 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16558 size_type erase(const key_type& __k)
559 {return __tree_.__erase_unique(__k);}
Howard Hinnant28c97e62010-09-23 16:27:36560 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16561 iterator erase(const_iterator __f, const_iterator __l)
562 {return __tree_.erase(__f, __l);}
Howard Hinnant28c97e62010-09-23 16:27:36563 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantb2e2a8f2011-06-04 15:22:34564 void clear() _NOEXCEPT {__tree_.clear();}
Howard Hinnantbc8d3f92010-05-11 19:42:16565
Howard Hinnant28c97e62010-09-23 16:27:36566 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantb2e2a8f2011-06-04 15:22:34567 void swap(set& __s) _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
568 {__tree_.swap(__s.__tree_);}
Howard Hinnantbc8d3f92010-05-11 19:42:16569
Howard Hinnant28c97e62010-09-23 16:27:36570 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantb2e2a8f2011-06-04 15:22:34571 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
Howard Hinnant28c97e62010-09-23 16:27:36572 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16573 key_compare key_comp() const {return __tree_.value_comp();}
Howard Hinnant28c97e62010-09-23 16:27:36574 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16575 value_compare value_comp() const {return __tree_.value_comp();}
576
577 // set operations:
Howard Hinnant28c97e62010-09-23 16:27:36578 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16579 iterator find(const key_type& __k) {return __tree_.find(__k);}
Howard Hinnant28c97e62010-09-23 16:27:36580 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16581 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
Howard Hinnant28c97e62010-09-23 16:27:36582 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16583 size_type count(const key_type& __k) const
584 {return __tree_.__count_unique(__k);}
Howard Hinnant28c97e62010-09-23 16:27:36585 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16586 iterator lower_bound(const key_type& __k)
587 {return __tree_.lower_bound(__k);}
Howard Hinnant28c97e62010-09-23 16:27:36588 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16589 const_iterator lower_bound(const key_type& __k) const
590 {return __tree_.lower_bound(__k);}
Howard Hinnant28c97e62010-09-23 16:27:36591 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16592 iterator upper_bound(const key_type& __k)
593 {return __tree_.upper_bound(__k);}
Howard Hinnant28c97e62010-09-23 16:27:36594 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16595 const_iterator upper_bound(const key_type& __k) const
596 {return __tree_.upper_bound(__k);}
Howard Hinnant28c97e62010-09-23 16:27:36597 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16598 pair<iterator,iterator> equal_range(const key_type& __k)
599 {return __tree_.__equal_range_unique(__k);}
Howard Hinnant28c97e62010-09-23 16:27:36600 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16601 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
602 {return __tree_.__equal_range_unique(__k);}
603};
604
Howard Hinnant73d21a42010-09-04 23:28:19605#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16606
607template <class _Key, class _Compare, class _Allocator>
608set<_Key, _Compare, _Allocator>::set(set&& __s, const allocator_type& __a)
Howard Hinnant0949eed2011-06-30 21:18:19609 : __tree_(_VSTD::move(__s.__tree_), __a)
Howard Hinnantbc8d3f92010-05-11 19:42:16610{
611 if (__a != __s.get_allocator())
612 {
613 const_iterator __e = cend();
614 while (!__s.empty())
Howard Hinnant0949eed2011-06-30 21:18:19615 insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_));
Howard Hinnantbc8d3f92010-05-11 19:42:16616 }
617}
618
Howard Hinnant73d21a42010-09-04 23:28:19619#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16620
621template <class _Key, class _Compare, class _Allocator>
Howard Hinnant28c97e62010-09-23 16:27:36622inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16623bool
624operator==(const set<_Key, _Compare, _Allocator>& __x,
625 const set<_Key, _Compare, _Allocator>& __y)
626{
Howard Hinnant0949eed2011-06-30 21:18:19627 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
Howard Hinnantbc8d3f92010-05-11 19:42:16628}
629
630template <class _Key, class _Compare, class _Allocator>
Howard Hinnant28c97e62010-09-23 16:27:36631inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16632bool
633operator< (const set<_Key, _Compare, _Allocator>& __x,
634 const set<_Key, _Compare, _Allocator>& __y)
635{
Howard Hinnant0949eed2011-06-30 21:18:19636 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
Howard Hinnantbc8d3f92010-05-11 19:42:16637}
638
639template <class _Key, class _Compare, class _Allocator>
Howard Hinnant28c97e62010-09-23 16:27:36640inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16641bool
642operator!=(const set<_Key, _Compare, _Allocator>& __x,
643 const set<_Key, _Compare, _Allocator>& __y)
644{
645 return !(__x == __y);
646}
647
648template <class _Key, class _Compare, class _Allocator>
Howard Hinnant28c97e62010-09-23 16:27:36649inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16650bool
651operator> (const set<_Key, _Compare, _Allocator>& __x,
652 const set<_Key, _Compare, _Allocator>& __y)
653{
654 return __y < __x;
655}
656
657template <class _Key, class _Compare, class _Allocator>
Howard Hinnant28c97e62010-09-23 16:27:36658inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16659bool
660operator>=(const set<_Key, _Compare, _Allocator>& __x,
661 const set<_Key, _Compare, _Allocator>& __y)
662{
663 return !(__x < __y);
664}
665
666template <class _Key, class _Compare, class _Allocator>
Howard Hinnant28c97e62010-09-23 16:27:36667inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16668bool
669operator<=(const set<_Key, _Compare, _Allocator>& __x,
670 const set<_Key, _Compare, _Allocator>& __y)
671{
672 return !(__y < __x);
673}
674
675// specialized algorithms:
676template <class _Key, class _Compare, class _Allocator>
Howard Hinnant28c97e62010-09-23 16:27:36677inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16678void
679swap(set<_Key, _Compare, _Allocator>& __x,
680 set<_Key, _Compare, _Allocator>& __y)
Howard Hinnantb2e2a8f2011-06-04 15:22:34681 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantbc8d3f92010-05-11 19:42:16682{
683 __x.swap(__y);
684}
685
Howard Hinnantbc8d3f92010-05-11 19:42:16686template <class _Key, class _Compare = less<_Key>,
687 class _Allocator = allocator<_Key> >
Howard Hinnant83eade62013-03-06 23:30:19688class _LIBCPP_TYPE_VIS multiset
Howard Hinnantbc8d3f92010-05-11 19:42:16689{
690public:
691 // types:
692 typedef _Key key_type;
693 typedef key_type value_type;
694 typedef _Compare key_compare;
695 typedef key_compare value_compare;
696 typedef _Allocator allocator_type;
697 typedef value_type& reference;
698 typedef const value_type& const_reference;
699
700private:
701 typedef __tree<value_type, value_compare, allocator_type> __base;
702 typedef allocator_traits<allocator_type> __alloc_traits;
703 typedef typename __base::__node_holder __node_holder;
704
705 __base __tree_;
706
707public:
708 typedef typename __base::pointer pointer;
709 typedef typename __base::const_pointer const_pointer;
710 typedef typename __base::size_type size_type;
711 typedef typename __base::difference_type difference_type;
712 typedef typename __base::const_iterator iterator;
713 typedef typename __base::const_iterator const_iterator;
Howard Hinnant0949eed2011-06-30 21:18:19714 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
715 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
Howard Hinnantbc8d3f92010-05-11 19:42:16716
717 // construct/copy/destroy:
Howard Hinnant28c97e62010-09-23 16:27:36718 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16719 explicit multiset(const value_compare& __comp = value_compare())
Howard Hinnantb2e2a8f2011-06-04 15:22:34720 _NOEXCEPT_(
721 is_nothrow_default_constructible<allocator_type>::value &&
722 is_nothrow_default_constructible<key_compare>::value &&
723 is_nothrow_copy_constructible<key_compare>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16724 : __tree_(__comp) {}
Howard Hinnant28c97e62010-09-23 16:27:36725 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16726 multiset(const value_compare& __comp, const allocator_type& __a)
727 : __tree_(__comp, __a) {}
728 template <class _InputIterator>
Howard Hinnant28c97e62010-09-23 16:27:36729 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16730 multiset(_InputIterator __f, _InputIterator __l,
731 const value_compare& __comp = value_compare())
732 : __tree_(__comp)
733 {
734 insert(__f, __l);
735 }
736
737 template <class _InputIterator>
Howard Hinnant28c97e62010-09-23 16:27:36738 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16739 multiset(_InputIterator __f, _InputIterator __l,
740 const value_compare& __comp, const allocator_type& __a)
741 : __tree_(__comp, __a)
742 {
743 insert(__f, __l);
744 }
745
Howard Hinnant28c97e62010-09-23 16:27:36746 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16747 multiset(const multiset& __s)
748 : __tree_(__s.__tree_.value_comp(),
749 __alloc_traits::select_on_container_copy_construction(__s.__tree_.__alloc()))
750 {
751 insert(__s.begin(), __s.end());
752 }
753
Howard Hinnant61aa6012011-07-01 19:24:36754 _LIBCPP_INLINE_VISIBILITY
755 multiset& operator=(const multiset& __s)
756 {
757 __tree_ = __s.__tree_;
758 return *this;
759 }
760
Howard Hinnant73d21a42010-09-04 23:28:19761#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant28c97e62010-09-23 16:27:36762 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16763 multiset(multiset&& __s)
Howard Hinnantb2e2a8f2011-06-04 15:22:34764 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
Howard Hinnant0949eed2011-06-30 21:18:19765 : __tree_(_VSTD::move(__s.__tree_)) {}
Howard Hinnant73d21a42010-09-04 23:28:19766#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant28c97e62010-09-23 16:27:36767 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16768 explicit multiset(const allocator_type& __a)
769 : __tree_(__a) {}
Howard Hinnant28c97e62010-09-23 16:27:36770 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16771 multiset(const multiset& __s, const allocator_type& __a)
772 : __tree_(__s.__tree_.value_comp(), __a)
773 {
774 insert(__s.begin(), __s.end());
775 }
Howard Hinnant73d21a42010-09-04 23:28:19776#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16777 multiset(multiset&& __s, const allocator_type& __a);
778#endif
779
Howard Hinnante3e32912011-08-12 21:56:02780#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnant28c97e62010-09-23 16:27:36781 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16782 multiset(initializer_list<value_type> __il, const value_compare& __comp = value_compare())
783 : __tree_(__comp)
784 {
785 insert(__il.begin(), __il.end());
786 }
787
Howard Hinnant28c97e62010-09-23 16:27:36788 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16789 multiset(initializer_list<value_type> __il, const value_compare& __comp,
790 const allocator_type& __a)
791 : __tree_(__comp, __a)
792 {
793 insert(__il.begin(), __il.end());
794 }
795
Howard Hinnant28c97e62010-09-23 16:27:36796 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16797 multiset& operator=(initializer_list<value_type> __il)
798 {
799 __tree_.__assign_multi(__il.begin(), __il.end());
800 return *this;
801 }
Howard Hinnante3e32912011-08-12 21:56:02802#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16803
Howard Hinnant73d21a42010-09-04 23:28:19804#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant28c97e62010-09-23 16:27:36805 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16806 multiset& operator=(multiset&& __s)
Howard Hinnantb2e2a8f2011-06-04 15:22:34807 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16808 {
Howard Hinnant0949eed2011-06-30 21:18:19809 __tree_ = _VSTD::move(__s.__tree_);
Howard Hinnantbc8d3f92010-05-11 19:42:16810 return *this;
811 }
Howard Hinnant73d21a42010-09-04 23:28:19812#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16813
Howard Hinnant28c97e62010-09-23 16:27:36814 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantb2e2a8f2011-06-04 15:22:34815 iterator begin() _NOEXCEPT {return __tree_.begin();}
Howard Hinnant28c97e62010-09-23 16:27:36816 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantb2e2a8f2011-06-04 15:22:34817 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
Howard Hinnant28c97e62010-09-23 16:27:36818 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantb2e2a8f2011-06-04 15:22:34819 iterator end() _NOEXCEPT {return __tree_.end();}
Howard Hinnant28c97e62010-09-23 16:27:36820 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantb2e2a8f2011-06-04 15:22:34821 const_iterator end() const _NOEXCEPT {return __tree_.end();}
Howard Hinnantbc8d3f92010-05-11 19:42:16822
Howard Hinnant28c97e62010-09-23 16:27:36823 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantb2e2a8f2011-06-04 15:22:34824 reverse_iterator rbegin() _NOEXCEPT
825 {return reverse_iterator(end());}
Howard Hinnant28c97e62010-09-23 16:27:36826 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantb2e2a8f2011-06-04 15:22:34827 const_reverse_iterator rbegin() const _NOEXCEPT
828 {return const_reverse_iterator(end());}
Howard Hinnant28c97e62010-09-23 16:27:36829 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantb2e2a8f2011-06-04 15:22:34830 reverse_iterator rend() _NOEXCEPT
831 {return reverse_iterator(begin());}
Howard Hinnant28c97e62010-09-23 16:27:36832 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantb2e2a8f2011-06-04 15:22:34833 const_reverse_iterator rend() const _NOEXCEPT
834 {return const_reverse_iterator(begin());}
Howard Hinnantbc8d3f92010-05-11 19:42:16835
Howard Hinnant28c97e62010-09-23 16:27:36836 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantb2e2a8f2011-06-04 15:22:34837 const_iterator cbegin() const _NOEXCEPT {return begin();}
Howard Hinnant28c97e62010-09-23 16:27:36838 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantb2e2a8f2011-06-04 15:22:34839 const_iterator cend() const _NOEXCEPT {return end();}
Howard Hinnant28c97e62010-09-23 16:27:36840 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantb2e2a8f2011-06-04 15:22:34841 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
Howard Hinnant28c97e62010-09-23 16:27:36842 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantb2e2a8f2011-06-04 15:22:34843 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
Howard Hinnantbc8d3f92010-05-11 19:42:16844
Howard Hinnant28c97e62010-09-23 16:27:36845 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantb2e2a8f2011-06-04 15:22:34846 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
Howard Hinnant28c97e62010-09-23 16:27:36847 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantb2e2a8f2011-06-04 15:22:34848 size_type size() const _NOEXCEPT {return __tree_.size();}
Howard Hinnant28c97e62010-09-23 16:27:36849 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantb2e2a8f2011-06-04 15:22:34850 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
Howard Hinnantbc8d3f92010-05-11 19:42:16851
852 // modifiers:
Howard Hinnant73d21a42010-09-04 23:28:19853#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
Howard Hinnantbc8d3f92010-05-11 19:42:16854 template <class... _Args>
Howard Hinnant28c97e62010-09-23 16:27:36855 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16856 iterator emplace(_Args&&... __args)
Howard Hinnant0949eed2011-06-30 21:18:19857 {return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...);}
Howard Hinnantbc8d3f92010-05-11 19:42:16858 template <class... _Args>
Howard Hinnant28c97e62010-09-23 16:27:36859 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16860 iterator emplace_hint(const_iterator __p, _Args&&... __args)
Howard Hinnant0949eed2011-06-30 21:18:19861 {return __tree_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);}
Howard Hinnant73d21a42010-09-04 23:28:19862#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
Howard Hinnant28c97e62010-09-23 16:27:36863 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16864 iterator insert(const value_type& __v)
865 {return __tree_.__insert_multi(__v);}
Howard Hinnant73d21a42010-09-04 23:28:19866#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant28c97e62010-09-23 16:27:36867 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16868 iterator insert(value_type&& __v)
Howard Hinnant0949eed2011-06-30 21:18:19869 {return __tree_.__insert_multi(_VSTD::move(__v));}
Howard Hinnant73d21a42010-09-04 23:28:19870#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant28c97e62010-09-23 16:27:36871 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16872 iterator insert(const_iterator __p, const value_type& __v)
873 {return __tree_.__insert_multi(__p, __v);}
Howard Hinnant73d21a42010-09-04 23:28:19874#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant28c97e62010-09-23 16:27:36875 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16876 iterator insert(const_iterator __p, value_type&& __v)
Howard Hinnant0949eed2011-06-30 21:18:19877 {return __tree_.__insert_multi(_VSTD::move(__v));}
Howard Hinnant73d21a42010-09-04 23:28:19878#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16879 template <class _InputIterator>
Howard Hinnant28c97e62010-09-23 16:27:36880 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16881 void insert(_InputIterator __f, _InputIterator __l)
882 {
883 for (const_iterator __e = cend(); __f != __l; ++__f)
884 __tree_.__insert_multi(__e, *__f);
885 }
886
Howard Hinnante3e32912011-08-12 21:56:02887#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnant28c97e62010-09-23 16:27:36888 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16889 void insert(initializer_list<value_type> __il)
890 {insert(__il.begin(), __il.end());}
Howard Hinnante3e32912011-08-12 21:56:02891#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16892
Howard Hinnant28c97e62010-09-23 16:27:36893 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16894 iterator erase(const_iterator __p) {return __tree_.erase(__p);}
Howard Hinnant28c97e62010-09-23 16:27:36895 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16896 size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);}
Howard Hinnant28c97e62010-09-23 16:27:36897 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16898 iterator erase(const_iterator __f, const_iterator __l)
899 {return __tree_.erase(__f, __l);}
Howard Hinnant28c97e62010-09-23 16:27:36900 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantb2e2a8f2011-06-04 15:22:34901 void clear() _NOEXCEPT {__tree_.clear();}
Howard Hinnantbc8d3f92010-05-11 19:42:16902
Howard Hinnant28c97e62010-09-23 16:27:36903 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantb2e2a8f2011-06-04 15:22:34904 void swap(multiset& __s)
905 _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
906 {__tree_.swap(__s.__tree_);}
Howard Hinnantbc8d3f92010-05-11 19:42:16907
Howard Hinnant28c97e62010-09-23 16:27:36908 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantb2e2a8f2011-06-04 15:22:34909 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
Howard Hinnant28c97e62010-09-23 16:27:36910 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16911 key_compare key_comp() const {return __tree_.value_comp();}
Howard Hinnant28c97e62010-09-23 16:27:36912 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16913 value_compare value_comp() const {return __tree_.value_comp();}
914
915 // set operations:
Howard Hinnant28c97e62010-09-23 16:27:36916 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16917 iterator find(const key_type& __k) {return __tree_.find(__k);}
Howard Hinnant28c97e62010-09-23 16:27:36918 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16919 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
Howard Hinnant28c97e62010-09-23 16:27:36920 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16921 size_type count(const key_type& __k) const
922 {return __tree_.__count_multi(__k);}
Howard Hinnant28c97e62010-09-23 16:27:36923 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16924 iterator lower_bound(const key_type& __k)
925 {return __tree_.lower_bound(__k);}
Howard Hinnant28c97e62010-09-23 16:27:36926 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16927 const_iterator lower_bound(const key_type& __k) const
928 {return __tree_.lower_bound(__k);}
Howard Hinnant28c97e62010-09-23 16:27:36929 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16930 iterator upper_bound(const key_type& __k)
931 {return __tree_.upper_bound(__k);}
Howard Hinnant28c97e62010-09-23 16:27:36932 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16933 const_iterator upper_bound(const key_type& __k) const
934 {return __tree_.upper_bound(__k);}
Howard Hinnant28c97e62010-09-23 16:27:36935 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16936 pair<iterator,iterator> equal_range(const key_type& __k)
937 {return __tree_.__equal_range_multi(__k);}
Howard Hinnant28c97e62010-09-23 16:27:36938 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16939 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
940 {return __tree_.__equal_range_multi(__k);}
941};
942
Howard Hinnant73d21a42010-09-04 23:28:19943#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16944
945template <class _Key, class _Compare, class _Allocator>
946multiset<_Key, _Compare, _Allocator>::multiset(multiset&& __s, const allocator_type& __a)
Howard Hinnant0949eed2011-06-30 21:18:19947 : __tree_(_VSTD::move(__s.__tree_), __a)
Howard Hinnantbc8d3f92010-05-11 19:42:16948{
949 if (__a != __s.get_allocator())
950 {
951 const_iterator __e = cend();
952 while (!__s.empty())
Howard Hinnant0949eed2011-06-30 21:18:19953 insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_));
Howard Hinnantbc8d3f92010-05-11 19:42:16954 }
955}
956
Howard Hinnant73d21a42010-09-04 23:28:19957#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16958
959template <class _Key, class _Compare, class _Allocator>
Howard Hinnant28c97e62010-09-23 16:27:36960inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16961bool
962operator==(const multiset<_Key, _Compare, _Allocator>& __x,
963 const multiset<_Key, _Compare, _Allocator>& __y)
964{
Howard Hinnant0949eed2011-06-30 21:18:19965 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
Howard Hinnantbc8d3f92010-05-11 19:42:16966}
967
968template <class _Key, class _Compare, class _Allocator>
Howard Hinnant28c97e62010-09-23 16:27:36969inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16970bool
971operator< (const multiset<_Key, _Compare, _Allocator>& __x,
972 const multiset<_Key, _Compare, _Allocator>& __y)
973{
Howard Hinnant0949eed2011-06-30 21:18:19974 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
Howard Hinnantbc8d3f92010-05-11 19:42:16975}
976
977template <class _Key, class _Compare, class _Allocator>
Howard Hinnant28c97e62010-09-23 16:27:36978inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16979bool
980operator!=(const multiset<_Key, _Compare, _Allocator>& __x,
981 const multiset<_Key, _Compare, _Allocator>& __y)
982{
983 return !(__x == __y);
984}
985
986template <class _Key, class _Compare, class _Allocator>
Howard Hinnant28c97e62010-09-23 16:27:36987inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16988bool
989operator> (const multiset<_Key, _Compare, _Allocator>& __x,
990 const multiset<_Key, _Compare, _Allocator>& __y)
991{
992 return __y < __x;
993}
994
995template <class _Key, class _Compare, class _Allocator>
Howard Hinnant28c97e62010-09-23 16:27:36996inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16997bool
998operator>=(const multiset<_Key, _Compare, _Allocator>& __x,
999 const multiset<_Key, _Compare, _Allocator>& __y)
1000{
1001 return !(__x < __y);
1002}
1003
1004template <class _Key, class _Compare, class _Allocator>
Howard Hinnant28c97e62010-09-23 16:27:361005inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:161006bool
1007operator<=(const multiset<_Key, _Compare, _Allocator>& __x,
1008 const multiset<_Key, _Compare, _Allocator>& __y)
1009{
1010 return !(__y < __x);
1011}
1012
1013template <class _Key, class _Compare, class _Allocator>
Howard Hinnant28c97e62010-09-23 16:27:361014inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:161015void
1016swap(multiset<_Key, _Compare, _Allocator>& __x,
1017 multiset<_Key, _Compare, _Allocator>& __y)
Howard Hinnantb2e2a8f2011-06-04 15:22:341018 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantbc8d3f92010-05-11 19:42:161019{
1020 __x.swap(__y);
1021}
1022
Howard Hinnantbc8d3f92010-05-11 19:42:161023_LIBCPP_END_NAMESPACE_STD
1024
1025#endif // _LIBCPP_SET