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