Gitiles
Code Review Sign In
gerrit-public.fairphone.software / platform / external / libcxx / ed2c2916b218361524764b6da427db2f2cb249f6 / . / include / set
blob: cf88ed9c43f3ceb5b022ed3cc0ff956728d18eac [file] [log] [blame]
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]1// -*- C++ -*-
2//===---------------------------- set -------------------------------------===//
3//
Howard Hinnantf5256e12010-05-11 21:36:01 +0000[diff] [blame]4// The LLVM Compiler Infrastructure
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]5//
6// This file is distributed under the University of Illinois Open Source
7// License. See LICENSE.TXT for details.
8//
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:
45 explicit set(const value_compare& comp = value_compare());
46 set(const value_compare& comp, const allocator_type& a);
47 template <class InputIterator>
48 set(InputIterator first, InputIterator last,
49 const value_compare& comp = value_compare());
50 template <class InputIterator>
51 set(InputIterator first, InputIterator last, const value_compare& comp,
52 const allocator_type& a);
53 set(const set& s);
54 set(set&& s);
55 explicit set(const allocator_type& a);
56 set(const set& s, const allocator_type& a);
57 set(set&& s, const allocator_type& a);
58 set(initializer_list<value_type> il, const value_compare& comp = value_compare());
59 set(initializer_list<value_type> il, const value_compare& comp,
60 const allocator_type& a);
61 ~set();
62
63 set& operator=(const set& s);
64 set& operator=(set&& s);
65 set& operator=(initializer_list<value_type> il);
66
67 // iterators:
68 iterator begin();
69 const_iterator begin() const;
70 iterator end();
71 const_iterator end() const;
72
73 reverse_iterator rbegin();
74 const_reverse_iterator rbegin() const;
75 reverse_iterator rend();
76 const_reverse_iterator rend() const;
77
78 const_iterator cbegin() const;
79 const_iterator cend() const;
80 const_reverse_iterator crbegin() const;
81 const_reverse_iterator crend() const;
82
83 // capacity:
84 bool empty() const;
85 size_type size() const;
86 size_type max_size() const;
87
88 // modifiers:
89 template <class... Args>
90 pair<iterator, bool> emplace(Args&&... args);
91 template <class... Args>
92 iterator emplace_hint(const_iterator position, Args&&... args);
93 pair<iterator,bool> insert(const value_type& v);
94 pair<iterator,bool> insert(value_type&& v);
95 iterator insert(const_iterator position, const value_type& v);
96 iterator insert(const_iterator position, value_type&& v);
97 template <class InputIterator>
98 void insert(InputIterator first, InputIterator last);
99 void insert(initializer_list<value_type> il);
100
101 iterator erase(const_iterator position);
102 size_type erase(const key_type& k);
103 iterator erase(const_iterator first, const_iterator last);
104 void clear();
105
106 void swap(set& s);
107
108 // observers:
109 allocator_type get_allocator() const;
110 key_compare key_comp() const;
111 value_compare value_comp() const;
112
113 // set operations:
114 iterator find(const key_type& k);
115 const_iterator find(const key_type& k) const;
116 size_type count(const key_type& k) const;
117 iterator lower_bound(const key_type& k);
118 const_iterator lower_bound(const key_type& k) const;
119 iterator upper_bound(const key_type& k);
120 const_iterator upper_bound(const key_type& k) const;
121 pair<iterator,iterator> equal_range(const key_type& k);
122 pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
123};
124
125template <class Key, class Compare, class Allocator>
126bool
127operator==(const set<Key, Compare, Allocator>& x,
128 const set<Key, Compare, Allocator>& y);
129
130template <class Key, class Compare, class Allocator>
131bool
132operator< (const set<Key, Compare, Allocator>& x,
133 const set<Key, Compare, Allocator>& y);
134
135template <class Key, class Compare, class Allocator>
136bool
137operator!=(const set<Key, Compare, Allocator>& x,
138 const set<Key, Compare, Allocator>& y);
139
140template <class Key, class Compare, class Allocator>
141bool
142operator> (const set<Key, Compare, Allocator>& x,
143 const set<Key, Compare, Allocator>& y);
144
145template <class Key, class Compare, class Allocator>
146bool
147operator>=(const set<Key, Compare, Allocator>& x,
148 const set<Key, Compare, Allocator>& y);
149
150template <class Key, class Compare, class Allocator>
151bool
152operator<=(const set<Key, Compare, Allocator>& x,
153 const set<Key, Compare, Allocator>& y);
154
155// specialized algorithms:
156template <class Key, class Compare, class Allocator>
157void
158swap(set<Key, Compare, Allocator>& x, set<Key, Compare, Allocator>& y);
159
160
161template <class Key, class Compare = less<Key>,
162 class Allocator = allocator<Key>>
163class multiset
164{
165public:
166 // types:
167 typedef Key key_type;
168 typedef key_type value_type;
169 typedef Compare key_compare;
170 typedef key_compare value_compare;
171 typedef Allocator allocator_type;
172 typedef typename allocator_type::reference reference;
173 typedef typename allocator_type::const_reference const_reference;
174 typedef typename allocator_type::size_type size_type;
175 typedef typename allocator_type::difference_type difference_type;
176 typedef typename allocator_type::pointer pointer;
177 typedef typename allocator_type::const_pointer const_pointer;
178
179 typedef implementation-defined iterator;
180 typedef implementation-defined const_iterator;
181 typedef std::reverse_iterator<iterator> reverse_iterator;
182 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
183
184 // construct/copy/destroy:
185 explicit multiset(const value_compare& comp = value_compare());
186 multiset(const value_compare& comp, const allocator_type& a);
187 template <class InputIterator>
188 multiset(InputIterator first, InputIterator last,
189 const value_compare& comp = value_compare());
190 template <class InputIterator>
191 multiset(InputIterator first, InputIterator last,
192 const value_compare& comp, const allocator_type& a);
193 multiset(const multiset& s);
194 multiset(multiset&& s);
195 explicit multiset(const allocator_type& a);
196 multiset(const multiset& s, const allocator_type& a);
197 multiset(multiset&& s, const allocator_type& a);
198 multiset(initializer_list<value_type> il, const value_compare& comp = value_compare());
199 multiset(initializer_list<value_type> il, const value_compare& comp,
200 const allocator_type& a);
201 ~multiset();
202
203 multiset& operator=(const multiset& s);
204 multiset& operator=(multiset&& s);
205 multiset& operator=(initializer_list<value_type> il);
206
207 // iterators:
208 iterator begin();
209 const_iterator begin() const;
210 iterator end();
211 const_iterator end() const;
212
213 reverse_iterator rbegin();
214 const_reverse_iterator rbegin() const;
215 reverse_iterator rend();
216 const_reverse_iterator rend() const;
217
218 const_iterator cbegin() const;
219 const_iterator cend() const;
220 const_reverse_iterator crbegin() const;
221 const_reverse_iterator crend() const;
222
223 // capacity:
224 bool empty() const;
225 size_type size() const;
226 size_type max_size() const;
227
228 // modifiers:
229 template <class... Args>
230 iterator emplace(Args&&... args);
231 template <class... Args>
232 iterator emplace_hint(const_iterator position, Args&&... args);
233 iterator insert(const value_type& v);
234 iterator insert(value_type&& v);
235 iterator insert(const_iterator position, const value_type& v);
236 iterator insert(const_iterator position, value_type&& v);
237 template <class InputIterator>
238 void insert(InputIterator first, InputIterator last);
239 void insert(initializer_list<value_type> il);
240
241 iterator erase(const_iterator position);
242 size_type erase(const key_type& k);
243 iterator erase(const_iterator first, const_iterator last);
244 void clear();
245
246 void swap(multiset& s);
247
248 // observers:
249 allocator_type get_allocator() const;
250 key_compare key_comp() const;
251 value_compare value_comp() const;
252
253 // set operations:
254 iterator find(const key_type& k);
255 const_iterator find(const key_type& k) const;
256 size_type count(const key_type& k) const;
257 iterator lower_bound(const key_type& k);
258 const_iterator lower_bound(const key_type& k) const;
259 iterator upper_bound(const key_type& k);
260 const_iterator upper_bound(const key_type& k) const;
261 pair<iterator,iterator> equal_range(const key_type& k);
262 pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
263};
264
265template <class Key, class Compare, class Allocator>
266bool
267operator==(const multiset<Key, Compare, Allocator>& x,
268 const multiset<Key, Compare, Allocator>& y);
269
270template <class Key, class Compare, class Allocator>
271bool
272operator< (const multiset<Key, Compare, Allocator>& x,
273 const multiset<Key, Compare, Allocator>& y);
274
275template <class Key, class Compare, class Allocator>
276bool
277operator!=(const multiset<Key, Compare, Allocator>& x,
278 const multiset<Key, Compare, Allocator>& y);
279
280template <class Key, class Compare, class Allocator>
281bool
282operator> (const multiset<Key, Compare, Allocator>& x,
283 const multiset<Key, Compare, Allocator>& y);
284
285template <class Key, class Compare, class Allocator>
286bool
287operator>=(const multiset<Key, Compare, Allocator>& x,
288 const multiset<Key, Compare, Allocator>& y);
289
290template <class Key, class Compare, class Allocator>
291bool
292operator<=(const multiset<Key, Compare, Allocator>& x,
293 const multiset<Key, Compare, Allocator>& y);
294
295// specialized algorithms:
296template <class Key, class Compare, class Allocator>
297void
298swap(multiset<Key, Compare, Allocator>& x, multiset<Key, Compare, Allocator>& y);
299
300} // std
301
302*/
303
304#include <__config>
305#include <__tree>
306#include <functional>
307
308#pragma GCC system_header
309
310_LIBCPP_BEGIN_NAMESPACE_STD
311
312template <class _Key, class _Compare = less<_Key>,
313 class _Allocator = allocator<_Key> >
314class set
315{
316public:
317 // types:
318 typedef _Key key_type;
319 typedef key_type value_type;
320 typedef _Compare key_compare;
321 typedef key_compare value_compare;
322 typedef _Allocator allocator_type;
323 typedef value_type& reference;
324 typedef const value_type& const_reference;
325
326private:
327 typedef __tree<value_type, value_compare, allocator_type> __base;
328 typedef allocator_traits<allocator_type> __alloc_traits;
329 typedef typename __base::__node_holder __node_holder;
330
331 __base __tree_;
332
333public:
334 typedef typename __base::pointer pointer;
335 typedef typename __base::const_pointer const_pointer;
336 typedef typename __base::size_type size_type;
337 typedef typename __base::difference_type difference_type;
338 typedef typename __base::const_iterator iterator;
339 typedef typename __base::const_iterator const_iterator;
340 typedef _STD::reverse_iterator<iterator> reverse_iterator;
341 typedef _STD::reverse_iterator<const_iterator> const_reverse_iterator;
342
343 explicit set(const value_compare& __comp = value_compare())
344 : __tree_(__comp) {}
345 set(const value_compare& __comp, const allocator_type& __a)
346 : __tree_(__comp, __a) {}
347 template <class _InputIterator>
348 set(_InputIterator __f, _InputIterator __l,
349 const value_compare& __comp = value_compare())
350 : __tree_(__comp)
351 {
352 insert(__f, __l);
353 }
354
355 template <class _InputIterator>
356 set(_InputIterator __f, _InputIterator __l, const value_compare& __comp,
357 const allocator_type& __a)
358 : __tree_(__comp, __a)
359 {
360 insert(__f, __l);
361 }
362
363 set(const set& __s)
364 : __tree_(__s.__tree_)
365 {
366 insert(__s.begin(), __s.end());
367 }
368
369#ifdef _LIBCPP_MOVE
370 set(set&& __s)
371 : __tree_(_STD::move(__s.__tree_)) {}
372#endif
373
374 explicit set(const allocator_type& __a)
375 : __tree_(__a) {}
376
377 set(const set& __s, const allocator_type& __a)
378 : __tree_(__s.__tree_.value_comp(), __a)
379 {
380 insert(__s.begin(), __s.end());
381 }
382
383#ifdef _LIBCPP_MOVE
384 set(set&& __s, const allocator_type& __a);
385#endif
386
387 set(initializer_list<value_type> __il, const value_compare& __comp = value_compare())
388 : __tree_(__comp)
389 {
390 insert(__il.begin(), __il.end());
391 }
392
393 set(initializer_list<value_type> __il, const value_compare& __comp,
394 const allocator_type& __a)
395 : __tree_(__comp, __a)
396 {
397 insert(__il.begin(), __il.end());
398 }
399
400 set& operator=(initializer_list<value_type> __il)
401 {
402 __tree_.__assign_unique(__il.begin(), __il.end());
403 return *this;
404 }
405
406#ifdef _LIBCPP_MOVE
407 set& operator=(set&& __s)
408 {
409 __tree_ = _STD::move(__s.__tree_);
410 return *this;
411 }
412#endif
413
414 iterator begin() {return __tree_.begin();}
415 const_iterator begin() const {return __tree_.begin();}
416 iterator end() {return __tree_.end();}
417 const_iterator end() const {return __tree_.end();}
418
419 reverse_iterator rbegin() {return reverse_iterator(end());}
420 const_reverse_iterator rbegin() const {return const_reverse_iterator(end());}
421 reverse_iterator rend() {return reverse_iterator(begin());}
422 const_reverse_iterator rend() const {return const_reverse_iterator(begin());}
423
424 const_iterator cbegin() const {return begin();}
425 const_iterator cend() const {return end();}
426 const_reverse_iterator crbegin() const {return rbegin();}
427 const_reverse_iterator crend() const {return rend();}
428
429 bool empty() const {return __tree_.size() == 0;}
430 size_type size() const {return __tree_.size();}
431 size_type max_size() const {return __tree_.max_size();}
432
433 // modifiers:
434#ifdef _LIBCPP_MOVE
435 template <class... _Args>
436 pair<iterator, bool> emplace(_Args&&... __args)
437 {return __tree_.__emplace_unique(_STD::forward<_Args>(__args)...);}
438 template <class... _Args>
439 iterator emplace_hint(const_iterator __p, _Args&&... __args)
440 {return __tree_.__emplace_hint_unique(__p, _STD::forward<_Args>(__args)...);}
441#endif
442 pair<iterator,bool> insert(const value_type& __v)
443 {return __tree_.__insert_unique(__v);}
444#ifdef _LIBCPP_MOVE
445 pair<iterator,bool> insert(value_type&& __v)
446 {return __tree_.__insert_unique(_STD::move(__v));}
447#endif
448 iterator insert(const_iterator __p, const value_type& __v)
449 {return __tree_.__insert_unique(__p, __v);}
450#ifdef _LIBCPP_MOVE
451 iterator insert(const_iterator __p, value_type&& __v)
452 {return __tree_.__insert_unique(__p, _STD::move(__v));}
453#endif
454 template <class _InputIterator>
455 void insert(_InputIterator __f, _InputIterator __l)
456 {
457 for (const_iterator __e = cend(); __f != __l; ++__f)
458 __tree_.__insert_unique(__e, *__f);
459 }
460
461 void insert(initializer_list<value_type> __il)
462 {insert(__il.begin(), __il.end());}
463
464 iterator erase(const_iterator __p) {return __tree_.erase(__p);}
465 size_type erase(const key_type& __k)
466 {return __tree_.__erase_unique(__k);}
467 iterator erase(const_iterator __f, const_iterator __l)
468 {return __tree_.erase(__f, __l);}
469 void clear() {__tree_.clear();}
470
471 void swap(set& __s) {__tree_.swap(__s.__tree_);}
472
473 allocator_type get_allocator() const {return __tree_.__alloc();}
474 key_compare key_comp() const {return __tree_.value_comp();}
475 value_compare value_comp() const {return __tree_.value_comp();}
476
477 // set operations:
478 iterator find(const key_type& __k) {return __tree_.find(__k);}
479 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
480 size_type count(const key_type& __k) const
481 {return __tree_.__count_unique(__k);}
482 iterator lower_bound(const key_type& __k)
483 {return __tree_.lower_bound(__k);}
484 const_iterator lower_bound(const key_type& __k) const
485 {return __tree_.lower_bound(__k);}
486 iterator upper_bound(const key_type& __k)
487 {return __tree_.upper_bound(__k);}
488 const_iterator upper_bound(const key_type& __k) const
489 {return __tree_.upper_bound(__k);}
490 pair<iterator,iterator> equal_range(const key_type& __k)
491 {return __tree_.__equal_range_unique(__k);}
492 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
493 {return __tree_.__equal_range_unique(__k);}
494};
495
496#ifdef _LIBCPP_MOVE
497
498template <class _Key, class _Compare, class _Allocator>
499set<_Key, _Compare, _Allocator>::set(set&& __s, const allocator_type& __a)
500 : __tree_(_STD::move(__s.__tree_), __a)
501{
502 if (__a != __s.get_allocator())
503 {
504 const_iterator __e = cend();
505 while (!__s.empty())
506 insert(__e, _STD::move(__s.__tree_.remove(__s.begin())->__value_));
507 }
508}
509
510#endif
511
512template <class _Key, class _Compare, class _Allocator>
513inline
514bool
515operator==(const set<_Key, _Compare, _Allocator>& __x,
516 const set<_Key, _Compare, _Allocator>& __y)
517{
518 return __x.size() == __y.size() && _STD::equal(__x.begin(), __x.end(), __y.begin());
519}
520
521template <class _Key, class _Compare, class _Allocator>
522inline
523bool
524operator< (const set<_Key, _Compare, _Allocator>& __x,
525 const set<_Key, _Compare, _Allocator>& __y)
526{
527 return _STD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
528}
529
530template <class _Key, class _Compare, class _Allocator>
531inline
532bool
533operator!=(const set<_Key, _Compare, _Allocator>& __x,
534 const set<_Key, _Compare, _Allocator>& __y)
535{
536 return !(__x == __y);
537}
538
539template <class _Key, class _Compare, class _Allocator>
540inline
541bool
542operator> (const set<_Key, _Compare, _Allocator>& __x,
543 const set<_Key, _Compare, _Allocator>& __y)
544{
545 return __y < __x;
546}
547
548template <class _Key, class _Compare, class _Allocator>
549inline
550bool
551operator>=(const set<_Key, _Compare, _Allocator>& __x,
552 const set<_Key, _Compare, _Allocator>& __y)
553{
554 return !(__x < __y);
555}
556
557template <class _Key, class _Compare, class _Allocator>
558inline
559bool
560operator<=(const set<_Key, _Compare, _Allocator>& __x,
561 const set<_Key, _Compare, _Allocator>& __y)
562{
563 return !(__y < __x);
564}
565
566// specialized algorithms:
567template <class _Key, class _Compare, class _Allocator>
568inline
569void
570swap(set<_Key, _Compare, _Allocator>& __x,
571 set<_Key, _Compare, _Allocator>& __y)
572{
573 __x.swap(__y);
574}
575
576
577template <class _Key, class _Compare = less<_Key>,
578 class _Allocator = allocator<_Key> >
579class multiset
580{
581public:
582 // types:
583 typedef _Key key_type;
584 typedef key_type value_type;
585 typedef _Compare key_compare;
586 typedef key_compare value_compare;
587 typedef _Allocator allocator_type;
588 typedef value_type& reference;
589 typedef const value_type& const_reference;
590
591private:
592 typedef __tree<value_type, value_compare, allocator_type> __base;
593 typedef allocator_traits<allocator_type> __alloc_traits;
594 typedef typename __base::__node_holder __node_holder;
595
596 __base __tree_;
597
598public:
599 typedef typename __base::pointer pointer;
600 typedef typename __base::const_pointer const_pointer;
601 typedef typename __base::size_type size_type;
602 typedef typename __base::difference_type difference_type;
603 typedef typename __base::const_iterator iterator;
604 typedef typename __base::const_iterator const_iterator;
605 typedef _STD::reverse_iterator<iterator> reverse_iterator;
606 typedef _STD::reverse_iterator<const_iterator> const_reverse_iterator;
607
608 // construct/copy/destroy:
609 explicit multiset(const value_compare& __comp = value_compare())
610 : __tree_(__comp) {}
611 multiset(const value_compare& __comp, const allocator_type& __a)
612 : __tree_(__comp, __a) {}
613 template <class _InputIterator>
614 multiset(_InputIterator __f, _InputIterator __l,
615 const value_compare& __comp = value_compare())
616 : __tree_(__comp)
617 {
618 insert(__f, __l);
619 }
620
621 template <class _InputIterator>
622 multiset(_InputIterator __f, _InputIterator __l,
623 const value_compare& __comp, const allocator_type& __a)
624 : __tree_(__comp, __a)
625 {
626 insert(__f, __l);
627 }
628
629 multiset(const multiset& __s)
630 : __tree_(__s.__tree_.value_comp(),
631 __alloc_traits::select_on_container_copy_construction(__s.__tree_.__alloc()))
632 {
633 insert(__s.begin(), __s.end());
634 }
635
636#ifdef _LIBCPP_MOVE
637 multiset(multiset&& __s)
638 : __tree_(_STD::move(__s.__tree_)) {}
639#endif
640 explicit multiset(const allocator_type& __a)
641 : __tree_(__a) {}
642 multiset(const multiset& __s, const allocator_type& __a)
643 : __tree_(__s.__tree_.value_comp(), __a)
644 {
645 insert(__s.begin(), __s.end());
646 }
647#ifdef _LIBCPP_MOVE
648 multiset(multiset&& __s, const allocator_type& __a);
649#endif
650
651 multiset(initializer_list<value_type> __il, const value_compare& __comp = value_compare())
652 : __tree_(__comp)
653 {
654 insert(__il.begin(), __il.end());
655 }
656
657 multiset(initializer_list<value_type> __il, const value_compare& __comp,
658 const allocator_type& __a)
659 : __tree_(__comp, __a)
660 {
661 insert(__il.begin(), __il.end());
662 }
663
664 multiset& operator=(initializer_list<value_type> __il)
665 {
666 __tree_.__assign_multi(__il.begin(), __il.end());
667 return *this;
668 }
669
670#ifdef _LIBCPP_MOVE
671 multiset& operator=(multiset&& __s)
672 {
673 __tree_ = _STD::move(__s.__tree_);
674 return *this;
675 }
676#endif
677
678 iterator begin() {return __tree_.begin();}
679 const_iterator begin() const {return __tree_.begin();}
680 iterator end() {return __tree_.end();}
681 const_iterator end() const {return __tree_.end();}
682
683 reverse_iterator rbegin() {return reverse_iterator(end());}
684 const_reverse_iterator rbegin() const {return const_reverse_iterator(end());}
685 reverse_iterator rend() {return reverse_iterator(begin());}
686 const_reverse_iterator rend() const {return const_reverse_iterator(begin());}
687
688 const_iterator cbegin() const {return begin();}
689 const_iterator cend() const {return end();}
690 const_reverse_iterator crbegin() const {return rbegin();}
691 const_reverse_iterator crend() const {return rend();}
692
693 bool empty() const {return __tree_.size() == 0;}
694 size_type size() const {return __tree_.size();}
695 size_type max_size() const {return __tree_.max_size();}
696
697 // modifiers:
698#ifdef _LIBCPP_MOVE
699 template <class... _Args>
700 iterator emplace(_Args&&... __args)
701 {return __tree_.__emplace_multi(_STD::forward<_Args>(__args)...);}
702 template <class... _Args>
703 iterator emplace_hint(const_iterator __p, _Args&&... __args)
704 {return __tree_.__emplace_hint_multi(__p, _STD::forward<_Args>(__args)...);}
705#endif
706 iterator insert(const value_type& __v)
707 {return __tree_.__insert_multi(__v);}
708#ifdef _LIBCPP_MOVE
709 iterator insert(value_type&& __v)
710 {return __tree_.__insert_multi(_STD::move(__v));}
711#endif
712 iterator insert(const_iterator __p, const value_type& __v)
713 {return __tree_.__insert_multi(__p, __v);}
714#ifdef _LIBCPP_MOVE
715 iterator insert(const_iterator __p, value_type&& __v)
716 {return __tree_.__insert_multi(_STD::move(__v));}
717#endif
718 template <class _InputIterator>
719 void insert(_InputIterator __f, _InputIterator __l)
720 {
721 for (const_iterator __e = cend(); __f != __l; ++__f)
722 __tree_.__insert_multi(__e, *__f);
723 }
724
725 void insert(initializer_list<value_type> __il)
726 {insert(__il.begin(), __il.end());}
727
728 iterator erase(const_iterator __p) {return __tree_.erase(__p);}
729 size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);}
730 iterator erase(const_iterator __f, const_iterator __l)
731 {return __tree_.erase(__f, __l);}
732 void clear() {__tree_.clear();}
733
734 void swap(multiset& __s) {__tree_.swap(__s.__tree_);}
735
736 allocator_type get_allocator() const {return __tree_.__alloc();}
737 key_compare key_comp() const {return __tree_.value_comp();}
738 value_compare value_comp() const {return __tree_.value_comp();}
739
740 // set operations:
741 iterator find(const key_type& __k) {return __tree_.find(__k);}
742 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
743 size_type count(const key_type& __k) const
744 {return __tree_.__count_multi(__k);}
745 iterator lower_bound(const key_type& __k)
746 {return __tree_.lower_bound(__k);}
747 const_iterator lower_bound(const key_type& __k) const
748 {return __tree_.lower_bound(__k);}
749 iterator upper_bound(const key_type& __k)
750 {return __tree_.upper_bound(__k);}
751 const_iterator upper_bound(const key_type& __k) const
752 {return __tree_.upper_bound(__k);}
753 pair<iterator,iterator> equal_range(const key_type& __k)
754 {return __tree_.__equal_range_multi(__k);}
755 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
756 {return __tree_.__equal_range_multi(__k);}
757};
758
759#ifdef _LIBCPP_MOVE
760
761template <class _Key, class _Compare, class _Allocator>
762multiset<_Key, _Compare, _Allocator>::multiset(multiset&& __s, const allocator_type& __a)
763 : __tree_(_STD::move(__s.__tree_), __a)
764{
765 if (__a != __s.get_allocator())
766 {
767 const_iterator __e = cend();
768 while (!__s.empty())
769 insert(__e, _STD::move(__s.__tree_.remove(__s.begin())->__value_));
770 }
771}
772
773#endif
774
775template <class _Key, class _Compare, class _Allocator>
776inline
777bool
778operator==(const multiset<_Key, _Compare, _Allocator>& __x,
779 const multiset<_Key, _Compare, _Allocator>& __y)
780{
781 return __x.size() == __y.size() && _STD::equal(__x.begin(), __x.end(), __y.begin());
782}
783
784template <class _Key, class _Compare, class _Allocator>
785inline
786bool
787operator< (const multiset<_Key, _Compare, _Allocator>& __x,
788 const multiset<_Key, _Compare, _Allocator>& __y)
789{
790 return _STD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
791}
792
793template <class _Key, class _Compare, class _Allocator>
794inline
795bool
796operator!=(const multiset<_Key, _Compare, _Allocator>& __x,
797 const multiset<_Key, _Compare, _Allocator>& __y)
798{
799 return !(__x == __y);
800}
801
802template <class _Key, class _Compare, class _Allocator>
803inline
804bool
805operator> (const multiset<_Key, _Compare, _Allocator>& __x,
806 const multiset<_Key, _Compare, _Allocator>& __y)
807{
808 return __y < __x;
809}
810
811template <class _Key, class _Compare, class _Allocator>
812inline
813bool
814operator>=(const multiset<_Key, _Compare, _Allocator>& __x,
815 const multiset<_Key, _Compare, _Allocator>& __y)
816{
817 return !(__x < __y);
818}
819
820template <class _Key, class _Compare, class _Allocator>
821inline
822bool
823operator<=(const multiset<_Key, _Compare, _Allocator>& __x,
824 const multiset<_Key, _Compare, _Allocator>& __y)
825{
826 return !(__y < __x);
827}
828
829template <class _Key, class _Compare, class _Allocator>
830inline
831void
832swap(multiset<_Key, _Compare, _Allocator>& __x,
833 multiset<_Key, _Compare, _Allocator>& __y)
834{
835 __x.swap(__y);
836}
837
838
839_LIBCPP_END_NAMESPACE_STD
840
841#endif // _LIBCPP_SET