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