00001 // Set implementation -*- C++ -*- 00002 00003 // Copyright (C) 2001, 2002, 2004, 2005 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 /** @file stl_set.h 00057 * This is an internal header file, included by other library headers. 00058 * You should not attempt to use it directly. 00059 */ 00060 00061 #ifndef _SET_H 00062 #define _SET_H 1 00063 00064 #include <bits/concept_check.h> 00065 00066 namespace _GLIBCXX_STD 00067 { 00068 // Forward declarations of operators < and ==, needed for friend declaration. 00069 template<class _Key, class _Compare = std::less<_Key>, 00070 class _Alloc = std::allocator<_Key> > 00071 class set; 00072 00073 template<class _Key, class _Compare, class _Alloc> 00074 inline bool 00075 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 00080 operator<(const set<_Key,_Compare,_Alloc>& __x, 00081 const set<_Key,_Compare,_Alloc>& __y); 00082 00083 /** 00084 * @brief A standard container made up of unique keys, which can be 00085 * retrieved in logarithmic time. 00086 * 00087 * @ingroup Containers 00088 * @ingroup Assoc_containers 00089 * 00090 * Meets the requirements of a <a href="tables.html#65">container</a>, a 00091 * <a href="tables.html#66">reversible container</a>, and an 00092 * <a href="tables.html#69">associative container</a> (using unique keys). 00093 * 00094 * Sets support bidirectional iterators. 00095 * 00096 * @param Key Type of key objects. 00097 * @param Compare Comparison function object type, defaults to less<Key>. 00098 * @param Alloc Allocator type, defaults to allocator<Key>. 00099 * 00100 * @if maint 00101 * The private tree data is declared exactly the same way for set and 00102 * multiset; the distinction is made entirely in how the tree functions are 00103 * called (*_unique versus *_equal, same as the standard). 00104 * @endif 00105 */ 00106 template<class _Key, class _Compare, class _Alloc> 00107 class set 00108 { 00109 // concept requirements 00110 __glibcxx_class_requires(_Key, _SGIAssignableConcept) 00111 __glibcxx_class_requires4(_Compare, bool, _Key, _Key, 00112 _BinaryFunctionConcept) 00113 00114 public: 00115 // typedefs: 00116 //@{ 00117 /// Public typedefs. 00118 typedef _Key key_type; 00119 typedef _Key value_type; 00120 typedef _Compare key_compare; 00121 typedef _Compare value_compare; 00122 //@} 00123 00124 private: 00125 typedef _Rb_tree<key_type, value_type, 00126 _Identity<value_type>, key_compare, _Alloc> _Rep_type; 00127 _Rep_type _M_t; // red-black tree representing set 00128 public: 00129 //@{ 00130 /// Iterator-related typedefs. 00131 typedef typename _Alloc::pointer pointer; 00132 typedef typename _Alloc::const_pointer const_pointer; 00133 typedef typename _Alloc::reference reference; 00134 typedef typename _Alloc::const_reference const_reference; 00135 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00136 // DR 103. set::iterator is required to be modifiable, 00137 // but this allows modification of keys. 00138 typedef typename _Rep_type::const_iterator iterator; 00139 typedef typename _Rep_type::const_iterator const_iterator; 00140 typedef typename _Rep_type::const_reverse_iterator reverse_iterator; 00141 typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator; 00142 typedef typename _Rep_type::size_type size_type; 00143 typedef typename _Rep_type::difference_type difference_type; 00144 typedef typename _Rep_type::allocator_type allocator_type; 00145 //@} 00146 00147 // allocation/deallocation 00148 /// Default constructor creates no elements. 00149 set() 00150 : _M_t(_Compare(), allocator_type()) {} 00151 00152 /** 00153 * @brief Default constructor creates no elements. 00154 * 00155 * @param comp Comparator to use. 00156 * @param a Allocator to use. 00157 */ 00158 explicit set(const _Compare& __comp, 00159 const allocator_type& __a = allocator_type()) 00160 : _M_t(__comp, __a) {} 00161 00162 /** 00163 * @brief Builds a %set from a range. 00164 * @param first An input iterator. 00165 * @param last An input iterator. 00166 * 00167 * Create a %set consisting of copies of the elements from [first,last). 00168 * This is linear in N if the range is already sorted, and NlogN 00169 * otherwise (where N is distance(first,last)). 00170 */ 00171 template<class _InputIterator> 00172 set(_InputIterator __first, _InputIterator __last) 00173 : _M_t(_Compare(), allocator_type()) 00174 { _M_t.insert_unique(__first, __last); } 00175 00176 /** 00177 * @brief Builds a %set from a range. 00178 * @param first An input iterator. 00179 * @param last An input iterator. 00180 * @param comp A comparison functor. 00181 * @param a An allocator object. 00182 * 00183 * Create a %set consisting of copies of the elements from [first,last). 00184 * This is linear in N if the range is already sorted, and NlogN 00185 * otherwise (where N is distance(first,last)). 00186 */ 00187 template<class _InputIterator> 00188 set(_InputIterator __first, _InputIterator __last, 00189 const _Compare& __comp, 00190 const allocator_type& __a = allocator_type()) 00191 : _M_t(__comp, __a) 00192 { _M_t.insert_unique(__first, __last); } 00193 00194 /** 00195 * @brief Set copy constructor. 00196 * @param x A %set of identical element and allocator types. 00197 * 00198 * The newly-created %set uses a copy of the allocation object used 00199 * by @a x. 00200 */ 00201 set(const set<_Key,_Compare,_Alloc>& __x) 00202 : _M_t(__x._M_t) { } 00203 00204 /** 00205 * @brief Set assignment operator. 00206 * @param x A %set of identical element and allocator types. 00207 * 00208 * All the elements of @a x are copied, but unlike the copy constructor, 00209 * the allocator object is not copied. 00210 */ 00211 set<_Key,_Compare,_Alloc>& 00212 operator=(const set<_Key, _Compare, _Alloc>& __x) 00213 { 00214 _M_t = __x._M_t; 00215 return *this; 00216 } 00217 00218 // accessors: 00219 00220 /// Returns the comparison object with which the %set was constructed. 00221 key_compare 00222 key_comp() const 00223 { return _M_t.key_comp(); } 00224 /// Returns the comparison object with which the %set was constructed. 00225 value_compare 00226 value_comp() const 00227 { return _M_t.key_comp(); } 00228 /// Returns the allocator object with which the %set was constructed. 00229 allocator_type 00230 get_allocator() const 00231 { return _M_t.get_allocator(); } 00232 00233 /** 00234 * Returns a read/write iterator that points to the first element in the 00235 * %set. Iteration is done in ascending order according to the keys. 00236 */ 00237 iterator 00238 begin() const 00239 { return _M_t.begin(); } 00240 00241 /** 00242 * Returns a read/write iterator that points one past the last element in 00243 * the %set. Iteration is done in ascending order according to the keys. 00244 */ 00245 iterator 00246 end() const 00247 { return _M_t.end(); } 00248 00249 /** 00250 * Returns a read/write reverse iterator that points to the last element 00251 * in the %set. Iteration is done in descending order according to the 00252 * keys. 00253 */ 00254 reverse_iterator 00255 rbegin() const 00256 { return _M_t.rbegin(); } 00257 00258 /** 00259 * Returns a read-only (constant) reverse iterator that points to the 00260 * last pair in the %map. Iteration is done in descending order 00261 * according to the keys. 00262 */ 00263 reverse_iterator 00264 rend() const 00265 { return _M_t.rend(); } 00266 00267 /// Returns true if the %set is empty. 00268 bool 00269 empty() const 00270 { return _M_t.empty(); } 00271 00272 /// Returns the size of the %set. 00273 size_type 00274 size() const 00275 { return _M_t.size(); } 00276 00277 /// Returns the maximum size of the %set. 00278 size_type 00279 max_size() const 00280 { return _M_t.max_size(); } 00281 00282 /** 00283 * @brief Swaps data with another %set. 00284 * @param x A %set of the same element and allocator types. 00285 * 00286 * This exchanges the elements between two sets in constant time. 00287 * (It is only swapping a pointer, an integer, and an instance of 00288 * the @c Compare type (which itself is often stateless and empty), so it 00289 * should be quite fast.) 00290 * Note that the global std::swap() function is specialized such that 00291 * std::swap(s1,s2) will feed to this function. 00292 */ 00293 void 00294 swap(set<_Key,_Compare,_Alloc>& __x) 00295 { _M_t.swap(__x._M_t); } 00296 00297 // insert/erase 00298 /** 00299 * @brief Attempts to insert an element into the %set. 00300 * @param x Element to be inserted. 00301 * @return A pair, of which the first element is an iterator that points 00302 * to the possibly inserted element, and the second is a bool 00303 * that is true if the element was actually inserted. 00304 * 00305 * This function attempts to insert an element into the %set. A %set 00306 * relies on unique keys and thus an element is only inserted if it is 00307 * not already present in the %set. 00308 * 00309 * Insertion requires logarithmic time. 00310 */ 00311 std::pair<iterator,bool> 00312 insert(const value_type& __x) 00313 { 00314 std::pair<typename _Rep_type::iterator, bool> __p = 00315 _M_t.insert_unique(__x); 00316 return std::pair<iterator, bool>(__p.first, __p.second); 00317 } 00318 00319 /** 00320 * @brief Attempts to insert an element into the %set. 00321 * @param position An iterator that serves as a hint as to where the 00322 * element should be inserted. 00323 * @param x Element to be inserted. 00324 * @return An iterator that points to the element with key of @a x (may 00325 * or may not be the element passed in). 00326 * 00327 * This function is not concerned about whether the insertion took place, 00328 * and thus does not return a boolean like the single-argument insert() 00329 * does. Note that the first parameter is only a hint and can 00330 * potentially improve the performance of the insertion process. A bad 00331 * hint would cause no gains in efficiency. 00332 * 00333 * See http://gcc.gnu.org/onlinedocs/libstdc++/23_containers/howto.html#4 00334 * for more on "hinting". 00335 * 00336 * Insertion requires logarithmic time (if the hint is not taken). 00337 */ 00338 iterator 00339 insert(iterator __position, const value_type& __x) 00340 { 00341 typedef typename _Rep_type::iterator _Rep_iterator; 00342 return _M_t.insert_unique((_Rep_iterator&)__position, __x); 00343 } 00344 00345 /** 00346 * @brief A template function that attemps to insert a range of elements. 00347 * @param first Iterator pointing to the start of the range to be 00348 * inserted. 00349 * @param last Iterator pointing to the end of the range. 00350 * 00351 * Complexity similar to that of the range constructor. 00352 */ 00353 template<class _InputIterator> 00354 void 00355 insert(_InputIterator __first, _InputIterator __last) 00356 { _M_t.insert_unique(__first, __last); } 00357 00358 /** 00359 * @brief Erases an element from a %set. 00360 * @param position An iterator pointing to the element to be erased. 00361 * 00362 * This function erases an element, pointed to by the given iterator, 00363 * from a %set. Note that this function only erases the element, and 00364 * that if the element is itself a pointer, the pointed-to memory is not 00365 * touched in any way. Managing the pointer is the user's responsibilty. 00366 */ 00367 void 00368 erase(iterator __position) 00369 { 00370 typedef typename _Rep_type::iterator _Rep_iterator; 00371 _M_t.erase((_Rep_iterator&)__position); 00372 } 00373 00374 /** 00375 * @brief Erases elements according to the provided key. 00376 * @param x Key of element to be erased. 00377 * @return The number of elements erased. 00378 * 00379 * This function erases all the elements located by the given key from 00380 * a %set. 00381 * Note that this function only erases the element, and that if 00382 * the element is itself a pointer, the pointed-to memory is not touched 00383 * in any way. Managing the pointer is the user's responsibilty. 00384 */ 00385 size_type 00386 erase(const key_type& __x) { return _M_t.erase(__x); } 00387 00388 /** 00389 * @brief Erases a [first,last) range of elements from a %set. 00390 * @param first Iterator pointing to the start of the range to be 00391 * erased. 00392 * @param last Iterator pointing to the end of the range to be erased. 00393 * 00394 * This function erases a sequence of elements from a %set. 00395 * Note that this function only erases the element, and that if 00396 * the element is itself a pointer, the pointed-to memory is not touched 00397 * in any way. Managing the pointer is the user's responsibilty. 00398 */ 00399 void 00400 erase(iterator __first, iterator __last) 00401 { 00402 typedef typename _Rep_type::iterator _Rep_iterator; 00403 _M_t.erase((_Rep_iterator&)__first, (_Rep_iterator&)__last); 00404 } 00405 00406 /** 00407 * Erases all elements in a %set. Note that this function only erases 00408 * the elements, and that if the elements themselves are pointers, the 00409 * pointed-to memory is not touched in any way. Managing the pointer is 00410 * the user's responsibilty. 00411 */ 00412 void 00413 clear() 00414 { _M_t.clear(); } 00415 00416 // set operations: 00417 00418 /** 00419 * @brief Finds the number of elements. 00420 * @param x Element to located. 00421 * @return Number of elements with specified key. 00422 * 00423 * This function only makes sense for multisets; for set the result will 00424 * either be 0 (not present) or 1 (present). 00425 */ 00426 size_type 00427 count(const key_type& __x) const 00428 { return _M_t.find(__x) == _M_t.end() ? 0 : 1; } 00429 00430 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00431 // 214. set::find() missing const overload 00432 //@{ 00433 /** 00434 * @brief Tries to locate an element in a %set. 00435 * @param x Element to be located. 00436 * @return Iterator pointing to sought-after element, or end() if not 00437 * found. 00438 * 00439 * This function takes a key and tries to locate the element with which 00440 * the key matches. If successful the function returns an iterator 00441 * pointing to the sought after element. If unsuccessful it returns the 00442 * past-the-end ( @c end() ) iterator. 00443 */ 00444 iterator 00445 find(const key_type& __x) 00446 { return _M_t.find(__x); } 00447 00448 const_iterator 00449 find(const key_type& __x) const 00450 { return _M_t.find(__x); } 00451 //@} 00452 00453 //@{ 00454 /** 00455 * @brief Finds the beginning of a subsequence matching given key. 00456 * @param x Key to be located. 00457 * @return Iterator pointing to first element equal to or greater 00458 * than key, or end(). 00459 * 00460 * This function returns the first element of a subsequence of elements 00461 * that matches the given key. If unsuccessful it returns an iterator 00462 * pointing to the first element that has a greater value than given key 00463 * or end() if no such element exists. 00464 */ 00465 iterator 00466 lower_bound(const key_type& __x) 00467 { return _M_t.lower_bound(__x); } 00468 00469 const_iterator 00470 lower_bound(const key_type& __x) const 00471 { return _M_t.lower_bound(__x); } 00472 //@} 00473 00474 //@{ 00475 /** 00476 * @brief Finds the end of a subsequence matching given key. 00477 * @param x Key to be located. 00478 * @return Iterator pointing to the first element 00479 * greater than key, or end(). 00480 */ 00481 iterator 00482 upper_bound(const key_type& __x) 00483 { return _M_t.upper_bound(__x); } 00484 00485 const_iterator 00486 upper_bound(const key_type& __x) const 00487 { return _M_t.upper_bound(__x); } 00488 //@} 00489 00490 //@{ 00491 /** 00492 * @brief Finds a subsequence matching given key. 00493 * @param x Key to be located. 00494 * @return Pair of iterators that possibly points to the subsequence 00495 * matching given key. 00496 * 00497 * This function is equivalent to 00498 * @code 00499 * std::make_pair(c.lower_bound(val), 00500 * c.upper_bound(val)) 00501 * @endcode 00502 * (but is faster than making the calls separately). 00503 * 00504 * This function probably only makes sense for multisets. 00505 */ 00506 std::pair<iterator,iterator> 00507 equal_range(const key_type& __x) 00508 { return _M_t.equal_range(__x); } 00509 00510 std::pair<const_iterator,const_iterator> 00511 equal_range(const key_type& __x) const 00512 { return _M_t.equal_range(__x); } 00513 //@} 00514 00515 template<class _K1, class _C1, class _A1> 00516 friend bool 00517 operator== (const set<_K1,_C1,_A1>&, const set<_K1,_C1,_A1>&); 00518 00519 template<class _K1, class _C1, class _A1> 00520 friend bool 00521 operator< (const set<_K1,_C1,_A1>&, const set<_K1,_C1,_A1>&); 00522 }; 00523 00524 00525 /** 00526 * @brief Set equality comparison. 00527 * @param x A %set. 00528 * @param y A %set of the same type as @a x. 00529 * @return True iff the size and elements of the sets are equal. 00530 * 00531 * This is an equivalence relation. It is linear in the size of the sets. 00532 * Sets are considered equivalent if their sizes are equal, and if 00533 * corresponding elements compare equal. 00534 */ 00535 template<class _Key, class _Compare, class _Alloc> 00536 inline bool 00537 operator==(const set<_Key,_Compare,_Alloc>& __x, 00538 const set<_Key,_Compare,_Alloc>& __y) 00539 { return __x._M_t == __y._M_t; } 00540 00541 /** 00542 * @brief Set ordering relation. 00543 * @param x A %set. 00544 * @param y A %set of the same type as @a x. 00545 * @return True iff @a x is lexicographically less than @a y. 00546 * 00547 * This is a total ordering relation. It is linear in the size of the 00548 * maps. The elements must be comparable with @c <. 00549 * 00550 * See std::lexicographical_compare() for how the determination is made. 00551 */ 00552 template<class _Key, class _Compare, class _Alloc> 00553 inline bool 00554 operator<(const set<_Key,_Compare,_Alloc>& __x, 00555 const set<_Key,_Compare,_Alloc>& __y) 00556 { return __x._M_t < __y._M_t; } 00557 00558 /// Returns !(x == y). 00559 template<class _Key, class _Compare, class _Alloc> 00560 inline bool 00561 operator!=(const set<_Key,_Compare,_Alloc>& __x, 00562 const set<_Key,_Compare,_Alloc>& __y) 00563 { return !(__x == __y); } 00564 00565 /// Returns y < x. 00566 template<class _Key, class _Compare, class _Alloc> 00567 inline bool 00568 operator>(const set<_Key,_Compare,_Alloc>& __x, 00569 const set<_Key,_Compare,_Alloc>& __y) 00570 { return __y < __x; } 00571 00572 /// Returns !(y < x) 00573 template<class _Key, class _Compare, class _Alloc> 00574 inline bool 00575 operator<=(const set<_Key,_Compare,_Alloc>& __x, 00576 const set<_Key,_Compare,_Alloc>& __y) 00577 { return !(__y < __x); } 00578 00579 /// Returns !(x < y) 00580 template<class _Key, class _Compare, class _Alloc> 00581 inline bool 00582 operator>=(const set<_Key,_Compare,_Alloc>& __x, 00583 const set<_Key,_Compare,_Alloc>& __y) 00584 { return !(__x < __y); } 00585 00586 /// See std::set::swap(). 00587 template<class _Key, class _Compare, class _Alloc> 00588 inline void 00589 swap(set<_Key,_Compare,_Alloc>& __x, set<_Key,_Compare,_Alloc>& __y) 00590 { __x.swap(__y); } 00591 00592 } // namespace std 00593 00594 #endif /* _SET_H */