1// Map implementation -*- C++ -*-
2
3// Copyright (C) 2001-2017 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library. This library is free
6// software; you can redistribute it and/or modify it under the
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 3, or (at your option)
9// any later version.
10
11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14// GNU General Public License for more details.
15
16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23// <http://www.gnu.org/licenses/>.
24
25/*
26 *
27 * Copyright (c) 1994
28 * Hewlett-Packard Company
29 *
30 * Permission to use, copy, modify, distribute and sell this software
31 * and its documentation for any purpose is hereby granted without fee,
32 * provided that the above copyright notice appear in all copies and
33 * that both that copyright notice and this permission notice appear
34 * in supporting documentation. Hewlett-Packard Company makes no
35 * representations about the suitability of this software for any
36 * purpose. It is provided "as is" without express or implied warranty.
37 *
38 *
39 * Copyright (c) 1996,1997
40 * Silicon Graphics Computer Systems, Inc.
41 *
42 * Permission to use, copy, modify, distribute and sell this software
43 * and its documentation for any purpose is hereby granted without fee,
44 * provided that the above copyright notice appear in all copies and
45 * that both that copyright notice and this permission notice appear
46 * in supporting documentation. Silicon Graphics makes no
47 * representations about the suitability of this software for any
48 * purpose. It is provided "as is" without express or implied warranty.
49 */
50
51/** @file bits/stl_map.h
52 * This is an internal header file, included by other library headers.
53 * Do not attempt to use it directly. @headername{map}
54 */
55
56#ifndef _STL_MAP_H
57#define _STL_MAP_H 1
58
59#include <bits/functexcept.h>
60#include <bits/concept_check.h>
61#if __cplusplus >= 201103L
62#include <initializer_list>
63#include <tuple>
64#endif
65
66namespace std _GLIBCXX_VISIBILITY(default)
67{
68_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
69
70 template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
71 class multimap;
72
73 /**
74 * @brief A standard container made up of (key,value) pairs, which can be
75 * retrieved based on a key, in logarithmic time.
76 *
77 * @ingroup associative_containers
78 *
79 * @tparam _Key Type of key objects.
80 * @tparam _Tp Type of mapped objects.
81 * @tparam _Compare Comparison function object type, defaults to less<_Key>.
82 * @tparam _Alloc Allocator type, defaults to
83 * allocator<pair<const _Key, _Tp>.
84 *
85 * Meets the requirements of a <a href="tables.html#65">container</a>, a
86 * <a href="tables.html#66">reversible container</a>, and an
87 * <a href="tables.html#69">associative container</a> (using unique keys).
88 * For a @c map<Key,T> the key_type is Key, the mapped_type is T, and the
89 * value_type is std::pair<const Key,T>.
90 *
91 * Maps support bidirectional iterators.
92 *
93 * The private tree data is declared exactly the same way for map and
94 * multimap; the distinction is made entirely in how the tree functions are
95 * called (*_unique versus *_equal, same as the standard).
96 */
97 template <typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
98 typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
99 class map
100 {
101 public:
102 typedef _Key key_type;
103 typedef _Tp mapped_type;
104 typedef std::pair<const _Key, _Tp> value_type;
105 typedef _Compare key_compare;
106 typedef _Alloc allocator_type;
107
108 private:
109#ifdef _GLIBCXX_CONCEPT_CHECKS
110 // concept requirements
111 typedef typename _Alloc::value_type _Alloc_value_type;
112# if __cplusplus < 201103L
113 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
114# endif
115 __glibcxx_class_requires4(_Compare, bool, _Key, _Key,
116 _BinaryFunctionConcept)
117 __glibcxx_class_requires2(value_type, _Alloc_value_type, _SameTypeConcept)
118#endif
119
120 public:
121 class value_compare
122 : public std::binary_function<value_type, value_type, bool>
123 {
124 friend class map<_Key, _Tp, _Compare, _Alloc>;
125 protected:
126 _Compare comp;
127
128 value_compare(_Compare __c)
129 : comp(__c) { }
130
131 public:
132 bool operator()(const value_type& __x, const value_type& __y) const
133 { return comp(__x.first, __y.first); }
134 };
135
136 private:
137 /// This turns a red-black tree into a [multi]map.
138 typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
139 rebind<value_type>::other _Pair_alloc_type;
140
141 typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,
142 key_compare, _Pair_alloc_type> _Rep_type;
143
144 /// The actual tree structure.
145 _Rep_type _M_t;
146
147 typedef __gnu_cxx::__alloc_traits<_Pair_alloc_type> _Alloc_traits;
148
149 public:
150 // many of these are specified differently in ISO, but the following are
151 // "functionally equivalent"
152 typedef typename _Alloc_traits::pointer pointer;
153 typedef typename _Alloc_traits::const_pointer const_pointer;
154 typedef typename _Alloc_traits::reference reference;
155 typedef typename _Alloc_traits::const_reference const_reference;
156 typedef typename _Rep_type::iterator iterator;
157 typedef typename _Rep_type::const_iterator const_iterator;
158 typedef typename _Rep_type::size_type size_type;
159 typedef typename _Rep_type::difference_type difference_type;
160 typedef typename _Rep_type::reverse_iterator reverse_iterator;
161 typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
162
163#if __cplusplus > 201402L
164 using node_type = typename _Rep_type::node_type;
165 using insert_return_type = typename _Rep_type::insert_return_type;
166#endif
167
168 // [23.3.1.1] construct/copy/destroy
169 // (get_allocator() is also listed in this section)
170
171 /**
172 * @brief Default constructor creates no elements.
173 */
174#if __cplusplus < 201103L
175 map() : _M_t() { }
176#else
177 map() = default;
178#endif
179
180 /**
181 * @brief Creates a %map with no elements.
182 * @param __comp A comparison object.
183 * @param __a An allocator object.
184 */
185 explicit
186 map(const _Compare& __comp,
187 const allocator_type& __a = allocator_type())
188 : _M_t(__comp, _Pair_alloc_type(__a)) { }
189
190 /**
191 * @brief %Map copy constructor.
192 *
193 * Whether the allocator is copied depends on the allocator traits.
194 */
195#if __cplusplus < 201103L
196 map(const map& __x)
197 : _M_t(__x._M_t) { }
198#else
199 map(const map&) = default;
200
201 /**
202 * @brief %Map move constructor.
203 *
204 * The newly-created %map contains the exact contents of the moved
205 * instance. The moved instance is a valid, but unspecified, %map.
206 */
207 map(map&&) = default;
208
209 /**
210 * @brief Builds a %map from an initializer_list.
211 * @param __l An initializer_list.
212 * @param __comp A comparison object.
213 * @param __a An allocator object.
214 *
215 * Create a %map consisting of copies of the elements in the
216 * initializer_list @a __l.
217 * This is linear in N if the range is already sorted, and NlogN
218 * otherwise (where N is @a __l.size()).
219 */
220 map(initializer_list<value_type> __l,
221 const _Compare& __comp = _Compare(),
222 const allocator_type& __a = allocator_type())
223 : _M_t(__comp, _Pair_alloc_type(__a))
224 { _M_t._M_insert_unique(__l.begin(), __l.end()); }
225
226 /// Allocator-extended default constructor.
227 explicit
228 map(const allocator_type& __a)
229 : _M_t(_Compare(), _Pair_alloc_type(__a)) { }
230
231 /// Allocator-extended copy constructor.
232 map(const map& __m, const allocator_type& __a)
233 : _M_t(__m._M_t, _Pair_alloc_type(__a)) { }
234
235 /// Allocator-extended move constructor.
236 map(map&& __m, const allocator_type& __a)
237 noexcept(is_nothrow_copy_constructible<_Compare>::value
238 && _Alloc_traits::_S_always_equal())
239 : _M_t(std::move(__m._M_t), _Pair_alloc_type(__a)) { }
240
241 /// Allocator-extended initialier-list constructor.
242 map(initializer_list<value_type> __l, const allocator_type& __a)
243 : _M_t(_Compare(), _Pair_alloc_type(__a))
244 { _M_t._M_insert_unique(__l.begin(), __l.end()); }
245
246 /// Allocator-extended range constructor.
247 template<typename _InputIterator>
248 map(_InputIterator __first, _InputIterator __last,
249 const allocator_type& __a)
250 : _M_t(_Compare(), _Pair_alloc_type(__a))
251 { _M_t._M_insert_unique(__first, __last); }
252#endif
253
254 /**
255 * @brief Builds a %map from a range.
256 * @param __first An input iterator.
257 * @param __last An input iterator.
258 *
259 * Create a %map consisting of copies of the elements from
260 * [__first,__last). This is linear in N if the range is
261 * already sorted, and NlogN otherwise (where N is
262 * distance(__first,__last)).
263 */
264 template<typename _InputIterator>
265 map(_InputIterator __first, _InputIterator __last)
266 : _M_t()
267 { _M_t._M_insert_unique(__first, __last); }
268
269 /**
270 * @brief Builds a %map from a range.
271 * @param __first An input iterator.
272 * @param __last An input iterator.
273 * @param __comp A comparison functor.
274 * @param __a An allocator object.
275 *
276 * Create a %map consisting of copies of the elements from
277 * [__first,__last). This is linear in N if the range is
278 * already sorted, and NlogN otherwise (where N is
279 * distance(__first,__last)).
280 */
281 template<typename _InputIterator>
282 map(_InputIterator __first, _InputIterator __last,
283 const _Compare& __comp,
284 const allocator_type& __a = allocator_type())
285 : _M_t(__comp, _Pair_alloc_type(__a))
286 { _M_t._M_insert_unique(__first, __last); }
287
288#if __cplusplus >= 201103L
289 /**
290 * The dtor only erases the elements, and note that if the elements
291 * themselves are pointers, the pointed-to memory is not touched in any
292 * way. Managing the pointer is the user's responsibility.
293 */
294 ~map() = default;
295#endif
296
297 /**
298 * @brief %Map assignment operator.
299 *
300 * Whether the allocator is copied depends on the allocator traits.
301 */
302#if __cplusplus < 201103L
303 map&
304 operator=(const map& __x)
305 {
306 _M_t = __x._M_t;
307 return *this;
308 }
309#else
310 map&
311 operator=(const map&) = default;
312
313 /// Move assignment operator.
314 map&
315 operator=(map&&) = default;
316
317 /**
318 * @brief %Map list assignment operator.
319 * @param __l An initializer_list.
320 *
321 * This function fills a %map with copies of the elements in the
322 * initializer list @a __l.
323 *
324 * Note that the assignment completely changes the %map and
325 * that the resulting %map's size is the same as the number
326 * of elements assigned.
327 */
328 map&
329 operator=(initializer_list<value_type> __l)
330 {
331 _M_t._M_assign_unique(__l.begin(), __l.end());
332 return *this;
333 }
334#endif
335
336 /// Get a copy of the memory allocation object.
337 allocator_type
338 get_allocator() const _GLIBCXX_NOEXCEPT
339 { return allocator_type(_M_t.get_allocator()); }
340
341 // iterators
342 /**
343 * Returns a read/write iterator that points to the first pair in the
344 * %map.
345 * Iteration is done in ascending order according to the keys.
346 */
347 iterator
348 begin() _GLIBCXX_NOEXCEPT
349 { return _M_t.begin(); }
350
351 /**
352 * Returns a read-only (constant) iterator that points to the first pair
353 * in the %map. Iteration is done in ascending order according to the
354 * keys.
355 */
356 const_iterator
357 begin() const _GLIBCXX_NOEXCEPT
358 { return _M_t.begin(); }
359
360 /**
361 * Returns a read/write iterator that points one past the last
362 * pair in the %map. Iteration is done in ascending order
363 * according to the keys.
364 */
365 iterator
366 end() _GLIBCXX_NOEXCEPT
367 { return _M_t.end(); }
368
369 /**
370 * Returns a read-only (constant) iterator that points one past the last
371 * pair in the %map. Iteration is done in ascending order according to
372 * the keys.
373 */
374 const_iterator
375 end() const _GLIBCXX_NOEXCEPT
376 { return _M_t.end(); }
377
378 /**
379 * Returns a read/write reverse iterator that points to the last pair in
380 * the %map. Iteration is done in descending order according to the
381 * keys.
382 */
383 reverse_iterator
384 rbegin() _GLIBCXX_NOEXCEPT
385 { return _M_t.rbegin(); }
386
387 /**
388 * Returns a read-only (constant) reverse iterator that points to the
389 * last pair in the %map. Iteration is done in descending order
390 * according to the keys.
391 */
392 const_reverse_iterator
393 rbegin() const _GLIBCXX_NOEXCEPT
394 { return _M_t.rbegin(); }
395
396 /**
397 * Returns a read/write reverse iterator that points to one before the
398 * first pair in the %map. Iteration is done in descending order
399 * according to the keys.
400 */
401 reverse_iterator
402 rend() _GLIBCXX_NOEXCEPT
403 { return _M_t.rend(); }
404
405 /**
406 * Returns a read-only (constant) reverse iterator that points to one
407 * before the first pair in the %map. Iteration is done in descending
408 * order according to the keys.
409 */
410 const_reverse_iterator
411 rend() const _GLIBCXX_NOEXCEPT
412 { return _M_t.rend(); }
413
414#if __cplusplus >= 201103L
415 /**
416 * Returns a read-only (constant) iterator that points to the first pair
417 * in the %map. Iteration is done in ascending order according to the
418 * keys.
419 */
420 const_iterator
421 cbegin() const noexcept
422 { return _M_t.begin(); }
423
424 /**
425 * Returns a read-only (constant) iterator that points one past the last
426 * pair in the %map. Iteration is done in ascending order according to
427 * the keys.
428 */
429 const_iterator
430 cend() const noexcept
431 { return _M_t.end(); }
432
433 /**
434 * Returns a read-only (constant) reverse iterator that points to the
435 * last pair in the %map. Iteration is done in descending order
436 * according to the keys.
437 */
438 const_reverse_iterator
439 crbegin() const noexcept
440 { return _M_t.rbegin(); }
441
442 /**
443 * Returns a read-only (constant) reverse iterator that points to one
444 * before the first pair in the %map. Iteration is done in descending
445 * order according to the keys.
446 */
447 const_reverse_iterator
448 crend() const noexcept
449 { return _M_t.rend(); }
450#endif
451
452 // capacity
453 /** Returns true if the %map is empty. (Thus begin() would equal
454 * end().)
455 */
456 bool
457 empty() const _GLIBCXX_NOEXCEPT
458 { return _M_t.empty(); }
459
460 /** Returns the size of the %map. */
461 size_type
462 size() const _GLIBCXX_NOEXCEPT
463 { return _M_t.size(); }
464
465 /** Returns the maximum size of the %map. */
466 size_type
467 max_size() const _GLIBCXX_NOEXCEPT
468 { return _M_t.max_size(); }
469
470 // [23.3.1.2] element access
471 /**
472 * @brief Subscript ( @c [] ) access to %map data.
473 * @param __k The key for which data should be retrieved.
474 * @return A reference to the data of the (key,data) %pair.
475 *
476 * Allows for easy lookup with the subscript ( @c [] )
477 * operator. Returns data associated with the key specified in
478 * subscript. If the key does not exist, a pair with that key
479 * is created using default values, which is then returned.
480 *
481 * Lookup requires logarithmic time.
482 */
483 mapped_type&
484 operator[](const key_type& __k)
485 {
486 // concept requirements
487 __glibcxx_function_requires(_DefaultConstructibleConcept<mapped_type>)
488
489 iterator __i = lower_bound(__k);
490 // __i->first is greater than or equivalent to __k.
491 if (__i == end() || key_comp()(__k, (*__i).first))
492#if __cplusplus >= 201103L
493 __i = _M_t._M_emplace_hint_unique(__i, std::piecewise_construct,
494 std::tuple<const key_type&>(__k),
495 std::tuple<>());
496#else
497 __i = insert(__i, value_type(__k, mapped_type()));
498#endif
499 return (*__i).second;
500 }
501
502#if __cplusplus >= 201103L
503 mapped_type&
504 operator[](key_type&& __k)
505 {
506 // concept requirements
507 __glibcxx_function_requires(_DefaultConstructibleConcept<mapped_type>)
508
509 iterator __i = lower_bound(__k);
510 // __i->first is greater than or equivalent to __k.
511 if (__i == end() || key_comp()(__k, (*__i).first))
512 __i = _M_t._M_emplace_hint_unique(__i, std::piecewise_construct,
513 std::forward_as_tuple(std::move(__k)),
514 std::tuple<>());
515 return (*__i).second;
516 }
517#endif
518
519 // _GLIBCXX_RESOLVE_LIB_DEFECTS
520 // DR 464. Suggestion for new member functions in standard containers.
521 /**
522 * @brief Access to %map data.
523 * @param __k The key for which data should be retrieved.
524 * @return A reference to the data whose key is equivalent to @a __k, if
525 * such a data is present in the %map.
526 * @throw std::out_of_range If no such data is present.
527 */
528 mapped_type&
529 at(const key_type& __k)
530 {
531 iterator __i = lower_bound(__k);
532 if (__i == end() || key_comp()(__k, (*__i).first))
533 __throw_out_of_range(__N("map::at"));
534 return (*__i).second;
535 }
536
537 const mapped_type&
538 at(const key_type& __k) const
539 {
540 const_iterator __i = lower_bound(__k);
541 if (__i == end() || key_comp()(__k, (*__i).first))
542 __throw_out_of_range(__N("map::at"));
543 return (*__i).second;
544 }
545
546 // modifiers
547#if __cplusplus >= 201103L
548 /**
549 * @brief Attempts to build and insert a std::pair into the %map.
550 *
551 * @param __args Arguments used to generate a new pair instance (see
552 * std::piecewise_contruct for passing arguments to each
553 * part of the pair constructor).
554 *
555 * @return A pair, of which the first element is an iterator that points
556 * to the possibly inserted pair, and the second is a bool that
557 * is true if the pair was actually inserted.
558 *
559 * This function attempts to build and insert a (key, value) %pair into
560 * the %map.
561 * A %map relies on unique keys and thus a %pair is only inserted if its
562 * first element (the key) is not already present in the %map.
563 *
564 * Insertion requires logarithmic time.
565 */
566 template<typename... _Args>
567 std::pair<iterator, bool>
568 emplace(_Args&&... __args)
569 { return _M_t._M_emplace_unique(std::forward<_Args>(__args)...); }
570
571 /**
572 * @brief Attempts to build and insert a std::pair into the %map.
573 *
574 * @param __pos An iterator that serves as a hint as to where the pair
575 * should be inserted.
576 * @param __args Arguments used to generate a new pair instance (see
577 * std::piecewise_contruct for passing arguments to each
578 * part of the pair constructor).
579 * @return An iterator that points to the element with key of the
580 * std::pair built from @a __args (may or may not be that
581 * std::pair).
582 *
583 * This function is not concerned about whether the insertion took place,
584 * and thus does not return a boolean like the single-argument emplace()
585 * does.
586 * Note that the first parameter is only a hint and can potentially
587 * improve the performance of the insertion process. A bad hint would
588 * cause no gains in efficiency.
589 *
590 * See
591 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
592 * for more on @a hinting.
593 *
594 * Insertion requires logarithmic time (if the hint is not taken).
595 */
596 template<typename... _Args>
597 iterator
598 emplace_hint(const_iterator __pos, _Args&&... __args)
599 {
600 return _M_t._M_emplace_hint_unique(__pos,
601 std::forward<_Args>(__args)...);
602 }
603#endif
604
605#if __cplusplus > 201402L
606 /// Extract a node.
607 node_type
608 extract(const_iterator __pos)
609 {
610 __glibcxx_assert(__pos != end());
611 return _M_t.extract(__pos);
612 }
613
614 /// Extract a node.
615 node_type
616 extract(const key_type& __x)
617 { return _M_t.extract(__x); }
618
619 /// Re-insert an extracted node.
620 insert_return_type
621 insert(node_type&& __nh)
622 { return _M_t._M_reinsert_node_unique(std::move(__nh)); }
623
624 /// Re-insert an extracted node.
625 iterator
626 insert(const_iterator __hint, node_type&& __nh)
627 { return _M_t._M_reinsert_node_hint_unique(__hint, std::move(__nh)); }
628
629 template<typename, typename>
630 friend class _Rb_tree_merge_helper;
631
632 template<typename _C2>
633 void
634 merge(map<_Key, _Tp, _C2, _Alloc>& __source)
635 {
636 using _Merge_helper = _Rb_tree_merge_helper<map, _C2>;
637 _M_t._M_merge_unique(_Merge_helper::_S_get_tree(__source));
638 }
639
640 template<typename _C2>
641 void
642 merge(map<_Key, _Tp, _C2, _Alloc>&& __source)
643 { merge(__source); }
644
645 template<typename _C2>
646 void
647 merge(multimap<_Key, _Tp, _C2, _Alloc>& __source)
648 {
649 using _Merge_helper = _Rb_tree_merge_helper<map, _C2>;
650 _M_t._M_merge_unique(_Merge_helper::_S_get_tree(__source));
651 }
652
653 template<typename _C2>
654 void
655 merge(multimap<_Key, _Tp, _C2, _Alloc>&& __source)
656 { merge(__source); }
657#endif // C++17
658
659#if __cplusplus > 201402L
660#define __cpp_lib_map_try_emplace 201411
661 /**
662 * @brief Attempts to build and insert a std::pair into the %map.
663 *
664 * @param __k Key to use for finding a possibly existing pair in
665 * the map.
666 * @param __args Arguments used to generate the .second for a new pair
667 * instance.
668 *
669 * @return A pair, of which the first element is an iterator that points
670 * to the possibly inserted pair, and the second is a bool that
671 * is true if the pair was actually inserted.
672 *
673 * This function attempts to build and insert a (key, value) %pair into
674 * the %map.
675 * A %map relies on unique keys and thus a %pair is only inserted if its
676 * first element (the key) is not already present in the %map.
677 * If a %pair is not inserted, this function has no effect.
678 *
679 * Insertion requires logarithmic time.
680 */
681 template <typename... _Args>
682 pair<iterator, bool>
683 try_emplace(const key_type& __k, _Args&&... __args)
684 {
685 iterator __i = lower_bound(__k);
686 if (__i == end() || key_comp()(__k, (*__i).first))
687 {
688 __i = emplace_hint(__i, std::piecewise_construct,
689 std::forward_as_tuple(__k),
690 std::forward_as_tuple(
691 std::forward<_Args>(__args)...));
692 return {__i, true};
693 }
694 return {__i, false};
695 }
696
697 // move-capable overload
698 template <typename... _Args>
699 pair<iterator, bool>
700 try_emplace(key_type&& __k, _Args&&... __args)
701 {
702 iterator __i = lower_bound(__k);
703 if (__i == end() || key_comp()(__k, (*__i).first))
704 {
705 __i = emplace_hint(__i, std::piecewise_construct,
706 std::forward_as_tuple(std::move(__k)),
707 std::forward_as_tuple(
708 std::forward<_Args>(__args)...));
709 return {__i, true};
710 }
711 return {__i, false};
712 }
713
714 /**
715 * @brief Attempts to build and insert a std::pair into the %map.
716 *
717 * @param __hint An iterator that serves as a hint as to where the
718 * pair should be inserted.
719 * @param __k Key to use for finding a possibly existing pair in
720 * the map.
721 * @param __args Arguments used to generate the .second for a new pair
722 * instance.
723 * @return An iterator that points to the element with key of the
724 * std::pair built from @a __args (may or may not be that
725 * std::pair).
726 *
727 * This function is not concerned about whether the insertion took place,
728 * and thus does not return a boolean like the single-argument
729 * try_emplace() does. However, if insertion did not take place,
730 * this function has no effect.
731 * Note that the first parameter is only a hint and can potentially
732 * improve the performance of the insertion process. A bad hint would
733 * cause no gains in efficiency.
734 *
735 * See
736 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
737 * for more on @a hinting.
738 *
739 * Insertion requires logarithmic time (if the hint is not taken).
740 */
741 template <typename... _Args>
742 iterator
743 try_emplace(const_iterator __hint, const key_type& __k,
744 _Args&&... __args)
745 {
746 iterator __i;
747 auto __true_hint = _M_t._M_get_insert_hint_unique_pos(__hint, __k);
748 if (__true_hint.second)
749 __i = emplace_hint(iterator(__true_hint.second),
750 std::piecewise_construct,
751 std::forward_as_tuple(__k),
752 std::forward_as_tuple(
753 std::forward<_Args>(__args)...));
754 else
755 __i = iterator(__true_hint.first);
756 return __i;
757 }
758
759 // move-capable overload
760 template <typename... _Args>
761 iterator
762 try_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args)
763 {
764 iterator __i;
765 auto __true_hint = _M_t._M_get_insert_hint_unique_pos(__hint, __k);
766 if (__true_hint.second)
767 __i = emplace_hint(iterator(__true_hint.second),
768 std::piecewise_construct,
769 std::forward_as_tuple(std::move(__k)),
770 std::forward_as_tuple(
771 std::forward<_Args>(__args)...));
772 else
773 __i = iterator(__true_hint.first);
774 return __i;
775 }
776#endif
777
778 /**
779 * @brief Attempts to insert a std::pair into the %map.
780 * @param __x Pair to be inserted (see std::make_pair for easy
781 * creation of pairs).
782 *
783 * @return A pair, of which the first element is an iterator that
784 * points to the possibly inserted pair, and the second is
785 * a bool that is true if the pair was actually inserted.
786 *
787 * This function attempts to insert a (key, value) %pair into the %map.
788 * A %map relies on unique keys and thus a %pair is only inserted if its
789 * first element (the key) is not already present in the %map.
790 *
791 * Insertion requires logarithmic time.
792 * @{
793 */
794 std::pair<iterator, bool>
795 insert(const value_type& __x)
796 { return _M_t._M_insert_unique(__x); }
797
798#if __cplusplus >= 201103L
799 // _GLIBCXX_RESOLVE_LIB_DEFECTS
800 // 2354. Unnecessary copying when inserting into maps with braced-init
801 std::pair<iterator, bool>
802 insert(value_type&& __x)
803 { return _M_t._M_insert_unique(std::move(__x)); }
804
805 template<typename _Pair, typename = typename
806 std::enable_if<std::is_constructible<value_type,
807 _Pair&&>::value>::type>
808 std::pair<iterator, bool>
809 insert(_Pair&& __x)
810 { return _M_t._M_insert_unique(std::forward<_Pair>(__x)); }
811#endif
812 // @}
813
814#if __cplusplus >= 201103L
815 /**
816 * @brief Attempts to insert a list of std::pairs into the %map.
817 * @param __list A std::initializer_list<value_type> of pairs to be
818 * inserted.
819 *
820 * Complexity similar to that of the range constructor.
821 */
822 void
823 insert(std::initializer_list<value_type> __list)
824 { insert(__list.begin(), __list.end()); }
825#endif
826
827 /**
828 * @brief Attempts to insert a std::pair into the %map.
829 * @param __position An iterator that serves as a hint as to where the
830 * pair should be inserted.
831 * @param __x Pair to be inserted (see std::make_pair for easy creation
832 * of pairs).
833 * @return An iterator that points to the element with key of
834 * @a __x (may or may not be the %pair passed in).
835 *
836
837 * This function is not concerned about whether the insertion
838 * took place, and thus does not return a boolean like the
839 * single-argument insert() does. Note that the first
840 * parameter is only a hint and can potentially improve the
841 * performance of the insertion process. A bad hint would
842 * cause no gains in efficiency.
843 *
844 * See
845 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
846 * for more on @a hinting.
847 *
848 * Insertion requires logarithmic time (if the hint is not taken).
849 * @{
850 */
851 iterator
852#if __cplusplus >= 201103L
853 insert(const_iterator __position, const value_type& __x)
854#else
855 insert(iterator __position, const value_type& __x)
856#endif
857 { return _M_t._M_insert_unique_(__position, __x); }
858
859#if __cplusplus >= 201103L
860 // _GLIBCXX_RESOLVE_LIB_DEFECTS
861 // 2354. Unnecessary copying when inserting into maps with braced-init
862 iterator
863 insert(const_iterator __position, value_type&& __x)
864 { return _M_t._M_insert_unique_(__position, std::move(__x)); }
865
866 template<typename _Pair, typename = typename
867 std::enable_if<std::is_constructible<value_type,
868 _Pair&&>::value>::type>
869 iterator
870 insert(const_iterator __position, _Pair&& __x)
871 { return _M_t._M_insert_unique_(__position,
872 std::forward<_Pair>(__x)); }
873#endif
874 // @}
875
876 /**
877 * @brief Template function that attempts to insert a range of elements.
878 * @param __first Iterator pointing to the start of the range to be
879 * inserted.
880 * @param __last Iterator pointing to the end of the range.
881 *
882 * Complexity similar to that of the range constructor.
883 */
884 template<typename _InputIterator>
885 void
886 insert(_InputIterator __first, _InputIterator __last)
887 { _M_t._M_insert_unique(__first, __last); }
888
889#if __cplusplus > 201402L
890#define __cpp_lib_map_insertion 201411
891 /**
892 * @brief Attempts to insert or assign a std::pair into the %map.
893 * @param __k Key to use for finding a possibly existing pair in
894 * the map.
895 * @param __obj Argument used to generate the .second for a pair
896 * instance.
897 *
898 * @return A pair, of which the first element is an iterator that
899 * points to the possibly inserted pair, and the second is
900 * a bool that is true if the pair was actually inserted.
901 *
902 * This function attempts to insert a (key, value) %pair into the %map.
903 * A %map relies on unique keys and thus a %pair is only inserted if its
904 * first element (the key) is not already present in the %map.
905 * If the %pair was already in the %map, the .second of the %pair
906 * is assigned from __obj.
907 *
908 * Insertion requires logarithmic time.
909 */
910 template <typename _Obj>
911 pair<iterator, bool>
912 insert_or_assign(const key_type& __k, _Obj&& __obj)
913 {
914 iterator __i = lower_bound(__k);
915 if (__i == end() || key_comp()(__k, (*__i).first))
916 {
917 __i = emplace_hint(__i, std::piecewise_construct,
918 std::forward_as_tuple(__k),
919 std::forward_as_tuple(
920 std::forward<_Obj>(__obj)));
921 return {__i, true};
922 }
923 (*__i).second = std::forward<_Obj>(__obj);
924 return {__i, false};
925 }
926
927 // move-capable overload
928 template <typename _Obj>
929 pair<iterator, bool>
930 insert_or_assign(key_type&& __k, _Obj&& __obj)
931 {
932 iterator __i = lower_bound(__k);
933 if (__i == end() || key_comp()(__k, (*__i).first))
934 {
935 __i = emplace_hint(__i, std::piecewise_construct,
936 std::forward_as_tuple(std::move(__k)),
937 std::forward_as_tuple(
938 std::forward<_Obj>(__obj)));
939 return {__i, true};
940 }
941 (*__i).second = std::forward<_Obj>(__obj);
942 return {__i, false};
943 }
944
945 /**
946 * @brief Attempts to insert or assign a std::pair into the %map.
947 * @param __hint An iterator that serves as a hint as to where the
948 * pair should be inserted.
949 * @param __k Key to use for finding a possibly existing pair in
950 * the map.
951 * @param __obj Argument used to generate the .second for a pair
952 * instance.
953 *
954 * @return An iterator that points to the element with key of
955 * @a __x (may or may not be the %pair passed in).
956 *
957 * This function attempts to insert a (key, value) %pair into the %map.
958 * A %map relies on unique keys and thus a %pair is only inserted if its
959 * first element (the key) is not already present in the %map.
960 * If the %pair was already in the %map, the .second of the %pair
961 * is assigned from __obj.
962 *
963 * Insertion requires logarithmic time.
964 */
965 template <typename _Obj>
966 iterator
967 insert_or_assign(const_iterator __hint,
968 const key_type& __k, _Obj&& __obj)
969 {
970 iterator __i;
971 auto __true_hint = _M_t._M_get_insert_hint_unique_pos(__hint, __k);
972 if (__true_hint.second)
973 {
974 return emplace_hint(iterator(__true_hint.second),
975 std::piecewise_construct,
976 std::forward_as_tuple(__k),
977 std::forward_as_tuple(
978 std::forward<_Obj>(__obj)));
979 }
980 __i = iterator(__true_hint.first);
981 (*__i).second = std::forward<_Obj>(__obj);
982 return __i;
983 }
984
985 // move-capable overload
986 template <typename _Obj>
987 iterator
988 insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj)
989 {
990 iterator __i;
991 auto __true_hint = _M_t._M_get_insert_hint_unique_pos(__hint, __k);
992 if (__true_hint.second)
993 {
994 return emplace_hint(iterator(__true_hint.second),
995 std::piecewise_construct,
996 std::forward_as_tuple(std::move(__k)),
997 std::forward_as_tuple(
998 std::forward<_Obj>(__obj)));
999 }
1000 __i = iterator(__true_hint.first);
1001 (*__i).second = std::forward<_Obj>(__obj);
1002 return __i;
1003 }
1004#endif
1005
1006#if __cplusplus >= 201103L
1007 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1008 // DR 130. Associative erase should return an iterator.
1009 /**
1010 * @brief Erases an element from a %map.
1011 * @param __position An iterator pointing to the element to be erased.
1012 * @return An iterator pointing to the element immediately following
1013 * @a position prior to the element being erased. If no such
1014 * element exists, end() is returned.
1015 *
1016 * This function erases an element, pointed to by the given
1017 * iterator, from a %map. Note that this function only erases
1018 * the element, and that if the element is itself a pointer,
1019 * the pointed-to memory is not touched in any way. Managing
1020 * the pointer is the user's responsibility.
1021 *
1022 * @{
1023 */
1024 iterator
1025 erase(const_iterator __position)
1026 { return _M_t.erase(__position); }
1027
1028 // LWG 2059
1029 _GLIBCXX_ABI_TAG_CXX11
1030 iterator
1031 erase(iterator __position)
1032 { return _M_t.erase(__position); }
1033 // @}
1034#else
1035 /**
1036 * @brief Erases an element from a %map.
1037 * @param __position An iterator pointing to the element to be erased.
1038 *
1039 * This function erases an element, pointed to by the given
1040 * iterator, from a %map. Note that this function only erases
1041 * the element, and that if the element is itself a pointer,
1042 * the pointed-to memory is not touched in any way. Managing
1043 * the pointer is the user's responsibility.
1044 */
1045 void
1046 erase(iterator __position)
1047 { _M_t.erase(__position); }
1048#endif
1049
1050 /**
1051 * @brief Erases elements according to the provided key.
1052 * @param __x Key of element to be erased.
1053 * @return The number of elements erased.
1054 *
1055 * This function erases all the elements located by the given key from
1056 * a %map.
1057 * Note that this function only erases the element, and that if
1058 * the element is itself a pointer, the pointed-to memory is not touched
1059 * in any way. Managing the pointer is the user's responsibility.
1060 */
1061 size_type
1062 erase(const key_type& __x)
1063 { return _M_t.erase(__x); }
1064
1065#if __cplusplus >= 201103L
1066 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1067 // DR 130. Associative erase should return an iterator.
1068 /**
1069 * @brief Erases a [first,last) range of elements from a %map.
1070 * @param __first Iterator pointing to the start of the range to be
1071 * erased.
1072 * @param __last Iterator pointing to the end of the range to
1073 * be erased.
1074 * @return The iterator @a __last.
1075 *
1076 * This function erases a sequence of elements from a %map.
1077 * Note that this function only erases the element, and that if
1078 * the element is itself a pointer, the pointed-to memory is not touched
1079 * in any way. Managing the pointer is the user's responsibility.
1080 */
1081 iterator
1082 erase(const_iterator __first, const_iterator __last)
1083 { return _M_t.erase(__first, __last); }
1084#else
1085 /**
1086 * @brief Erases a [__first,__last) range of elements from a %map.
1087 * @param __first Iterator pointing to the start of the range to be
1088 * erased.
1089 * @param __last Iterator pointing to the end of the range to
1090 * be erased.
1091 *
1092 * This function erases a sequence of elements from a %map.
1093 * Note that this function only erases the element, and that if
1094 * the element is itself a pointer, the pointed-to memory is not touched
1095 * in any way. Managing the pointer is the user's responsibility.
1096 */
1097 void
1098 erase(iterator __first, iterator __last)
1099 { _M_t.erase(__first, __last); }
1100#endif
1101
1102 /**
1103 * @brief Swaps data with another %map.
1104 * @param __x A %map of the same element and allocator types.
1105 *
1106 * This exchanges the elements between two maps in constant
1107 * time. (It is only swapping a pointer, an integer, and an
1108 * instance of the @c Compare type (which itself is often
1109 * stateless and empty), so it should be quite fast.) Note
1110 * that the global std::swap() function is specialized such
1111 * that std::swap(m1,m2) will feed to this function.
1112 *
1113 * Whether the allocators are swapped depends on the allocator traits.
1114 */
1115 void
1116 swap(map& __x)
1117 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value)
1118 { _M_t.swap(__x._M_t); }
1119
1120 /**
1121 * Erases all elements in a %map. Note that this function only
1122 * erases the elements, and that if the elements themselves are
1123 * pointers, the pointed-to memory is not touched in any way.
1124 * Managing the pointer is the user's responsibility.
1125 */
1126 void
1127 clear() _GLIBCXX_NOEXCEPT
1128 { _M_t.clear(); }
1129
1130 // observers
1131 /**
1132 * Returns the key comparison object out of which the %map was
1133 * constructed.
1134 */
1135 key_compare
1136 key_comp() const
1137 { return _M_t.key_comp(); }
1138
1139 /**
1140 * Returns a value comparison object, built from the key comparison
1141 * object out of which the %map was constructed.
1142 */
1143 value_compare
1144 value_comp() const
1145 { return value_compare(_M_t.key_comp()); }
1146
1147 // [23.3.1.3] map operations
1148
1149 //@{
1150 /**
1151 * @brief Tries to locate an element in a %map.
1152 * @param __x Key of (key, value) %pair to be located.
1153 * @return Iterator pointing to sought-after element, or end() if not
1154 * found.
1155 *
1156 * This function takes a key and tries to locate the element with which
1157 * the key matches. If successful the function returns an iterator
1158 * pointing to the sought after %pair. If unsuccessful it returns the
1159 * past-the-end ( @c end() ) iterator.
1160 */
1161
1162 iterator
1163 find(const key_type& __x)
1164 { return _M_t.find(__x); }
1165
1166#if __cplusplus > 201103L
1167 template<typename _Kt>
1168 auto
1169 find(const _Kt& __x) -> decltype(_M_t._M_find_tr(__x))
1170 { return _M_t._M_find_tr(__x); }
1171#endif
1172 //@}
1173
1174 //@{
1175 /**
1176 * @brief Tries to locate an element in a %map.
1177 * @param __x Key of (key, value) %pair to be located.
1178 * @return Read-only (constant) iterator pointing to sought-after
1179 * element, or end() if not found.
1180 *
1181 * This function takes a key and tries to locate the element with which
1182 * the key matches. If successful the function returns a constant
1183 * iterator pointing to the sought after %pair. If unsuccessful it
1184 * returns the past-the-end ( @c end() ) iterator.
1185 */
1186
1187 const_iterator
1188 find(const key_type& __x) const
1189 { return _M_t.find(__x); }
1190
1191#if __cplusplus > 201103L
1192 template<typename _Kt>
1193 auto
1194 find(const _Kt& __x) const -> decltype(_M_t._M_find_tr(__x))
1195 { return _M_t._M_find_tr(__x); }
1196#endif
1197 //@}
1198
1199 //@{
1200 /**
1201 * @brief Finds the number of elements with given key.
1202 * @param __x Key of (key, value) pairs to be located.
1203 * @return Number of elements with specified key.
1204 *
1205 * This function only makes sense for multimaps; for map the result will
1206 * either be 0 (not present) or 1 (present).
1207 */
1208 size_type
1209 count(const key_type& __x) const
1210 { return _M_t.find(__x) == _M_t.end() ? 0 : 1; }
1211
1212#if __cplusplus > 201103L
1213 template<typename _Kt>
1214 auto
1215 count(const _Kt& __x) const -> decltype(_M_t._M_count_tr(__x))
1216 { return _M_t._M_count_tr(__x); }
1217#endif
1218 //@}
1219
1220 //@{
1221 /**
1222 * @brief Finds the beginning of a subsequence matching given key.
1223 * @param __x Key of (key, value) pair to be located.
1224 * @return Iterator pointing to first element equal to or greater
1225 * than key, or end().
1226 *
1227 * This function returns the first element of a subsequence of elements
1228 * that matches the given key. If unsuccessful it returns an iterator
1229 * pointing to the first element that has a greater value than given key
1230 * or end() if no such element exists.
1231 */
1232 iterator
1233 lower_bound(const key_type& __x)
1234 { return _M_t.lower_bound(__x); }
1235
1236#if __cplusplus > 201103L
1237 template<typename _Kt>
1238 auto
1239 lower_bound(const _Kt& __x)
1240 -> decltype(iterator(_M_t._M_lower_bound_tr(__x)))
1241 { return iterator(_M_t._M_lower_bound_tr(__x)); }
1242#endif
1243 //@}
1244
1245 //@{
1246 /**
1247 * @brief Finds the beginning of a subsequence matching given key.
1248 * @param __x Key of (key, value) pair to be located.
1249 * @return Read-only (constant) iterator pointing to first element
1250 * equal to or greater than key, or end().
1251 *
1252 * This function returns the first element of a subsequence of elements
1253 * that matches the given key. If unsuccessful it returns an iterator
1254 * pointing to the first element that has a greater value than given key
1255 * or end() if no such element exists.
1256 */
1257 const_iterator
1258 lower_bound(const key_type& __x) const
1259 { return _M_t.lower_bound(__x); }
1260
1261#if __cplusplus > 201103L
1262 template<typename _Kt>
1263 auto
1264 lower_bound(const _Kt& __x) const
1265 -> decltype(const_iterator(_M_t._M_lower_bound_tr(__x)))
1266 { return const_iterator(_M_t._M_lower_bound_tr(__x)); }
1267#endif
1268 //@}
1269
1270 //@{
1271 /**
1272 * @brief Finds the end of a subsequence matching given key.
1273 * @param __x Key of (key, value) pair to be located.
1274 * @return Iterator pointing to the first element
1275 * greater than key, or end().
1276 */
1277 iterator
1278 upper_bound(const key_type& __x)
1279 { return _M_t.upper_bound(__x); }
1280
1281#if __cplusplus > 201103L
1282 template<typename _Kt>
1283 auto
1284 upper_bound(const _Kt& __x)
1285 -> decltype(iterator(_M_t._M_upper_bound_tr(__x)))
1286 { return iterator(_M_t._M_upper_bound_tr(__x)); }
1287#endif
1288 //@}
1289
1290 //@{
1291 /**
1292 * @brief Finds the end of a subsequence matching given key.
1293 * @param __x Key of (key, value) pair to be located.
1294 * @return Read-only (constant) iterator pointing to first iterator
1295 * greater than key, or end().
1296 */
1297 const_iterator
1298 upper_bound(const key_type& __x) const
1299 { return _M_t.upper_bound(__x); }
1300
1301#if __cplusplus > 201103L
1302 template<typename _Kt>
1303 auto
1304 upper_bound(const _Kt& __x) const
1305 -> decltype(const_iterator(_M_t._M_upper_bound_tr(__x)))
1306 { return const_iterator(_M_t._M_upper_bound_tr(__x)); }
1307#endif
1308 //@}
1309
1310 //@{
1311 /**
1312 * @brief Finds a subsequence matching given key.
1313 * @param __x Key of (key, value) pairs to be located.
1314 * @return Pair of iterators that possibly points to the subsequence
1315 * matching given key.
1316 *
1317 * This function is equivalent to
1318 * @code
1319 * std::make_pair(c.lower_bound(val),
1320 * c.upper_bound(val))
1321 * @endcode
1322 * (but is faster than making the calls separately).
1323 *
1324 * This function probably only makes sense for multimaps.
1325 */
1326 std::pair<iterator, iterator>
1327 equal_range(const key_type& __x)
1328 { return _M_t.equal_range(__x); }
1329
1330#if __cplusplus > 201103L
1331 template<typename _Kt>
1332 auto
1333 equal_range(const _Kt& __x)
1334 -> decltype(pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)))
1335 { return pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)); }
1336#endif
1337 //@}
1338
1339 //@{
1340 /**
1341 * @brief Finds a subsequence matching given key.
1342 * @param __x Key of (key, value) pairs to be located.
1343 * @return Pair of read-only (constant) iterators that possibly points
1344 * to the subsequence matching given key.
1345 *
1346 * This function is equivalent to
1347 * @code
1348 * std::make_pair(c.lower_bound(val),
1349 * c.upper_bound(val))
1350 * @endcode
1351 * (but is faster than making the calls separately).
1352 *
1353 * This function probably only makes sense for multimaps.
1354 */
1355 std::pair<const_iterator, const_iterator>
1356 equal_range(const key_type& __x) const
1357 { return _M_t.equal_range(__x); }
1358
1359#if __cplusplus > 201103L
1360 template<typename _Kt>
1361 auto
1362 equal_range(const _Kt& __x) const
1363 -> decltype(pair<const_iterator, const_iterator>(
1364 _M_t._M_equal_range_tr(__x)))
1365 {
1366 return pair<const_iterator, const_iterator>(
1367 _M_t._M_equal_range_tr(__x));
1368 }
1369#endif
1370 //@}
1371
1372 template<typename _K1, typename _T1, typename _C1, typename _A1>
1373 friend bool
1374 operator==(const map<_K1, _T1, _C1, _A1>&,
1375 const map<_K1, _T1, _C1, _A1>&);
1376
1377 template<typename _K1, typename _T1, typename _C1, typename _A1>
1378 friend bool
1379 operator<(const map<_K1, _T1, _C1, _A1>&,
1380 const map<_K1, _T1, _C1, _A1>&);
1381 };
1382
1383 /**
1384 * @brief Map equality comparison.
1385 * @param __x A %map.
1386 * @param __y A %map of the same type as @a x.
1387 * @return True iff the size and elements of the maps are equal.
1388 *
1389 * This is an equivalence relation. It is linear in the size of the
1390 * maps. Maps are considered equivalent if their sizes are equal,
1391 * and if corresponding elements compare equal.
1392 */
1393 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1394 inline bool
1395 operator==(const map<_Key, _Tp, _Compare, _Alloc>& __x,
1396 const map<_Key, _Tp, _Compare, _Alloc>& __y)
1397 { return __x._M_t == __y._M_t; }
1398
1399 /**
1400 * @brief Map ordering relation.
1401 * @param __x A %map.
1402 * @param __y A %map of the same type as @a x.
1403 * @return True iff @a x is lexicographically less than @a y.
1404 *
1405 * This is a total ordering relation. It is linear in the size of the
1406 * maps. The elements must be comparable with @c <.
1407 *
1408 * See std::lexicographical_compare() for how the determination is made.
1409 */
1410 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1411 inline bool
1412 operator<(const map<_Key, _Tp, _Compare, _Alloc>& __x,
1413 const map<_Key, _Tp, _Compare, _Alloc>& __y)
1414 { return __x._M_t < __y._M_t; }
1415
1416 /// Based on operator==
1417 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1418 inline bool
1419 operator!=(const map<_Key, _Tp, _Compare, _Alloc>& __x,
1420 const map<_Key, _Tp, _Compare, _Alloc>& __y)
1421 { return !(__x == __y); }
1422
1423 /// Based on operator<
1424 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1425 inline bool
1426 operator>(const map<_Key, _Tp, _Compare, _Alloc>& __x,
1427 const map<_Key, _Tp, _Compare, _Alloc>& __y)
1428 { return __y < __x; }
1429
1430 /// Based on operator<
1431 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1432 inline bool
1433 operator<=(const map<_Key, _Tp, _Compare, _Alloc>& __x,
1434 const map<_Key, _Tp, _Compare, _Alloc>& __y)
1435 { return !(__y < __x); }
1436
1437 /// Based on operator<
1438 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1439 inline bool
1440 operator>=(const map<_Key, _Tp, _Compare, _Alloc>& __x,
1441 const map<_Key, _Tp, _Compare, _Alloc>& __y)
1442 { return !(__x < __y); }
1443
1444 /// See std::map::swap().
1445 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1446 inline void
1447 swap(map<_Key, _Tp, _Compare, _Alloc>& __x,
1448 map<_Key, _Tp, _Compare, _Alloc>& __y)
1449 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
1450 { __x.swap(__y); }
1451
1452_GLIBCXX_END_NAMESPACE_CONTAINER
1453
1454#if __cplusplus > 201402L
1455_GLIBCXX_BEGIN_NAMESPACE_VERSION
1456 // Allow std::map access to internals of compatible maps.
1457 template<typename _Key, typename _Val, typename _Cmp1, typename _Alloc,
1458 typename _Cmp2>
1459 struct
1460 _Rb_tree_merge_helper<_GLIBCXX_STD_C::map<_Key, _Val, _Cmp1, _Alloc>,
1461 _Cmp2>
1462 {
1463 private:
1464 friend class _GLIBCXX_STD_C::map<_Key, _Val, _Cmp1, _Alloc>;
1465
1466 static auto&
1467 _S_get_tree(_GLIBCXX_STD_C::map<_Key, _Val, _Cmp2, _Alloc>& __map)
1468 { return __map._M_t; }
1469
1470 static auto&
1471 _S_get_tree(_GLIBCXX_STD_C::multimap<_Key, _Val, _Cmp2, _Alloc>& __map)
1472 { return __map._M_t; }
1473 };
1474_GLIBCXX_END_NAMESPACE_VERSION
1475#endif // C++17
1476
1477} // namespace std
1478
1479#endif /* _STL_MAP_H */
1480