libstdc++
|
00001 // Multimap 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,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_range_equal(__l.begin(), __l.end()); } 00228 00229 /// Allocator-extended default constructor. 00230 explicit 00231 multimap(const allocator_type& __a) 00232 : _M_t(_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(_Pair_alloc_type(__a)) 00247 { _M_t._M_insert_range_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(_Pair_alloc_type(__a)) 00254 { _M_t._M_insert_range_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_range_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_range_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 _GLIBCXX_NODISCARD 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_range_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 #if __cplusplus > 201703L 00895 //@{ 00896 /** 00897 * @brief Finds whether an element with the given key exists. 00898 * @param __x Key of (key, value) pairs to be located. 00899 * @return True if there is any element with the specified key. 00900 */ 00901 bool 00902 contains(const key_type& __x) const 00903 { return _M_t.find(__x) != _M_t.end(); } 00904 00905 template<typename _Kt> 00906 auto 00907 contains(const _Kt& __x) const 00908 -> decltype(_M_t._M_find_tr(__x), void(), true) 00909 { return _M_t._M_find_tr(__x) != _M_t.end(); } 00910 //@} 00911 #endif 00912 00913 //@{ 00914 /** 00915 * @brief Finds the beginning of a subsequence matching given key. 00916 * @param __x Key of (key, value) pair to be located. 00917 * @return Iterator pointing to first element equal to or greater 00918 * than key, or end(). 00919 * 00920 * This function returns the first element of a subsequence of elements 00921 * that matches the given key. If unsuccessful it returns an iterator 00922 * pointing to the first element that has a greater value than given key 00923 * or end() if no such element exists. 00924 */ 00925 iterator 00926 lower_bound(const key_type& __x) 00927 { return _M_t.lower_bound(__x); } 00928 00929 #if __cplusplus > 201103L 00930 template<typename _Kt> 00931 auto 00932 lower_bound(const _Kt& __x) 00933 -> decltype(iterator(_M_t._M_lower_bound_tr(__x))) 00934 { return iterator(_M_t._M_lower_bound_tr(__x)); } 00935 #endif 00936 //@} 00937 00938 //@{ 00939 /** 00940 * @brief Finds the beginning of a subsequence matching given key. 00941 * @param __x Key of (key, value) pair to be located. 00942 * @return Read-only (constant) iterator pointing to first element 00943 * equal to or greater than key, or end(). 00944 * 00945 * This function returns the first element of a subsequence of 00946 * elements that matches the given key. If unsuccessful the 00947 * iterator will point to the next greatest element or, if no 00948 * such greater element exists, to end(). 00949 */ 00950 const_iterator 00951 lower_bound(const key_type& __x) const 00952 { return _M_t.lower_bound(__x); } 00953 00954 #if __cplusplus > 201103L 00955 template<typename _Kt> 00956 auto 00957 lower_bound(const _Kt& __x) const 00958 -> decltype(const_iterator(_M_t._M_lower_bound_tr(__x))) 00959 { return const_iterator(_M_t._M_lower_bound_tr(__x)); } 00960 #endif 00961 //@} 00962 00963 //@{ 00964 /** 00965 * @brief Finds the end of a subsequence matching given key. 00966 * @param __x Key of (key, value) pair to be located. 00967 * @return Iterator pointing to the first element 00968 * greater than key, or end(). 00969 */ 00970 iterator 00971 upper_bound(const key_type& __x) 00972 { return _M_t.upper_bound(__x); } 00973 00974 #if __cplusplus > 201103L 00975 template<typename _Kt> 00976 auto 00977 upper_bound(const _Kt& __x) 00978 -> decltype(iterator(_M_t._M_upper_bound_tr(__x))) 00979 { return iterator(_M_t._M_upper_bound_tr(__x)); } 00980 #endif 00981 //@} 00982 00983 //@{ 00984 /** 00985 * @brief Finds the end of a subsequence matching given key. 00986 * @param __x Key of (key, value) pair to be located. 00987 * @return Read-only (constant) iterator pointing to first iterator 00988 * greater than key, or end(). 00989 */ 00990 const_iterator 00991 upper_bound(const key_type& __x) const 00992 { return _M_t.upper_bound(__x); } 00993 00994 #if __cplusplus > 201103L 00995 template<typename _Kt> 00996 auto 00997 upper_bound(const _Kt& __x) const 00998 -> decltype(const_iterator(_M_t._M_upper_bound_tr(__x))) 00999 { return const_iterator(_M_t._M_upper_bound_tr(__x)); } 01000 #endif 01001 //@} 01002 01003 //@{ 01004 /** 01005 * @brief Finds a subsequence matching given key. 01006 * @param __x Key of (key, value) pairs to be located. 01007 * @return Pair of iterators that possibly points to the subsequence 01008 * matching given key. 01009 * 01010 * This function is equivalent to 01011 * @code 01012 * std::make_pair(c.lower_bound(val), 01013 * c.upper_bound(val)) 01014 * @endcode 01015 * (but is faster than making the calls separately). 01016 */ 01017 std::pair<iterator, iterator> 01018 equal_range(const key_type& __x) 01019 { return _M_t.equal_range(__x); } 01020 01021 #if __cplusplus > 201103L 01022 template<typename _Kt> 01023 auto 01024 equal_range(const _Kt& __x) 01025 -> decltype(pair<iterator, iterator>(_M_t._M_equal_range_tr(__x))) 01026 { return pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)); } 01027 #endif 01028 //@} 01029 01030 //@{ 01031 /** 01032 * @brief Finds a subsequence matching given key. 01033 * @param __x Key of (key, value) pairs to be located. 01034 * @return Pair of read-only (constant) iterators that possibly points 01035 * to the subsequence matching given key. 01036 * 01037 * This function is equivalent to 01038 * @code 01039 * std::make_pair(c.lower_bound(val), 01040 * c.upper_bound(val)) 01041 * @endcode 01042 * (but is faster than making the calls separately). 01043 */ 01044 std::pair<const_iterator, const_iterator> 01045 equal_range(const key_type& __x) const 01046 { return _M_t.equal_range(__x); } 01047 01048 #if __cplusplus > 201103L 01049 template<typename _Kt> 01050 auto 01051 equal_range(const _Kt& __x) const 01052 -> decltype(pair<const_iterator, const_iterator>( 01053 _M_t._M_equal_range_tr(__x))) 01054 { 01055 return pair<const_iterator, const_iterator>( 01056 _M_t._M_equal_range_tr(__x)); 01057 } 01058 #endif 01059 //@} 01060 01061 template<typename _K1, typename _T1, typename _C1, typename _A1> 01062 friend bool 01063 operator==(const multimap<_K1, _T1, _C1, _A1>&, 01064 const multimap<_K1, _T1, _C1, _A1>&); 01065 01066 template<typename _K1, typename _T1, typename _C1, typename _A1> 01067 friend bool 01068 operator<(const multimap<_K1, _T1, _C1, _A1>&, 01069 const multimap<_K1, _T1, _C1, _A1>&); 01070 }; 01071 01072 #if __cpp_deduction_guides >= 201606 01073 01074 template<typename _InputIterator, 01075 typename _Compare = less<__iter_key_t<_InputIterator>>, 01076 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>, 01077 typename = _RequireInputIter<_InputIterator>, 01078 typename = _RequireNotAllocator<_Compare>, 01079 typename = _RequireAllocator<_Allocator>> 01080 multimap(_InputIterator, _InputIterator, 01081 _Compare = _Compare(), _Allocator = _Allocator()) 01082 -> multimap<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, 01083 _Compare, _Allocator>; 01084 01085 template<typename _Key, typename _Tp, typename _Compare = less<_Key>, 01086 typename _Allocator = allocator<pair<const _Key, _Tp>>, 01087 typename = _RequireNotAllocator<_Compare>, 01088 typename = _RequireAllocator<_Allocator>> 01089 multimap(initializer_list<pair<_Key, _Tp>>, 01090 _Compare = _Compare(), _Allocator = _Allocator()) 01091 -> multimap<_Key, _Tp, _Compare, _Allocator>; 01092 01093 template<typename _InputIterator, typename _Allocator, 01094 typename = _RequireInputIter<_InputIterator>, 01095 typename = _RequireAllocator<_Allocator>> 01096 multimap(_InputIterator, _InputIterator, _Allocator) 01097 -> multimap<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, 01098 less<__iter_key_t<_InputIterator>>, _Allocator>; 01099 01100 template<typename _Key, typename _Tp, typename _Allocator, 01101 typename = _RequireAllocator<_Allocator>> 01102 multimap(initializer_list<pair<_Key, _Tp>>, _Allocator) 01103 -> multimap<_Key, _Tp, less<_Key>, _Allocator>; 01104 01105 #endif 01106 01107 /** 01108 * @brief Multimap equality comparison. 01109 * @param __x A %multimap. 01110 * @param __y A %multimap of the same type as @a __x. 01111 * @return True iff the size and elements of the maps are equal. 01112 * 01113 * This is an equivalence relation. It is linear in the size of the 01114 * multimaps. Multimaps are considered equivalent if their sizes are equal, 01115 * and if corresponding elements compare equal. 01116 */ 01117 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 01118 inline bool 01119 operator==(const multimap<_Key, _Tp, _Compare, _Alloc>& __x, 01120 const multimap<_Key, _Tp, _Compare, _Alloc>& __y) 01121 { return __x._M_t == __y._M_t; } 01122 01123 /** 01124 * @brief Multimap ordering relation. 01125 * @param __x A %multimap. 01126 * @param __y A %multimap of the same type as @a __x. 01127 * @return True iff @a x is lexicographically less than @a y. 01128 * 01129 * This is a total ordering relation. It is linear in the size of the 01130 * multimaps. The elements must be comparable with @c <. 01131 * 01132 * See std::lexicographical_compare() for how the determination is made. 01133 */ 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 __x._M_t < __y._M_t; } 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 /// Based on operator< 01148 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 01149 inline bool 01150 operator>(const multimap<_Key, _Tp, _Compare, _Alloc>& __x, 01151 const multimap<_Key, _Tp, _Compare, _Alloc>& __y) 01152 { return __y < __x; } 01153 01154 /// Based on operator< 01155 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 01156 inline bool 01157 operator<=(const multimap<_Key, _Tp, _Compare, _Alloc>& __x, 01158 const multimap<_Key, _Tp, _Compare, _Alloc>& __y) 01159 { return !(__y < __x); } 01160 01161 /// Based on operator< 01162 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 01163 inline bool 01164 operator>=(const multimap<_Key, _Tp, _Compare, _Alloc>& __x, 01165 const multimap<_Key, _Tp, _Compare, _Alloc>& __y) 01166 { return !(__x < __y); } 01167 01168 /// See std::multimap::swap(). 01169 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 01170 inline void 01171 swap(multimap<_Key, _Tp, _Compare, _Alloc>& __x, 01172 multimap<_Key, _Tp, _Compare, _Alloc>& __y) 01173 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y))) 01174 { __x.swap(__y); } 01175 01176 _GLIBCXX_END_NAMESPACE_CONTAINER 01177 01178 #if __cplusplus > 201402L 01179 // Allow std::multimap access to internals of compatible maps. 01180 template<typename _Key, typename _Val, typename _Cmp1, typename _Alloc, 01181 typename _Cmp2> 01182 struct 01183 _Rb_tree_merge_helper<_GLIBCXX_STD_C::multimap<_Key, _Val, _Cmp1, _Alloc>, 01184 _Cmp2> 01185 { 01186 private: 01187 friend class _GLIBCXX_STD_C::multimap<_Key, _Val, _Cmp1, _Alloc>; 01188 01189 static auto& 01190 _S_get_tree(_GLIBCXX_STD_C::map<_Key, _Val, _Cmp2, _Alloc>& __map) 01191 { return __map._M_t; } 01192 01193 static auto& 01194 _S_get_tree(_GLIBCXX_STD_C::multimap<_Key, _Val, _Cmp2, _Alloc>& __map) 01195 { return __map._M_t; } 01196 }; 01197 #endif // C++17 01198 01199 _GLIBCXX_END_NAMESPACE_VERSION 01200 } // namespace std 01201 01202 #endif /* _STL_MULTIMAP_H */