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