diff options
Diffstat (limited to 'contrib/libstdc++/include/bits/stl_set.h')
| -rw-r--r-- | contrib/libstdc++/include/bits/stl_set.h | 131 |
1 files changed, 58 insertions, 73 deletions
diff --git a/contrib/libstdc++/include/bits/stl_set.h b/contrib/libstdc++/include/bits/stl_set.h index bb28bddc7af9..b61106aef652 100644 --- a/contrib/libstdc++/include/bits/stl_set.h +++ b/contrib/libstdc++/include/bits/stl_set.h @@ -1,6 +1,6 @@ // Set implementation -*- C++ -*- -// Copyright (C) 2001, 2002, 2004 Free Software Foundation, Inc. +// Copyright (C) 2001, 2002, 2004, 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the @@ -15,7 +15,7 @@ // You should have received a copy of the GNU General Public License along // with this library; see the file COPYING. If not, write to the Free -// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, +// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, // USA. // As a special exception, you may use this file as part of a free software @@ -63,22 +63,7 @@ #include <bits/concept_check.h> -namespace _GLIBCXX_STD -{ - // Forward declarations of operators < and ==, needed for friend declaration. - template<class _Key, class _Compare = less<_Key>, - class _Alloc = allocator<_Key> > - class set; - - template<class _Key, class _Compare, class _Alloc> - inline bool - operator==(const set<_Key,_Compare,_Alloc>& __x, - const set<_Key,_Compare,_Alloc>& __y); - - template<class _Key, class _Compare, class _Alloc> - inline bool - operator<(const set<_Key,_Compare,_Alloc>& __x, - const set<_Key,_Compare,_Alloc>& __y); +_GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD) /** * @brief A standard container made up of unique keys, which can be @@ -103,13 +88,16 @@ namespace _GLIBCXX_STD * called (*_unique versus *_equal, same as the standard). * @endif */ - template<class _Key, class _Compare, class _Alloc> + template<class _Key, class _Compare = std::less<_Key>, + class _Alloc = std::allocator<_Key> > class set { // concept requirements + typedef typename _Alloc::value_type _Alloc_value_type; __glibcxx_class_requires(_Key, _SGIAssignableConcept) __glibcxx_class_requires4(_Compare, bool, _Key, _Key, _BinaryFunctionConcept) + __glibcxx_class_requires2(_Key, _Alloc_value_type, _SameTypeConcept) public: // typedefs: @@ -119,29 +107,32 @@ namespace _GLIBCXX_STD typedef _Key value_type; typedef _Compare key_compare; typedef _Compare value_compare; + typedef _Alloc allocator_type; //@} private: - typedef _Rb_tree<key_type, value_type, - _Identity<value_type>, key_compare, _Alloc> _Rep_type; + typedef typename _Alloc::template rebind<_Key>::other _Key_alloc_type; + + typedef _Rb_tree<key_type, value_type, _Identity<value_type>, + key_compare, _Key_alloc_type> _Rep_type; _Rep_type _M_t; // red-black tree representing set + public: //@{ /// Iterator-related typedefs. - typedef typename _Alloc::pointer pointer; - typedef typename _Alloc::const_pointer const_pointer; - typedef typename _Alloc::reference reference; - typedef typename _Alloc::const_reference const_reference; + typedef typename _Key_alloc_type::pointer pointer; + typedef typename _Key_alloc_type::const_pointer const_pointer; + typedef typename _Key_alloc_type::reference reference; + typedef typename _Key_alloc_type::const_reference const_reference; // _GLIBCXX_RESOLVE_LIB_DEFECTS // DR 103. set::iterator is required to be modifiable, // but this allows modification of keys. - typedef typename _Rep_type::const_iterator iterator; - typedef typename _Rep_type::const_iterator const_iterator; - typedef typename _Rep_type::const_reverse_iterator reverse_iterator; - typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator; - typedef typename _Rep_type::size_type size_type; - typedef typename _Rep_type::difference_type difference_type; - typedef typename _Rep_type::allocator_type allocator_type; + typedef typename _Rep_type::const_iterator iterator; + typedef typename _Rep_type::const_iterator const_iterator; + typedef typename _Rep_type::const_reverse_iterator reverse_iterator; + typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator; + typedef typename _Rep_type::size_type size_type; + typedef typename _Rep_type::difference_type difference_type; //@} // allocation/deallocation @@ -155,8 +146,9 @@ namespace _GLIBCXX_STD * @param comp Comparator to use. * @param a Allocator to use. */ - explicit set(const _Compare& __comp, - const allocator_type& __a = allocator_type()) + explicit + set(const _Compare& __comp, + const allocator_type& __a = allocator_type()) : _M_t(__comp, __a) {} /** @@ -171,7 +163,7 @@ namespace _GLIBCXX_STD template<class _InputIterator> set(_InputIterator __first, _InputIterator __last) : _M_t(_Compare(), allocator_type()) - { _M_t.insert_unique(__first, __last); } + { _M_t._M_insert_unique(__first, __last); } /** * @brief Builds a %set from a range. @@ -189,7 +181,7 @@ namespace _GLIBCXX_STD const _Compare& __comp, const allocator_type& __a = allocator_type()) : _M_t(__comp, __a) - { _M_t.insert_unique(__first, __last); } + { _M_t._M_insert_unique(__first, __last); } /** * @brief Set copy constructor. @@ -308,11 +300,12 @@ namespace _GLIBCXX_STD * * Insertion requires logarithmic time. */ - pair<iterator,bool> + std::pair<iterator,bool> insert(const value_type& __x) { - pair<typename _Rep_type::iterator, bool> __p = _M_t.insert_unique(__x); - return pair<iterator, bool>(__p.first, __p.second); + std::pair<typename _Rep_type::iterator, bool> __p = + _M_t._M_insert_unique(__x); + return std::pair<iterator, bool>(__p.first, __p.second); } /** @@ -336,10 +329,7 @@ namespace _GLIBCXX_STD */ iterator insert(iterator __position, const value_type& __x) - { - typedef typename _Rep_type::iterator _Rep_iterator; - return _M_t.insert_unique((_Rep_iterator&)__position, __x); - } + { return _M_t._M_insert_unique(__position, __x); } /** * @brief A template function that attemps to insert a range of elements. @@ -350,9 +340,9 @@ namespace _GLIBCXX_STD * Complexity similar to that of the range constructor. */ template<class _InputIterator> - void - insert(_InputIterator __first, _InputIterator __last) - { _M_t.insert_unique(__first, __last); } + void + insert(_InputIterator __first, _InputIterator __last) + { _M_t._M_insert_unique(__first, __last); } /** * @brief Erases an element from a %set. @@ -365,10 +355,7 @@ namespace _GLIBCXX_STD */ void erase(iterator __position) - { - typedef typename _Rep_type::iterator _Rep_iterator; - _M_t.erase((_Rep_iterator&)__position); - } + { _M_t.erase(__position); } /** * @brief Erases elements according to the provided key. @@ -382,7 +369,8 @@ namespace _GLIBCXX_STD * in any way. Managing the pointer is the user's responsibilty. */ size_type - erase(const key_type& __x) { return _M_t.erase(__x); } + erase(const key_type& __x) + { return _M_t.erase(__x); } /** * @brief Erases a [first,last) range of elements from a %set. @@ -397,10 +385,7 @@ namespace _GLIBCXX_STD */ void erase(iterator __first, iterator __last) - { - typedef typename _Rep_type::iterator _Rep_iterator; - _M_t.erase((_Rep_iterator&)__first, (_Rep_iterator&)__last); - } + { _M_t.erase(__first, __last); } /** * Erases all elements in a %set. Note that this function only erases @@ -502,22 +487,22 @@ namespace _GLIBCXX_STD * * This function probably only makes sense for multisets. */ - pair<iterator,iterator> + std::pair<iterator, iterator> equal_range(const key_type& __x) { return _M_t.equal_range(__x); } - pair<const_iterator,const_iterator> + std::pair<const_iterator, const_iterator> equal_range(const key_type& __x) const { return _M_t.equal_range(__x); } //@} template<class _K1, class _C1, class _A1> friend bool - operator== (const set<_K1,_C1,_A1>&, const set<_K1,_C1,_A1>&); + operator== (const set<_K1, _C1, _A1>&, const set<_K1, _C1, _A1>&); template<class _K1, class _C1, class _A1> friend bool - operator< (const set<_K1,_C1,_A1>&, const set<_K1,_C1,_A1>&); + operator< (const set<_K1, _C1, _A1>&, const set<_K1, _C1, _A1>&); }; @@ -533,8 +518,8 @@ namespace _GLIBCXX_STD */ template<class _Key, class _Compare, class _Alloc> inline bool - operator==(const set<_Key,_Compare,_Alloc>& __x, - const set<_Key,_Compare,_Alloc>& __y) + operator==(const set<_Key, _Compare, _Alloc>& __x, + const set<_Key, _Compare, _Alloc>& __y) { return __x._M_t == __y._M_t; } /** @@ -550,44 +535,44 @@ namespace _GLIBCXX_STD */ template<class _Key, class _Compare, class _Alloc> inline bool - operator<(const set<_Key,_Compare,_Alloc>& __x, - const set<_Key,_Compare,_Alloc>& __y) + operator<(const set<_Key, _Compare, _Alloc>& __x, + const set<_Key, _Compare, _Alloc>& __y) { return __x._M_t < __y._M_t; } /// Returns !(x == y). template<class _Key, class _Compare, class _Alloc> inline bool - operator!=(const set<_Key,_Compare,_Alloc>& __x, - const set<_Key,_Compare,_Alloc>& __y) + operator!=(const set<_Key, _Compare, _Alloc>& __x, + const set<_Key, _Compare, _Alloc>& __y) { return !(__x == __y); } /// Returns y < x. template<class _Key, class _Compare, class _Alloc> inline bool - operator>(const set<_Key,_Compare,_Alloc>& __x, - const set<_Key,_Compare,_Alloc>& __y) + operator>(const set<_Key, _Compare, _Alloc>& __x, + const set<_Key, _Compare, _Alloc>& __y) { return __y < __x; } /// Returns !(y < x) template<class _Key, class _Compare, class _Alloc> inline bool - operator<=(const set<_Key,_Compare,_Alloc>& __x, - const set<_Key,_Compare,_Alloc>& __y) + operator<=(const set<_Key, _Compare, _Alloc>& __x, + const set<_Key, _Compare, _Alloc>& __y) { return !(__y < __x); } /// Returns !(x < y) template<class _Key, class _Compare, class _Alloc> inline bool - operator>=(const set<_Key,_Compare,_Alloc>& __x, - const set<_Key,_Compare,_Alloc>& __y) + operator>=(const set<_Key, _Compare, _Alloc>& __x, + const set<_Key, _Compare, _Alloc>& __y) { return !(__x < __y); } /// See std::set::swap(). template<class _Key, class _Compare, class _Alloc> inline void - swap(set<_Key,_Compare,_Alloc>& __x, set<_Key,_Compare,_Alloc>& __y) + swap(set<_Key, _Compare, _Alloc>& __x, set<_Key, _Compare, _Alloc>& __y) { __x.swap(__y); } -} // namespace std +_GLIBCXX_END_NESTED_NAMESPACE #endif /* _SET_H */ |