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