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