libstdc++
|
00001 // Multiset implementation -*- C++ -*- 00002 00003 // Copyright (C) 2001-2014 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 3, 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 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 /* 00026 * 00027 * Copyright (c) 1994 00028 * Hewlett-Packard Company 00029 * 00030 * Permission to use, copy, modify, distribute and sell this software 00031 * and its documentation for any purpose is hereby granted without fee, 00032 * provided that the above copyright notice appear in all copies and 00033 * that both that copyright notice and this permission notice appear 00034 * in supporting documentation. Hewlett-Packard Company makes no 00035 * representations about the suitability of this software for any 00036 * purpose. It is provided "as is" without express or implied warranty. 00037 * 00038 * 00039 * Copyright (c) 1996 00040 * Silicon Graphics Computer Systems, Inc. 00041 * 00042 * Permission to use, copy, modify, distribute and sell this software 00043 * and its documentation for any purpose is hereby granted without fee, 00044 * provided that the above copyright notice appear in all copies and 00045 * that both that copyright notice and this permission notice appear 00046 * in supporting documentation. Silicon Graphics makes no 00047 * representations about the suitability of this software for any 00048 * purpose. It is provided "as is" without express or implied warranty. 00049 */ 00050 00051 /** @file bits/stl_multiset.h 00052 * This is an internal header file, included by other library headers. 00053 * Do not attempt to use it directly. @headername{set} 00054 */ 00055 00056 #ifndef _STL_MULTISET_H 00057 #define _STL_MULTISET_H 1 00058 00059 #include <bits/concept_check.h> 00060 #if __cplusplus >= 201103L 00061 #include <initializer_list> 00062 #endif 00063 00064 namespace std _GLIBCXX_VISIBILITY(default) 00065 { 00066 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER 00067 00068 /** 00069 * @brief A standard container made up of elements, which can be retrieved 00070 * in logarithmic time. 00071 * 00072 * @ingroup associative_containers 00073 * 00074 * 00075 * @tparam _Key Type of key objects. 00076 * @tparam _Compare Comparison function object type, defaults to less<_Key>. 00077 * @tparam _Alloc Allocator type, defaults to allocator<_Key>. 00078 * 00079 * Meets the requirements of a <a href="tables.html#65">container</a>, a 00080 * <a href="tables.html#66">reversible container</a>, and an 00081 * <a href="tables.html#69">associative container</a> (using equivalent 00082 * keys). For a @c multiset<Key> the key_type and value_type are Key. 00083 * 00084 * Multisets support bidirectional iterators. 00085 * 00086 * The private tree data is declared exactly the same way for set and 00087 * multiset; the distinction is made entirely in how the tree functions are 00088 * called (*_unique versus *_equal, same as the standard). 00089 */ 00090 template <typename _Key, typename _Compare = std::less<_Key>, 00091 typename _Alloc = std::allocator<_Key> > 00092 class multiset 00093 { 00094 // concept requirements 00095 typedef typename _Alloc::value_type _Alloc_value_type; 00096 __glibcxx_class_requires(_Key, _SGIAssignableConcept) 00097 __glibcxx_class_requires4(_Compare, bool, _Key, _Key, 00098 _BinaryFunctionConcept) 00099 __glibcxx_class_requires2(_Key, _Alloc_value_type, _SameTypeConcept) 00100 00101 public: 00102 // typedefs: 00103 typedef _Key key_type; 00104 typedef _Key value_type; 00105 typedef _Compare key_compare; 00106 typedef _Compare value_compare; 00107 typedef _Alloc allocator_type; 00108 00109 private: 00110 /// This turns a red-black tree into a [multi]set. 00111 typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template 00112 rebind<_Key>::other _Key_alloc_type; 00113 00114 typedef _Rb_tree<key_type, value_type, _Identity<value_type>, 00115 key_compare, _Key_alloc_type> _Rep_type; 00116 /// The actual tree structure. 00117 _Rep_type _M_t; 00118 00119 typedef __gnu_cxx::__alloc_traits<_Key_alloc_type> _Alloc_traits; 00120 00121 public: 00122 typedef typename _Alloc_traits::pointer pointer; 00123 typedef typename _Alloc_traits::const_pointer const_pointer; 00124 typedef typename _Alloc_traits::reference reference; 00125 typedef typename _Alloc_traits::const_reference const_reference; 00126 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00127 // DR 103. set::iterator is required to be modifiable, 00128 // but this allows modification of keys. 00129 typedef typename _Rep_type::const_iterator iterator; 00130 typedef typename _Rep_type::const_iterator const_iterator; 00131 typedef typename _Rep_type::const_reverse_iterator reverse_iterator; 00132 typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator; 00133 typedef typename _Rep_type::size_type size_type; 00134 typedef typename _Rep_type::difference_type difference_type; 00135 00136 // allocation/deallocation 00137 /** 00138 * @brief Default constructor creates no elements. 00139 */ 00140 multiset() 00141 : _M_t() { } 00142 00143 /** 00144 * @brief Creates a %multiset with no elements. 00145 * @param __comp Comparator to use. 00146 * @param __a An allocator object. 00147 */ 00148 explicit 00149 multiset(const _Compare& __comp, 00150 const allocator_type& __a = allocator_type()) 00151 : _M_t(__comp, _Key_alloc_type(__a)) { } 00152 00153 /** 00154 * @brief Builds a %multiset from a range. 00155 * @param __first An input iterator. 00156 * @param __last An input iterator. 00157 * 00158 * Create a %multiset consisting of copies of the elements from 00159 * [first,last). This is linear in N if the range is already sorted, 00160 * and NlogN otherwise (where N is distance(__first,__last)). 00161 */ 00162 template<typename _InputIterator> 00163 multiset(_InputIterator __first, _InputIterator __last) 00164 : _M_t() 00165 { _M_t._M_insert_equal(__first, __last); } 00166 00167 /** 00168 * @brief Builds a %multiset from a range. 00169 * @param __first An input iterator. 00170 * @param __last An input iterator. 00171 * @param __comp A comparison functor. 00172 * @param __a An allocator object. 00173 * 00174 * Create a %multiset consisting of copies of the elements from 00175 * [__first,__last). This is linear in N if the range is already sorted, 00176 * and NlogN otherwise (where N is distance(__first,__last)). 00177 */ 00178 template<typename _InputIterator> 00179 multiset(_InputIterator __first, _InputIterator __last, 00180 const _Compare& __comp, 00181 const allocator_type& __a = allocator_type()) 00182 : _M_t(__comp, _Key_alloc_type(__a)) 00183 { _M_t._M_insert_equal(__first, __last); } 00184 00185 /** 00186 * @brief %Multiset copy constructor. 00187 * @param __x A %multiset of identical element and allocator types. 00188 * 00189 * The newly-created %multiset uses a copy of the allocation object used 00190 * by @a __x. 00191 */ 00192 multiset(const multiset& __x) 00193 : _M_t(__x._M_t) { } 00194 00195 #if __cplusplus >= 201103L 00196 /** 00197 * @brief %Multiset move constructor. 00198 * @param __x A %multiset of identical element and allocator types. 00199 * 00200 * The newly-created %multiset contains the exact contents of @a __x. 00201 * The contents of @a __x are a valid, but unspecified %multiset. 00202 */ 00203 multiset(multiset&& __x) 00204 noexcept(is_nothrow_copy_constructible<_Compare>::value) 00205 : _M_t(std::move(__x._M_t)) { } 00206 00207 /** 00208 * @brief Builds a %multiset from an initializer_list. 00209 * @param __l An initializer_list. 00210 * @param __comp A comparison functor. 00211 * @param __a An allocator object. 00212 * 00213 * Create a %multiset consisting of copies of the elements from 00214 * the list. This is linear in N if the list is already sorted, 00215 * and NlogN otherwise (where N is @a __l.size()). 00216 */ 00217 multiset(initializer_list<value_type> __l, 00218 const _Compare& __comp = _Compare(), 00219 const allocator_type& __a = allocator_type()) 00220 : _M_t(__comp, _Key_alloc_type(__a)) 00221 { _M_t._M_insert_equal(__l.begin(), __l.end()); } 00222 00223 /// Allocator-extended default constructor. 00224 explicit 00225 multiset(const allocator_type& __a) 00226 : _M_t(_Compare(), _Key_alloc_type(__a)) { } 00227 00228 /// Allocator-extended copy constructor. 00229 multiset(const multiset& __m, const allocator_type& __a) 00230 : _M_t(__m._M_t, _Key_alloc_type(__a)) { } 00231 00232 /// Allocator-extended move constructor. 00233 multiset(multiset&& __m, const allocator_type& __a) 00234 noexcept(is_nothrow_copy_constructible<_Compare>::value 00235 && _Alloc_traits::_S_always_equal()) 00236 : _M_t(std::move(__m._M_t), _Key_alloc_type(__a)) { } 00237 00238 /// Allocator-extended initialier-list constructor. 00239 multiset(initializer_list<value_type> __l, const allocator_type& __a) 00240 : _M_t(_Compare(), _Key_alloc_type(__a)) 00241 { _M_t._M_insert_equal(__l.begin(), __l.end()); } 00242 00243 /// Allocator-extended range constructor. 00244 template<typename _InputIterator> 00245 multiset(_InputIterator __first, _InputIterator __last, 00246 const allocator_type& __a) 00247 : _M_t(_Compare(), _Key_alloc_type(__a)) 00248 { _M_t._M_insert_equal(__first, __last); } 00249 #endif 00250 00251 /** 00252 * @brief %Multiset assignment operator. 00253 * @param __x A %multiset of identical element and allocator types. 00254 * 00255 * All the elements of @a __x are copied, but unlike the copy 00256 * constructor, the allocator object is not copied. 00257 */ 00258 multiset& 00259 operator=(const multiset& __x) 00260 { 00261 _M_t = __x._M_t; 00262 return *this; 00263 } 00264 00265 #if __cplusplus >= 201103L 00266 /** 00267 * @brief %Multiset move assignment operator. 00268 * @param __x A %multiset of identical element and allocator types. 00269 * 00270 * The contents of @a __x are moved into this %multiset (without 00271 * copying if the allocators compare equal or get moved on assignment). 00272 * Afterwards @a __x is in a valid, but unspecified state. 00273 */ 00274 multiset& 00275 operator=(multiset&& __x) noexcept(_Alloc_traits::_S_nothrow_move()) 00276 { 00277 if (!_M_t._M_move_assign(__x._M_t)) 00278 { 00279 // The rvalue's allocator cannot be moved and is not equal, 00280 // so we need to individually move each element. 00281 clear(); 00282 insert(std::__make_move_if_noexcept_iterator(__x._M_t.begin()), 00283 std::__make_move_if_noexcept_iterator(__x._M_t.end())); 00284 __x.clear(); 00285 } 00286 return *this; 00287 } 00288 00289 /** 00290 * @brief %Multiset list assignment operator. 00291 * @param __l An initializer_list. 00292 * 00293 * This function fills a %multiset with copies of the elements in the 00294 * initializer list @a __l. 00295 * 00296 * Note that the assignment completely changes the %multiset and 00297 * that the resulting %multiset's size is the same as the number 00298 * of elements assigned. Old data may be lost. 00299 */ 00300 multiset& 00301 operator=(initializer_list<value_type> __l) 00302 { 00303 this->clear(); 00304 this->insert(__l.begin(), __l.end()); 00305 return *this; 00306 } 00307 #endif 00308 00309 // accessors: 00310 00311 /// Returns the comparison object. 00312 key_compare 00313 key_comp() const 00314 { return _M_t.key_comp(); } 00315 /// Returns the comparison object. 00316 value_compare 00317 value_comp() const 00318 { return _M_t.key_comp(); } 00319 /// Returns the memory allocation object. 00320 allocator_type 00321 get_allocator() const _GLIBCXX_NOEXCEPT 00322 { return allocator_type(_M_t.get_allocator()); } 00323 00324 /** 00325 * Returns a read-only (constant) iterator that points to the first 00326 * element in the %multiset. Iteration is done in ascending order 00327 * according to the keys. 00328 */ 00329 iterator 00330 begin() const _GLIBCXX_NOEXCEPT 00331 { return _M_t.begin(); } 00332 00333 /** 00334 * Returns a read-only (constant) iterator that points one past the last 00335 * element in the %multiset. Iteration is done in ascending order 00336 * according to the keys. 00337 */ 00338 iterator 00339 end() const _GLIBCXX_NOEXCEPT 00340 { return _M_t.end(); } 00341 00342 /** 00343 * Returns a read-only (constant) reverse iterator that points to the 00344 * last element in the %multiset. Iteration is done in descending order 00345 * according to the keys. 00346 */ 00347 reverse_iterator 00348 rbegin() const _GLIBCXX_NOEXCEPT 00349 { return _M_t.rbegin(); } 00350 00351 /** 00352 * Returns a read-only (constant) reverse iterator that points to the 00353 * last element in the %multiset. Iteration is done in descending order 00354 * according to the keys. 00355 */ 00356 reverse_iterator 00357 rend() const _GLIBCXX_NOEXCEPT 00358 { return _M_t.rend(); } 00359 00360 #if __cplusplus >= 201103L 00361 /** 00362 * Returns a read-only (constant) iterator that points to the first 00363 * element in the %multiset. Iteration is done in ascending order 00364 * according to the keys. 00365 */ 00366 iterator 00367 cbegin() const noexcept 00368 { return _M_t.begin(); } 00369 00370 /** 00371 * Returns a read-only (constant) iterator that points one past the last 00372 * element in the %multiset. Iteration is done in ascending order 00373 * according to the keys. 00374 */ 00375 iterator 00376 cend() const noexcept 00377 { return _M_t.end(); } 00378 00379 /** 00380 * Returns a read-only (constant) reverse iterator that points to the 00381 * last element in the %multiset. Iteration is done in descending order 00382 * according to the keys. 00383 */ 00384 reverse_iterator 00385 crbegin() const noexcept 00386 { return _M_t.rbegin(); } 00387 00388 /** 00389 * Returns a read-only (constant) reverse iterator that points to the 00390 * last element in the %multiset. Iteration is done in descending order 00391 * according to the keys. 00392 */ 00393 reverse_iterator 00394 crend() const noexcept 00395 { return _M_t.rend(); } 00396 #endif 00397 00398 /// Returns true if the %set is empty. 00399 bool 00400 empty() const _GLIBCXX_NOEXCEPT 00401 { return _M_t.empty(); } 00402 00403 /// Returns the size of the %set. 00404 size_type 00405 size() const _GLIBCXX_NOEXCEPT 00406 { return _M_t.size(); } 00407 00408 /// Returns the maximum size of the %set. 00409 size_type 00410 max_size() const _GLIBCXX_NOEXCEPT 00411 { return _M_t.max_size(); } 00412 00413 /** 00414 * @brief Swaps data with another %multiset. 00415 * @param __x A %multiset of the same element and allocator types. 00416 * 00417 * This exchanges the elements between two multisets in constant time. 00418 * (It is only swapping a pointer, an integer, and an instance of the @c 00419 * Compare type (which itself is often stateless and empty), so it should 00420 * be quite fast.) 00421 * Note that the global std::swap() function is specialized such that 00422 * std::swap(s1,s2) will feed to this function. 00423 */ 00424 void 00425 swap(multiset& __x) 00426 #if __cplusplus >= 201103L 00427 noexcept(_Alloc_traits::_S_nothrow_swap()) 00428 #endif 00429 { _M_t.swap(__x._M_t); } 00430 00431 // insert/erase 00432 #if __cplusplus >= 201103L 00433 /** 00434 * @brief Builds and inserts an element into the %multiset. 00435 * @param __args Arguments used to generate the element instance to be 00436 * inserted. 00437 * @return An iterator that points to the inserted element. 00438 * 00439 * This function inserts an element into the %multiset. Contrary 00440 * to a std::set the %multiset does not rely on unique keys and thus 00441 * multiple copies of the same element can be inserted. 00442 * 00443 * Insertion requires logarithmic time. 00444 */ 00445 template<typename... _Args> 00446 iterator 00447 emplace(_Args&&... __args) 00448 { return _M_t._M_emplace_equal(std::forward<_Args>(__args)...); } 00449 00450 /** 00451 * @brief Builds and inserts an element into the %multiset. 00452 * @param __pos An iterator that serves as a hint as to where the 00453 * element should be inserted. 00454 * @param __args Arguments used to generate the element instance to be 00455 * inserted. 00456 * @return An iterator that points to the inserted element. 00457 * 00458 * This function inserts an element into the %multiset. Contrary 00459 * to a std::set the %multiset does not rely on unique keys and thus 00460 * multiple copies of the same element can be inserted. 00461 * 00462 * Note that the first parameter is only a hint and can potentially 00463 * improve the performance of the insertion process. A bad hint would 00464 * cause no gains in efficiency. 00465 * 00466 * See http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html 00467 * for more on @a hinting. 00468 * 00469 * Insertion requires logarithmic time (if the hint is not taken). 00470 */ 00471 template<typename... _Args> 00472 iterator 00473 emplace_hint(const_iterator __pos, _Args&&... __args) 00474 { 00475 return _M_t._M_emplace_hint_equal(__pos, 00476 std::forward<_Args>(__args)...); 00477 } 00478 #endif 00479 00480 /** 00481 * @brief Inserts an element into the %multiset. 00482 * @param __x Element to be inserted. 00483 * @return An iterator that points to the inserted element. 00484 * 00485 * This function inserts an element into the %multiset. Contrary 00486 * to a std::set the %multiset does not rely on unique keys and thus 00487 * multiple copies of the same element can be inserted. 00488 * 00489 * Insertion requires logarithmic time. 00490 */ 00491 iterator 00492 insert(const value_type& __x) 00493 { return _M_t._M_insert_equal(__x); } 00494 00495 #if __cplusplus >= 201103L 00496 iterator 00497 insert(value_type&& __x) 00498 { return _M_t._M_insert_equal(std::move(__x)); } 00499 #endif 00500 00501 /** 00502 * @brief Inserts an element into the %multiset. 00503 * @param __position An iterator that serves as a hint as to where the 00504 * element should be inserted. 00505 * @param __x Element to be inserted. 00506 * @return An iterator that points to the inserted element. 00507 * 00508 * This function inserts an element into the %multiset. Contrary 00509 * to a std::set the %multiset does not rely on unique keys and thus 00510 * multiple copies of the same element can be inserted. 00511 * 00512 * Note that the first parameter is only a hint and can potentially 00513 * improve the performance of the insertion process. A bad hint would 00514 * cause no gains in efficiency. 00515 * 00516 * See http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html 00517 * for more on @a hinting. 00518 * 00519 * Insertion requires logarithmic time (if the hint is not taken). 00520 */ 00521 iterator 00522 insert(const_iterator __position, const value_type& __x) 00523 { return _M_t._M_insert_equal_(__position, __x); } 00524 00525 #if __cplusplus >= 201103L 00526 iterator 00527 insert(const_iterator __position, value_type&& __x) 00528 { return _M_t._M_insert_equal_(__position, std::move(__x)); } 00529 #endif 00530 00531 /** 00532 * @brief A template function that tries to insert a range of elements. 00533 * @param __first Iterator pointing to the start of the range to be 00534 * inserted. 00535 * @param __last Iterator pointing to the end of the range. 00536 * 00537 * Complexity similar to that of the range constructor. 00538 */ 00539 template<typename _InputIterator> 00540 void 00541 insert(_InputIterator __first, _InputIterator __last) 00542 { _M_t._M_insert_equal(__first, __last); } 00543 00544 #if __cplusplus >= 201103L 00545 /** 00546 * @brief Attempts to insert a list of elements into the %multiset. 00547 * @param __l A std::initializer_list<value_type> of elements 00548 * to be inserted. 00549 * 00550 * Complexity similar to that of the range constructor. 00551 */ 00552 void 00553 insert(initializer_list<value_type> __l) 00554 { this->insert(__l.begin(), __l.end()); } 00555 #endif 00556 00557 #if __cplusplus >= 201103L 00558 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00559 // DR 130. Associative erase should return an iterator. 00560 /** 00561 * @brief Erases an element from a %multiset. 00562 * @param __position An iterator pointing to the element to be erased. 00563 * @return An iterator pointing to the element immediately following 00564 * @a position prior to the element being erased. If no such 00565 * element exists, end() is returned. 00566 * 00567 * This function erases an element, pointed to by the given iterator, 00568 * from a %multiset. Note that this function only erases the element, 00569 * and that if the element is itself a pointer, the pointed-to memory is 00570 * not touched in any way. Managing the pointer is the user's 00571 * responsibility. 00572 */ 00573 _GLIBCXX_ABI_TAG_CXX11 00574 iterator 00575 erase(const_iterator __position) 00576 { return _M_t.erase(__position); } 00577 #else 00578 /** 00579 * @brief Erases an element from a %multiset. 00580 * @param __position An iterator pointing to the element to be erased. 00581 * 00582 * This function erases an element, pointed to by the given iterator, 00583 * from a %multiset. Note that this function only erases the element, 00584 * and that if the element is itself a pointer, the pointed-to memory is 00585 * not touched in any way. Managing the pointer is the user's 00586 * responsibility. 00587 */ 00588 void 00589 erase(iterator __position) 00590 { _M_t.erase(__position); } 00591 #endif 00592 00593 /** 00594 * @brief Erases elements according to the provided key. 00595 * @param __x Key of element to be erased. 00596 * @return The number of elements erased. 00597 * 00598 * This function erases all elements located by the given key from a 00599 * %multiset. 00600 * Note that this function only erases the element, and that if 00601 * the element is itself a pointer, the pointed-to memory is not touched 00602 * in any way. Managing the pointer is the user's responsibility. 00603 */ 00604 size_type 00605 erase(const key_type& __x) 00606 { return _M_t.erase(__x); } 00607 00608 #if __cplusplus >= 201103L 00609 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00610 // DR 130. Associative erase should return an iterator. 00611 /** 00612 * @brief Erases a [first,last) range of elements from a %multiset. 00613 * @param __first Iterator pointing to the start of the range to be 00614 * erased. 00615 * @param __last Iterator pointing to the end of the range to 00616 * be erased. 00617 * @return The iterator @a last. 00618 * 00619 * This function erases a sequence of elements from a %multiset. 00620 * Note that this function only erases the elements, and that if 00621 * the elements themselves are pointers, the pointed-to memory is not 00622 * touched in any way. Managing the pointer is the user's 00623 * responsibility. 00624 */ 00625 _GLIBCXX_ABI_TAG_CXX11 00626 iterator 00627 erase(const_iterator __first, const_iterator __last) 00628 { return _M_t.erase(__first, __last); } 00629 #else 00630 /** 00631 * @brief Erases a [first,last) range of elements from a %multiset. 00632 * @param first Iterator pointing to the start of the range to be 00633 * erased. 00634 * @param last Iterator pointing to the end of the range to be erased. 00635 * 00636 * This function erases a sequence of elements from a %multiset. 00637 * Note that this function only erases the elements, and that if 00638 * the elements themselves are pointers, the pointed-to memory is not 00639 * touched in any way. Managing the pointer is the user's 00640 * responsibility. 00641 */ 00642 void 00643 erase(iterator __first, iterator __last) 00644 { _M_t.erase(__first, __last); } 00645 #endif 00646 00647 /** 00648 * Erases all elements in a %multiset. Note that this function only 00649 * erases the elements, and that if the elements themselves are pointers, 00650 * the pointed-to memory is not touched in any way. Managing the pointer 00651 * is the user's responsibility. 00652 */ 00653 void 00654 clear() _GLIBCXX_NOEXCEPT 00655 { _M_t.clear(); } 00656 00657 // multiset operations: 00658 00659 /** 00660 * @brief Finds the number of elements with given key. 00661 * @param __x Key of elements to be located. 00662 * @return Number of elements with specified key. 00663 */ 00664 size_type 00665 count(const key_type& __x) const 00666 { return _M_t.count(__x); } 00667 00668 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00669 // 214. set::find() missing const overload 00670 //@{ 00671 /** 00672 * @brief Tries to locate an element in a %set. 00673 * @param __x Element to be located. 00674 * @return Iterator pointing to sought-after element, or end() if not 00675 * found. 00676 * 00677 * This function takes a key and tries to locate the element with which 00678 * the key matches. If successful the function returns an iterator 00679 * pointing to the sought after element. If unsuccessful it returns the 00680 * past-the-end ( @c end() ) iterator. 00681 */ 00682 iterator 00683 find(const key_type& __x) 00684 { return _M_t.find(__x); } 00685 00686 const_iterator 00687 find(const key_type& __x) const 00688 { return _M_t.find(__x); } 00689 //@} 00690 00691 //@{ 00692 /** 00693 * @brief Finds the beginning of a subsequence matching given key. 00694 * @param __x Key to be located. 00695 * @return Iterator pointing to first element equal to or greater 00696 * than key, or end(). 00697 * 00698 * This function returns the first element of a subsequence of elements 00699 * that matches the given key. If unsuccessful it returns an iterator 00700 * pointing to the first element that has a greater value than given key 00701 * or end() if no such element exists. 00702 */ 00703 iterator 00704 lower_bound(const key_type& __x) 00705 { return _M_t.lower_bound(__x); } 00706 00707 const_iterator 00708 lower_bound(const key_type& __x) const 00709 { return _M_t.lower_bound(__x); } 00710 //@} 00711 00712 //@{ 00713 /** 00714 * @brief Finds the end of a subsequence matching given key. 00715 * @param __x Key to be located. 00716 * @return Iterator pointing to the first element 00717 * greater than key, or end(). 00718 */ 00719 iterator 00720 upper_bound(const key_type& __x) 00721 { return _M_t.upper_bound(__x); } 00722 00723 const_iterator 00724 upper_bound(const key_type& __x) const 00725 { return _M_t.upper_bound(__x); } 00726 //@} 00727 00728 //@{ 00729 /** 00730 * @brief Finds a subsequence matching given key. 00731 * @param __x Key to be located. 00732 * @return Pair of iterators that possibly points to the subsequence 00733 * matching given key. 00734 * 00735 * This function is equivalent to 00736 * @code 00737 * std::make_pair(c.lower_bound(val), 00738 * c.upper_bound(val)) 00739 * @endcode 00740 * (but is faster than making the calls separately). 00741 * 00742 * This function probably only makes sense for multisets. 00743 */ 00744 std::pair<iterator, iterator> 00745 equal_range(const key_type& __x) 00746 { return _M_t.equal_range(__x); } 00747 00748 std::pair<const_iterator, const_iterator> 00749 equal_range(const key_type& __x) const 00750 { return _M_t.equal_range(__x); } 00751 //@} 00752 00753 template<typename _K1, typename _C1, typename _A1> 00754 friend bool 00755 operator==(const multiset<_K1, _C1, _A1>&, 00756 const multiset<_K1, _C1, _A1>&); 00757 00758 template<typename _K1, typename _C1, typename _A1> 00759 friend bool 00760 operator< (const multiset<_K1, _C1, _A1>&, 00761 const multiset<_K1, _C1, _A1>&); 00762 }; 00763 00764 /** 00765 * @brief Multiset equality comparison. 00766 * @param __x A %multiset. 00767 * @param __y A %multiset of the same type as @a __x. 00768 * @return True iff the size and elements of the multisets are equal. 00769 * 00770 * This is an equivalence relation. It is linear in the size of the 00771 * multisets. 00772 * Multisets are considered equivalent if their sizes are equal, and if 00773 * corresponding elements compare equal. 00774 */ 00775 template<typename _Key, typename _Compare, typename _Alloc> 00776 inline bool 00777 operator==(const multiset<_Key, _Compare, _Alloc>& __x, 00778 const multiset<_Key, _Compare, _Alloc>& __y) 00779 { return __x._M_t == __y._M_t; } 00780 00781 /** 00782 * @brief Multiset ordering relation. 00783 * @param __x A %multiset. 00784 * @param __y A %multiset of the same type as @a __x. 00785 * @return True iff @a __x is lexicographically less than @a __y. 00786 * 00787 * This is a total ordering relation. It is linear in the size of the 00788 * sets. The elements must be comparable with @c <. 00789 * 00790 * See std::lexicographical_compare() for how the determination is made. 00791 */ 00792 template<typename _Key, typename _Compare, typename _Alloc> 00793 inline bool 00794 operator<(const multiset<_Key, _Compare, _Alloc>& __x, 00795 const multiset<_Key, _Compare, _Alloc>& __y) 00796 { return __x._M_t < __y._M_t; } 00797 00798 /// Returns !(x == y). 00799 template<typename _Key, typename _Compare, typename _Alloc> 00800 inline bool 00801 operator!=(const multiset<_Key, _Compare, _Alloc>& __x, 00802 const multiset<_Key, _Compare, _Alloc>& __y) 00803 { return !(__x == __y); } 00804 00805 /// Returns y < x. 00806 template<typename _Key, typename _Compare, typename _Alloc> 00807 inline bool 00808 operator>(const multiset<_Key,_Compare,_Alloc>& __x, 00809 const multiset<_Key,_Compare,_Alloc>& __y) 00810 { return __y < __x; } 00811 00812 /// Returns !(y < x) 00813 template<typename _Key, typename _Compare, typename _Alloc> 00814 inline bool 00815 operator<=(const multiset<_Key, _Compare, _Alloc>& __x, 00816 const multiset<_Key, _Compare, _Alloc>& __y) 00817 { return !(__y < __x); } 00818 00819 /// Returns !(x < y) 00820 template<typename _Key, typename _Compare, typename _Alloc> 00821 inline bool 00822 operator>=(const multiset<_Key, _Compare, _Alloc>& __x, 00823 const multiset<_Key, _Compare, _Alloc>& __y) 00824 { return !(__x < __y); } 00825 00826 /// See std::multiset::swap(). 00827 template<typename _Key, typename _Compare, typename _Alloc> 00828 inline void 00829 swap(multiset<_Key, _Compare, _Alloc>& __x, 00830 multiset<_Key, _Compare, _Alloc>& __y) 00831 { __x.swap(__y); } 00832 00833 _GLIBCXX_END_NAMESPACE_CONTAINER 00834 } // namespace std 00835 00836 #endif /* _STL_MULTISET_H */