libstdc++
|
00001 // Multiset implementation -*- C++ -*- 00002 00003 // Copyright (C) 2001-2017 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 template<typename _Key, typename _Compare, typename _Alloc> 00069 class set; 00070 00071 /** 00072 * @brief A standard container made up of elements, which can be retrieved 00073 * in logarithmic time. 00074 * 00075 * @ingroup associative_containers 00076 * 00077 * 00078 * @tparam _Key Type of key objects. 00079 * @tparam _Compare Comparison function object type, defaults to less<_Key>. 00080 * @tparam _Alloc Allocator type, defaults to allocator<_Key>. 00081 * 00082 * Meets the requirements of a <a href="tables.html#65">container</a>, a 00083 * <a href="tables.html#66">reversible container</a>, and an 00084 * <a href="tables.html#69">associative container</a> (using equivalent 00085 * keys). For a @c multiset<Key> the key_type and value_type are Key. 00086 * 00087 * Multisets support bidirectional iterators. 00088 * 00089 * The private tree data is declared exactly the same way for set and 00090 * multiset; the distinction is made entirely in how the tree functions are 00091 * called (*_unique versus *_equal, same as the standard). 00092 */ 00093 template <typename _Key, typename _Compare = std::less<_Key>, 00094 typename _Alloc = std::allocator<_Key> > 00095 class multiset 00096 { 00097 #ifdef _GLIBCXX_CONCEPT_CHECKS 00098 // concept requirements 00099 typedef typename _Alloc::value_type _Alloc_value_type; 00100 # if __cplusplus < 201103L 00101 __glibcxx_class_requires(_Key, _SGIAssignableConcept) 00102 # endif 00103 __glibcxx_class_requires4(_Compare, bool, _Key, _Key, 00104 _BinaryFunctionConcept) 00105 __glibcxx_class_requires2(_Key, _Alloc_value_type, _SameTypeConcept) 00106 #endif 00107 00108 public: 00109 // typedefs: 00110 typedef _Key key_type; 00111 typedef _Key value_type; 00112 typedef _Compare key_compare; 00113 typedef _Compare value_compare; 00114 typedef _Alloc allocator_type; 00115 00116 private: 00117 /// This turns a red-black tree into a [multi]set. 00118 typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template 00119 rebind<_Key>::other _Key_alloc_type; 00120 00121 typedef _Rb_tree<key_type, value_type, _Identity<value_type>, 00122 key_compare, _Key_alloc_type> _Rep_type; 00123 /// The actual tree structure. 00124 _Rep_type _M_t; 00125 00126 typedef __gnu_cxx::__alloc_traits<_Key_alloc_type> _Alloc_traits; 00127 00128 public: 00129 typedef typename _Alloc_traits::pointer pointer; 00130 typedef typename _Alloc_traits::const_pointer const_pointer; 00131 typedef typename _Alloc_traits::reference reference; 00132 typedef typename _Alloc_traits::const_reference const_reference; 00133 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00134 // DR 103. set::iterator is required to be modifiable, 00135 // but this allows modification of keys. 00136 typedef typename _Rep_type::const_iterator iterator; 00137 typedef typename _Rep_type::const_iterator const_iterator; 00138 typedef typename _Rep_type::const_reverse_iterator reverse_iterator; 00139 typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator; 00140 typedef typename _Rep_type::size_type size_type; 00141 typedef typename _Rep_type::difference_type difference_type; 00142 00143 #if __cplusplus > 201402L 00144 using node_type = typename _Rep_type::node_type; 00145 #endif 00146 00147 // allocation/deallocation 00148 /** 00149 * @brief Default constructor creates no elements. 00150 */ 00151 #if __cplusplus < 201103L 00152 multiset() : _M_t() { } 00153 #else 00154 multiset() = default; 00155 #endif 00156 00157 /** 00158 * @brief Creates a %multiset with no elements. 00159 * @param __comp Comparator to use. 00160 * @param __a An allocator object. 00161 */ 00162 explicit 00163 multiset(const _Compare& __comp, 00164 const allocator_type& __a = allocator_type()) 00165 : _M_t(__comp, _Key_alloc_type(__a)) { } 00166 00167 /** 00168 * @brief Builds a %multiset from a range. 00169 * @param __first An input iterator. 00170 * @param __last An input iterator. 00171 * 00172 * Create a %multiset consisting of copies of the elements from 00173 * [first,last). This is linear in N if the range is already sorted, 00174 * and NlogN otherwise (where N is distance(__first,__last)). 00175 */ 00176 template<typename _InputIterator> 00177 multiset(_InputIterator __first, _InputIterator __last) 00178 : _M_t() 00179 { _M_t._M_insert_equal(__first, __last); } 00180 00181 /** 00182 * @brief Builds a %multiset from a range. 00183 * @param __first An input iterator. 00184 * @param __last An input iterator. 00185 * @param __comp A comparison functor. 00186 * @param __a An allocator object. 00187 * 00188 * Create a %multiset consisting of copies of the elements from 00189 * [__first,__last). This is linear in N if the range is already sorted, 00190 * and NlogN otherwise (where N is distance(__first,__last)). 00191 */ 00192 template<typename _InputIterator> 00193 multiset(_InputIterator __first, _InputIterator __last, 00194 const _Compare& __comp, 00195 const allocator_type& __a = allocator_type()) 00196 : _M_t(__comp, _Key_alloc_type(__a)) 00197 { _M_t._M_insert_equal(__first, __last); } 00198 00199 /** 00200 * @brief %Multiset copy constructor. 00201 * 00202 * Whether the allocator is copied depends on the allocator traits. 00203 */ 00204 #if __cplusplus < 201103L 00205 multiset(const multiset& __x) 00206 : _M_t(__x._M_t) { } 00207 #else 00208 multiset(const multiset&) = default; 00209 00210 /** 00211 * @brief %Multiset move constructor. 00212 * 00213 * The newly-created %multiset contains the exact contents of the 00214 * moved instance. The moved instance is a valid, but unspecified 00215 * %multiset. 00216 */ 00217 multiset(multiset&&) = default; 00218 00219 /** 00220 * @brief Builds a %multiset from an initializer_list. 00221 * @param __l An initializer_list. 00222 * @param __comp A comparison functor. 00223 * @param __a An allocator object. 00224 * 00225 * Create a %multiset consisting of copies of the elements from 00226 * the list. This is linear in N if the list is already sorted, 00227 * and NlogN otherwise (where N is @a __l.size()). 00228 */ 00229 multiset(initializer_list<value_type> __l, 00230 const _Compare& __comp = _Compare(), 00231 const allocator_type& __a = allocator_type()) 00232 : _M_t(__comp, _Key_alloc_type(__a)) 00233 { _M_t._M_insert_equal(__l.begin(), __l.end()); } 00234 00235 /// Allocator-extended default constructor. 00236 explicit 00237 multiset(const allocator_type& __a) 00238 : _M_t(_Compare(), _Key_alloc_type(__a)) { } 00239 00240 /// Allocator-extended copy constructor. 00241 multiset(const multiset& __m, const allocator_type& __a) 00242 : _M_t(__m._M_t, _Key_alloc_type(__a)) { } 00243 00244 /// Allocator-extended move constructor. 00245 multiset(multiset&& __m, const allocator_type& __a) 00246 noexcept(is_nothrow_copy_constructible<_Compare>::value 00247 && _Alloc_traits::_S_always_equal()) 00248 : _M_t(std::move(__m._M_t), _Key_alloc_type(__a)) { } 00249 00250 /// Allocator-extended initialier-list constructor. 00251 multiset(initializer_list<value_type> __l, const allocator_type& __a) 00252 : _M_t(_Compare(), _Key_alloc_type(__a)) 00253 { _M_t._M_insert_equal(__l.begin(), __l.end()); } 00254 00255 /// Allocator-extended range constructor. 00256 template<typename _InputIterator> 00257 multiset(_InputIterator __first, _InputIterator __last, 00258 const allocator_type& __a) 00259 : _M_t(_Compare(), _Key_alloc_type(__a)) 00260 { _M_t._M_insert_equal(__first, __last); } 00261 00262 /** 00263 * The dtor only erases the elements, and note that if the elements 00264 * themselves are pointers, the pointed-to memory is not touched in any 00265 * way. Managing the pointer is the user's responsibility. 00266 */ 00267 ~multiset() = default; 00268 #endif 00269 00270 /** 00271 * @brief %Multiset assignment operator. 00272 * 00273 * Whether the allocator is copied depends on the allocator traits. 00274 */ 00275 #if __cplusplus < 201103L 00276 multiset& 00277 operator=(const multiset& __x) 00278 { 00279 _M_t = __x._M_t; 00280 return *this; 00281 } 00282 #else 00283 multiset& 00284 operator=(const multiset&) = default; 00285 00286 /// Move assignment operator. 00287 multiset& 00288 operator=(multiset&&) = default; 00289 00290 /** 00291 * @brief %Multiset list assignment operator. 00292 * @param __l An initializer_list. 00293 * 00294 * This function fills a %multiset with copies of the elements in the 00295 * initializer list @a __l. 00296 * 00297 * Note that the assignment completely changes the %multiset and 00298 * that the resulting %multiset's size is the same as the number 00299 * of elements assigned. 00300 */ 00301 multiset& 00302 operator=(initializer_list<value_type> __l) 00303 { 00304 _M_t._M_assign_equal(__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 * Whether the allocators are swapped depends on the allocator traits. 00425 */ 00426 void 00427 swap(multiset& __x) 00428 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value) 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 https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints 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 https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints 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 > 201402L 00558 /// Extract a node. 00559 node_type 00560 extract(const_iterator __pos) 00561 { 00562 __glibcxx_assert(__pos != end()); 00563 return _M_t.extract(__pos); 00564 } 00565 00566 /// Extract a node. 00567 node_type 00568 extract(const key_type& __x) 00569 { return _M_t.extract(__x); } 00570 00571 /// Re-insert an extracted node. 00572 iterator 00573 insert(node_type&& __nh) 00574 { return _M_t._M_reinsert_node_equal(std::move(__nh)); } 00575 00576 /// Re-insert an extracted node. 00577 iterator 00578 insert(const_iterator __hint, node_type&& __nh) 00579 { return _M_t._M_reinsert_node_hint_equal(__hint, std::move(__nh)); } 00580 00581 template<typename, typename> 00582 friend class _Rb_tree_merge_helper; 00583 00584 template<typename _Compare1> 00585 void 00586 merge(multiset<_Key, _Compare1, _Alloc>& __source) 00587 { 00588 using _Merge_helper = _Rb_tree_merge_helper<multiset, _Compare1>; 00589 _M_t._M_merge_equal(_Merge_helper::_S_get_tree(__source)); 00590 } 00591 00592 template<typename _Compare1> 00593 void 00594 merge(multiset<_Key, _Compare1, _Alloc>&& __source) 00595 { merge(__source); } 00596 00597 template<typename _Compare1> 00598 void 00599 merge(set<_Key, _Compare1, _Alloc>& __source) 00600 { 00601 using _Merge_helper = _Rb_tree_merge_helper<multiset, _Compare1>; 00602 _M_t._M_merge_equal(_Merge_helper::_S_get_tree(__source)); 00603 } 00604 00605 template<typename _Compare1> 00606 void 00607 merge(set<_Key, _Compare1, _Alloc>&& __source) 00608 { merge(__source); } 00609 #endif // C++17 00610 00611 #if __cplusplus >= 201103L 00612 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00613 // DR 130. Associative erase should return an iterator. 00614 /** 00615 * @brief Erases an element from a %multiset. 00616 * @param __position An iterator pointing to the element to be erased. 00617 * @return An iterator pointing to the element immediately following 00618 * @a position prior to the element being erased. If no such 00619 * element exists, end() is returned. 00620 * 00621 * This function erases an element, pointed to by the given iterator, 00622 * from a %multiset. Note that this function only erases the element, 00623 * and that if the element is itself a pointer, the pointed-to memory is 00624 * not touched in any way. Managing the pointer is the user's 00625 * responsibility. 00626 */ 00627 _GLIBCXX_ABI_TAG_CXX11 00628 iterator 00629 erase(const_iterator __position) 00630 { return _M_t.erase(__position); } 00631 #else 00632 /** 00633 * @brief Erases an element from a %multiset. 00634 * @param __position An iterator pointing to the element to be erased. 00635 * 00636 * This function erases an element, pointed to by the given iterator, 00637 * from a %multiset. Note that this function only erases the element, 00638 * and that if the element is itself a pointer, the pointed-to memory is 00639 * not touched in any way. Managing the pointer is the user's 00640 * responsibility. 00641 */ 00642 void 00643 erase(iterator __position) 00644 { _M_t.erase(__position); } 00645 #endif 00646 00647 /** 00648 * @brief Erases elements according to the provided key. 00649 * @param __x Key of element to be erased. 00650 * @return The number of elements erased. 00651 * 00652 * This function erases all elements located by the given key from a 00653 * %multiset. 00654 * Note that this function only erases the element, and that if 00655 * the element is itself a pointer, the pointed-to memory is not touched 00656 * in any way. Managing the pointer is the user's responsibility. 00657 */ 00658 size_type 00659 erase(const key_type& __x) 00660 { return _M_t.erase(__x); } 00661 00662 #if __cplusplus >= 201103L 00663 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00664 // DR 130. Associative erase should return an iterator. 00665 /** 00666 * @brief Erases a [first,last) range of elements from a %multiset. 00667 * @param __first Iterator pointing to the start of the range to be 00668 * erased. 00669 * @param __last Iterator pointing to the end of the range to 00670 * be erased. 00671 * @return The iterator @a last. 00672 * 00673 * This function erases a sequence of elements from a %multiset. 00674 * Note that this function only erases the elements, and that if 00675 * the elements themselves are pointers, the pointed-to memory is not 00676 * touched in any way. Managing the pointer is the user's 00677 * responsibility. 00678 */ 00679 _GLIBCXX_ABI_TAG_CXX11 00680 iterator 00681 erase(const_iterator __first, const_iterator __last) 00682 { return _M_t.erase(__first, __last); } 00683 #else 00684 /** 00685 * @brief Erases a [first,last) range of elements from a %multiset. 00686 * @param first Iterator pointing to the start of the range to be 00687 * erased. 00688 * @param last Iterator pointing to the end of the range to be erased. 00689 * 00690 * This function erases a sequence of elements from a %multiset. 00691 * Note that this function only erases the elements, and that if 00692 * the elements themselves are pointers, the pointed-to memory is not 00693 * touched in any way. Managing the pointer is the user's 00694 * responsibility. 00695 */ 00696 void 00697 erase(iterator __first, iterator __last) 00698 { _M_t.erase(__first, __last); } 00699 #endif 00700 00701 /** 00702 * Erases all elements in a %multiset. Note that this function only 00703 * erases the elements, and that if the elements themselves are pointers, 00704 * the pointed-to memory is not touched in any way. Managing the pointer 00705 * is the user's responsibility. 00706 */ 00707 void 00708 clear() _GLIBCXX_NOEXCEPT 00709 { _M_t.clear(); } 00710 00711 // multiset operations: 00712 00713 //@{ 00714 /** 00715 * @brief Finds the number of elements with given key. 00716 * @param __x Key of elements to be located. 00717 * @return Number of elements with specified key. 00718 */ 00719 size_type 00720 count(const key_type& __x) const 00721 { return _M_t.count(__x); } 00722 00723 #if __cplusplus > 201103L 00724 template<typename _Kt> 00725 auto 00726 count(const _Kt& __x) const -> decltype(_M_t._M_count_tr(__x)) 00727 { return _M_t._M_count_tr(__x); } 00728 #endif 00729 //@} 00730 00731 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00732 // 214. set::find() missing const overload 00733 //@{ 00734 /** 00735 * @brief Tries to locate an element in a %set. 00736 * @param __x Element to be located. 00737 * @return Iterator pointing to sought-after element, or end() if not 00738 * found. 00739 * 00740 * This function takes a key and tries to locate the element with which 00741 * the key matches. If successful the function returns an iterator 00742 * pointing to the sought after element. If unsuccessful it returns the 00743 * past-the-end ( @c end() ) iterator. 00744 */ 00745 iterator 00746 find(const key_type& __x) 00747 { return _M_t.find(__x); } 00748 00749 const_iterator 00750 find(const key_type& __x) const 00751 { return _M_t.find(__x); } 00752 00753 #if __cplusplus > 201103L 00754 template<typename _Kt> 00755 auto 00756 find(const _Kt& __x) 00757 -> decltype(iterator{_M_t._M_find_tr(__x)}) 00758 { return iterator{_M_t._M_find_tr(__x)}; } 00759 00760 template<typename _Kt> 00761 auto 00762 find(const _Kt& __x) const 00763 -> decltype(const_iterator{_M_t._M_find_tr(__x)}) 00764 { return const_iterator{_M_t._M_find_tr(__x)}; } 00765 #endif 00766 //@} 00767 00768 //@{ 00769 /** 00770 * @brief Finds the beginning of a subsequence matching given key. 00771 * @param __x Key to be located. 00772 * @return Iterator pointing to first element equal to or greater 00773 * than key, or end(). 00774 * 00775 * This function returns the first element of a subsequence of elements 00776 * that matches the given key. If unsuccessful it returns an iterator 00777 * pointing to the first element that has a greater value than given key 00778 * or end() if no such element exists. 00779 */ 00780 iterator 00781 lower_bound(const key_type& __x) 00782 { return _M_t.lower_bound(__x); } 00783 00784 const_iterator 00785 lower_bound(const key_type& __x) const 00786 { return _M_t.lower_bound(__x); } 00787 00788 #if __cplusplus > 201103L 00789 template<typename _Kt> 00790 auto 00791 lower_bound(const _Kt& __x) 00792 -> decltype(iterator(_M_t._M_lower_bound_tr(__x))) 00793 { return iterator(_M_t._M_lower_bound_tr(__x)); } 00794 00795 template<typename _Kt> 00796 auto 00797 lower_bound(const _Kt& __x) const 00798 -> decltype(iterator(_M_t._M_lower_bound_tr(__x))) 00799 { return iterator(_M_t._M_lower_bound_tr(__x)); } 00800 #endif 00801 //@} 00802 00803 //@{ 00804 /** 00805 * @brief Finds the end of a subsequence matching given key. 00806 * @param __x Key to be located. 00807 * @return Iterator pointing to the first element 00808 * greater than key, or end(). 00809 */ 00810 iterator 00811 upper_bound(const key_type& __x) 00812 { return _M_t.upper_bound(__x); } 00813 00814 const_iterator 00815 upper_bound(const key_type& __x) const 00816 { return _M_t.upper_bound(__x); } 00817 00818 #if __cplusplus > 201103L 00819 template<typename _Kt> 00820 auto 00821 upper_bound(const _Kt& __x) 00822 -> decltype(iterator(_M_t._M_upper_bound_tr(__x))) 00823 { return iterator(_M_t._M_upper_bound_tr(__x)); } 00824 00825 template<typename _Kt> 00826 auto 00827 upper_bound(const _Kt& __x) const 00828 -> decltype(iterator(_M_t._M_upper_bound_tr(__x))) 00829 { return iterator(_M_t._M_upper_bound_tr(__x)); } 00830 #endif 00831 //@} 00832 00833 //@{ 00834 /** 00835 * @brief Finds a subsequence matching given key. 00836 * @param __x Key to be located. 00837 * @return Pair of iterators that possibly points to the subsequence 00838 * matching given key. 00839 * 00840 * This function is equivalent to 00841 * @code 00842 * std::make_pair(c.lower_bound(val), 00843 * c.upper_bound(val)) 00844 * @endcode 00845 * (but is faster than making the calls separately). 00846 * 00847 * This function probably only makes sense for multisets. 00848 */ 00849 std::pair<iterator, iterator> 00850 equal_range(const key_type& __x) 00851 { return _M_t.equal_range(__x); } 00852 00853 std::pair<const_iterator, const_iterator> 00854 equal_range(const key_type& __x) const 00855 { return _M_t.equal_range(__x); } 00856 00857 #if __cplusplus > 201103L 00858 template<typename _Kt> 00859 auto 00860 equal_range(const _Kt& __x) 00861 -> decltype(pair<iterator, iterator>(_M_t._M_equal_range_tr(__x))) 00862 { return pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)); } 00863 00864 template<typename _Kt> 00865 auto 00866 equal_range(const _Kt& __x) const 00867 -> decltype(pair<iterator, iterator>(_M_t._M_equal_range_tr(__x))) 00868 { return pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)); } 00869 #endif 00870 //@} 00871 00872 template<typename _K1, typename _C1, typename _A1> 00873 friend bool 00874 operator==(const multiset<_K1, _C1, _A1>&, 00875 const multiset<_K1, _C1, _A1>&); 00876 00877 template<typename _K1, typename _C1, typename _A1> 00878 friend bool 00879 operator< (const multiset<_K1, _C1, _A1>&, 00880 const multiset<_K1, _C1, _A1>&); 00881 }; 00882 00883 /** 00884 * @brief Multiset equality comparison. 00885 * @param __x A %multiset. 00886 * @param __y A %multiset of the same type as @a __x. 00887 * @return True iff the size and elements of the multisets are equal. 00888 * 00889 * This is an equivalence relation. It is linear in the size of the 00890 * multisets. 00891 * Multisets are considered equivalent if their sizes are equal, and if 00892 * corresponding elements compare equal. 00893 */ 00894 template<typename _Key, typename _Compare, typename _Alloc> 00895 inline bool 00896 operator==(const multiset<_Key, _Compare, _Alloc>& __x, 00897 const multiset<_Key, _Compare, _Alloc>& __y) 00898 { return __x._M_t == __y._M_t; } 00899 00900 /** 00901 * @brief Multiset ordering relation. 00902 * @param __x A %multiset. 00903 * @param __y A %multiset of the same type as @a __x. 00904 * @return True iff @a __x is lexicographically less than @a __y. 00905 * 00906 * This is a total ordering relation. It is linear in the size of the 00907 * sets. The elements must be comparable with @c <. 00908 * 00909 * See std::lexicographical_compare() for how the determination is made. 00910 */ 00911 template<typename _Key, typename _Compare, typename _Alloc> 00912 inline bool 00913 operator<(const multiset<_Key, _Compare, _Alloc>& __x, 00914 const multiset<_Key, _Compare, _Alloc>& __y) 00915 { return __x._M_t < __y._M_t; } 00916 00917 /// Returns !(x == y). 00918 template<typename _Key, typename _Compare, typename _Alloc> 00919 inline bool 00920 operator!=(const multiset<_Key, _Compare, _Alloc>& __x, 00921 const multiset<_Key, _Compare, _Alloc>& __y) 00922 { return !(__x == __y); } 00923 00924 /// Returns y < x. 00925 template<typename _Key, typename _Compare, typename _Alloc> 00926 inline bool 00927 operator>(const multiset<_Key,_Compare,_Alloc>& __x, 00928 const multiset<_Key,_Compare,_Alloc>& __y) 00929 { return __y < __x; } 00930 00931 /// Returns !(y < x) 00932 template<typename _Key, typename _Compare, typename _Alloc> 00933 inline bool 00934 operator<=(const multiset<_Key, _Compare, _Alloc>& __x, 00935 const multiset<_Key, _Compare, _Alloc>& __y) 00936 { return !(__y < __x); } 00937 00938 /// Returns !(x < y) 00939 template<typename _Key, typename _Compare, typename _Alloc> 00940 inline bool 00941 operator>=(const multiset<_Key, _Compare, _Alloc>& __x, 00942 const multiset<_Key, _Compare, _Alloc>& __y) 00943 { return !(__x < __y); } 00944 00945 /// See std::multiset::swap(). 00946 template<typename _Key, typename _Compare, typename _Alloc> 00947 inline void 00948 swap(multiset<_Key, _Compare, _Alloc>& __x, 00949 multiset<_Key, _Compare, _Alloc>& __y) 00950 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y))) 00951 { __x.swap(__y); } 00952 00953 _GLIBCXX_END_NAMESPACE_CONTAINER 00954 00955 #if __cplusplus > 201402L 00956 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00957 // Allow std::multiset access to internals of compatible sets. 00958 template<typename _Val, typename _Cmp1, typename _Alloc, typename _Cmp2> 00959 struct 00960 _Rb_tree_merge_helper<_GLIBCXX_STD_C::multiset<_Val, _Cmp1, _Alloc>, 00961 _Cmp2> 00962 { 00963 private: 00964 friend class _GLIBCXX_STD_C::multiset<_Val, _Cmp1, _Alloc>; 00965 00966 static auto& 00967 _S_get_tree(_GLIBCXX_STD_C::set<_Val, _Cmp2, _Alloc>& __set) 00968 { return __set._M_t; } 00969 00970 static auto& 00971 _S_get_tree(_GLIBCXX_STD_C::multiset<_Val, _Cmp2, _Alloc>& __set) 00972 { return __set._M_t; } 00973 }; 00974 _GLIBCXX_END_NAMESPACE_VERSION 00975 #endif // C++17 00976 00977 } // namespace std 00978 00979 #endif /* _STL_MULTISET_H */