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  */
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  */
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
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>
682  pair<iterator, bool>
683  try_emplace(const key_type& __k, _Args&&... __args)
684  {
685  iterator __i = lower_bound(__k);
686  if (__i == end() || key_comp()(__k, (*__i).first))
687  {
689  std::forward_as_tuple(__k),
690  std::forward_as_tuple(
691  std::forward<_Args>(__args)...));
692  return {__i, true};
693  }
694  return {__i, false};
695  }
696 
697  // move-capable overload
698  template <typename... _Args>
699  pair<iterator, bool>
700  try_emplace(key_type&& __k, _Args&&... __args)
701  {
702  iterator __i = lower_bound(__k);
703  if (__i == end() || key_comp()(__k, (*__i).first))
704  {
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
803  { return _M_t._M_insert_unique(std::move(__x)); }
804 
805  template<typename _Pair, typename = typename
806  std::enable_if<std::is_constructible<value_type,
807  _Pair&&>::value>::type>
809  insert(_Pair&& __x)
810  { return _M_t._M_insert_unique(std::forward<_Pair>(__x)); }
811 #endif
812  // @}
813 
814 #if __cplusplus >= 201103L
815  /**
816  * @brief Attempts to insert a list of std::pairs into the %map.
817  * @param __list A std::initializer_list<value_type> of pairs to be
818  * inserted.
819  *
820  * Complexity similar to that of the range constructor.
821  */
822  void
824  { insert(__list.begin(), __list.end()); }
825 #endif
826 
827  /**
828  * @brief Attempts to insert a std::pair into the %map.
829  * @param __position An iterator that serves as a hint as to where the
830  * pair should be inserted.
831  * @param __x Pair to be inserted (see std::make_pair for easy creation
832  * of pairs).
833  * @return An iterator that points to the element with key of
834  * @a __x (may or may not be the %pair passed in).
835  *
836 
837  * This function is not concerned about whether the insertion
838  * took place, and thus does not return a boolean like the
839  * single-argument insert() does. Note that the first
840  * parameter is only a hint and can potentially improve the
841  * performance of the insertion process. A bad hint would
842  * cause no gains in efficiency.
843  *
844  * See
845  * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
846  * for more on @a hinting.
847  *
848  * Insertion requires logarithmic time (if the hint is not taken).
849  * @{
850  */
851  iterator
852 #if __cplusplus >= 201103L
853  insert(const_iterator __position, const value_type& __x)
854 #else
855  insert(iterator __position, const value_type& __x)
856 #endif
857  { return _M_t._M_insert_unique_(__position, __x); }
858 
859 #if __cplusplus >= 201103L
860  // _GLIBCXX_RESOLVE_LIB_DEFECTS
861  // 2354. Unnecessary copying when inserting into maps with braced-init
862  iterator
863  insert(const_iterator __position, value_type&& __x)
864  { return _M_t._M_insert_unique_(__position, std::move(__x)); }
865 
866  template<typename _Pair, typename = typename
867  std::enable_if<std::is_constructible<value_type,
868  _Pair&&>::value>::type>
869  iterator
870  insert(const_iterator __position, _Pair&& __x)
871  { return _M_t._M_insert_unique_(__position,
872  std::forward<_Pair>(__x)); }
873 #endif
874  // @}
875 
876  /**
877  * @brief Template function that attempts to insert a range of elements.
878  * @param __first Iterator pointing to the start of the range to be
879  * inserted.
880  * @param __last Iterator pointing to the end of the range.
881  *
882  * Complexity similar to that of the range constructor.
883  */
884  template<typename _InputIterator>
885  void
886  insert(_InputIterator __first, _InputIterator __last)
887  { _M_t._M_insert_unique(__first, __last); }
888 
889 #if __cplusplus > 201402L
890 #define __cpp_lib_map_insertion 201411
891  /**
892  * @brief Attempts to insert or assign a std::pair into the %map.
893  * @param __k Key to use for finding a possibly existing pair in
894  * the map.
895  * @param __obj Argument used to generate the .second for a pair
896  * instance.
897  *
898  * @return A pair, of which the first element is an iterator that
899  * points to the possibly inserted pair, and the second is
900  * a bool that is true if the pair was actually inserted.
901  *
902  * This function attempts to insert a (key, value) %pair into the %map.
903  * A %map relies on unique keys and thus a %pair is only inserted if its
904  * first element (the key) is not already present in the %map.
905  * If the %pair was already in the %map, the .second of the %pair
906  * is assigned from __obj.
907  *
908  * Insertion requires logarithmic time.
909  */
910  template <typename _Obj>
912  insert_or_assign(const key_type& __k, _Obj&& __obj)
913  {
914  iterator __i = lower_bound(__k);
915  if (__i == end() || key_comp()(__k, (*__i).first))
916  {
918  std::forward_as_tuple(__k),
919  std::forward_as_tuple(
920  std::forward<_Obj>(__obj)));
921  return {__i, true};
922  }
923  (*__i).second = std::forward<_Obj>(__obj);
924  return {__i, false};
925  }
926 
927  // move-capable overload
928  template <typename _Obj>
929  pair<iterator, bool>
930  insert_or_assign(key_type&& __k, _Obj&& __obj)
931  {
932  iterator __i = lower_bound(__k);
933  if (__i == end() || key_comp()(__k, (*__i).first))
934  {
936  std::forward_as_tuple(std::move(__k)),
937  std::forward_as_tuple(
938  std::forward<_Obj>(__obj)));
939  return {__i, true};
940  }
941  (*__i).second = std::forward<_Obj>(__obj);
942  return {__i, false};
943  }
944 
945  /**
946  * @brief Attempts to insert or assign a std::pair into the %map.
947  * @param __hint An iterator that serves as a hint as to where the
948  * pair should be inserted.
949  * @param __k Key to use for finding a possibly existing pair in
950  * the map.
951  * @param __obj Argument used to generate the .second for a pair
952  * instance.
953  *
954  * @return An iterator that points to the element with key of
955  * @a __x (may or may not be the %pair passed in).
956  *
957  * This function attempts to insert a (key, value) %pair into the %map.
958  * A %map relies on unique keys and thus a %pair is only inserted if its
959  * first element (the key) is not already present in the %map.
960  * If the %pair was already in the %map, the .second of the %pair
961  * is assigned from __obj.
962  *
963  * Insertion requires logarithmic time.
964  */
965  template <typename _Obj>
966  iterator
967  insert_or_assign(const_iterator __hint,
968  const key_type& __k, _Obj&& __obj)
969  {
970  iterator __i;
971  auto __true_hint = _M_t._M_get_insert_hint_unique_pos(__hint, __k);
972  if (__true_hint.second)
973  {
974  return emplace_hint(iterator(__true_hint.second),
976  std::forward_as_tuple(__k),
977  std::forward_as_tuple(
978  std::forward<_Obj>(__obj)));
979  }
980  __i = iterator(__true_hint.first);
981  (*__i).second = std::forward<_Obj>(__obj);
982  return __i;
983  }
984 
985  // move-capable overload
986  template <typename _Obj>
987  iterator
988  insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj)
989  {
990  iterator __i;
991  auto __true_hint = _M_t._M_get_insert_hint_unique_pos(__hint, __k);
992  if (__true_hint.second)
993  {
994  return emplace_hint(iterator(__true_hint.second),
996  std::forward_as_tuple(std::move(__k)),
997  std::forward_as_tuple(
998  std::forward<_Obj>(__obj)));
999  }
1000  __i = iterator(__true_hint.first);
1001  (*__i).second = std::forward<_Obj>(__obj);
1002  return __i;
1003  }
1004 #endif
1005 
1006 #if __cplusplus >= 201103L
1007  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1008  // DR 130. Associative erase should return an iterator.
1009  /**
1010  * @brief Erases an element from a %map.
1011  * @param __position An iterator pointing to the element to be erased.
1012  * @return An iterator pointing to the element immediately following
1013  * @a position prior to the element being erased. If no such
1014  * element exists, end() is returned.
1015  *
1016  * This function erases an element, pointed to by the given
1017  * iterator, from a %map. Note that this function only erases
1018  * the element, and that if the element is itself a pointer,
1019  * the pointed-to memory is not touched in any way. Managing
1020  * the pointer is the user's responsibility.
1021  *
1022  * @{
1023  */
1024  iterator
1025  erase(const_iterator __position)
1026  { return _M_t.erase(__position); }
1027 
1028  // LWG 2059
1029  _GLIBCXX_ABI_TAG_CXX11
1030  iterator
1031  erase(iterator __position)
1032  { return _M_t.erase(__position); }
1033  // @}
1034 #else
1035  /**
1036  * @brief Erases an element from a %map.
1037  * @param __position An iterator pointing to the element to be erased.
1038  *
1039  * This function erases an element, pointed to by the given
1040  * iterator, from a %map. Note that this function only erases
1041  * the element, and that if the element is itself a pointer,
1042  * the pointed-to memory is not touched in any way. Managing
1043  * the pointer is the user's responsibility.
1044  */
1045  void
1046  erase(iterator __position)
1047  { _M_t.erase(__position); }
1048 #endif
1049 
1050  /**
1051  * @brief Erases elements according to the provided key.
1052  * @param __x Key of element to be erased.
1053  * @return The number of elements erased.
1054  *
1055  * This function erases all the elements located by the given key from
1056  * a %map.
1057  * Note that this function only erases the element, and that if
1058  * the element is itself a pointer, the pointed-to memory is not touched
1059  * in any way. Managing the pointer is the user's responsibility.
1060  */
1061  size_type
1062  erase(const key_type& __x)
1063  { return _M_t.erase(__x); }
1064 
1065 #if __cplusplus >= 201103L
1066  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1067  // DR 130. Associative erase should return an iterator.
1068  /**
1069  * @brief Erases a [first,last) range of elements from a %map.
1070  * @param __first Iterator pointing to the start of the range to be
1071  * erased.
1072  * @param __last Iterator pointing to the end of the range to
1073  * be erased.
1074  * @return The iterator @a __last.
1075  *
1076  * This function erases a sequence of elements from a %map.
1077  * Note that this function only erases the element, and that if
1078  * the element is itself a pointer, the pointed-to memory is not touched
1079  * in any way. Managing the pointer is the user's responsibility.
1080  */
1081  iterator
1082  erase(const_iterator __first, const_iterator __last)
1083  { return _M_t.erase(__first, __last); }
1084 #else
1085  /**
1086  * @brief Erases a [__first,__last) range of elements from a %map.
1087  * @param __first Iterator pointing to the start of the range to be
1088  * erased.
1089  * @param __last Iterator pointing to the end of the range to
1090  * be erased.
1091  *
1092  * This function erases a sequence of elements from a %map.
1093  * Note that this function only erases the element, and that if
1094  * the element is itself a pointer, the pointed-to memory is not touched
1095  * in any way. Managing the pointer is the user's responsibility.
1096  */
1097  void
1098  erase(iterator __first, iterator __last)
1099  { _M_t.erase(__first, __last); }
1100 #endif
1101 
1102  /**
1103  * @brief Swaps data with another %map.
1104  * @param __x A %map of the same element and allocator types.
1105  *
1106  * This exchanges the elements between two maps in constant
1107  * time. (It is only swapping a pointer, an integer, and an
1108  * instance of the @c Compare type (which itself is often
1109  * stateless and empty), so it should be quite fast.) Note
1110  * that the global std::swap() function is specialized such
1111  * that std::swap(m1,m2) will feed to this function.
1112  *
1113  * Whether the allocators are swapped depends on the allocator traits.
1114  */
1115  void
1116  swap(map& __x)
1117  _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value)
1118  { _M_t.swap(__x._M_t); }
1119 
1120  /**
1121  * Erases all elements in a %map. Note that this function only
1122  * erases the elements, and that if the elements themselves are
1123  * pointers, the pointed-to memory is not touched in any way.
1124  * Managing the pointer is the user's responsibility.
1125  */
1126  void
1127  clear() _GLIBCXX_NOEXCEPT
1128  { _M_t.clear(); }
1129 
1130  // observers
1131  /**
1132  * Returns the key comparison object out of which the %map was
1133  * constructed.
1134  */
1135  key_compare
1136  key_comp() const
1137  { return _M_t.key_comp(); }
1138 
1139  /**
1140  * Returns a value comparison object, built from the key comparison
1141  * object out of which the %map was constructed.
1142  */
1143  value_compare
1144  value_comp() const
1145  { return value_compare(_M_t.key_comp()); }
1146 
1147  // [23.3.1.3] map operations
1148 
1149  //@{
1150  /**
1151  * @brief Tries to locate an element in a %map.
1152  * @param __x Key of (key, value) %pair to be located.
1153  * @return Iterator pointing to sought-after element, or end() if not
1154  * found.
1155  *
1156  * This function takes a key and tries to locate the element with which
1157  * the key matches. If successful the function returns an iterator
1158  * pointing to the sought after %pair. If unsuccessful it returns the
1159  * past-the-end ( @c end() ) iterator.
1160  */
1161 
1162  iterator
1163  find(const key_type& __x)
1164  { return _M_t.find(__x); }
1165 
1166 #if __cplusplus > 201103L
1167  template<typename _Kt>
1168  auto
1169  find(const _Kt& __x) -> decltype(_M_t._M_find_tr(__x))
1170  { return _M_t._M_find_tr(__x); }
1171 #endif
1172  //@}
1173 
1174  //@{
1175  /**
1176  * @brief Tries to locate an element in a %map.
1177  * @param __x Key of (key, value) %pair to be located.
1178  * @return Read-only (constant) iterator pointing to sought-after
1179  * element, or end() if not found.
1180  *
1181  * This function takes a key and tries to locate the element with which
1182  * the key matches. If successful the function returns a constant
1183  * iterator pointing to the sought after %pair. If unsuccessful it
1184  * returns the past-the-end ( @c end() ) iterator.
1185  */
1186 
1187  const_iterator
1188  find(const key_type& __x) const
1189  { return _M_t.find(__x); }
1190 
1191 #if __cplusplus > 201103L
1192  template<typename _Kt>
1193  auto
1194  find(const _Kt& __x) const -> decltype(_M_t._M_find_tr(__x))
1195  { return _M_t._M_find_tr(__x); }
1196 #endif
1197  //@}
1198 
1199  //@{
1200  /**
1201  * @brief Finds the number of elements with given key.
1202  * @param __x Key of (key, value) pairs to be located.
1203  * @return Number of elements with specified key.
1204  *
1205  * This function only makes sense for multimaps; for map the result will
1206  * either be 0 (not present) or 1 (present).
1207  */
1208  size_type
1209  count(const key_type& __x) const
1210  { return _M_t.find(__x) == _M_t.end() ? 0 : 1; }
1211 
1212 #if __cplusplus > 201103L
1213  template<typename _Kt>
1214  auto
1215  count(const _Kt& __x) const -> decltype(_M_t._M_count_tr(__x))
1216  { return _M_t._M_count_tr(__x); }
1217 #endif
1218  //@}
1219 
1220  //@{
1221  /**
1222  * @brief Finds the beginning of a subsequence matching given key.
1223  * @param __x Key of (key, value) pair to be located.
1224  * @return Iterator pointing to first element equal to or greater
1225  * than key, or end().
1226  *
1227  * This function returns the first element of a subsequence of elements
1228  * that matches the given key. If unsuccessful it returns an iterator
1229  * pointing to the first element that has a greater value than given key
1230  * or end() if no such element exists.
1231  */
1232  iterator
1233  lower_bound(const key_type& __x)
1234  { return _M_t.lower_bound(__x); }
1235 
1236 #if __cplusplus > 201103L
1237  template<typename _Kt>
1238  auto
1239  lower_bound(const _Kt& __x)
1240  -> decltype(iterator(_M_t._M_lower_bound_tr(__x)))
1241  { return iterator(_M_t._M_lower_bound_tr(__x)); }
1242 #endif
1243  //@}
1244 
1245  //@{
1246  /**
1247  * @brief Finds the beginning of a subsequence matching given key.
1248  * @param __x Key of (key, value) pair to be located.
1249  * @return Read-only (constant) iterator pointing to first element
1250  * equal to or greater than key, or end().
1251  *
1252  * This function returns the first element of a subsequence of elements
1253  * that matches the given key. If unsuccessful it returns an iterator
1254  * pointing to the first element that has a greater value than given key
1255  * or end() if no such element exists.
1256  */
1257  const_iterator
1258  lower_bound(const key_type& __x) const
1259  { return _M_t.lower_bound(__x); }
1260 
1261 #if __cplusplus > 201103L
1262  template<typename _Kt>
1263  auto
1264  lower_bound(const _Kt& __x) const
1265  -> decltype(const_iterator(_M_t._M_lower_bound_tr(__x)))
1266  { return const_iterator(_M_t._M_lower_bound_tr(__x)); }
1267 #endif
1268  //@}
1269 
1270  //@{
1271  /**
1272  * @brief Finds the end of a subsequence matching given key.
1273  * @param __x Key of (key, value) pair to be located.
1274  * @return Iterator pointing to the first element
1275  * greater than key, or end().
1276  */
1277  iterator
1278  upper_bound(const key_type& __x)
1279  { return _M_t.upper_bound(__x); }
1280 
1281 #if __cplusplus > 201103L
1282  template<typename _Kt>
1283  auto
1284  upper_bound(const _Kt& __x)
1285  -> decltype(iterator(_M_t._M_upper_bound_tr(__x)))
1286  { return iterator(_M_t._M_upper_bound_tr(__x)); }
1287 #endif
1288  //@}
1289 
1290  //@{
1291  /**
1292  * @brief Finds the end of a subsequence matching given key.
1293  * @param __x Key of (key, value) pair to be located.
1294  * @return Read-only (constant) iterator pointing to first iterator
1295  * greater than key, or end().
1296  */
1297  const_iterator
1298  upper_bound(const key_type& __x) const
1299  { return _M_t.upper_bound(__x); }
1300 
1301 #if __cplusplus > 201103L
1302  template<typename _Kt>
1303  auto
1304  upper_bound(const _Kt& __x) const
1305  -> decltype(const_iterator(_M_t._M_upper_bound_tr(__x)))
1306  { return const_iterator(_M_t._M_upper_bound_tr(__x)); }
1307 #endif
1308  //@}
1309 
1310  //@{
1311  /**
1312  * @brief Finds a subsequence matching given key.
1313  * @param __x Key of (key, value) pairs to be located.
1314  * @return Pair of iterators that possibly points to the subsequence
1315  * matching given key.
1316  *
1317  * This function is equivalent to
1318  * @code
1319  * std::make_pair(c.lower_bound(val),
1320  * c.upper_bound(val))
1321  * @endcode
1322  * (but is faster than making the calls separately).
1323  *
1324  * This function probably only makes sense for multimaps.
1325  */
1327  equal_range(const key_type& __x)
1328  { return _M_t.equal_range(__x); }
1329 
1330 #if __cplusplus > 201103L
1331  template<typename _Kt>
1332  auto
1333  equal_range(const _Kt& __x)
1334  -> decltype(pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)))
1335  { return pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)); }
1336 #endif
1337  //@}
1338 
1339  //@{
1340  /**
1341  * @brief Finds a subsequence matching given key.
1342  * @param __x Key of (key, value) pairs to be located.
1343  * @return Pair of read-only (constant) iterators that possibly points
1344  * to the subsequence matching given key.
1345  *
1346  * This function is equivalent to
1347  * @code
1348  * std::make_pair(c.lower_bound(val),
1349  * c.upper_bound(val))
1350  * @endcode
1351  * (but is faster than making the calls separately).
1352  *
1353  * This function probably only makes sense for multimaps.
1354  */
1356  equal_range(const key_type& __x) const
1357  { return _M_t.equal_range(__x); }
1358 
1359 #if __cplusplus > 201103L
1360  template<typename _Kt>
1361  auto
1362  equal_range(const _Kt& __x) const
1364  _M_t._M_equal_range_tr(__x)))
1365  {
1367  _M_t._M_equal_range_tr(__x));
1368  }
1369 #endif
1370  //@}
1371 
1372  template<typename _K1, typename _T1, typename _C1, typename _A1>
1373  friend bool
1374  operator==(const map<_K1, _T1, _C1, _A1>&,
1375  const map<_K1, _T1, _C1, _A1>&);
1376 
1377  template<typename _K1, typename _T1, typename _C1, typename _A1>
1378  friend bool
1379  operator<(const map<_K1, _T1, _C1, _A1>&,
1380  const map<_K1, _T1, _C1, _A1>&);
1381  };
1382 
1383  /**
1384  * @brief Map equality comparison.
1385  * @param __x A %map.
1386  * @param __y A %map of the same type as @a x.
1387  * @return True iff the size and elements of the maps are equal.
1388  *
1389  * This is an equivalence relation. It is linear in the size of the
1390  * maps. Maps are considered equivalent if their sizes are equal,
1391  * and if corresponding elements compare equal.
1392  */
1393  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1394  inline bool
1395  operator==(const map<_Key, _Tp, _Compare, _Alloc>& __x,
1397  { return __x._M_t == __y._M_t; }
1398 
1399  /**
1400  * @brief Map ordering relation.
1401  * @param __x A %map.
1402  * @param __y A %map of the same type as @a x.
1403  * @return True iff @a x is lexicographically less than @a y.
1404  *
1405  * This is a total ordering relation. It is linear in the size of the
1406  * maps. The elements must be comparable with @c <.
1407  *
1408  * See std::lexicographical_compare() for how the determination is made.
1409  */
1410  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1411  inline bool
1412  operator<(const map<_Key, _Tp, _Compare, _Alloc>& __x,
1414  { return __x._M_t < __y._M_t; }
1415 
1416  /// Based on operator==
1417  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1418  inline bool
1419  operator!=(const map<_Key, _Tp, _Compare, _Alloc>& __x,
1421  { return !(__x == __y); }
1422 
1423  /// Based on operator<
1424  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1425  inline bool
1426  operator>(const map<_Key, _Tp, _Compare, _Alloc>& __x,
1428  { return __y < __x; }
1429 
1430  /// Based on operator<
1431  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1432  inline bool
1433  operator<=(const map<_Key, _Tp, _Compare, _Alloc>& __x,
1435  { return !(__y < __x); }
1436 
1437  /// Based on operator<
1438  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1439  inline bool
1440  operator>=(const map<_Key, _Tp, _Compare, _Alloc>& __x,
1442  { return !(__x < __y); }
1443 
1444  /// See std::map::swap().
1445  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1446  inline void
1449  _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
1450  { __x.swap(__y); }
1451 
1452 _GLIBCXX_END_NAMESPACE_CONTAINER
1453 
1454 #if __cplusplus > 201402L
1455 _GLIBCXX_BEGIN_NAMESPACE_VERSION
1456  // Allow std::map access to internals of compatible maps.
1457  template<typename _Key, typename _Val, typename _Cmp1, typename _Alloc,
1458  typename _Cmp2>
1459  struct
1460  _Rb_tree_merge_helper<_GLIBCXX_STD_C::map<_Key, _Val, _Cmp1, _Alloc>,
1461  _Cmp2>
1462  {
1463  private:
1464  friend class _GLIBCXX_STD_C::map<_Key, _Val, _Cmp1, _Alloc>;
1465 
1466  static auto&
1467  _S_get_tree(_GLIBCXX_STD_C::map<_Key, _Val, _Cmp2, _Alloc>& __map)
1468  { return __map._M_t; }
1469 
1470  static auto&
1471  _S_get_tree(_GLIBCXX_STD_C::multimap<_Key, _Val, _Cmp2, _Alloc>& __map)
1472  { return __map._M_t; }
1473  };
1474 _GLIBCXX_END_NAMESPACE_VERSION
1475 #endif // C++17
1476 
1477 } // namespace std
1478 
1479 #endif /* _STL_MAP_H */
iterator erase(const_iterator __first, const_iterator __last)
Erases a [first,last) range of elements from a map.
Definition: stl_map.h:1082
iterator upper_bound(const key_type &__x)
Finds the end of a subsequence matching given key.
Definition: stl_map.h:1278
map(_InputIterator __first, _InputIterator __last)
Builds a map from a range.
Definition: stl_map.h:265
void noexcept()
Swaps data with another map.
Definition: stl_map.h:1117
std::pair< iterator, iterator > equal_range(const key_type &__x)
Finds a subsequence matching given key.
Definition: stl_map.h:1327
mapped_type & at(const key_type &__k)
Access to map data.
Definition: stl_map.h:529
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
iterator end() noexcept
Definition: stl_map.h:366
map(_InputIterator __first, _InputIterator __last, const allocator_type &__a)
Allocator-extended range constructor.
Definition: stl_map.h:248
bool empty() const noexcept
Definition: stl_map.h:457
A standard container made up of (key,value) pairs, which can be retrieved based on a key...
Definition: stl_map.h:71
~map()=default
const_iterator lower_bound(const key_type &__x) const
Finds the beginning of a subsequence matching given key.
Definition: stl_map.h:1258
void insert(std::initializer_list< value_type > __list)
Attempts to insert a list of std::pairs into the map.
Definition: stl_map.h:823
map(initializer_list< value_type > __l, const allocator_type &__a)
Allocator-extended initialier-list constructor.
Definition: stl_map.h:242
const_iterator upper_bound(const key_type &__x) const
Finds the end of a subsequence matching given key.
Definition: stl_map.h:1298
iterator insert(const_iterator __position, value_type &&__x)
Attempts to insert a std::pair into the map.
Definition: stl_map.h:863
std::pair< const_iterator, const_iterator > equal_range(const key_type &__x) const
Finds a subsequence matching given key.
Definition: stl_map.h:1356
_GLIBCXX17_INLINE constexpr piecewise_construct_t piecewise_construct
piecewise_construct
Definition: stl_pair.h:79
_GLIBCXX_ABI_TAG_CXX11 iterator erase(iterator __position)
Erases an element from a map.
Definition: stl_map.h:1031
size_type max_size() const noexcept
Definition: stl_map.h:467
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:1264
void clear() noexcept
Definition: stl_map.h:1127
key_compare key_comp() const
Definition: stl_map.h:1136
std::pair< iterator, bool > insert(_Pair &&__x)
Attempts to insert a std::pair into the map.
Definition: stl_map.h:809
const_iterator find(const key_type &__x) const
Tries to locate an element in a map.
Definition: stl_map.h:1188
iterator insert(const_iterator __position, _Pair &&__x)
Attempts to insert a std::pair into the map.
Definition: stl_map.h:870
map(const _Compare &__comp, const allocator_type &__a=allocator_type())
Creates a map with no elements.
Definition: stl_map.h:186
auto find(const _Kt &__x) -> decltype(_M_t._M_find_tr(__x))
Tries to locate an element in a map.
Definition: stl_map.h:1169
initializer_list
iterator erase(const_iterator __position)
Erases an element from a map.
Definition: stl_map.h:1025
const_iterator cbegin() const noexcept
Definition: stl_map.h:421
const_reverse_iterator rend() const noexcept
Definition: stl_map.h:411
map(const map &__m, const allocator_type &__a)
Allocator-extended copy constructor.
Definition: stl_map.h:232
map()=default
Default constructor creates no elements.
const_reverse_iterator rbegin() const noexcept
Definition: stl_map.h:393
map & operator=(const map &)=default
Map assignment operator.
Primary class template, tuple.
Definition: tuple:53
const_iterator begin() const noexcept
Definition: stl_map.h:357
iterator lower_bound(const key_type &__x)
Finds the beginning of a subsequence matching given key.
Definition: stl_map.h:1233
map(const allocator_type &__a)
Allocator-extended default constructor.
Definition: stl_map.h:228
std::pair< iterator, bool > insert(value_type &&__x)
Attempts to insert a std::pair into the map.
Definition: stl_map.h:802
allocator_type get_allocator() const noexcept
Get a copy of the memory allocation object.
Definition: stl_map.h:338
size_type count(const key_type &__x) const
Finds the number of elements with given key.
Definition: stl_map.h:1209
A standard container made up of (key,value) pairs, which can be retrieved based on a key...
Definition: stl_map.h:99
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:1194
std::pair< iterator, bool > emplace(_Args &&...__args)
Attempts to build and insert a std::pair into the map.
Definition: stl_map.h:568
mapped_type & operator[](const key_type &__k)
Subscript ( [] ) access to map data.
Definition: stl_map.h:484
reverse_iterator rend() noexcept
Definition: stl_map.h:402
size_type size() const noexcept
Definition: stl_map.h:462
iterator find(const key_type &__x)
Tries to locate an element in a map.
Definition: stl_map.h:1163
std::pair< iterator, bool > insert(const value_type &__x)
Attempts to insert a std::pair into the map.
Definition: stl_map.h:795
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
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:198
const_iterator cend() const noexcept
Definition: stl_map.h:430
map & operator=(initializer_list< value_type > __l)
Map list assignment operator.
Definition: stl_map.h:329
value_compare value_comp() const
Definition: stl_map.h:1144
void insert(_InputIterator __first, _InputIterator __last)
Template function that attempts to insert a range of elements.
Definition: stl_map.h:886
_T1 first
second_type is the second bound type
Definition: stl_pair.h:203
size_type erase(const key_type &__x)
Erases elements according to the provided key.
Definition: stl_map.h:1062
const_reverse_iterator crbegin() const noexcept
Definition: stl_map.h:439
reverse_iterator rbegin() noexcept
Definition: stl_map.h:384
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:1362
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:1304
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:1215
iterator emplace_hint(const_iterator __pos, _Args &&...__args)
Attempts to build and insert a std::pair into the map.
Definition: stl_map.h:598
Uniform interface to C++98 and C++11 allocators.
const_iterator end() const noexcept
Definition: stl_map.h:375
Common iterator class.
const_reverse_iterator crend() const noexcept
Definition: stl_map.h:448
iterator begin() noexcept
Definition: stl_map.h:348