libstdc++
|
00001 // Multiset implementation -*- C++ -*- 00002 00003 // Copyright (C) 2001-2019 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_VERSION 00067 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER 00068 00069 template<typename _Key, typename _Compare, typename _Alloc> 00070 class set; 00071 00072 /** 00073 * @brief A standard container made up of elements, which can be retrieved 00074 * in logarithmic time. 00075 * 00076 * @ingroup associative_containers 00077 * 00078 * 00079 * @tparam _Key Type of key objects. 00080 * @tparam _Compare Comparison function object type, defaults to less<_Key>. 00081 * @tparam _Alloc Allocator type, defaults to allocator<_Key>. 00082 * 00083 * Meets the requirements of a <a href="tables.html#65">container</a>, a 00084 * <a href="tables.html#66">reversible container</a>, and an 00085 * <a href="tables.html#69">associative container</a> (using equivalent 00086 * keys). For a @c multiset<Key> the key_type and value_type are Key. 00087 * 00088 * Multisets support bidirectional iterators. 00089 * 00090 * The private tree data is declared exactly the same way for set and 00091 * multiset; the distinction is made entirely in how the tree functions are 00092 * called (*_unique versus *_equal, same as the standard). 00093 */ 00094 template <typename _Key, typename _Compare = std::less<_Key>, 00095 typename _Alloc = std::allocator<_Key> > 00096 class multiset 00097 { 00098 #ifdef _GLIBCXX_CONCEPT_CHECKS 00099 // concept requirements 00100 typedef typename _Alloc::value_type _Alloc_value_type; 00101 # if __cplusplus < 201103L 00102 __glibcxx_class_requires(_Key, _SGIAssignableConcept) 00103 # endif 00104 __glibcxx_class_requires4(_Compare, bool, _Key, _Key, 00105 _BinaryFunctionConcept) 00106 __glibcxx_class_requires2(_Key, _Alloc_value_type, _SameTypeConcept) 00107 #endif 00108 00109 #if __cplusplus >= 201103L 00110 static_assert(is_same<typename remove_cv<_Key>::type, _Key>::value, 00111 "std::multiset must have a non-const, non-volatile value_type"); 00112 # ifdef __STRICT_ANSI__ 00113 static_assert(is_same<typename _Alloc::value_type, _Key>::value, 00114 "std::multiset must have the same value_type as its allocator"); 00115 # endif 00116 #endif 00117 00118 public: 00119 // typedefs: 00120 typedef _Key key_type; 00121 typedef _Key value_type; 00122 typedef _Compare key_compare; 00123 typedef _Compare value_compare; 00124 typedef _Alloc allocator_type; 00125 00126 private: 00127 /// This turns a red-black tree into a [multi]set. 00128 typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template 00129 rebind<_Key>::other _Key_alloc_type; 00130 00131 typedef _Rb_tree<key_type, value_type, _Identity<value_type>, 00132 key_compare, _Key_alloc_type> _Rep_type; 00133 /// The actual tree structure. 00134 _Rep_type _M_t; 00135 00136 typedef __gnu_cxx::__alloc_traits<_Key_alloc_type> _Alloc_traits; 00137 00138 public: 00139 typedef typename _Alloc_traits::pointer pointer; 00140 typedef typename _Alloc_traits::const_pointer const_pointer; 00141 typedef typename _Alloc_traits::reference reference; 00142 typedef typename _Alloc_traits::const_reference const_reference; 00143 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00144 // DR 103. set::iterator is required to be modifiable, 00145 // but this allows modification of keys. 00146 typedef typename _Rep_type::const_iterator iterator; 00147 typedef typename _Rep_type::const_iterator const_iterator; 00148 typedef typename _Rep_type::const_reverse_iterator reverse_iterator; 00149 typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator; 00150 typedef typename _Rep_type::size_type size_type; 00151 typedef typename _Rep_type::difference_type difference_type; 00152 00153 #if __cplusplus > 201402L 00154 using node_type = typename _Rep_type::node_type; 00155 #endif 00156 00157 // allocation/deallocation 00158 /** 00159 * @brief Default constructor creates no elements. 00160 */ 00161 #if __cplusplus < 201103L 00162 multiset() : _M_t() { } 00163 #else 00164 multiset() = default; 00165 #endif 00166 00167 /** 00168 * @brief Creates a %multiset with no elements. 00169 * @param __comp Comparator to use. 00170 * @param __a An allocator object. 00171 */ 00172 explicit 00173 multiset(const _Compare& __comp, 00174 const allocator_type& __a = allocator_type()) 00175 : _M_t(__comp, _Key_alloc_type(__a)) { } 00176 00177 /** 00178 * @brief Builds a %multiset from a range. 00179 * @param __first An input iterator. 00180 * @param __last An input iterator. 00181 * 00182 * Create a %multiset consisting of copies of the elements from 00183 * [first,last). This is linear in N if the range is already sorted, 00184 * and NlogN otherwise (where N is distance(__first,__last)). 00185 */ 00186 template<typename _InputIterator> 00187 multiset(_InputIterator __first, _InputIterator __last) 00188 : _M_t() 00189 { _M_t._M_insert_range_equal(__first, __last); } 00190 00191 /** 00192 * @brief Builds a %multiset from a range. 00193 * @param __first An input iterator. 00194 * @param __last An input iterator. 00195 * @param __comp A comparison functor. 00196 * @param __a An allocator object. 00197 * 00198 * Create a %multiset consisting of copies of the elements from 00199 * [__first,__last). This is linear in N if the range is already sorted, 00200 * and NlogN otherwise (where N is distance(__first,__last)). 00201 */ 00202 template<typename _InputIterator> 00203 multiset(_InputIterator __first, _InputIterator __last, 00204 const _Compare& __comp, 00205 const allocator_type& __a = allocator_type()) 00206 : _M_t(__comp, _Key_alloc_type(__a)) 00207 { _M_t._M_insert_range_equal(__first, __last); } 00208 00209 /** 00210 * @brief %Multiset copy constructor. 00211 * 00212 * Whether the allocator is copied depends on the allocator traits. 00213 */ 00214 #if __cplusplus < 201103L 00215 multiset(const multiset& __x) 00216 : _M_t(__x._M_t) { } 00217 #else 00218 multiset(const multiset&) = default; 00219 00220 /** 00221 * @brief %Multiset move constructor. 00222 * 00223 * The newly-created %multiset contains the exact contents of the 00224 * moved instance. The moved instance is a valid, but unspecified 00225 * %multiset. 00226 */ 00227 multiset(multiset&&) = default; 00228 00229 /** 00230 * @brief Builds a %multiset from an initializer_list. 00231 * @param __l An initializer_list. 00232 * @param __comp A comparison functor. 00233 * @param __a An allocator object. 00234 * 00235 * Create a %multiset consisting of copies of the elements from 00236 * the list. This is linear in N if the list is already sorted, 00237 * and NlogN otherwise (where N is @a __l.size()). 00238 */ 00239 multiset(initializer_list<value_type> __l, 00240 const _Compare& __comp = _Compare(), 00241 const allocator_type& __a = allocator_type()) 00242 : _M_t(__comp, _Key_alloc_type(__a)) 00243 { _M_t._M_insert_range_equal(__l.begin(), __l.end()); } 00244 00245 /// Allocator-extended default constructor. 00246 explicit 00247 multiset(const allocator_type& __a) 00248 : _M_t(_Key_alloc_type(__a)) { } 00249 00250 /// Allocator-extended copy constructor. 00251 multiset(const multiset& __m, const allocator_type& __a) 00252 : _M_t(__m._M_t, _Key_alloc_type(__a)) { } 00253 00254 /// Allocator-extended move constructor. 00255 multiset(multiset&& __m, const allocator_type& __a) 00256 noexcept(is_nothrow_copy_constructible<_Compare>::value 00257 && _Alloc_traits::_S_always_equal()) 00258 : _M_t(std::move(__m._M_t), _Key_alloc_type(__a)) { } 00259 00260 /// Allocator-extended initialier-list constructor. 00261 multiset(initializer_list<value_type> __l, const allocator_type& __a) 00262 : _M_t(_Key_alloc_type(__a)) 00263 { _M_t._M_insert_range_equal(__l.begin(), __l.end()); } 00264 00265 /// Allocator-extended range constructor. 00266 template<typename _InputIterator> 00267 multiset(_InputIterator __first, _InputIterator __last, 00268 const allocator_type& __a) 00269 : _M_t(_Key_alloc_type(__a)) 00270 { _M_t._M_insert_range_equal(__first, __last); } 00271 00272 /** 00273 * The dtor only erases the elements, and note that if the elements 00274 * themselves are pointers, the pointed-to memory is not touched in any 00275 * way. Managing the pointer is the user's responsibility. 00276 */ 00277 ~multiset() = default; 00278 #endif 00279 00280 /** 00281 * @brief %Multiset assignment operator. 00282 * 00283 * Whether the allocator is copied depends on the allocator traits. 00284 */ 00285 #if __cplusplus < 201103L 00286 multiset& 00287 operator=(const multiset& __x) 00288 { 00289 _M_t = __x._M_t; 00290 return *this; 00291 } 00292 #else 00293 multiset& 00294 operator=(const multiset&) = default; 00295 00296 /// Move assignment operator. 00297 multiset& 00298 operator=(multiset&&) = default; 00299 00300 /** 00301 * @brief %Multiset list assignment operator. 00302 * @param __l An initializer_list. 00303 * 00304 * This function fills a %multiset with copies of the elements in the 00305 * initializer list @a __l. 00306 * 00307 * Note that the assignment completely changes the %multiset and 00308 * that the resulting %multiset's size is the same as the number 00309 * of elements assigned. 00310 */ 00311 multiset& 00312 operator=(initializer_list<value_type> __l) 00313 { 00314 _M_t._M_assign_equal(__l.begin(), __l.end()); 00315 return *this; 00316 } 00317 #endif 00318 00319 // accessors: 00320 00321 /// Returns the comparison object. 00322 key_compare 00323 key_comp() const 00324 { return _M_t.key_comp(); } 00325 /// Returns the comparison object. 00326 value_compare 00327 value_comp() const 00328 { return _M_t.key_comp(); } 00329 /// Returns the memory allocation object. 00330 allocator_type 00331 get_allocator() const _GLIBCXX_NOEXCEPT 00332 { return allocator_type(_M_t.get_allocator()); } 00333 00334 /** 00335 * Returns a read-only (constant) iterator that points to the first 00336 * element in the %multiset. Iteration is done in ascending order 00337 * according to the keys. 00338 */ 00339 iterator 00340 begin() const _GLIBCXX_NOEXCEPT 00341 { return _M_t.begin(); } 00342 00343 /** 00344 * Returns a read-only (constant) iterator that points one past the last 00345 * element in the %multiset. Iteration is done in ascending order 00346 * according to the keys. 00347 */ 00348 iterator 00349 end() const _GLIBCXX_NOEXCEPT 00350 { return _M_t.end(); } 00351 00352 /** 00353 * Returns a read-only (constant) reverse iterator that points to the 00354 * last element in the %multiset. Iteration is done in descending order 00355 * according to the keys. 00356 */ 00357 reverse_iterator 00358 rbegin() const _GLIBCXX_NOEXCEPT 00359 { return _M_t.rbegin(); } 00360 00361 /** 00362 * Returns a read-only (constant) reverse iterator that points to the 00363 * last element in the %multiset. Iteration is done in descending order 00364 * according to the keys. 00365 */ 00366 reverse_iterator 00367 rend() const _GLIBCXX_NOEXCEPT 00368 { return _M_t.rend(); } 00369 00370 #if __cplusplus >= 201103L 00371 /** 00372 * Returns a read-only (constant) iterator that points to the first 00373 * element in the %multiset. Iteration is done in ascending order 00374 * according to the keys. 00375 */ 00376 iterator 00377 cbegin() const noexcept 00378 { return _M_t.begin(); } 00379 00380 /** 00381 * Returns a read-only (constant) iterator that points one past the last 00382 * element in the %multiset. Iteration is done in ascending order 00383 * according to the keys. 00384 */ 00385 iterator 00386 cend() const noexcept 00387 { return _M_t.end(); } 00388 00389 /** 00390 * Returns a read-only (constant) reverse iterator that points to the 00391 * last element in the %multiset. Iteration is done in descending order 00392 * according to the keys. 00393 */ 00394 reverse_iterator 00395 crbegin() const noexcept 00396 { return _M_t.rbegin(); } 00397 00398 /** 00399 * Returns a read-only (constant) reverse iterator that points to the 00400 * last element in the %multiset. Iteration is done in descending order 00401 * according to the keys. 00402 */ 00403 reverse_iterator 00404 crend() const noexcept 00405 { return _M_t.rend(); } 00406 #endif 00407 00408 /// Returns true if the %set is empty. 00409 _GLIBCXX_NODISCARD bool 00410 empty() const _GLIBCXX_NOEXCEPT 00411 { return _M_t.empty(); } 00412 00413 /// Returns the size of the %set. 00414 size_type 00415 size() const _GLIBCXX_NOEXCEPT 00416 { return _M_t.size(); } 00417 00418 /// Returns the maximum size of the %set. 00419 size_type 00420 max_size() const _GLIBCXX_NOEXCEPT 00421 { return _M_t.max_size(); } 00422 00423 /** 00424 * @brief Swaps data with another %multiset. 00425 * @param __x A %multiset of the same element and allocator types. 00426 * 00427 * This exchanges the elements between two multisets in constant time. 00428 * (It is only swapping a pointer, an integer, and an instance of the @c 00429 * Compare type (which itself is often stateless and empty), so it should 00430 * be quite fast.) 00431 * Note that the global std::swap() function is specialized such that 00432 * std::swap(s1,s2) will feed to this function. 00433 * 00434 * Whether the allocators are swapped depends on the allocator traits. 00435 */ 00436 void 00437 swap(multiset& __x) 00438 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value) 00439 { _M_t.swap(__x._M_t); } 00440 00441 // insert/erase 00442 #if __cplusplus >= 201103L 00443 /** 00444 * @brief Builds and inserts an element into the %multiset. 00445 * @param __args Arguments used to generate the element instance to be 00446 * inserted. 00447 * @return An iterator that points to the inserted element. 00448 * 00449 * This function inserts an element into the %multiset. Contrary 00450 * to a std::set the %multiset does not rely on unique keys and thus 00451 * multiple copies of the same element can be inserted. 00452 * 00453 * Insertion requires logarithmic time. 00454 */ 00455 template<typename... _Args> 00456 iterator 00457 emplace(_Args&&... __args) 00458 { return _M_t._M_emplace_equal(std::forward<_Args>(__args)...); } 00459 00460 /** 00461 * @brief Builds and inserts an element into the %multiset. 00462 * @param __pos An iterator that serves as a hint as to where the 00463 * element should be inserted. 00464 * @param __args Arguments used to generate the element instance to be 00465 * inserted. 00466 * @return An iterator that points to the inserted element. 00467 * 00468 * This function inserts an element into the %multiset. Contrary 00469 * to a std::set the %multiset does not rely on unique keys and thus 00470 * multiple copies of the same element can be inserted. 00471 * 00472 * Note that the first parameter is only a hint and can potentially 00473 * improve the performance of the insertion process. A bad hint would 00474 * cause no gains in efficiency. 00475 * 00476 * See https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints 00477 * for more on @a hinting. 00478 * 00479 * Insertion requires logarithmic time (if the hint is not taken). 00480 */ 00481 template<typename... _Args> 00482 iterator 00483 emplace_hint(const_iterator __pos, _Args&&... __args) 00484 { 00485 return _M_t._M_emplace_hint_equal(__pos, 00486 std::forward<_Args>(__args)...); 00487 } 00488 #endif 00489 00490 /** 00491 * @brief Inserts an element into the %multiset. 00492 * @param __x Element to be inserted. 00493 * @return An iterator that points to the inserted element. 00494 * 00495 * This function inserts an element into the %multiset. Contrary 00496 * to a std::set the %multiset does not rely on unique keys and thus 00497 * multiple copies of the same element can be inserted. 00498 * 00499 * Insertion requires logarithmic time. 00500 */ 00501 iterator 00502 insert(const value_type& __x) 00503 { return _M_t._M_insert_equal(__x); } 00504 00505 #if __cplusplus >= 201103L 00506 iterator 00507 insert(value_type&& __x) 00508 { return _M_t._M_insert_equal(std::move(__x)); } 00509 #endif 00510 00511 /** 00512 * @brief Inserts an element into the %multiset. 00513 * @param __position An iterator that serves as a hint as to where the 00514 * element should be inserted. 00515 * @param __x Element to be inserted. 00516 * @return An iterator that points to the inserted element. 00517 * 00518 * This function inserts an element into the %multiset. Contrary 00519 * to a std::set the %multiset does not rely on unique keys and thus 00520 * multiple copies of the same element can be inserted. 00521 * 00522 * Note that the first parameter is only a hint and can potentially 00523 * improve the performance of the insertion process. A bad hint would 00524 * cause no gains in efficiency. 00525 * 00526 * See https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints 00527 * for more on @a hinting. 00528 * 00529 * Insertion requires logarithmic time (if the hint is not taken). 00530 */ 00531 iterator 00532 insert(const_iterator __position, const value_type& __x) 00533 { return _M_t._M_insert_equal_(__position, __x); } 00534 00535 #if __cplusplus >= 201103L 00536 iterator 00537 insert(const_iterator __position, value_type&& __x) 00538 { return _M_t._M_insert_equal_(__position, std::move(__x)); } 00539 #endif 00540 00541 /** 00542 * @brief A template function that tries to insert a range of elements. 00543 * @param __first Iterator pointing to the start of the range to be 00544 * inserted. 00545 * @param __last Iterator pointing to the end of the range. 00546 * 00547 * Complexity similar to that of the range constructor. 00548 */ 00549 template<typename _InputIterator> 00550 void 00551 insert(_InputIterator __first, _InputIterator __last) 00552 { _M_t._M_insert_range_equal(__first, __last); } 00553 00554 #if __cplusplus >= 201103L 00555 /** 00556 * @brief Attempts to insert a list of elements into the %multiset. 00557 * @param __l A std::initializer_list<value_type> of elements 00558 * to be inserted. 00559 * 00560 * Complexity similar to that of the range constructor. 00561 */ 00562 void 00563 insert(initializer_list<value_type> __l) 00564 { this->insert(__l.begin(), __l.end()); } 00565 #endif 00566 00567 #if __cplusplus > 201402L 00568 /// Extract a node. 00569 node_type 00570 extract(const_iterator __pos) 00571 { 00572 __glibcxx_assert(__pos != end()); 00573 return _M_t.extract(__pos); 00574 } 00575 00576 /// Extract a node. 00577 node_type 00578 extract(const key_type& __x) 00579 { return _M_t.extract(__x); } 00580 00581 /// Re-insert an extracted node. 00582 iterator 00583 insert(node_type&& __nh) 00584 { return _M_t._M_reinsert_node_equal(std::move(__nh)); } 00585 00586 /// Re-insert an extracted node. 00587 iterator 00588 insert(const_iterator __hint, node_type&& __nh) 00589 { return _M_t._M_reinsert_node_hint_equal(__hint, std::move(__nh)); } 00590 00591 template<typename, typename> 00592 friend class std::_Rb_tree_merge_helper; 00593 00594 template<typename _Compare1> 00595 void 00596 merge(multiset<_Key, _Compare1, _Alloc>& __source) 00597 { 00598 using _Merge_helper = _Rb_tree_merge_helper<multiset, _Compare1>; 00599 _M_t._M_merge_equal(_Merge_helper::_S_get_tree(__source)); 00600 } 00601 00602 template<typename _Compare1> 00603 void 00604 merge(multiset<_Key, _Compare1, _Alloc>&& __source) 00605 { merge(__source); } 00606 00607 template<typename _Compare1> 00608 void 00609 merge(set<_Key, _Compare1, _Alloc>& __source) 00610 { 00611 using _Merge_helper = _Rb_tree_merge_helper<multiset, _Compare1>; 00612 _M_t._M_merge_equal(_Merge_helper::_S_get_tree(__source)); 00613 } 00614 00615 template<typename _Compare1> 00616 void 00617 merge(set<_Key, _Compare1, _Alloc>&& __source) 00618 { merge(__source); } 00619 #endif // C++17 00620 00621 #if __cplusplus >= 201103L 00622 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00623 // DR 130. Associative erase should return an iterator. 00624 /** 00625 * @brief Erases an element from a %multiset. 00626 * @param __position An iterator pointing to the element to be erased. 00627 * @return An iterator pointing to the element immediately following 00628 * @a position prior to the element being erased. If no such 00629 * element exists, end() is returned. 00630 * 00631 * This function erases an element, pointed to by the given iterator, 00632 * from a %multiset. Note that this function only erases the element, 00633 * and that if the element is itself a pointer, the pointed-to memory is 00634 * not touched in any way. Managing the pointer is the user's 00635 * responsibility. 00636 */ 00637 _GLIBCXX_ABI_TAG_CXX11 00638 iterator 00639 erase(const_iterator __position) 00640 { return _M_t.erase(__position); } 00641 #else 00642 /** 00643 * @brief Erases an element from a %multiset. 00644 * @param __position An iterator pointing to the element to be erased. 00645 * 00646 * This function erases an element, pointed to by the given iterator, 00647 * from a %multiset. Note that this function only erases the element, 00648 * and that if the element is itself a pointer, the pointed-to memory is 00649 * not touched in any way. Managing the pointer is the user's 00650 * responsibility. 00651 */ 00652 void 00653 erase(iterator __position) 00654 { _M_t.erase(__position); } 00655 #endif 00656 00657 /** 00658 * @brief Erases elements according to the provided key. 00659 * @param __x Key of element to be erased. 00660 * @return The number of elements erased. 00661 * 00662 * This function erases all elements located by the given key from a 00663 * %multiset. 00664 * Note that this function only erases the element, and that if 00665 * the element is itself a pointer, the pointed-to memory is not touched 00666 * in any way. Managing the pointer is the user's responsibility. 00667 */ 00668 size_type 00669 erase(const key_type& __x) 00670 { return _M_t.erase(__x); } 00671 00672 #if __cplusplus >= 201103L 00673 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00674 // DR 130. Associative erase should return an iterator. 00675 /** 00676 * @brief Erases a [first,last) range of elements from a %multiset. 00677 * @param __first Iterator pointing to the start of the range to be 00678 * erased. 00679 * @param __last Iterator pointing to the end of the range to 00680 * be erased. 00681 * @return The iterator @a last. 00682 * 00683 * This function erases a sequence of elements from a %multiset. 00684 * Note that this function only erases the elements, and that if 00685 * the elements themselves are pointers, the pointed-to memory is not 00686 * touched in any way. Managing the pointer is the user's 00687 * responsibility. 00688 */ 00689 _GLIBCXX_ABI_TAG_CXX11 00690 iterator 00691 erase(const_iterator __first, const_iterator __last) 00692 { return _M_t.erase(__first, __last); } 00693 #else 00694 /** 00695 * @brief Erases a [first,last) range of elements from a %multiset. 00696 * @param first Iterator pointing to the start of the range to be 00697 * erased. 00698 * @param last Iterator pointing to the end of the range to be erased. 00699 * 00700 * This function erases a sequence of elements from a %multiset. 00701 * Note that this function only erases the elements, and that if 00702 * the elements themselves are pointers, the pointed-to memory is not 00703 * touched in any way. Managing the pointer is the user's 00704 * responsibility. 00705 */ 00706 void 00707 erase(iterator __first, iterator __last) 00708 { _M_t.erase(__first, __last); } 00709 #endif 00710 00711 /** 00712 * Erases all elements in a %multiset. Note that this function only 00713 * erases the elements, and that if the elements themselves are pointers, 00714 * the pointed-to memory is not touched in any way. Managing the pointer 00715 * is the user's responsibility. 00716 */ 00717 void 00718 clear() _GLIBCXX_NOEXCEPT 00719 { _M_t.clear(); } 00720 00721 // multiset operations: 00722 00723 //@{ 00724 /** 00725 * @brief Finds the number of elements with given key. 00726 * @param __x Key of elements to be located. 00727 * @return Number of elements with specified key. 00728 */ 00729 size_type 00730 count(const key_type& __x) const 00731 { return _M_t.count(__x); } 00732 00733 #if __cplusplus > 201103L 00734 template<typename _Kt> 00735 auto 00736 count(const _Kt& __x) const -> decltype(_M_t._M_count_tr(__x)) 00737 { return _M_t._M_count_tr(__x); } 00738 #endif 00739 //@} 00740 00741 #if __cplusplus > 201703L 00742 //@{ 00743 /** 00744 * @brief Finds whether an element with the given key exists. 00745 * @param __x Key of elements to be located. 00746 * @return True if there is any element with the specified key. 00747 */ 00748 bool 00749 contains(const key_type& __x) const 00750 { return _M_t.find(__x) != _M_t.end(); } 00751 00752 template<typename _Kt> 00753 auto 00754 contains(const _Kt& __x) const 00755 -> decltype(_M_t._M_find_tr(__x), void(), true) 00756 { return _M_t._M_find_tr(__x) != _M_t.end(); } 00757 //@} 00758 #endif 00759 00760 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00761 // 214. set::find() missing const overload 00762 //@{ 00763 /** 00764 * @brief Tries to locate an element in a %set. 00765 * @param __x Element to be located. 00766 * @return Iterator pointing to sought-after element, or end() if not 00767 * found. 00768 * 00769 * This function takes a key and tries to locate the element with which 00770 * the key matches. If successful the function returns an iterator 00771 * pointing to the sought after element. If unsuccessful it returns the 00772 * past-the-end ( @c end() ) iterator. 00773 */ 00774 iterator 00775 find(const key_type& __x) 00776 { return _M_t.find(__x); } 00777 00778 const_iterator 00779 find(const key_type& __x) const 00780 { return _M_t.find(__x); } 00781 00782 #if __cplusplus > 201103L 00783 template<typename _Kt> 00784 auto 00785 find(const _Kt& __x) 00786 -> decltype(iterator{_M_t._M_find_tr(__x)}) 00787 { return iterator{_M_t._M_find_tr(__x)}; } 00788 00789 template<typename _Kt> 00790 auto 00791 find(const _Kt& __x) const 00792 -> decltype(const_iterator{_M_t._M_find_tr(__x)}) 00793 { return const_iterator{_M_t._M_find_tr(__x)}; } 00794 #endif 00795 //@} 00796 00797 //@{ 00798 /** 00799 * @brief Finds the beginning of a subsequence matching given key. 00800 * @param __x Key to be located. 00801 * @return Iterator pointing to first element equal to or greater 00802 * than key, or end(). 00803 * 00804 * This function returns the first element of a subsequence of elements 00805 * that matches the given key. If unsuccessful it returns an iterator 00806 * pointing to the first element that has a greater value than given key 00807 * or end() if no such element exists. 00808 */ 00809 iterator 00810 lower_bound(const key_type& __x) 00811 { return _M_t.lower_bound(__x); } 00812 00813 const_iterator 00814 lower_bound(const key_type& __x) const 00815 { return _M_t.lower_bound(__x); } 00816 00817 #if __cplusplus > 201103L 00818 template<typename _Kt> 00819 auto 00820 lower_bound(const _Kt& __x) 00821 -> decltype(iterator(_M_t._M_lower_bound_tr(__x))) 00822 { return iterator(_M_t._M_lower_bound_tr(__x)); } 00823 00824 template<typename _Kt> 00825 auto 00826 lower_bound(const _Kt& __x) const 00827 -> decltype(iterator(_M_t._M_lower_bound_tr(__x))) 00828 { return iterator(_M_t._M_lower_bound_tr(__x)); } 00829 #endif 00830 //@} 00831 00832 //@{ 00833 /** 00834 * @brief Finds the end of a subsequence matching given key. 00835 * @param __x Key to be located. 00836 * @return Iterator pointing to the first element 00837 * greater than key, or end(). 00838 */ 00839 iterator 00840 upper_bound(const key_type& __x) 00841 { return _M_t.upper_bound(__x); } 00842 00843 const_iterator 00844 upper_bound(const key_type& __x) const 00845 { return _M_t.upper_bound(__x); } 00846 00847 #if __cplusplus > 201103L 00848 template<typename _Kt> 00849 auto 00850 upper_bound(const _Kt& __x) 00851 -> decltype(iterator(_M_t._M_upper_bound_tr(__x))) 00852 { return iterator(_M_t._M_upper_bound_tr(__x)); } 00853 00854 template<typename _Kt> 00855 auto 00856 upper_bound(const _Kt& __x) const 00857 -> decltype(iterator(_M_t._M_upper_bound_tr(__x))) 00858 { return iterator(_M_t._M_upper_bound_tr(__x)); } 00859 #endif 00860 //@} 00861 00862 //@{ 00863 /** 00864 * @brief Finds a subsequence matching given key. 00865 * @param __x Key to be located. 00866 * @return Pair of iterators that possibly points to the subsequence 00867 * matching given key. 00868 * 00869 * This function is equivalent to 00870 * @code 00871 * std::make_pair(c.lower_bound(val), 00872 * c.upper_bound(val)) 00873 * @endcode 00874 * (but is faster than making the calls separately). 00875 * 00876 * This function probably only makes sense for multisets. 00877 */ 00878 std::pair<iterator, iterator> 00879 equal_range(const key_type& __x) 00880 { return _M_t.equal_range(__x); } 00881 00882 std::pair<const_iterator, const_iterator> 00883 equal_range(const key_type& __x) const 00884 { return _M_t.equal_range(__x); } 00885 00886 #if __cplusplus > 201103L 00887 template<typename _Kt> 00888 auto 00889 equal_range(const _Kt& __x) 00890 -> decltype(pair<iterator, iterator>(_M_t._M_equal_range_tr(__x))) 00891 { return pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)); } 00892 00893 template<typename _Kt> 00894 auto 00895 equal_range(const _Kt& __x) const 00896 -> decltype(pair<iterator, iterator>(_M_t._M_equal_range_tr(__x))) 00897 { return pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)); } 00898 #endif 00899 //@} 00900 00901 template<typename _K1, typename _C1, typename _A1> 00902 friend bool 00903 operator==(const multiset<_K1, _C1, _A1>&, 00904 const multiset<_K1, _C1, _A1>&); 00905 00906 template<typename _K1, typename _C1, typename _A1> 00907 friend bool 00908 operator< (const multiset<_K1, _C1, _A1>&, 00909 const multiset<_K1, _C1, _A1>&); 00910 }; 00911 00912 #if __cpp_deduction_guides >= 201606 00913 00914 template<typename _InputIterator, 00915 typename _Compare = 00916 less<typename iterator_traits<_InputIterator>::value_type>, 00917 typename _Allocator = 00918 allocator<typename iterator_traits<_InputIterator>::value_type>, 00919 typename = _RequireInputIter<_InputIterator>, 00920 typename = _RequireNotAllocator<_Compare>, 00921 typename = _RequireAllocator<_Allocator>> 00922 multiset(_InputIterator, _InputIterator, 00923 _Compare = _Compare(), _Allocator = _Allocator()) 00924 -> multiset<typename iterator_traits<_InputIterator>::value_type, 00925 _Compare, _Allocator>; 00926 00927 template<typename _Key, 00928 typename _Compare = less<_Key>, 00929 typename _Allocator = allocator<_Key>, 00930 typename = _RequireNotAllocator<_Compare>, 00931 typename = _RequireAllocator<_Allocator>> 00932 multiset(initializer_list<_Key>, 00933 _Compare = _Compare(), _Allocator = _Allocator()) 00934 -> multiset<_Key, _Compare, _Allocator>; 00935 00936 template<typename _InputIterator, typename _Allocator, 00937 typename = _RequireInputIter<_InputIterator>, 00938 typename = _RequireAllocator<_Allocator>> 00939 multiset(_InputIterator, _InputIterator, _Allocator) 00940 -> multiset<typename iterator_traits<_InputIterator>::value_type, 00941 less<typename iterator_traits<_InputIterator>::value_type>, 00942 _Allocator>; 00943 00944 template<typename _Key, typename _Allocator, 00945 typename = _RequireAllocator<_Allocator>> 00946 multiset(initializer_list<_Key>, _Allocator) 00947 -> multiset<_Key, less<_Key>, _Allocator>; 00948 00949 #endif 00950 00951 /** 00952 * @brief Multiset equality comparison. 00953 * @param __x A %multiset. 00954 * @param __y A %multiset of the same type as @a __x. 00955 * @return True iff the size and elements of the multisets are equal. 00956 * 00957 * This is an equivalence relation. It is linear in the size of the 00958 * multisets. 00959 * Multisets are considered equivalent if their sizes are equal, and if 00960 * corresponding elements compare equal. 00961 */ 00962 template<typename _Key, typename _Compare, typename _Alloc> 00963 inline bool 00964 operator==(const multiset<_Key, _Compare, _Alloc>& __x, 00965 const multiset<_Key, _Compare, _Alloc>& __y) 00966 { return __x._M_t == __y._M_t; } 00967 00968 /** 00969 * @brief Multiset ordering relation. 00970 * @param __x A %multiset. 00971 * @param __y A %multiset of the same type as @a __x. 00972 * @return True iff @a __x is lexicographically less than @a __y. 00973 * 00974 * This is a total ordering relation. It is linear in the size of the 00975 * sets. The elements must be comparable with @c <. 00976 * 00977 * See std::lexicographical_compare() for how the determination is made. 00978 */ 00979 template<typename _Key, typename _Compare, typename _Alloc> 00980 inline bool 00981 operator<(const multiset<_Key, _Compare, _Alloc>& __x, 00982 const multiset<_Key, _Compare, _Alloc>& __y) 00983 { return __x._M_t < __y._M_t; } 00984 00985 /// Returns !(x == y). 00986 template<typename _Key, typename _Compare, typename _Alloc> 00987 inline bool 00988 operator!=(const multiset<_Key, _Compare, _Alloc>& __x, 00989 const multiset<_Key, _Compare, _Alloc>& __y) 00990 { return !(__x == __y); } 00991 00992 /// Returns y < x. 00993 template<typename _Key, typename _Compare, typename _Alloc> 00994 inline bool 00995 operator>(const multiset<_Key,_Compare,_Alloc>& __x, 00996 const multiset<_Key,_Compare,_Alloc>& __y) 00997 { return __y < __x; } 00998 00999 /// Returns !(y < x) 01000 template<typename _Key, typename _Compare, typename _Alloc> 01001 inline bool 01002 operator<=(const multiset<_Key, _Compare, _Alloc>& __x, 01003 const multiset<_Key, _Compare, _Alloc>& __y) 01004 { return !(__y < __x); } 01005 01006 /// Returns !(x < y) 01007 template<typename _Key, typename _Compare, typename _Alloc> 01008 inline bool 01009 operator>=(const multiset<_Key, _Compare, _Alloc>& __x, 01010 const multiset<_Key, _Compare, _Alloc>& __y) 01011 { return !(__x < __y); } 01012 01013 /// See std::multiset::swap(). 01014 template<typename _Key, typename _Compare, typename _Alloc> 01015 inline void 01016 swap(multiset<_Key, _Compare, _Alloc>& __x, 01017 multiset<_Key, _Compare, _Alloc>& __y) 01018 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y))) 01019 { __x.swap(__y); } 01020 01021 _GLIBCXX_END_NAMESPACE_CONTAINER 01022 01023 #if __cplusplus > 201402L 01024 // Allow std::multiset access to internals of compatible sets. 01025 template<typename _Val, typename _Cmp1, typename _Alloc, typename _Cmp2> 01026 struct 01027 _Rb_tree_merge_helper<_GLIBCXX_STD_C::multiset<_Val, _Cmp1, _Alloc>, 01028 _Cmp2> 01029 { 01030 private: 01031 friend class _GLIBCXX_STD_C::multiset<_Val, _Cmp1, _Alloc>; 01032 01033 static auto& 01034 _S_get_tree(_GLIBCXX_STD_C::set<_Val, _Cmp2, _Alloc>& __set) 01035 { return __set._M_t; } 01036 01037 static auto& 01038 _S_get_tree(_GLIBCXX_STD_C::multiset<_Val, _Cmp2, _Alloc>& __set) 01039 { return __set._M_t; } 01040 }; 01041 01042 #endif // C++17 01043 01044 _GLIBCXX_END_NAMESPACE_VERSION 01045 } // namespace std 01046 01047 #endif /* _STL_MULTISET_H */