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, typename = typename 00548 std::enable_if<std::is_constructible<value_type, 00549 _Pair&&>::value>::type> 00550 iterator 00551 insert(_Pair&& __x) 00552 { return _M_t._M_insert_equal(std::forward<_Pair>(__x)); } 00553 #endif 00554 // @} 00555 00556 /** 00557 * @brief Inserts a std::pair into the %multimap. 00558 * @param __position An iterator that serves as a hint as to where the 00559 * pair should be inserted. 00560 * @param __x Pair to be inserted (see std::make_pair for easy creation 00561 * of pairs). 00562 * @return An iterator that points to the inserted (key,value) pair. 00563 * 00564 * This function inserts a (key, value) pair into the %multimap. 00565 * Contrary to a std::map the %multimap does not rely on unique keys and 00566 * thus multiple pairs with the same key can be inserted. 00567 * Note that the first parameter is only a hint and can potentially 00568 * improve the performance of the insertion process. A bad hint would 00569 * cause no gains in efficiency. 00570 * 00571 * For more on @a hinting, see: 00572 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints 00573 * 00574 * Insertion requires logarithmic time (if the hint is not taken). 00575 * @{ 00576 */ 00577 iterator 00578 #if __cplusplus >= 201103L 00579 insert(const_iterator __position, const value_type& __x) 00580 #else 00581 insert(iterator __position, const value_type& __x) 00582 #endif 00583 { return _M_t._M_insert_equal_(__position, __x); } 00584 00585 #if __cplusplus >= 201103L 00586 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00587 // 2354. Unnecessary copying when inserting into maps with braced-init 00588 iterator 00589 insert(const_iterator __position, value_type&& __x) 00590 { return _M_t._M_insert_equal_(__position, std::move(__x)); } 00591 00592 template<typename _Pair, typename = typename 00593 std::enable_if<std::is_constructible<value_type, 00594 _Pair&&>::value>::type> 00595 iterator 00596 insert(const_iterator __position, _Pair&& __x) 00597 { return _M_t._M_insert_equal_(__position, 00598 std::forward<_Pair>(__x)); } 00599 #endif 00600 // @} 00601 00602 /** 00603 * @brief A template function that attempts to insert a range 00604 * of elements. 00605 * @param __first Iterator pointing to the start of the range to be 00606 * inserted. 00607 * @param __last Iterator pointing to the end of the range. 00608 * 00609 * Complexity similar to that of the range constructor. 00610 */ 00611 template<typename _InputIterator> 00612 void 00613 insert(_InputIterator __first, _InputIterator __last) 00614 { _M_t._M_insert_equal(__first, __last); } 00615 00616 #if __cplusplus >= 201103L 00617 /** 00618 * @brief Attempts to insert a list of std::pairs into the %multimap. 00619 * @param __l A std::initializer_list<value_type> of pairs to be 00620 * inserted. 00621 * 00622 * Complexity similar to that of the range constructor. 00623 */ 00624 void 00625 insert(initializer_list<value_type> __l) 00626 { this->insert(__l.begin(), __l.end()); } 00627 #endif 00628 00629 #if __cplusplus > 201402L 00630 /// Extract a node. 00631 node_type 00632 extract(const_iterator __pos) 00633 { 00634 __glibcxx_assert(__pos != end()); 00635 return _M_t.extract(__pos); 00636 } 00637 00638 /// Extract a node. 00639 node_type 00640 extract(const key_type& __x) 00641 { return _M_t.extract(__x); } 00642 00643 /// Re-insert an extracted node. 00644 iterator 00645 insert(node_type&& __nh) 00646 { return _M_t._M_reinsert_node_equal(std::move(__nh)); } 00647 00648 /// Re-insert an extracted node. 00649 iterator 00650 insert(const_iterator __hint, node_type&& __nh) 00651 { return _M_t._M_reinsert_node_hint_equal(__hint, std::move(__nh)); } 00652 00653 template<typename, typename> 00654 friend class std::_Rb_tree_merge_helper; 00655 00656 template<typename _C2> 00657 void 00658 merge(multimap<_Key, _Tp, _C2, _Alloc>& __source) 00659 { 00660 using _Merge_helper = _Rb_tree_merge_helper<multimap, _C2>; 00661 _M_t._M_merge_equal(_Merge_helper::_S_get_tree(__source)); 00662 } 00663 00664 template<typename _C2> 00665 void 00666 merge(multimap<_Key, _Tp, _C2, _Alloc>&& __source) 00667 { merge(__source); } 00668 00669 template<typename _C2> 00670 void 00671 merge(map<_Key, _Tp, _C2, _Alloc>& __source) 00672 { 00673 using _Merge_helper = _Rb_tree_merge_helper<multimap, _C2>; 00674 _M_t._M_merge_equal(_Merge_helper::_S_get_tree(__source)); 00675 } 00676 00677 template<typename _C2> 00678 void 00679 merge(map<_Key, _Tp, _C2, _Alloc>&& __source) 00680 { merge(__source); } 00681 #endif // C++17 00682 00683 #if __cplusplus >= 201103L 00684 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00685 // DR 130. Associative erase should return an iterator. 00686 /** 00687 * @brief Erases an element from a %multimap. 00688 * @param __position An iterator pointing to the element to be erased. 00689 * @return An iterator pointing to the element immediately following 00690 * @a position prior to the element being erased. If no such 00691 * element exists, end() is returned. 00692 * 00693 * This function erases an element, pointed to by the given iterator, 00694 * from a %multimap. Note that this function only erases the element, 00695 * and that if the element is itself a pointer, the pointed-to memory is 00696 * not touched in any way. Managing the pointer is the user's 00697 * responsibility. 00698 * 00699 * @{ 00700 */ 00701 iterator 00702 erase(const_iterator __position) 00703 { return _M_t.erase(__position); } 00704 00705 // LWG 2059. 00706 _GLIBCXX_ABI_TAG_CXX11 00707 iterator 00708 erase(iterator __position) 00709 { return _M_t.erase(__position); } 00710 // @} 00711 #else 00712 /** 00713 * @brief Erases an element from a %multimap. 00714 * @param __position An iterator pointing to the element to be erased. 00715 * 00716 * This function erases an element, pointed to by the given iterator, 00717 * from a %multimap. Note that this function only erases the element, 00718 * and that if the element is itself a pointer, the pointed-to memory is 00719 * not touched in any way. Managing the pointer is the user's 00720 * responsibility. 00721 */ 00722 void 00723 erase(iterator __position) 00724 { _M_t.erase(__position); } 00725 #endif 00726 00727 /** 00728 * @brief Erases elements according to the provided key. 00729 * @param __x Key of element to be erased. 00730 * @return The number of elements erased. 00731 * 00732 * This function erases all elements located by the given key from a 00733 * %multimap. 00734 * Note that this function only erases the element, and that if 00735 * the element is itself a pointer, the pointed-to memory is not touched 00736 * in any way. Managing the pointer is the user's responsibility. 00737 */ 00738 size_type 00739 erase(const key_type& __x) 00740 { return _M_t.erase(__x); } 00741 00742 #if __cplusplus >= 201103L 00743 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00744 // DR 130. Associative erase should return an iterator. 00745 /** 00746 * @brief Erases a [first,last) range of elements from a %multimap. 00747 * @param __first Iterator pointing to the start of the range to be 00748 * erased. 00749 * @param __last Iterator pointing to the end of the range to be 00750 * erased . 00751 * @return The iterator @a __last. 00752 * 00753 * This function erases a sequence of elements from a %multimap. 00754 * Note that this function only erases the elements, and that if 00755 * the elements themselves are pointers, the pointed-to memory is not 00756 * touched in any way. Managing the pointer is the user's 00757 * responsibility. 00758 */ 00759 iterator 00760 erase(const_iterator __first, const_iterator __last) 00761 { return _M_t.erase(__first, __last); } 00762 #else 00763 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00764 // DR 130. Associative erase should return an iterator. 00765 /** 00766 * @brief Erases a [first,last) range of elements from a %multimap. 00767 * @param __first Iterator pointing to the start of the range to be 00768 * erased. 00769 * @param __last Iterator pointing to the end of the range to 00770 * be erased. 00771 * 00772 * This function erases a sequence of elements from a %multimap. 00773 * Note that this function only erases the elements, and that if 00774 * the elements themselves are pointers, the pointed-to memory is not 00775 * touched in any way. Managing the pointer is the user's 00776 * responsibility. 00777 */ 00778 void 00779 erase(iterator __first, iterator __last) 00780 { _M_t.erase(__first, __last); } 00781 #endif 00782 00783 /** 00784 * @brief Swaps data with another %multimap. 00785 * @param __x A %multimap of the same element and allocator types. 00786 * 00787 * This exchanges the elements between two multimaps in constant time. 00788 * (It is only swapping a pointer, an integer, and an instance of 00789 * the @c Compare type (which itself is often stateless and empty), so it 00790 * should be quite fast.) 00791 * Note that the global std::swap() function is specialized such that 00792 * std::swap(m1,m2) will feed to this function. 00793 * 00794 * Whether the allocators are swapped depends on the allocator traits. 00795 */ 00796 void 00797 swap(multimap& __x) 00798 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value) 00799 { _M_t.swap(__x._M_t); } 00800 00801 /** 00802 * Erases all elements in a %multimap. Note that this function only 00803 * erases the elements, and that if the elements themselves are pointers, 00804 * the pointed-to memory is not touched in any way. Managing the pointer 00805 * is the user's responsibility. 00806 */ 00807 void 00808 clear() _GLIBCXX_NOEXCEPT 00809 { _M_t.clear(); } 00810 00811 // observers 00812 /** 00813 * Returns the key comparison object out of which the %multimap 00814 * was constructed. 00815 */ 00816 key_compare 00817 key_comp() const 00818 { return _M_t.key_comp(); } 00819 00820 /** 00821 * Returns a value comparison object, built from the key comparison 00822 * object out of which the %multimap was constructed. 00823 */ 00824 value_compare 00825 value_comp() const 00826 { return value_compare(_M_t.key_comp()); } 00827 00828 // multimap operations 00829 00830 //@{ 00831 /** 00832 * @brief Tries to locate an element in a %multimap. 00833 * @param __x Key of (key, value) pair to be located. 00834 * @return Iterator pointing to sought-after element, 00835 * or end() if not found. 00836 * 00837 * This function takes a key and tries to locate the element with which 00838 * the key matches. If successful the function returns an iterator 00839 * pointing to the sought after %pair. If unsuccessful it returns the 00840 * past-the-end ( @c end() ) iterator. 00841 */ 00842 iterator 00843 find(const key_type& __x) 00844 { return _M_t.find(__x); } 00845 00846 #if __cplusplus > 201103L 00847 template<typename _Kt> 00848 auto 00849 find(const _Kt& __x) -> decltype(_M_t._M_find_tr(__x)) 00850 { return _M_t._M_find_tr(__x); } 00851 #endif 00852 //@} 00853 00854 //@{ 00855 /** 00856 * @brief Tries to locate an element in a %multimap. 00857 * @param __x Key of (key, value) pair to be located. 00858 * @return Read-only (constant) iterator pointing to sought-after 00859 * element, or end() if not found. 00860 * 00861 * This function takes a key and tries to locate the element with which 00862 * the key matches. If successful the function returns a constant 00863 * iterator pointing to the sought after %pair. If unsuccessful it 00864 * returns the past-the-end ( @c end() ) iterator. 00865 */ 00866 const_iterator 00867 find(const key_type& __x) const 00868 { return _M_t.find(__x); } 00869 00870 #if __cplusplus > 201103L 00871 template<typename _Kt> 00872 auto 00873 find(const _Kt& __x) const -> decltype(_M_t._M_find_tr(__x)) 00874 { return _M_t._M_find_tr(__x); } 00875 #endif 00876 //@} 00877 00878 //@{ 00879 /** 00880 * @brief Finds the number of elements with given key. 00881 * @param __x Key of (key, value) pairs to be located. 00882 * @return Number of elements with specified key. 00883 */ 00884 size_type 00885 count(const key_type& __x) const 00886 { return _M_t.count(__x); } 00887 00888 #if __cplusplus > 201103L 00889 template<typename _Kt> 00890 auto 00891 count(const _Kt& __x) const -> decltype(_M_t._M_count_tr(__x)) 00892 { return _M_t._M_count_tr(__x); } 00893 #endif 00894 //@} 00895 00896 //@{ 00897 /** 00898 * @brief Finds the beginning of a subsequence matching given key. 00899 * @param __x Key of (key, value) pair to be located. 00900 * @return Iterator pointing to first element equal to or greater 00901 * than key, or end(). 00902 * 00903 * This function returns the first element of a subsequence of elements 00904 * that matches the given key. If unsuccessful it returns an iterator 00905 * pointing to the first element that has a greater value than given key 00906 * or end() if no such element exists. 00907 */ 00908 iterator 00909 lower_bound(const key_type& __x) 00910 { return _M_t.lower_bound(__x); } 00911 00912 #if __cplusplus > 201103L 00913 template<typename _Kt> 00914 auto 00915 lower_bound(const _Kt& __x) 00916 -> decltype(iterator(_M_t._M_lower_bound_tr(__x))) 00917 { return iterator(_M_t._M_lower_bound_tr(__x)); } 00918 #endif 00919 //@} 00920 00921 //@{ 00922 /** 00923 * @brief Finds the beginning of a subsequence matching given key. 00924 * @param __x Key of (key, value) pair to be located. 00925 * @return Read-only (constant) iterator pointing to first element 00926 * equal to or greater than key, or end(). 00927 * 00928 * This function returns the first element of a subsequence of 00929 * elements that matches the given key. If unsuccessful the 00930 * iterator will point to the next greatest element or, if no 00931 * such greater element exists, to end(). 00932 */ 00933 const_iterator 00934 lower_bound(const key_type& __x) const 00935 { return _M_t.lower_bound(__x); } 00936 00937 #if __cplusplus > 201103L 00938 template<typename _Kt> 00939 auto 00940 lower_bound(const _Kt& __x) const 00941 -> decltype(const_iterator(_M_t._M_lower_bound_tr(__x))) 00942 { return const_iterator(_M_t._M_lower_bound_tr(__x)); } 00943 #endif 00944 //@} 00945 00946 //@{ 00947 /** 00948 * @brief Finds the end of a subsequence matching given key. 00949 * @param __x Key of (key, value) pair to be located. 00950 * @return Iterator pointing to the first element 00951 * greater than key, or end(). 00952 */ 00953 iterator 00954 upper_bound(const key_type& __x) 00955 { return _M_t.upper_bound(__x); } 00956 00957 #if __cplusplus > 201103L 00958 template<typename _Kt> 00959 auto 00960 upper_bound(const _Kt& __x) 00961 -> decltype(iterator(_M_t._M_upper_bound_tr(__x))) 00962 { return iterator(_M_t._M_upper_bound_tr(__x)); } 00963 #endif 00964 //@} 00965 00966 //@{ 00967 /** 00968 * @brief Finds the end of a subsequence matching given key. 00969 * @param __x Key of (key, value) pair to be located. 00970 * @return Read-only (constant) iterator pointing to first iterator 00971 * greater than key, or end(). 00972 */ 00973 const_iterator 00974 upper_bound(const key_type& __x) const 00975 { return _M_t.upper_bound(__x); } 00976 00977 #if __cplusplus > 201103L 00978 template<typename _Kt> 00979 auto 00980 upper_bound(const _Kt& __x) const 00981 -> decltype(const_iterator(_M_t._M_upper_bound_tr(__x))) 00982 { return const_iterator(_M_t._M_upper_bound_tr(__x)); } 00983 #endif 00984 //@} 00985 00986 //@{ 00987 /** 00988 * @brief Finds a subsequence matching given key. 00989 * @param __x Key of (key, value) pairs to be located. 00990 * @return Pair of iterators that possibly points to the subsequence 00991 * matching given key. 00992 * 00993 * This function is equivalent to 00994 * @code 00995 * std::make_pair(c.lower_bound(val), 00996 * c.upper_bound(val)) 00997 * @endcode 00998 * (but is faster than making the calls separately). 00999 */ 01000 std::pair<iterator, iterator> 01001 equal_range(const key_type& __x) 01002 { return _M_t.equal_range(__x); } 01003 01004 #if __cplusplus > 201103L 01005 template<typename _Kt> 01006 auto 01007 equal_range(const _Kt& __x) 01008 -> decltype(pair<iterator, iterator>(_M_t._M_equal_range_tr(__x))) 01009 { return pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)); } 01010 #endif 01011 //@} 01012 01013 //@{ 01014 /** 01015 * @brief Finds a subsequence matching given key. 01016 * @param __x Key of (key, value) pairs to be located. 01017 * @return Pair of read-only (constant) iterators that possibly points 01018 * to the subsequence matching given key. 01019 * 01020 * This function is equivalent to 01021 * @code 01022 * std::make_pair(c.lower_bound(val), 01023 * c.upper_bound(val)) 01024 * @endcode 01025 * (but is faster than making the calls separately). 01026 */ 01027 std::pair<const_iterator, const_iterator> 01028 equal_range(const key_type& __x) const 01029 { return _M_t.equal_range(__x); } 01030 01031 #if __cplusplus > 201103L 01032 template<typename _Kt> 01033 auto 01034 equal_range(const _Kt& __x) const 01035 -> decltype(pair<const_iterator, const_iterator>( 01036 _M_t._M_equal_range_tr(__x))) 01037 { 01038 return pair<const_iterator, const_iterator>( 01039 _M_t._M_equal_range_tr(__x)); 01040 } 01041 #endif 01042 //@} 01043 01044 template<typename _K1, typename _T1, typename _C1, typename _A1> 01045 friend bool 01046 operator==(const multimap<_K1, _T1, _C1, _A1>&, 01047 const multimap<_K1, _T1, _C1, _A1>&); 01048 01049 template<typename _K1, typename _T1, typename _C1, typename _A1> 01050 friend bool 01051 operator<(const multimap<_K1, _T1, _C1, _A1>&, 01052 const multimap<_K1, _T1, _C1, _A1>&); 01053 }; 01054 01055 #if __cpp_deduction_guides >= 201606 01056 01057 template<typename _InputIterator, 01058 typename _Compare = less<__iter_key_t<_InputIterator>>, 01059 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>, 01060 typename = _RequireInputIter<_InputIterator>, 01061 typename = _RequireAllocator<_Allocator>> 01062 multimap(_InputIterator, _InputIterator, 01063 _Compare = _Compare(), _Allocator = _Allocator()) 01064 -> multimap<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, 01065 _Compare, _Allocator>; 01066 01067 template<typename _Key, typename _Tp, typename _Compare = less<_Key>, 01068 typename _Allocator = allocator<pair<const _Key, _Tp>>, 01069 typename = _RequireAllocator<_Allocator>> 01070 multimap(initializer_list<pair<_Key, _Tp>>, 01071 _Compare = _Compare(), _Allocator = _Allocator()) 01072 -> multimap<_Key, _Tp, _Compare, _Allocator>; 01073 01074 template<typename _InputIterator, typename _Allocator, 01075 typename = _RequireInputIter<_InputIterator>, 01076 typename = _RequireAllocator<_Allocator>> 01077 multimap(_InputIterator, _InputIterator, _Allocator) 01078 -> multimap<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, 01079 less<__iter_key_t<_InputIterator>>, _Allocator>; 01080 01081 template<typename _Key, typename _Tp, typename _Allocator, 01082 typename = _RequireAllocator<_Allocator>> 01083 multimap(initializer_list<pair<_Key, _Tp>>, _Allocator) 01084 -> multimap<_Key, _Tp, less<_Key>, _Allocator>; 01085 01086 #endif 01087 01088 /** 01089 * @brief Multimap equality comparison. 01090 * @param __x A %multimap. 01091 * @param __y A %multimap of the same type as @a __x. 01092 * @return True iff the size and elements of the maps are equal. 01093 * 01094 * This is an equivalence relation. It is linear in the size of the 01095 * multimaps. Multimaps are considered equivalent if their sizes are equal, 01096 * and if corresponding elements compare equal. 01097 */ 01098 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 01099 inline bool 01100 operator==(const multimap<_Key, _Tp, _Compare, _Alloc>& __x, 01101 const multimap<_Key, _Tp, _Compare, _Alloc>& __y) 01102 { return __x._M_t == __y._M_t; } 01103 01104 /** 01105 * @brief Multimap ordering relation. 01106 * @param __x A %multimap. 01107 * @param __y A %multimap of the same type as @a __x. 01108 * @return True iff @a x is lexicographically less than @a y. 01109 * 01110 * This is a total ordering relation. It is linear in the size of the 01111 * multimaps. The elements must be comparable with @c <. 01112 * 01113 * See std::lexicographical_compare() for how the determination is made. 01114 */ 01115 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 01116 inline bool 01117 operator<(const multimap<_Key, _Tp, _Compare, _Alloc>& __x, 01118 const multimap<_Key, _Tp, _Compare, _Alloc>& __y) 01119 { return __x._M_t < __y._M_t; } 01120 01121 /// Based on operator== 01122 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 01123 inline bool 01124 operator!=(const multimap<_Key, _Tp, _Compare, _Alloc>& __x, 01125 const multimap<_Key, _Tp, _Compare, _Alloc>& __y) 01126 { return !(__x == __y); } 01127 01128 /// Based on operator< 01129 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 01130 inline bool 01131 operator>(const multimap<_Key, _Tp, _Compare, _Alloc>& __x, 01132 const multimap<_Key, _Tp, _Compare, _Alloc>& __y) 01133 { return __y < __x; } 01134 01135 /// Based on operator< 01136 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 01137 inline bool 01138 operator<=(const multimap<_Key, _Tp, _Compare, _Alloc>& __x, 01139 const multimap<_Key, _Tp, _Compare, _Alloc>& __y) 01140 { return !(__y < __x); } 01141 01142 /// Based on operator< 01143 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 01144 inline bool 01145 operator>=(const multimap<_Key, _Tp, _Compare, _Alloc>& __x, 01146 const multimap<_Key, _Tp, _Compare, _Alloc>& __y) 01147 { return !(__x < __y); } 01148 01149 /// See std::multimap::swap(). 01150 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> 01151 inline void 01152 swap(multimap<_Key, _Tp, _Compare, _Alloc>& __x, 01153 multimap<_Key, _Tp, _Compare, _Alloc>& __y) 01154 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y))) 01155 { __x.swap(__y); } 01156 01157 _GLIBCXX_END_NAMESPACE_CONTAINER 01158 01159 #if __cplusplus > 201402L 01160 // Allow std::multimap access to internals of compatible maps. 01161 template<typename _Key, typename _Val, typename _Cmp1, typename _Alloc, 01162 typename _Cmp2> 01163 struct 01164 _Rb_tree_merge_helper<_GLIBCXX_STD_C::multimap<_Key, _Val, _Cmp1, _Alloc>, 01165 _Cmp2> 01166 { 01167 private: 01168 friend class _GLIBCXX_STD_C::multimap<_Key, _Val, _Cmp1, _Alloc>; 01169 01170 static auto& 01171 _S_get_tree(_GLIBCXX_STD_C::map<_Key, _Val, _Cmp2, _Alloc>& __map) 01172 { return __map._M_t; } 01173 01174 static auto& 01175 _S_get_tree(_GLIBCXX_STD_C::multimap<_Key, _Val, _Cmp2, _Alloc>& __map) 01176 { return __map._M_t; } 01177 }; 01178 #endif // C++17 01179 01180 _GLIBCXX_END_NAMESPACE_VERSION 01181 } // namespace std 01182 01183 #endif /* _STL_MULTIMAP_H */