111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert/* 211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * 311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * Copyright (c) 1994 411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * Hewlett-Packard Company 511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * 611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * Copyright (c) 1996,1997 711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * Silicon Graphics Computer Systems, Inc. 811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * 911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * Copyright (c) 1997 1011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * Moscow Center for SPARC Technology 1111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * 1211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * Copyright (c) 1999 1311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * Boris Fomitchev 1411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * 1511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * This material is provided "as is", with absolutely no warranty expressed 1611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * or implied. Any use is at your own risk. 1711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * 1811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * Permission to use or copy this software for any purpose is hereby granted 1911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * without fee, provided the above notices are retained on all copies. 2011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * Permission to modify the code and to distribute modified code is granted, 2111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * provided the above notices are retained, and a notice that the code was 2211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * modified is included with the above copyright notice. 2311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * 2411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert */ 2511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 2611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert/* NOTE: This is an internal header file, included by other STL headers. 2711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * You should not attempt to use it directly. 2811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert */ 2911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 3011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifndef _STLP_INTERNAL_SET_H 3111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define _STLP_INTERNAL_SET_H 3211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 3311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifndef _STLP_INTERNAL_TREE_H 3411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert# include <stl/_tree.h> 3511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 3611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 3711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#if !defined (_STLP_USE_PTR_SPECIALIZATIONS) 3811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 3911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert_STLP_BEGIN_NAMESPACE 4011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 4111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert//Specific iterator traits creation 4211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert_STLP_CREATE_ITERATOR_TRAITS(SetTraitsT, Const_traits) 4311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 4411cd02dfb91661c65134cac258cf5924270e9d2Dan Alberttemplate <class _Key, _STLP_DFL_TMPL_PARAM(_Compare, less<_Key>), 4511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_DFL_TMPL_PARAM(_Alloc, allocator<_Key>) > 4611cd02dfb91661c65134cac258cf5924270e9d2Dan Albertclass set 4711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) 4811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert : public __stlport_class<set<_Key, _Compare, _Alloc> > 4911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 5011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert{ 5111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef set<_Key, _Compare, _Alloc> _Self; 5211cd02dfb91661c65134cac258cf5924270e9d2Dan Albertpublic: 5311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// typedefs: 5411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef _Key key_type; 5511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef _Key value_type; 5611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef _Compare key_compare; 5711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef _Compare value_compare; 5811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 5911cd02dfb91661c65134cac258cf5924270e9d2Dan Albertprivate: 6011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert //Specific iterator traits creation 6111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef _STLP_PRIV _SetTraitsT<value_type> _SetTraits; 6211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 6311cd02dfb91661c65134cac258cf5924270e9d2Dan Albertpublic: 6411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert //Following typedef have to be public for __move_traits specialization. 6511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef _STLP_PRIV _Rb_tree<key_type, key_compare, 6611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert value_type, _STLP_PRIV _Identity<value_type>, 6711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _SetTraits, _Alloc> _Rep_type; 6811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 6911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Rep_type::pointer pointer; 7011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Rep_type::const_pointer const_pointer; 7111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Rep_type::reference reference; 7211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Rep_type::const_reference const_reference; 7311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Rep_type::iterator iterator; 7411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Rep_type::const_iterator const_iterator; 7511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Rep_type::reverse_iterator reverse_iterator; 7611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator; 7711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Rep_type::size_type size_type; 7811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Rep_type::difference_type difference_type; 7911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Rep_type::allocator_type allocator_type; 8011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 8111cd02dfb91661c65134cac258cf5924270e9d2Dan Albertprivate: 8211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rep_type _M_t; // red-black tree representing set 8311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_KEY_TYPE_FOR_CONT_EXT(key_type) 8411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 8511cd02dfb91661c65134cac258cf5924270e9d2Dan Albertpublic: 8611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 8711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // allocation/deallocation 8811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#if !defined (_STLP_DONT_SUP_DFLT_PARAM) 8911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert explicit set(const _Compare& __comp = _Compare(), 9011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const allocator_type& __a = allocator_type()) 9111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#else 9211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert set() 9311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert : _M_t(_Compare(), allocator_type()) {} 9411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert explicit set(const _Compare& __comp) 9511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert : _M_t(__comp, allocator_type()) {} 9611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert set(const _Compare& __comp, const allocator_type& __a) 9711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 9811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert : _M_t(__comp, __a) {} 9911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 10011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#if defined (_STLP_MEMBER_TEMPLATES) 10111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template <class _InputIterator> 10211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert set(_InputIterator __first, _InputIterator __last) 10311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert : _M_t(_Compare(), allocator_type()) 10411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { _M_t.insert_unique(__first, __last); } 10511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 10611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert# if defined (_STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS) 10711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template <class _InputIterator> 10811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert set(_InputIterator __first, _InputIterator __last, const _Compare& __comp) 10911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert : _M_t(__comp, allocator_type()) { _M_t.insert_unique(__first, __last); } 11011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert# endif 11111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template <class _InputIterator> 11211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert set(_InputIterator __first, _InputIterator __last, const _Compare& __comp, 11311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL) 11411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); } 11511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#else 11611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert set(const value_type* __first, const value_type* __last) 11711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert : _M_t(_Compare(), allocator_type()) 11811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { _M_t.insert_unique(__first, __last); } 11911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 12011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert set(const value_type* __first, 12111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const value_type* __last, const _Compare& __comp, 12211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const allocator_type& __a = allocator_type()) 12311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); } 12411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 12511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert set(const_iterator __first, const_iterator __last) 12611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert : _M_t(_Compare(), allocator_type()) 12711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { _M_t.insert_unique(__first, __last); } 12811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 12911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert set(const_iterator __first, const_iterator __last, const _Compare& __comp, 13011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const allocator_type& __a = allocator_type()) 13111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); } 13211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif /* _STLP_MEMBER_TEMPLATES */ 13311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 13411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert set(const _Self& __x) : _M_t(__x._M_t) {} 13511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 13611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#if !defined (_STLP_NO_MOVE_SEMANTIC) 13711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert set(__move_source<_Self> src) 13811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert : _M_t(__move_source<_Rep_type>(src.get()._M_t)) {} 13911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 14011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 14111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Self& operator=(const _Self& __x) { 14211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_t = __x._M_t; 14311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return *this; 14411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 14511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 14611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // accessors: 14711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert key_compare key_comp() const { return _M_t.key_comp(); } 14811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert value_compare value_comp() const { return _M_t.key_comp(); } 14911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert allocator_type get_allocator() const { return _M_t.get_allocator(); } 15011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 15111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert iterator begin() { return _M_t.begin(); } 15211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert iterator end() { return _M_t.end(); } 15311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const_iterator begin() const { return _M_t.begin(); } 15411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const_iterator end() const { return _M_t.end(); } 15511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert reverse_iterator rbegin() { return _M_t.rbegin(); } 15611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert reverse_iterator rend() { return _M_t.rend(); } 15711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const_reverse_iterator rbegin() const { return _M_t.rbegin(); } 15811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const_reverse_iterator rend() const { return _M_t.rend(); } 15911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool empty() const { return _M_t.empty(); } 16011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_type size() const { return _M_t.size(); } 16111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_type max_size() const { return _M_t.max_size(); } 16211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void swap(_Self& __x) { _M_t.swap(__x._M_t); } 16311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER) 16411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void _M_swap_workaround(_Self& __x) { swap(__x); } 16511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 16611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 16711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // insert/erase 16811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert pair<iterator,bool> insert(const value_type& __x) 16911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return _M_t.insert_unique(__x); } 17011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert iterator insert(iterator __pos, const value_type& __x) 17111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return _M_t.insert_unique( __pos , __x); } 17211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#if defined (_STLP_MEMBER_TEMPLATES) 17311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template <class _InputIterator> 17411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void insert(_InputIterator __first, _InputIterator __last) 17511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { _M_t.insert_unique(__first, __last); } 17611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#else 17711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void insert(const_iterator __first, const_iterator __last) 17811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { _M_t.insert_unique(__first, __last); } 17911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void insert(const value_type* __first, const value_type* __last) 18011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { _M_t.insert_unique(__first, __last); } 18111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif /* _STLP_MEMBER_TEMPLATES */ 18211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void erase(iterator __pos) { _M_t.erase( __pos ); } 18311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_type erase(const key_type& __x) { return _M_t.erase_unique(__x); } 18411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void erase(iterator __first, iterator __last) { _M_t.erase(__first, __last ); } 18511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void clear() { _M_t.clear(); } 18611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 18711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // set operations: 18811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_TEMPLATE_FOR_CONT_EXT 18911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const_iterator find(const _KT& __x) const { return _M_t.find(__x); } 19011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_TEMPLATE_FOR_CONT_EXT 19111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert iterator find(const _KT& __x) { return _M_t.find(__x); } 19211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_TEMPLATE_FOR_CONT_EXT 19311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_type count(const _KT& __x) const 19411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return _M_t.find(__x) == _M_t.end() ? 0 : 1 ; } 19511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_TEMPLATE_FOR_CONT_EXT 19611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert iterator lower_bound(const _KT& __x) { return _M_t.lower_bound(__x); } 19711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_TEMPLATE_FOR_CONT_EXT 19811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const_iterator lower_bound(const _KT& __x) const { return _M_t.lower_bound(__x); } 19911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_TEMPLATE_FOR_CONT_EXT 20011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert iterator upper_bound(const _KT& __x) { return _M_t.upper_bound(__x); } 20111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_TEMPLATE_FOR_CONT_EXT 20211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const_iterator upper_bound(const _KT& __x) const { return _M_t.upper_bound(__x); } 20311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_TEMPLATE_FOR_CONT_EXT 20411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert pair<iterator, iterator> equal_range(const _KT& __x) 20511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return _M_t.equal_range_unique(__x); } 20611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_TEMPLATE_FOR_CONT_EXT 20711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert pair<const_iterator, const_iterator> equal_range(const _KT& __x) const 20811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return _M_t.equal_range_unique(__x); } 20911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert}; 21011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 21111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert//Specific iterator traits creation 21211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert_STLP_CREATE_ITERATOR_TRAITS(MultisetTraitsT, Const_traits) 21311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 21411cd02dfb91661c65134cac258cf5924270e9d2Dan Alberttemplate <class _Key, _STLP_DFL_TMPL_PARAM(_Compare, less<_Key>), 21511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_DFL_TMPL_PARAM(_Alloc, allocator<_Key>) > 21611cd02dfb91661c65134cac258cf5924270e9d2Dan Albertclass multiset 21711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) 21811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert : public __stlport_class<multiset<_Key, _Compare, _Alloc> > 21911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 22011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert{ 22111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef multiset<_Key, _Compare, _Alloc> _Self; 22211cd02dfb91661c65134cac258cf5924270e9d2Dan Albertpublic: 22311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // typedefs: 22411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 22511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef _Key key_type; 22611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef _Key value_type; 22711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef _Compare key_compare; 22811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef _Compare value_compare; 22911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 23011cd02dfb91661c65134cac258cf5924270e9d2Dan Albertprivate: 23111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert //Specific iterator traits creation 23211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef _STLP_PRIV _MultisetTraitsT<value_type> _MultisetTraits; 23311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 23411cd02dfb91661c65134cac258cf5924270e9d2Dan Albertpublic: 23511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert //Following typedef have to be public for __move_traits specialization. 23611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef _STLP_PRIV _Rb_tree<key_type, key_compare, 23711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert value_type, _STLP_PRIV _Identity<value_type>, 23811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _MultisetTraits, _Alloc> _Rep_type; 23911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 24011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Rep_type::pointer pointer; 24111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Rep_type::const_pointer const_pointer; 24211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Rep_type::reference reference; 24311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Rep_type::const_reference const_reference; 24411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Rep_type::iterator iterator; 24511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Rep_type::const_iterator const_iterator; 24611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Rep_type::reverse_iterator reverse_iterator; 24711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator; 24811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Rep_type::size_type size_type; 24911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Rep_type::difference_type difference_type; 25011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Rep_type::allocator_type allocator_type; 25111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 25211cd02dfb91661c65134cac258cf5924270e9d2Dan Albertprivate: 25311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rep_type _M_t; // red-black tree representing multiset 25411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_KEY_TYPE_FOR_CONT_EXT(key_type) 25511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 25611cd02dfb91661c65134cac258cf5924270e9d2Dan Albertpublic: 25711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#if !defined (_STLP_DONT_SUP_DFLT_PARAM) 25811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert explicit multiset(const _Compare& __comp = _Compare(), 25911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const allocator_type& __a = allocator_type()) 26011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#else 26111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert multiset() 26211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert : _M_t(_Compare(), allocator_type()) {} 26311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert explicit multiset(const _Compare& __comp) 26411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert : _M_t(__comp, allocator_type()) {} 26511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert multiset(const _Compare& __comp, const allocator_type& __a) 26611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 26711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert : _M_t(__comp, __a) {} 26811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 26911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#if defined (_STLP_MEMBER_TEMPLATES) 27011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template <class _InputIterator> 27111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert multiset(_InputIterator __first, _InputIterator __last) 27211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert : _M_t(_Compare(), allocator_type()) 27311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { _M_t.insert_equal(__first, __last); } 27411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 27511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template <class _InputIterator> 27611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert multiset(_InputIterator __first, _InputIterator __last, 27711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const _Compare& __comp, 27811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL) 27911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); } 28011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert# if defined (_STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS) 28111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template <class _InputIterator> 28211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert multiset(_InputIterator __first, _InputIterator __last, 28311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const _Compare& __comp) 28411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert : _M_t(__comp, allocator_type()) { _M_t.insert_equal(__first, __last); } 28511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert# endif 28611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#else 28711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert multiset(const value_type* __first, const value_type* __last) 28811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert : _M_t(_Compare(), allocator_type()) 28911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { _M_t.insert_equal(__first, __last); } 29011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 29111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert multiset(const value_type* __first, const value_type* __last, 29211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const _Compare& __comp, 29311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const allocator_type& __a = allocator_type()) 29411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); } 29511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 29611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert multiset(const_iterator __first, const_iterator __last) 29711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert : _M_t(_Compare(), allocator_type()) 29811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { _M_t.insert_equal(__first, __last); } 29911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 30011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert multiset(const_iterator __first, const_iterator __last, 30111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const _Compare& __comp, 30211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const allocator_type& __a = allocator_type()) 30311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); } 30411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif /* _STLP_MEMBER_TEMPLATES */ 30511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 30611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert multiset(const _Self& __x) : _M_t(__x._M_t) {} 30711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Self& operator=(const _Self& __x) { 30811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_t = __x._M_t; 30911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return *this; 31011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 31111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 31211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#if !defined (_STLP_NO_MOVE_SEMANTIC) 31311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert multiset(__move_source<_Self> src) 31411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert : _M_t(__move_source<_Rep_type>(src.get()._M_t)) {} 31511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 31611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 31711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // accessors: 31811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert key_compare key_comp() const { return _M_t.key_comp(); } 31911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert value_compare value_comp() const { return _M_t.key_comp(); } 32011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert allocator_type get_allocator() const { return _M_t.get_allocator(); } 32111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 32211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert iterator begin() { return _M_t.begin(); } 32311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert iterator end() { return _M_t.end(); } 32411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const_iterator begin() const { return _M_t.begin(); } 32511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const_iterator end() const { return _M_t.end(); } 32611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert reverse_iterator rbegin() { return _M_t.rbegin(); } 32711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert reverse_iterator rend() { return _M_t.rend(); } 32811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const_reverse_iterator rbegin() const { return _M_t.rbegin(); } 32911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const_reverse_iterator rend() const { return _M_t.rend(); } 33011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool empty() const { return _M_t.empty(); } 33111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_type size() const { return _M_t.size(); } 33211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_type max_size() const { return _M_t.max_size(); } 33311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void swap(_Self& __x) { _M_t.swap(__x._M_t); } 33411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER) 33511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void _M_swap_workaround(_Self& __x) { swap(__x); } 33611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 33711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 33811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // insert/erase 33911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert iterator insert(const value_type& __x) 34011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return _M_t.insert_equal(__x); } 34111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert iterator insert(iterator __pos, const value_type& __x) 34211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return _M_t.insert_equal(__pos, __x); } 34311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 34411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#if defined (_STLP_MEMBER_TEMPLATES) 34511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template <class _InputIterator> 34611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void insert(_InputIterator __first, _InputIterator __last) 34711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { _M_t.insert_equal(__first, __last); } 34811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#else 34911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void insert(const value_type* __first, const value_type* __last) 35011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { _M_t.insert_equal(__first, __last); } 35111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void insert(const_iterator __first, const_iterator __last) 35211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { _M_t.insert_equal(__first, __last); } 35311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif /* _STLP_MEMBER_TEMPLATES */ 35411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void erase(iterator __pos) { _M_t.erase( __pos ); } 35511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_type erase(const key_type& __x) { return _M_t.erase(__x); } 35611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void erase(iterator __first, iterator __last) { _M_t.erase( __first, __last ); } 35711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void clear() { _M_t.clear(); } 35811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 35911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // multiset operations: 36011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_TEMPLATE_FOR_CONT_EXT 36111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert iterator find(const _KT& __x) { return _M_t.find(__x); } 36211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_TEMPLATE_FOR_CONT_EXT 36311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const_iterator find(const _KT& __x) const { return _M_t.find(__x); } 36411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_TEMPLATE_FOR_CONT_EXT 36511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_type count(const _KT& __x) const { return _M_t.count(__x); } 36611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_TEMPLATE_FOR_CONT_EXT 36711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert iterator lower_bound(const _KT& __x) { return _M_t.lower_bound(__x); } 36811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_TEMPLATE_FOR_CONT_EXT 36911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const_iterator lower_bound(const _KT& __x) const { return _M_t.lower_bound(__x); } 37011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_TEMPLATE_FOR_CONT_EXT 37111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert iterator upper_bound(const _KT& __x) { return _M_t.upper_bound(__x); } 37211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_TEMPLATE_FOR_CONT_EXT 37311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const_iterator upper_bound(const _KT& __x) const { return _M_t.upper_bound(__x); } 37411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_TEMPLATE_FOR_CONT_EXT 37511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert pair<iterator, iterator> equal_range(const _KT& __x) { return _M_t.equal_range(__x); } 37611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_TEMPLATE_FOR_CONT_EXT 37711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert pair<const_iterator, const_iterator> equal_range(const _KT& __x) const { return _M_t.equal_range(__x); } 37811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert}; 37911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 38011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#else 38111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert# include <stl/pointers/_set.h> 38211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert_STLP_BEGIN_NAMESPACE 38311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif /* _STLP_USE_PTR_SPECIALIZATIONS */ 38411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 38511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define _STLP_TEMPLATE_HEADER template <class _Key, class _Compare, class _Alloc> 38611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define _STLP_TEMPLATE_CONTAINER set<_Key,_Compare,_Alloc> 38711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <stl/_relops_cont.h> 38811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#undef _STLP_TEMPLATE_CONTAINER 38911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define _STLP_TEMPLATE_CONTAINER multiset<_Key,_Compare,_Alloc> 39011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <stl/_relops_cont.h> 39111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#undef _STLP_TEMPLATE_CONTAINER 39211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#undef _STLP_TEMPLATE_HEADER 39311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 39411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) && !defined (_STLP_NO_MOVE_SEMANTIC) 39511cd02dfb91661c65134cac258cf5924270e9d2Dan Alberttemplate <class _Key, class _Compare, class _Alloc> 39611cd02dfb91661c65134cac258cf5924270e9d2Dan Albertstruct __move_traits<set<_Key,_Compare,_Alloc> > : 39711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_PRIV __move_traits_aux<typename set<_Key,_Compare,_Alloc>::_Rep_type> 39811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert{}; 39911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 40011cd02dfb91661c65134cac258cf5924270e9d2Dan Alberttemplate <class _Key, class _Compare, class _Alloc> 40111cd02dfb91661c65134cac258cf5924270e9d2Dan Albertstruct __move_traits<multiset<_Key,_Compare,_Alloc> > : 40211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_PRIV __move_traits_aux<typename multiset<_Key,_Compare,_Alloc>::_Rep_type> 40311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert{}; 40411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 40511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 40611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert_STLP_END_NAMESPACE 40711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 40811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif /* _STLP_INTERNAL_SET_H */ 40911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 41011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Local Variables: 41111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// mode:C++ 41211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// End: 413