Copyright (C) 2000-2012 |
Whole document tree stl_set.hGo to the documentation of this file.00001 // Set implementation -*- C++ -*- 00002 00003 // Copyright (C) 2001 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the 00007 // terms of the GNU General Public License as published by the 00008 // Free Software Foundation; either version 2, or (at your option) 00009 // any later version. 00010 00011 // This library is distributed in the hope that it will be useful, 00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 // GNU General Public License for more details. 00015 00016 // You should have received a copy of the GNU General Public License along 00017 // with this library; see the file COPYING. If not, write to the Free 00018 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 00019 // USA. 00020 00021 // As a special exception, you may use this file as part of a free software 00022 // library without restriction. Specifically, if other files instantiate 00023 // templates or use macros or inline functions from this file, or you compile 00024 // this file and link it with other files to produce an executable, this 00025 // file does not by itself cause the resulting executable to be covered by 00026 // the GNU General Public License. This exception does not however 00027 // invalidate any other reasons why the executable file might be covered by 00028 // the GNU General Public License. 00029 00030 /* 00031 * 00032 * Copyright (c) 1994 00033 * Hewlett-Packard Company 00034 * 00035 * Permission to use, copy, modify, distribute and sell this software 00036 * and its documentation for any purpose is hereby granted without fee, 00037 * provided that the above copyright notice appear in all copies and 00038 * that both that copyright notice and this permission notice appear 00039 * in supporting documentation. Hewlett-Packard Company makes no 00040 * representations about the suitability of this software for any 00041 * purpose. It is provided "as is" without express or implied warranty. 00042 * 00043 * 00044 * Copyright (c) 1996,1997 00045 * Silicon Graphics Computer Systems, Inc. 00046 * 00047 * Permission to use, copy, modify, distribute and sell this software 00048 * and its documentation for any purpose is hereby granted without fee, 00049 * provided that the above copyright notice appear in all copies and 00050 * that both that copyright notice and this permission notice appear 00051 * in supporting documentation. Silicon Graphics makes no 00052 * representations about the suitability of this software for any 00053 * purpose. It is provided "as is" without express or implied warranty. 00054 */ 00055 00056 /* NOTE: This is an internal header file, included by other STL headers. 00057 * You should not attempt to use it directly. 00058 */ 00059 00060 #ifndef __SGI_STL_INTERNAL_SET_H 00061 #define __SGI_STL_INTERNAL_SET_H 00062 00063 #include <bits/concept_check.h> 00064 00065 namespace std 00066 { 00067 00068 // Forward declarations of operators < and ==, needed for friend declaration. 00069 00070 template <class _Key, class _Compare = less<_Key>, 00071 class _Alloc = allocator<_Key> > 00072 class set; 00073 00074 template <class _Key, class _Compare, class _Alloc> 00075 inline bool operator==(const set<_Key,_Compare,_Alloc>& __x, 00076 const set<_Key,_Compare,_Alloc>& __y); 00077 00078 template <class _Key, class _Compare, class _Alloc> 00079 inline bool operator<(const set<_Key,_Compare,_Alloc>& __x, 00080 const set<_Key,_Compare,_Alloc>& __y); 00081 00082 00083 template <class _Key, class _Compare, class _Alloc> 00084 class set 00085 { 00086 // concept requirements 00087 __glibcpp_class_requires(_Key, _SGIAssignableConcept); 00088 __glibcpp_class_requires4(_Compare, bool, _Key, _Key, _BinaryFunctionConcept); 00089 00090 public: 00091 // typedefs: 00092 typedef _Key key_type; 00093 typedef _Key value_type; 00094 typedef _Compare key_compare; 00095 typedef _Compare value_compare; 00096 private: 00097 typedef _Rb_tree<key_type, value_type, 00098 _Identity<value_type>, key_compare, _Alloc> _Rep_type; 00099 _Rep_type _M_t; // red-black tree representing set 00100 public: 00101 typedef typename _Rep_type::const_pointer pointer; 00102 typedef typename _Rep_type::const_pointer const_pointer; 00103 typedef typename _Rep_type::const_reference reference; 00104 typedef typename _Rep_type::const_reference const_reference; 00105 typedef typename _Rep_type::const_iterator iterator; 00106 typedef typename _Rep_type::const_iterator const_iterator; 00107 typedef typename _Rep_type::const_reverse_iterator reverse_iterator; 00108 typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator; 00109 typedef typename _Rep_type::size_type size_type; 00110 typedef typename _Rep_type::difference_type difference_type; 00111 typedef typename _Rep_type::allocator_type allocator_type; 00112 00113 // allocation/deallocation 00114 00115 set() : _M_t(_Compare(), allocator_type()) {} 00116 explicit set(const _Compare& __comp, 00117 const allocator_type& __a = allocator_type()) 00118 : _M_t(__comp, __a) {} 00119 00120 template <class _InputIterator> 00121 set(_InputIterator __first, _InputIterator __last) 00122 : _M_t(_Compare(), allocator_type()) 00123 { _M_t.insert_unique(__first, __last); } 00124 00125 template <class _InputIterator> 00126 set(_InputIterator __first, _InputIterator __last, const _Compare& __comp, 00127 const allocator_type& __a = allocator_type()) 00128 : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); } 00129 00130 set(const set<_Key,_Compare,_Alloc>& __x) : _M_t(__x._M_t) {} 00131 set<_Key,_Compare,_Alloc>& operator=(const set<_Key, _Compare, _Alloc>& __x) 00132 { 00133 _M_t = __x._M_t; 00134 return *this; 00135 } 00136 00137 // accessors: 00138 00139 key_compare key_comp() const { return _M_t.key_comp(); } 00140 value_compare value_comp() const { return _M_t.key_comp(); } 00141 allocator_type get_allocator() const { return _M_t.get_allocator(); } 00142 00143 iterator begin() const { return _M_t.begin(); } 00144 iterator end() const { return _M_t.end(); } 00145 reverse_iterator rbegin() const { return _M_t.rbegin(); } 00146 reverse_iterator rend() const { return _M_t.rend(); } 00147 bool empty() const { return _M_t.empty(); } 00148 size_type size() const { return _M_t.size(); } 00149 size_type max_size() const { return _M_t.max_size(); } 00150 void swap(set<_Key,_Compare,_Alloc>& __x) { _M_t.swap(__x._M_t); } 00151 00152 // insert/erase 00153 pair<iterator,bool> insert(const value_type& __x) { 00154 pair<typename _Rep_type::iterator, bool> __p = _M_t.insert_unique(__x); 00155 return pair<iterator, bool>(__p.first, __p.second); 00156 } 00157 iterator insert(iterator __position, const value_type& __x) { 00158 typedef typename _Rep_type::iterator _Rep_iterator; 00159 return _M_t.insert_unique((_Rep_iterator&)__position, __x); 00160 } 00161 template <class _InputIterator> 00162 void insert(_InputIterator __first, _InputIterator __last) { 00163 _M_t.insert_unique(__first, __last); 00164 } 00165 void erase(iterator __position) { 00166 typedef typename _Rep_type::iterator _Rep_iterator; 00167 _M_t.erase((_Rep_iterator&)__position); 00168 } 00169 size_type erase(const key_type& __x) { 00170 return _M_t.erase(__x); 00171 } 00172 void erase(iterator __first, iterator __last) { 00173 typedef typename _Rep_type::iterator _Rep_iterator; 00174 _M_t.erase((_Rep_iterator&)__first, (_Rep_iterator&)__last); 00175 } 00176 void clear() { _M_t.clear(); } 00177 00178 // set operations: 00179 00180 size_type count(const key_type& __x) const { 00181 return _M_t.find(__x) == _M_t.end() ? 0 : 1; 00182 } 00183 00184 #ifdef _GLIBCPP_RESOLVE_LIB_DEFECTS 00185 //214. set::find() missing const overload 00186 iterator find(const key_type& __x) { return _M_t.find(__x); } 00187 const_iterator find(const key_type& __x) const { return _M_t.find(__x); } 00188 iterator lower_bound(const key_type& __x) { 00189 return _M_t.lower_bound(__x); 00190 } 00191 const_iterator lower_bound(const key_type& __x) const { 00192 return _M_t.lower_bound(__x); 00193 } 00194 iterator upper_bound(const key_type& __x) { 00195 return _M_t.upper_bound(__x); 00196 } 00197 const_iterator upper_bound(const key_type& __x) const { 00198 return _M_t.upper_bound(__x); 00199 } 00200 pair<iterator,iterator> equal_range(const key_type& __x) { 00201 return _M_t.equal_range(__x); 00202 } 00203 pair<const_iterator,const_iterator> equal_range(const key_type& __x) const { 00204 return _M_t.equal_range(__x); 00205 } 00206 #else 00207 iterator find(const key_type& __x) const { return _M_t.find(__x); } 00208 iterator lower_bound(const key_type& __x) const { 00209 return _M_t.lower_bound(__x); 00210 } 00211 iterator upper_bound(const key_type& __x) const { 00212 return _M_t.upper_bound(__x); 00213 } 00214 pair<iterator,iterator> equal_range(const key_type& __x) const { 00215 return _M_t.equal_range(__x); 00216 } 00217 #endif 00218 00219 template <class _K1, class _C1, class _A1> 00220 friend bool operator== (const set<_K1,_C1,_A1>&, const set<_K1,_C1,_A1>&); 00221 template <class _K1, class _C1, class _A1> 00222 friend bool operator< (const set<_K1,_C1,_A1>&, const set<_K1,_C1,_A1>&); 00223 }; 00224 00225 template <class _Key, class _Compare, class _Alloc> 00226 inline bool operator==(const set<_Key,_Compare,_Alloc>& __x, 00227 const set<_Key,_Compare,_Alloc>& __y) { 00228 return __x._M_t == __y._M_t; 00229 } 00230 00231 template <class _Key, class _Compare, class _Alloc> 00232 inline bool operator<(const set<_Key,_Compare,_Alloc>& __x, 00233 const set<_Key,_Compare,_Alloc>& __y) { 00234 return __x._M_t < __y._M_t; 00235 } 00236 00237 template <class _Key, class _Compare, class _Alloc> 00238 inline bool operator!=(const set<_Key,_Compare,_Alloc>& __x, 00239 const set<_Key,_Compare,_Alloc>& __y) { 00240 return !(__x == __y); 00241 } 00242 00243 template <class _Key, class _Compare, class _Alloc> 00244 inline bool operator>(const set<_Key,_Compare,_Alloc>& __x, 00245 const set<_Key,_Compare,_Alloc>& __y) { 00246 return __y < __x; 00247 } 00248 00249 template <class _Key, class _Compare, class _Alloc> 00250 inline bool operator<=(const set<_Key,_Compare,_Alloc>& __x, 00251 const set<_Key,_Compare,_Alloc>& __y) { 00252 return !(__y < __x); 00253 } 00254 00255 template <class _Key, class _Compare, class _Alloc> 00256 inline bool operator>=(const set<_Key,_Compare,_Alloc>& __x, 00257 const set<_Key,_Compare,_Alloc>& __y) { 00258 return !(__x < __y); 00259 } 00260 00261 template <class _Key, class _Compare, class _Alloc> 00262 inline void swap(set<_Key,_Compare,_Alloc>& __x, 00263 set<_Key,_Compare,_Alloc>& __y) { 00264 __x.swap(__y); 00265 } 00266 00267 } // namespace std 00268 00269 #endif /* __SGI_STL_INTERNAL_SET_H */ 00270 00271 // Local Variables: 00272 // mode:C++ 00273 // End: Generated on Mon Apr 8 03:11:44 2002 for libstdc++-v3 Source by 1.2.15 |