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