| // -*- C++ -*- |
| /*************************************************************************** |
| * |
| * <set> - definition of the C++ Standard Library set class template |
| * |
| * $Id$ |
| * |
| *************************************************************************** |
| * |
| * Licensed to the Apache Software Foundation (ASF) under one or more |
| * contributor license agreements. See the NOTICE file distributed |
| * with this work for additional information regarding copyright |
| * ownership. The ASF licenses this file to you under the Apache |
| * License, Version 2.0 (the "License"); you may not use this file |
| * except in compliance with the License. You may obtain a copy of |
| * the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or |
| * implied. See the License for the specific language governing |
| * permissions and limitations under the License. |
| * |
| * Copyright 1994-2006 Rogue Wave Software. |
| * |
| *************************************************************************** |
| * |
| * Copyright (c) 1994 |
| * Hewlett-Packard Company |
| * |
| * Permission to use, copy, modify, distribute and sell this software |
| * and its documentation for any purpose is hereby granted without fee, |
| * provided that the above copyright notice appear in all copies and |
| * that both that copyright notice and this permission notice appear |
| * in supporting documentation. Hewlett-Packard Company makes no |
| * representations about the suitability of this software for any |
| * purpose. It is provided "as is" without express or implied warranty. |
| * |
| **************************************************************************/ |
| |
| #ifndef _RWSTD_SET_INCLUDED |
| #define _RWSTD_SET_INCLUDED |
| |
| |
| #include <rw/_allocator.h> // for allocator |
| #include <rw/_funcbase.h> // for less |
| #include <rw/_tree.h> // for __rb_tree |
| #include <rw/_defs.h> |
| |
| |
| _RWSTD_NAMESPACE (__rw) { |
| |
| |
| template <class _TypeT, class _TypeU> |
| struct __ident: _STD::unary_function<_TypeT, _TypeU> |
| { |
| const _TypeU& operator() (const _TypeT& __x) const { |
| return __x; |
| } |
| }; |
| |
| |
| } // namespace __rw |
| |
| |
| _RWSTD_NAMESPACE (std) { |
| |
| |
| template <class _Key, |
| class _Compare = less<_Key>, |
| class _Allocator = allocator<_Key> > |
| class set |
| { |
| public: |
| // |
| // Types |
| // |
| typedef _Key key_type; |
| typedef _Key value_type; |
| typedef _Compare key_compare; |
| typedef _Compare value_compare; |
| typedef _Allocator allocator_type; |
| |
| private: |
| |
| typedef _RW::__rb_tree<key_type, value_type, |
| _RW::__ident<value_type, key_type>, |
| key_compare, allocator_type> __rep_type; |
| __rep_type _C_rep; |
| |
| public: |
| // |
| // Types |
| // |
| // Note that iterator and reverse_iterator are typedefed to |
| // const iterators. This is intentional, the purpose is to |
| // prevent the modification of a set element after it has |
| // been inserted. |
| typedef typename __rep_type::reference reference; |
| typedef typename __rep_type::const_reference const_reference; |
| typedef typename __rep_type::const_iterator iterator; |
| typedef typename __rep_type::const_iterator const_iterator; |
| typedef typename __rep_type::size_type size_type; |
| typedef typename __rep_type::difference_type difference_type; |
| typedef typename __rep_type::pointer pointer; |
| typedef typename __rep_type::const_pointer const_pointer; |
| typedef typename __rep_type::const_reverse_iterator reverse_iterator; |
| typedef typename __rep_type::const_reverse_iterator |
| const_reverse_iterator; |
| |
| // |
| // construct/copy/destroy |
| // |
| explicit |
| set (const key_compare &__cmp = key_compare (), |
| const allocator_type &__alloc = allocator_type ()) |
| : _C_rep (__cmp, __alloc) { } |
| |
| template<class _InputIter> |
| set (_InputIter __first, _InputIter __last, |
| const key_compare& __cmp = key_compare (), |
| const allocator_type& __al = allocator_type ()) |
| : _C_rep (__first, __last, __cmp, __al, false) { } |
| |
| set (const set &__x) |
| : _C_rep (__x._C_rep) { } |
| |
| set& operator= (const set &__x) { |
| _C_rep = __x._C_rep; return *this; |
| } |
| |
| allocator_type get_allocator () const { |
| return _C_rep.get_allocator (); |
| } |
| |
| // |
| // iterators |
| // |
| iterator begin () { return _C_rep.begin (); } |
| const_iterator begin () const { return _C_rep.begin (); } |
| iterator end () { return _C_rep.end (); } |
| const_iterator end () const { return _C_rep.end (); } |
| reverse_iterator rbegin () { return _C_rep.rbegin (); } |
| const_reverse_iterator rbegin () const { return _C_rep.rbegin (); } |
| reverse_iterator rend () { return _C_rep.rend (); } |
| const_reverse_iterator rend () const { return _C_rep.rend (); } |
| |
| // |
| // capacity |
| // |
| bool empty () const { return _C_rep.empty (); } |
| size_type size () const { return _C_rep.size (); } |
| size_type max_size () const { return _C_rep.max_size (); } |
| |
| // |
| // modifiers |
| // |
| pair<iterator, bool> insert (const value_type& __x) { |
| const pair<typename __rep_type::iterator, bool> __p = |
| _C_rep.insert (__x, false); |
| return pair<iterator, bool>(__p.first, __p.second); |
| } |
| |
| #if !defined (_MSC_VER) || _MSC_VER > 1300 |
| |
| iterator insert (iterator __it, const value_type& __x) { |
| return _C_rep.insert (__it, __x, false); |
| } |
| |
| void erase (iterator __it) { |
| _C_rep.erase (__it); |
| } |
| |
| void erase (iterator __first, iterator __last) { |
| _C_rep.erase (__first, __last); |
| } |
| |
| #else |
| |
| // working around MSVC bugs |
| iterator insert (iterator __it, const value_type& __x) { |
| typedef typename __rep_type::iterator _Iterator; |
| return _RWSTD_REINTERPRET_CAST (iterator&, _C_rep.insert ( |
| _RWSTD_REINTERPRET_CAST (_Iterator&, __it), __x, false)); |
| } |
| |
| void erase (iterator __it) { |
| typedef typename __rep_type::iterator _Iterator; |
| _C_rep.erase (_RWSTD_REINTERPRET_CAST (_Iterator&, __it)); |
| } |
| |
| void erase (iterator __first, iterator __last) { |
| typedef typename __rep_type::iterator _Iterator; |
| _C_rep.erase (_RWSTD_REINTERPRET_CAST (_Iterator&, __first), |
| _RWSTD_REINTERPRET_CAST (_Iterator&, __last)); |
| } |
| |
| #endif |
| |
| template<class _InputIter> |
| void insert (_InputIter __first, _InputIter __last) { |
| for ( ;__first != __last; ++__first) |
| _C_rep.insert (*__first, false); |
| } |
| |
| size_type erase (const key_type& __x) { |
| return _C_rep.erase (__x); |
| } |
| |
| void swap (set& __x) { |
| _C_rep.swap (__x._C_rep); |
| } |
| |
| void clear () { |
| _C_rep.clear (); |
| } |
| |
| key_compare key_comp () const { |
| return _C_rep.key_comp (); |
| } |
| |
| value_compare value_comp () const { |
| return _C_rep.key_comp (); |
| } |
| |
| // follows proposed resolution of lwg issue 214 |
| iterator find (const key_type& __x) { |
| return _C_rep.find (__x); |
| } |
| |
| const_iterator find (const key_type& __x) const { |
| return _C_rep.find (__x); |
| } |
| |
| size_type count (const key_type& __x) const { |
| return _C_rep.count (__x); |
| } |
| |
| // follows proposed resolution of lwg issue 214 |
| iterator lower_bound (const key_type& __x) { |
| return _C_rep.lower_bound (__x); |
| } |
| |
| const_iterator lower_bound (const key_type& __x) const { |
| return _C_rep.lower_bound (__x); |
| } |
| |
| // follows proposed resolution of lwg issue 214 |
| iterator upper_bound (const key_type& __x) { |
| return _C_rep.upper_bound (__x); |
| } |
| |
| const_iterator upper_bound (const key_type& __x) const { |
| return _C_rep.upper_bound (__x); |
| } |
| |
| // follows proposed resolution of lwg issue 214 |
| pair<iterator, iterator> equal_range (const key_type& __x) { |
| return _RWSTD_CONST_CAST (const set*, this)->equal_range (__x); |
| } |
| |
| pair<const_iterator, const_iterator> |
| equal_range (const key_type& __x) const { |
| return _C_rep.equal_range (__x); |
| } |
| |
| #if defined (_RWSTD_NO_PART_SPEC_OVERLOAD) |
| friend void swap (set& __lhs, set& __rhs) { |
| __lhs.swap (__rhs); |
| } |
| #endif |
| |
| }; |
| |
| |
| template <class _Key, |
| class _Compare = less<_Key>, |
| class _Allocator = allocator<_Key> > |
| class multiset |
| { |
| public: |
| // |
| // types |
| // |
| typedef _Key key_type; |
| typedef _Key value_type; |
| typedef _Compare key_compare; |
| typedef _Compare value_compare; |
| typedef _Allocator allocator_type; |
| private: |
| |
| typedef _RW::__rb_tree<key_type, value_type, |
| _RW::__ident<value_type, key_type>, |
| key_compare, allocator_type> __rep_type; |
| __rep_type _C_rep; |
| |
| public: |
| // |
| // types |
| // |
| typedef typename __rep_type::reference reference; |
| typedef typename __rep_type::const_reference const_reference; |
| typedef typename __rep_type::iterator iterator; |
| typedef typename __rep_type::const_iterator const_iterator; |
| typedef typename __rep_type::size_type size_type; |
| typedef typename __rep_type::difference_type difference_type; |
| typedef typename __rep_type::pointer pointer; |
| typedef typename __rep_type::const_pointer const_pointer; |
| typedef typename __rep_type::reverse_iterator reverse_iterator; |
| typedef typename __rep_type::const_reverse_iterator |
| const_reverse_iterator; |
| |
| // |
| // construct/copy/destroy |
| // |
| explicit |
| multiset (const key_compare &__cmp = key_compare (), |
| const allocator_type &__alloc = allocator_type ()) |
| : _C_rep (__cmp, __alloc) { } |
| |
| template<class _InputIter> |
| multiset (_InputIter __first, _InputIter __last, |
| const key_compare &__cmp = key_compare (), |
| const allocator_type &__alloc = allocator_type ()) |
| : _C_rep (__first, __last, __cmp, __alloc, true) { } |
| |
| multiset (const multiset &__x) |
| : _C_rep (__x._C_rep) { } |
| |
| multiset& operator= (const multiset &__x) { |
| _C_rep = __x._C_rep; return *this; |
| } |
| |
| allocator_type get_allocator () const { |
| return _C_rep.get_allocator (); |
| } |
| |
| // |
| // iterators |
| // |
| iterator begin () { return _C_rep.begin (); } |
| const_iterator begin () const { return _C_rep.begin (); } |
| iterator end () { return _C_rep.end (); } |
| const_iterator end () const { return _C_rep.end (); } |
| reverse_iterator rbegin () { return _C_rep.rbegin (); } |
| const_reverse_iterator rbegin () const { return _C_rep.rbegin (); } |
| reverse_iterator rend () { return _C_rep.rend (); } |
| const_reverse_iterator rend () const { return _C_rep.rend (); } |
| |
| // |
| // capacity |
| // |
| bool empty () const { return _C_rep.empty (); } |
| size_type size () const { return _C_rep.size (); } |
| size_type max_size () const { return _C_rep.max_size (); } |
| |
| // |
| // modifiers |
| // |
| iterator insert (const value_type& __x) { |
| return _C_rep.insert (__x, true).first; |
| } |
| |
| iterator insert (iterator __it, const value_type& __x) { |
| return _C_rep.insert (__it, __x, true); |
| } |
| |
| template<class _InputIter> |
| void insert (_InputIter __first, _InputIter __last) { |
| for ( ;__first != __last; ++__first) |
| _C_rep.insert (*__first, true); |
| } |
| |
| void erase (iterator __it) { |
| _C_rep.erase (__it); |
| } |
| |
| size_type erase (const key_type& __x) { |
| return _C_rep.erase (__x); |
| } |
| |
| void erase (iterator __first, iterator __last) { |
| _C_rep.erase (__first, __last); |
| } |
| |
| void swap (multiset &__x) { |
| _C_rep.swap (__x._C_rep); |
| } |
| |
| void clear () { |
| _C_rep.clear (); |
| } |
| |
| key_compare key_comp () const { |
| return _C_rep.key_comp (); |
| } |
| |
| value_compare value_comp () const { |
| return _C_rep.key_comp (); |
| } |
| |
| // follows proposed resolution of lwg issue 214 |
| iterator find (const key_type& __x) { |
| return _C_rep.find (__x); |
| } |
| |
| const_iterator find (const key_type& __x) const { |
| return _C_rep.find (__x); |
| } |
| |
| size_type count (const key_type& __x) const { |
| return _C_rep.count (__x); |
| } |
| |
| // follows proposed resolution of lwg issue 214 |
| iterator lower_bound (const key_type& __x) { |
| return _C_rep.lower_bound (__x); |
| } |
| |
| const_iterator lower_bound (const key_type& __x) const { |
| return _C_rep.lower_bound (__x); |
| } |
| |
| // follows proposed resolution of lwg issue 214 |
| iterator upper_bound (const key_type& __x) { |
| return _C_rep.upper_bound (__x); |
| } |
| |
| const_iterator upper_bound (const key_type& __x) const { |
| return _C_rep.upper_bound (__x); |
| } |
| |
| // follows proposed resolution of lwg issue 214 |
| pair<iterator, iterator> |
| equal_range (const key_type& __x) { |
| return _C_rep.equal_range (__x); |
| } |
| |
| pair<const_iterator,const_iterator> |
| equal_range (const key_type& __x) const { |
| return _C_rep.equal_range (__x); |
| } |
| |
| #if defined (_RWSTD_NO_PART_SPEC_OVERLOAD) |
| friend void swap (multiset& __lhs, multiset& __rhs) { |
| __lhs.swap (__rhs); |
| } |
| #endif |
| |
| }; |
| |
| |
| template <class _Key, class _Compare, class _Allocator> |
| inline bool operator== (const set<_Key, _Compare, _Allocator>& __x, |
| const set<_Key, _Compare, _Allocator>& __y) |
| { |
| return __x.size () == __y.size () |
| && equal (__x.begin (), __x.end (), __y.begin ()); |
| } |
| |
| |
| template <class _Key, class _Compare, class _Allocator> |
| inline bool operator< (const set<_Key, _Compare, _Allocator>& __x, |
| const set<_Key, _Compare, _Allocator>& __y) |
| { |
| return lexicographical_compare (__x.begin (), __x.end (), |
| __y.begin (), __y.end ()); |
| } |
| |
| |
| template <class _Key, class _Compare, class _Allocator> |
| inline bool operator!= (const set<_Key,_Compare,_Allocator>& __x, |
| const set<_Key,_Compare,_Allocator>& __y) |
| { |
| return !(__x == __y); |
| } |
| |
| |
| template <class _Key, class _Compare, class _Allocator> |
| inline bool operator> (const set<_Key,_Compare,_Allocator>& __x, |
| const set<_Key,_Compare,_Allocator>& __y) |
| { |
| return __y < __x; |
| } |
| |
| |
| template <class _Key, class _Compare, class _Allocator> |
| inline bool operator>= (const set<_Key,_Compare,_Allocator>& __x, |
| const set<_Key,_Compare,_Allocator>& __y) |
| { |
| return !(__x < __y); |
| } |
| |
| |
| template <class _Key, class _Compare, class _Allocator> |
| inline bool operator<= (const set<_Key,_Compare,_Allocator>& __x, |
| const set<_Key,_Compare,_Allocator>& __y) |
| { |
| return !(__y < __x); |
| } |
| |
| |
| #ifndef _RWSTD_NO_PART_SPEC_OVERLOAD |
| |
| template <class _Key, class _Compare, class _Allocator> |
| void swap (set<_Key,_Compare,_Allocator>& __a, |
| set<_Key,_Compare,_Allocator>& __b) |
| { |
| __a.swap (__b); |
| } |
| |
| #endif // _RWSTD_NO_PART_SPEC_OVERLOAD |
| |
| |
| template <class _Key, class _Compare, class _Allocator> |
| inline bool operator== (const multiset<_Key, _Compare, _Allocator>& __x, |
| const multiset<_Key, _Compare, _Allocator>& __y) |
| { |
| return __x.size () == __y.size () |
| && equal (__x.begin (), __x.end (), __y.begin ()); |
| } |
| |
| |
| template <class _Key, class _Compare, class _Allocator> |
| inline bool operator< (const multiset<_Key, _Compare, _Allocator>& __x, |
| const multiset<_Key, _Compare, _Allocator>& __y) |
| { |
| return lexicographical_compare (__x.begin (), __x.end (), |
| __y.begin (), __y.end ()); |
| } |
| |
| |
| template <class _Key, class _Compare, class _Allocator> |
| inline bool operator!= (const multiset<_Key,_Compare,_Allocator>& __x, |
| const multiset<_Key,_Compare,_Allocator>& __y) |
| { |
| return !(__x == __y); |
| } |
| |
| |
| template <class _Key, class _Compare, class _Allocator> |
| inline bool operator> (const multiset<_Key,_Compare,_Allocator>& __x, |
| const multiset<_Key,_Compare,_Allocator>& __y) |
| { |
| return __y < __x; |
| } |
| |
| |
| template <class _Key, class _Compare, class _Allocator> |
| inline bool operator>= (const multiset<_Key,_Compare,_Allocator>& __x, |
| const multiset<_Key,_Compare,_Allocator>& __y) |
| { |
| return !(__x < __y); |
| } |
| |
| |
| template <class _Key, class _Compare, class _Allocator> |
| inline bool operator<= (const multiset<_Key,_Compare,_Allocator>& __x, |
| const multiset<_Key,_Compare,_Allocator>& __y) |
| { |
| return !(__y < __x); |
| } |
| |
| #ifndef _RWSTD_NO_PART_SPEC_OVERLOAD |
| |
| template <class _Key, class _Compare, class _Allocator> |
| void swap (multiset<_Key,_Compare,_Allocator>& __a, |
| multiset<_Key,_Compare,_Allocator>& __b) |
| { |
| __a.swap (__b); |
| } |
| |
| #endif // _RWSTD_NO_PART_SPEC_OVERLOAD |
| |
| |
| } // namespace std |
| |
| |
| #endif // _RWSTD_SET_INCLUDED |
