libstdc++
stl_map.h
Go to the documentation of this file.
1 // Map implementation -*- C++ -*-
2 
3 // Copyright (C) 2001-2015 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  /**
71  * @brief A standard container made up of (key,value) pairs, which can be
72  * retrieved based on a key, in logarithmic time.
73  *
74  * @ingroup associative_containers
75  *
76  * @tparam _Key Type of key objects.
77  * @tparam _Tp Type of mapped objects.
78  * @tparam _Compare Comparison function object type, defaults to less<_Key>.
79  * @tparam _Alloc Allocator type, defaults to
80  * allocator<pair<const _Key, _Tp>.
81  *
82  * Meets the requirements of a <a href="tables.html#65">container</a>, a
83  * <a href="tables.html#66">reversible container</a>, and an
84  * <a href="tables.html#69">associative container</a> (using unique keys).
85  * For a @c map<Key,T> the key_type is Key, the mapped_type is T, and the
86  * value_type is std::pair<const Key,T>.
87  *
88  * Maps support bidirectional iterators.
89  *
90  * The private tree data is declared exactly the same way for map and
91  * multimap; the distinction is made entirely in how the tree functions are
92  * called (*_unique versus *_equal, same as the standard).
93  */
94  template <typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
95  typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
96  class map
97  {
98  public:
99  typedef _Key key_type;
100  typedef _Tp mapped_type;
102  typedef _Compare key_compare;
103  typedef _Alloc allocator_type;
104 
105  private:
106  // concept requirements
107  typedef typename _Alloc::value_type _Alloc_value_type;
108  __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
109  __glibcxx_class_requires4(_Compare, bool, _Key, _Key,
110  _BinaryFunctionConcept)
111  __glibcxx_class_requires2(value_type, _Alloc_value_type, _SameTypeConcept)
112 
113  public:
114  class value_compare
115  : public std::binary_function<value_type, value_type, bool>
116  {
117  friend class map<_Key, _Tp, _Compare, _Alloc>;
118  protected:
119  _Compare comp;
120 
121  value_compare(_Compare __c)
122  : comp(__c) { }
123 
124  public:
125  bool operator()(const value_type& __x, const value_type& __y) const
126  { return comp(__x.first, __y.first); }
127  };
128 
129  private:
130  /// This turns a red-black tree into a [multi]map.
132  rebind<value_type>::other _Pair_alloc_type;
133 
134  typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,
135  key_compare, _Pair_alloc_type> _Rep_type;
136 
137  /// The actual tree structure.
138  _Rep_type _M_t;
139 
141 
142  public:
143  // many of these are specified differently in ISO, but the following are
144  // "functionally equivalent"
145  typedef typename _Alloc_traits::pointer pointer;
146  typedef typename _Alloc_traits::const_pointer const_pointer;
147  typedef typename _Alloc_traits::reference reference;
148  typedef typename _Alloc_traits::const_reference const_reference;
149  typedef typename _Rep_type::iterator iterator;
150  typedef typename _Rep_type::const_iterator const_iterator;
151  typedef typename _Rep_type::size_type size_type;
152  typedef typename _Rep_type::difference_type difference_type;
155 
156  // [23.3.1.1] construct/copy/destroy
157  // (get_allocator() is also listed in this section)
158 
159  /**
160  * @brief Default constructor creates no elements.
161  */
162  map()
163 #if __cplusplus >= 201103L
164  noexcept(is_nothrow_default_constructible<allocator_type>::value
165  && is_nothrow_default_constructible<key_compare>::value)
166 #endif
167  : _M_t() { }
168 
169  /**
170  * @brief Creates a %map with no elements.
171  * @param __comp A comparison object.
172  * @param __a An allocator object.
173  */
174  explicit
175  map(const _Compare& __comp,
176  const allocator_type& __a = allocator_type())
177  : _M_t(__comp, _Pair_alloc_type(__a)) { }
178 
179  /**
180  * @brief %Map copy constructor.
181  * @param __x A %map of identical element and allocator types.
182  *
183  * The newly-created %map uses a copy of the allocation object
184  * used by @a __x.
185  */
186  map(const map& __x)
187  : _M_t(__x._M_t) { }
188 
189 #if __cplusplus >= 201103L
190  /**
191  * @brief %Map move constructor.
192  * @param __x A %map of identical element and allocator types.
193  *
194  * The newly-created %map contains the exact contents of @a __x.
195  * The contents of @a __x are a valid, but unspecified %map.
196  */
197  map(map&& __x)
198  noexcept(is_nothrow_copy_constructible<_Compare>::value)
199  : _M_t(std::move(__x._M_t)) { }
200 
201  /**
202  * @brief Builds a %map from an initializer_list.
203  * @param __l An initializer_list.
204  * @param __comp A comparison object.
205  * @param __a An allocator object.
206  *
207  * Create a %map consisting of copies of the elements in the
208  * initializer_list @a __l.
209  * This is linear in N if the range is already sorted, and NlogN
210  * otherwise (where N is @a __l.size()).
211  */
213  const _Compare& __comp = _Compare(),
214  const allocator_type& __a = allocator_type())
215  : _M_t(__comp, _Pair_alloc_type(__a))
216  { _M_t._M_insert_unique(__l.begin(), __l.end()); }
217 
218  /// Allocator-extended default constructor.
219  explicit
220  map(const allocator_type& __a)
221  : _M_t(_Compare(), _Pair_alloc_type(__a)) { }
222 
223  /// Allocator-extended copy constructor.
224  map(const map& __m, const allocator_type& __a)
225  : _M_t(__m._M_t, _Pair_alloc_type(__a)) { }
226 
227  /// Allocator-extended move constructor.
228  map(map&& __m, const allocator_type& __a)
229  noexcept(is_nothrow_copy_constructible<_Compare>::value
230  && _Alloc_traits::_S_always_equal())
231  : _M_t(std::move(__m._M_t), _Pair_alloc_type(__a)) { }
232 
233  /// Allocator-extended initialier-list constructor.
234  map(initializer_list<value_type> __l, const allocator_type& __a)
235  : _M_t(_Compare(), _Pair_alloc_type(__a))
236  { _M_t._M_insert_unique(__l.begin(), __l.end()); }
237 
238  /// Allocator-extended range constructor.
239  template<typename _InputIterator>
240  map(_InputIterator __first, _InputIterator __last,
241  const allocator_type& __a)
242  : _M_t(_Compare(), _Pair_alloc_type(__a))
243  { _M_t._M_insert_unique(__first, __last); }
244 #endif
245 
246  /**
247  * @brief Builds a %map from a range.
248  * @param __first An input iterator.
249  * @param __last An input iterator.
250  *
251  * Create a %map consisting of copies of the elements from
252  * [__first,__last). This is linear in N if the range is
253  * already sorted, and NlogN otherwise (where N is
254  * distance(__first,__last)).
255  */
256  template<typename _InputIterator>
257  map(_InputIterator __first, _InputIterator __last)
258  : _M_t()
259  { _M_t._M_insert_unique(__first, __last); }
260 
261  /**
262  * @brief Builds a %map from a range.
263  * @param __first An input iterator.
264  * @param __last An input iterator.
265  * @param __comp A comparison functor.
266  * @param __a An allocator object.
267  *
268  * Create a %map consisting of copies of the elements from
269  * [__first,__last). This is linear in N if the range is
270  * already sorted, and NlogN otherwise (where N is
271  * distance(__first,__last)).
272  */
273  template<typename _InputIterator>
274  map(_InputIterator __first, _InputIterator __last,
275  const _Compare& __comp,
276  const allocator_type& __a = allocator_type())
277  : _M_t(__comp, _Pair_alloc_type(__a))
278  { _M_t._M_insert_unique(__first, __last); }
279 
280  // FIXME There is no dtor declared, but we should have something
281  // generated by Doxygen. I don't know what tags to add to this
282  // paragraph to make that happen:
283  /**
284  * The dtor only erases the elements, and note that if the elements
285  * themselves are pointers, the pointed-to memory is not touched in any
286  * way. Managing the pointer is the user's responsibility.
287  */
288 
289  /**
290  * @brief %Map assignment operator.
291  * @param __x A %map of identical element and allocator types.
292  *
293  * All the elements of @a __x are copied, but unlike the copy
294  * constructor, the allocator object is not copied.
295  */
296  map&
297  operator=(const map& __x)
298  {
299  _M_t = __x._M_t;
300  return *this;
301  }
302 
303 #if __cplusplus >= 201103L
304  /// Move assignment operator.
305  map&
306  operator=(map&&) = default;
307 
308  /**
309  * @brief %Map list assignment operator.
310  * @param __l An initializer_list.
311  *
312  * This function fills a %map with copies of the elements in the
313  * initializer list @a __l.
314  *
315  * Note that the assignment completely changes the %map and
316  * that the resulting %map's size is the same as the number
317  * of elements assigned. Old data may be lost.
318  */
319  map&
321  {
322  _M_t._M_assign_unique(__l.begin(), __l.end());
323  return *this;
324  }
325 #endif
326 
327  /// Get a copy of the memory allocation object.
328  allocator_type
329  get_allocator() const _GLIBCXX_NOEXCEPT
330  { return allocator_type(_M_t.get_allocator()); }
331 
332  // iterators
333  /**
334  * Returns a read/write iterator that points to the first pair in the
335  * %map.
336  * Iteration is done in ascending order according to the keys.
337  */
338  iterator
339  begin() _GLIBCXX_NOEXCEPT
340  { return _M_t.begin(); }
341 
342  /**
343  * Returns a read-only (constant) iterator that points to the first pair
344  * in the %map. Iteration is done in ascending order according to the
345  * keys.
346  */
347  const_iterator
348  begin() const _GLIBCXX_NOEXCEPT
349  { return _M_t.begin(); }
350 
351  /**
352  * Returns a read/write iterator that points one past the last
353  * pair in the %map. Iteration is done in ascending order
354  * according to the keys.
355  */
356  iterator
357  end() _GLIBCXX_NOEXCEPT
358  { return _M_t.end(); }
359 
360  /**
361  * Returns a read-only (constant) iterator that points one past the last
362  * pair in the %map. Iteration is done in ascending order according to
363  * the keys.
364  */
365  const_iterator
366  end() const _GLIBCXX_NOEXCEPT
367  { return _M_t.end(); }
368 
369  /**
370  * Returns a read/write reverse iterator that points to the last pair in
371  * the %map. Iteration is done in descending order according to the
372  * keys.
373  */
374  reverse_iterator
375  rbegin() _GLIBCXX_NOEXCEPT
376  { return _M_t.rbegin(); }
377 
378  /**
379  * Returns a read-only (constant) reverse iterator that points to the
380  * last pair in the %map. Iteration is done in descending order
381  * according to the keys.
382  */
383  const_reverse_iterator
384  rbegin() const _GLIBCXX_NOEXCEPT
385  { return _M_t.rbegin(); }
386 
387  /**
388  * Returns a read/write reverse iterator that points to one before the
389  * first pair in the %map. Iteration is done in descending order
390  * according to the keys.
391  */
392  reverse_iterator
393  rend() _GLIBCXX_NOEXCEPT
394  { return _M_t.rend(); }
395 
396  /**
397  * Returns a read-only (constant) reverse iterator that points to one
398  * before the first pair in the %map. Iteration is done in descending
399  * order according to the keys.
400  */
401  const_reverse_iterator
402  rend() const _GLIBCXX_NOEXCEPT
403  { return _M_t.rend(); }
404 
405 #if __cplusplus >= 201103L
406  /**
407  * Returns a read-only (constant) iterator that points to the first pair
408  * in the %map. Iteration is done in ascending order according to the
409  * keys.
410  */
411  const_iterator
412  cbegin() const noexcept
413  { return _M_t.begin(); }
414 
415  /**
416  * Returns a read-only (constant) iterator that points one past the last
417  * pair in the %map. Iteration is done in ascending order according to
418  * the keys.
419  */
420  const_iterator
421  cend() const noexcept
422  { return _M_t.end(); }
423 
424  /**
425  * Returns a read-only (constant) reverse iterator that points to the
426  * last pair in the %map. Iteration is done in descending order
427  * according to the keys.
428  */
429  const_reverse_iterator
430  crbegin() const noexcept
431  { return _M_t.rbegin(); }
432 
433  /**
434  * Returns a read-only (constant) reverse iterator that points to one
435  * before the first pair in the %map. Iteration is done in descending
436  * order according to the keys.
437  */
438  const_reverse_iterator
439  crend() const noexcept
440  { return _M_t.rend(); }
441 #endif
442 
443  // capacity
444  /** Returns true if the %map is empty. (Thus begin() would equal
445  * end().)
446  */
447  bool
448  empty() const _GLIBCXX_NOEXCEPT
449  { return _M_t.empty(); }
450 
451  /** Returns the size of the %map. */
452  size_type
453  size() const _GLIBCXX_NOEXCEPT
454  { return _M_t.size(); }
455 
456  /** Returns the maximum size of the %map. */
457  size_type
458  max_size() const _GLIBCXX_NOEXCEPT
459  { return _M_t.max_size(); }
460 
461  // [23.3.1.2] element access
462  /**
463  * @brief Subscript ( @c [] ) access to %map data.
464  * @param __k The key for which data should be retrieved.
465  * @return A reference to the data of the (key,data) %pair.
466  *
467  * Allows for easy lookup with the subscript ( @c [] )
468  * operator. Returns data associated with the key specified in
469  * subscript. If the key does not exist, a pair with that key
470  * is created using default values, which is then returned.
471  *
472  * Lookup requires logarithmic time.
473  */
474  mapped_type&
475  operator[](const key_type& __k)
476  {
477  // concept requirements
478  __glibcxx_function_requires(_DefaultConstructibleConcept<mapped_type>)
479 
480  iterator __i = lower_bound(__k);
481  // __i->first is greater than or equivalent to __k.
482  if (__i == end() || key_comp()(__k, (*__i).first))
483 #if __cplusplus >= 201103L
484  __i = _M_t._M_emplace_hint_unique(__i, std::piecewise_construct,
486  std::tuple<>());
487 #else
488  __i = insert(__i, value_type(__k, mapped_type()));
489 #endif
490  return (*__i).second;
491  }
492 
493 #if __cplusplus >= 201103L
494  mapped_type&
495  operator[](key_type&& __k)
496  {
497  // concept requirements
498  __glibcxx_function_requires(_DefaultConstructibleConcept<mapped_type>)
499 
500  iterator __i = lower_bound(__k);
501  // __i->first is greater than or equivalent to __k.
502  if (__i == end() || key_comp()(__k, (*__i).first))
503  __i = _M_t._M_emplace_hint_unique(__i, std::piecewise_construct,
504  std::forward_as_tuple(std::move(__k)),
505  std::tuple<>());
506  return (*__i).second;
507  }
508 #endif
509 
510  // _GLIBCXX_RESOLVE_LIB_DEFECTS
511  // DR 464. Suggestion for new member functions in standard containers.
512  /**
513  * @brief Access to %map data.
514  * @param __k The key for which data should be retrieved.
515  * @return A reference to the data whose key is equivalent to @a __k, if
516  * such a data is present in the %map.
517  * @throw std::out_of_range If no such data is present.
518  */
519  mapped_type&
520  at(const key_type& __k)
521  {
522  iterator __i = lower_bound(__k);
523  if (__i == end() || key_comp()(__k, (*__i).first))
524  __throw_out_of_range(__N("map::at"));
525  return (*__i).second;
526  }
527 
528  const mapped_type&
529  at(const key_type& __k) const
530  {
531  const_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  // modifiers
538 #if __cplusplus >= 201103L
539  /**
540  * @brief Attempts to build and insert a std::pair into the %map.
541  *
542  * @param __args Arguments used to generate a new pair instance (see
543  * std::piecewise_contruct for passing arguments to each
544  * part of the pair constructor).
545  *
546  * @return A pair, of which the first element is an iterator that points
547  * to the possibly inserted pair, and the second is a bool that
548  * is true if the pair was actually inserted.
549  *
550  * This function attempts to build and insert a (key, value) %pair into
551  * the %map.
552  * A %map relies on unique keys and thus a %pair is only inserted if its
553  * first element (the key) is not already present in the %map.
554  *
555  * Insertion requires logarithmic time.
556  */
557  template<typename... _Args>
559  emplace(_Args&&... __args)
560  { return _M_t._M_emplace_unique(std::forward<_Args>(__args)...); }
561 
562  /**
563  * @brief Attempts to build and insert a std::pair into the %map.
564  *
565  * @param __pos An iterator that serves as a hint as to where the pair
566  * should be inserted.
567  * @param __args Arguments used to generate a new pair instance (see
568  * std::piecewise_contruct for passing arguments to each
569  * part of the pair constructor).
570  * @return An iterator that points to the element with key of the
571  * std::pair built from @a __args (may or may not be that
572  * std::pair).
573  *
574  * This function is not concerned about whether the insertion took place,
575  * and thus does not return a boolean like the single-argument emplace()
576  * does.
577  * Note that the first parameter is only a hint and can potentially
578  * improve the performance of the insertion process. A bad hint would
579  * cause no gains in efficiency.
580  *
581  * See
582  * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
583  * for more on @a hinting.
584  *
585  * Insertion requires logarithmic time (if the hint is not taken).
586  */
587  template<typename... _Args>
588  iterator
589  emplace_hint(const_iterator __pos, _Args&&... __args)
590  {
591  return _M_t._M_emplace_hint_unique(__pos,
592  std::forward<_Args>(__args)...);
593  }
594 #endif
595 
596  /**
597  * @brief Attempts to insert a std::pair into the %map.
598 
599  * @param __x Pair to be inserted (see std::make_pair for easy
600  * creation of pairs).
601  *
602  * @return A pair, of which the first element is an iterator that
603  * points to the possibly inserted pair, and the second is
604  * a bool that is true if the pair was actually inserted.
605  *
606  * This function attempts to insert a (key, value) %pair into the %map.
607  * A %map relies on unique keys and thus a %pair is only inserted if its
608  * first element (the key) is not already present in the %map.
609  *
610  * Insertion requires logarithmic time.
611  */
613  insert(const value_type& __x)
614  { return _M_t._M_insert_unique(__x); }
615 
616 #if __cplusplus >= 201103L
617  template<typename _Pair, typename = typename
618  std::enable_if<std::is_constructible<value_type,
619  _Pair&&>::value>::type>
621  insert(_Pair&& __x)
622  { return _M_t._M_insert_unique(std::forward<_Pair>(__x)); }
623 #endif
624 
625 #if __cplusplus >= 201103L
626  /**
627  * @brief Attempts to insert a list of std::pairs into the %map.
628  * @param __list A std::initializer_list<value_type> of pairs to be
629  * inserted.
630  *
631  * Complexity similar to that of the range constructor.
632  */
633  void
635  { insert(__list.begin(), __list.end()); }
636 #endif
637 
638  /**
639  * @brief Attempts to insert a std::pair into the %map.
640  * @param __position An iterator that serves as a hint as to where the
641  * pair should be inserted.
642  * @param __x Pair to be inserted (see std::make_pair for easy creation
643  * of pairs).
644  * @return An iterator that points to the element with key of
645  * @a __x (may or may not be the %pair passed in).
646  *
647 
648  * This function is not concerned about whether the insertion
649  * took place, and thus does not return a boolean like the
650  * single-argument insert() does. Note that the first
651  * parameter is only a hint and can potentially improve the
652  * performance of the insertion process. A bad hint would
653  * cause no gains in efficiency.
654  *
655  * See
656  * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
657  * for more on @a hinting.
658  *
659  * Insertion requires logarithmic time (if the hint is not taken).
660  */
661  iterator
662 #if __cplusplus >= 201103L
663  insert(const_iterator __position, const value_type& __x)
664 #else
665  insert(iterator __position, const value_type& __x)
666 #endif
667  { return _M_t._M_insert_unique_(__position, __x); }
668 
669 #if __cplusplus >= 201103L
670  template<typename _Pair, typename = typename
671  std::enable_if<std::is_constructible<value_type,
672  _Pair&&>::value>::type>
673  iterator
674  insert(const_iterator __position, _Pair&& __x)
675  { return _M_t._M_insert_unique_(__position,
676  std::forward<_Pair>(__x)); }
677 #endif
678 
679  /**
680  * @brief Template function that attempts to insert a range of elements.
681  * @param __first Iterator pointing to the start of the range to be
682  * inserted.
683  * @param __last Iterator pointing to the end of the range.
684  *
685  * Complexity similar to that of the range constructor.
686  */
687  template<typename _InputIterator>
688  void
689  insert(_InputIterator __first, _InputIterator __last)
690  { _M_t._M_insert_unique(__first, __last); }
691 
692 #if __cplusplus >= 201103L
693  // _GLIBCXX_RESOLVE_LIB_DEFECTS
694  // DR 130. Associative erase should return an iterator.
695  /**
696  * @brief Erases an element from a %map.
697  * @param __position An iterator pointing to the element to be erased.
698  * @return An iterator pointing to the element immediately following
699  * @a position prior to the element being erased. If no such
700  * element exists, end() is returned.
701  *
702  * This function erases an element, pointed to by the given
703  * iterator, from a %map. Note that this function only erases
704  * the element, and that if the element is itself a pointer,
705  * the pointed-to memory is not touched in any way. Managing
706  * the pointer is the user's responsibility.
707  */
708  iterator
709  erase(const_iterator __position)
710  { return _M_t.erase(__position); }
711 
712  // LWG 2059
713  _GLIBCXX_ABI_TAG_CXX11
714  iterator
715  erase(iterator __position)
716  { return _M_t.erase(__position); }
717 #else
718  /**
719  * @brief Erases an element from a %map.
720  * @param __position An iterator pointing to the element to be erased.
721  *
722  * This function erases an element, pointed to by the given
723  * iterator, from a %map. Note that this function only erases
724  * the element, and that if the element is itself a pointer,
725  * the pointed-to memory is not touched in any way. Managing
726  * the pointer is the user's responsibility.
727  */
728  void
729  erase(iterator __position)
730  { _M_t.erase(__position); }
731 #endif
732 
733  /**
734  * @brief Erases elements according to the provided key.
735  * @param __x Key of element to be erased.
736  * @return The number of elements erased.
737  *
738  * This function erases all the elements located by the given key from
739  * a %map.
740  * Note that this function only erases the element, and that if
741  * the element is itself a pointer, the pointed-to memory is not touched
742  * in any way. Managing the pointer is the user's responsibility.
743  */
744  size_type
745  erase(const key_type& __x)
746  { return _M_t.erase(__x); }
747 
748 #if __cplusplus >= 201103L
749  // _GLIBCXX_RESOLVE_LIB_DEFECTS
750  // DR 130. Associative erase should return an iterator.
751  /**
752  * @brief Erases a [first,last) range of elements from a %map.
753  * @param __first Iterator pointing to the start of the range to be
754  * erased.
755  * @param __last Iterator pointing to the end of the range to
756  * be erased.
757  * @return The iterator @a __last.
758  *
759  * This function erases a sequence of elements from a %map.
760  * Note that this function only erases the element, and that if
761  * the element is itself a pointer, the pointed-to memory is not touched
762  * in any way. Managing the pointer is the user's responsibility.
763  */
764  iterator
765  erase(const_iterator __first, const_iterator __last)
766  { return _M_t.erase(__first, __last); }
767 #else
768  /**
769  * @brief Erases a [__first,__last) range of elements from a %map.
770  * @param __first Iterator pointing to the start of the range to be
771  * erased.
772  * @param __last Iterator pointing to the end of the range to
773  * be erased.
774  *
775  * This function erases a sequence of elements from a %map.
776  * Note that this function only erases the element, and that if
777  * the element is itself a pointer, the pointed-to memory is not touched
778  * in any way. Managing the pointer is the user's responsibility.
779  */
780  void
781  erase(iterator __first, iterator __last)
782  { _M_t.erase(__first, __last); }
783 #endif
784 
785  /**
786  * @brief Swaps data with another %map.
787  * @param __x A %map of the same element and allocator types.
788  *
789  * This exchanges the elements between two maps in constant
790  * time. (It is only swapping a pointer, an integer, and an
791  * instance of the @c Compare type (which itself is often
792  * stateless and empty), so it should be quite fast.) Note
793  * that the global std::swap() function is specialized such
794  * that std::swap(m1,m2) will feed to this function.
795  */
796  void
797  swap(map& __x)
798 #if __cplusplus >= 201103L
799  noexcept(_Alloc_traits::_S_nothrow_swap())
800 #endif
801  { _M_t.swap(__x._M_t); }
802 
803  /**
804  * Erases all elements in a %map. Note that this function only
805  * erases the elements, and that if the elements themselves are
806  * pointers, the pointed-to memory is not touched in any way.
807  * Managing the pointer is the user's responsibility.
808  */
809  void
810  clear() _GLIBCXX_NOEXCEPT
811  { _M_t.clear(); }
812 
813  // observers
814  /**
815  * Returns the key comparison object out of which the %map was
816  * constructed.
817  */
818  key_compare
819  key_comp() const
820  { return _M_t.key_comp(); }
821 
822  /**
823  * Returns a value comparison object, built from the key comparison
824  * object out of which the %map was constructed.
825  */
826  value_compare
827  value_comp() const
828  { return value_compare(_M_t.key_comp()); }
829 
830  // [23.3.1.3] map operations
831 
832  //@{
833  /**
834  * @brief Tries to locate an element in a %map.
835  * @param __x Key of (key, value) %pair to be located.
836  * @return Iterator pointing to sought-after element, or end() if not
837  * found.
838  *
839  * This function takes a key and tries to locate the element with which
840  * the key matches. If successful the function returns an iterator
841  * pointing to the sought after %pair. If unsuccessful it returns the
842  * past-the-end ( @c end() ) iterator.
843  */
844 
845  iterator
846  find(const key_type& __x)
847  { return _M_t.find(__x); }
848 
849 #if __cplusplus > 201103L
850  template<typename _Kt>
851  auto
852  find(const _Kt& __x) -> decltype(_M_t._M_find_tr(__x))
853  { return _M_t._M_find_tr(__x); }
854 #endif
855  //@}
856 
857  //@{
858  /**
859  * @brief Tries to locate an element in a %map.
860  * @param __x Key of (key, value) %pair to be located.
861  * @return Read-only (constant) iterator pointing to sought-after
862  * element, or end() if not found.
863  *
864  * This function takes a key and tries to locate the element with which
865  * the key matches. If successful the function returns a constant
866  * iterator pointing to the sought after %pair. If unsuccessful it
867  * returns the past-the-end ( @c end() ) iterator.
868  */
869 
870  const_iterator
871  find(const key_type& __x) const
872  { return _M_t.find(__x); }
873 
874 #if __cplusplus > 201103L
875  template<typename _Kt>
876  auto
877  find(const _Kt& __x) const -> decltype(_M_t._M_find_tr(__x))
878  { return _M_t._M_find_tr(__x); }
879 #endif
880  //@}
881 
882  //@{
883  /**
884  * @brief Finds the number of elements with given key.
885  * @param __x Key of (key, value) pairs to be located.
886  * @return Number of elements with specified key.
887  *
888  * This function only makes sense for multimaps; for map the result will
889  * either be 0 (not present) or 1 (present).
890  */
891  size_type
892  count(const key_type& __x) const
893  { return _M_t.find(__x) == _M_t.end() ? 0 : 1; }
894 
895 #if __cplusplus > 201103L
896  template<typename _Kt>
897  auto
898  count(const _Kt& __x) const -> decltype(_M_t._M_count_tr(__x))
899  { return _M_t._M_count_tr(__x); }
900 #endif
901  //@}
902 
903  //@{
904  /**
905  * @brief Finds the beginning of a subsequence matching given key.
906  * @param __x Key of (key, value) pair to be located.
907  * @return Iterator pointing to first element equal to or greater
908  * than key, or end().
909  *
910  * This function returns the first element of a subsequence of elements
911  * that matches the given key. If unsuccessful it returns an iterator
912  * pointing to the first element that has a greater value than given key
913  * or end() if no such element exists.
914  */
915  iterator
916  lower_bound(const key_type& __x)
917  { return _M_t.lower_bound(__x); }
918 
919 #if __cplusplus > 201103L
920  template<typename _Kt>
921  auto
922  lower_bound(const _Kt& __x)
923  -> decltype(iterator(_M_t._M_lower_bound_tr(__x)))
924  { return iterator(_M_t._M_lower_bound_tr(__x)); }
925 #endif
926  //@}
927 
928  //@{
929  /**
930  * @brief Finds the beginning of a subsequence matching given key.
931  * @param __x Key of (key, value) pair to be located.
932  * @return Read-only (constant) iterator pointing to first element
933  * equal to or greater than key, or end().
934  *
935  * This function returns the first element of a subsequence of elements
936  * that matches the given key. If unsuccessful it returns an iterator
937  * pointing to the first element that has a greater value than given key
938  * or end() if no such element exists.
939  */
940  const_iterator
941  lower_bound(const key_type& __x) const
942  { return _M_t.lower_bound(__x); }
943 
944 #if __cplusplus > 201103L
945  template<typename _Kt>
946  auto
947  lower_bound(const _Kt& __x) const
948  -> decltype(const_iterator(_M_t._M_lower_bound_tr(__x)))
949  { return const_iterator(_M_t._M_lower_bound_tr(__x)); }
950 #endif
951  //@}
952 
953  //@{
954  /**
955  * @brief Finds the end of a subsequence matching given key.
956  * @param __x Key of (key, value) pair to be located.
957  * @return Iterator pointing to the first element
958  * greater than key, or end().
959  */
960  iterator
961  upper_bound(const key_type& __x)
962  { return _M_t.upper_bound(__x); }
963 
964 #if __cplusplus > 201103L
965  template<typename _Kt>
966  auto
967  upper_bound(const _Kt& __x)
968  -> decltype(iterator(_M_t._M_upper_bound_tr(__x)))
969  { return iterator(_M_t._M_upper_bound_tr(__x)); }
970 #endif
971  //@}
972 
973  //@{
974  /**
975  * @brief Finds the end of a subsequence matching given key.
976  * @param __x Key of (key, value) pair to be located.
977  * @return Read-only (constant) iterator pointing to first iterator
978  * greater than key, or end().
979  */
980  const_iterator
981  upper_bound(const key_type& __x) const
982  { return _M_t.upper_bound(__x); }
983 
984 #if __cplusplus > 201103L
985  template<typename _Kt>
986  auto
987  upper_bound(const _Kt& __x) const
988  -> decltype(const_iterator(_M_t._M_upper_bound_tr(__x)))
989  { return const_iterator(_M_t._M_upper_bound_tr(__x)); }
990 #endif
991  //@}
992 
993  //@{
994  /**
995  * @brief Finds a subsequence matching given key.
996  * @param __x Key of (key, value) pairs to be located.
997  * @return Pair of iterators that possibly points to the subsequence
998  * matching given key.
999  *
1000  * This function is equivalent to
1001  * @code
1002  * std::make_pair(c.lower_bound(val),
1003  * c.upper_bound(val))
1004  * @endcode
1005  * (but is faster than making the calls separately).
1006  *
1007  * This function probably only makes sense for multimaps.
1008  */
1010  equal_range(const key_type& __x)
1011  { return _M_t.equal_range(__x); }
1012 
1013 #if __cplusplus > 201103L
1014  template<typename _Kt>
1015  auto
1016  equal_range(const _Kt& __x)
1017  -> decltype(pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)))
1018  { return pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)); }
1019 #endif
1020  //@}
1021 
1022  //@{
1023  /**
1024  * @brief Finds a subsequence matching given key.
1025  * @param __x Key of (key, value) pairs to be located.
1026  * @return Pair of read-only (constant) iterators that possibly points
1027  * to the subsequence matching given key.
1028  *
1029  * This function is equivalent to
1030  * @code
1031  * std::make_pair(c.lower_bound(val),
1032  * c.upper_bound(val))
1033  * @endcode
1034  * (but is faster than making the calls separately).
1035  *
1036  * This function probably only makes sense for multimaps.
1037  */
1039  equal_range(const key_type& __x) const
1040  { return _M_t.equal_range(__x); }
1041 
1042 #if __cplusplus > 201103L
1043  template<typename _Kt>
1044  auto
1045  equal_range(const _Kt& __x) const
1047  _M_t._M_equal_range_tr(__x)))
1048  {
1050  _M_t._M_equal_range_tr(__x));
1051  }
1052 #endif
1053  //@}
1054 
1055  template<typename _K1, typename _T1, typename _C1, typename _A1>
1056  friend bool
1058  const map<_K1, _T1, _C1, _A1>&);
1059 
1060  template<typename _K1, typename _T1, typename _C1, typename _A1>
1061  friend bool
1062  operator<(const map<_K1, _T1, _C1, _A1>&,
1063  const map<_K1, _T1, _C1, _A1>&);
1064  };
1065 
1066  /**
1067  * @brief Map equality comparison.
1068  * @param __x A %map.
1069  * @param __y A %map of the same type as @a x.
1070  * @return True iff the size and elements of the maps are equal.
1071  *
1072  * This is an equivalence relation. It is linear in the size of the
1073  * maps. Maps are considered equivalent if their sizes are equal,
1074  * and if corresponding elements compare equal.
1075  */
1076  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1077  inline bool
1080  { return __x._M_t == __y._M_t; }
1081 
1082  /**
1083  * @brief Map ordering relation.
1084  * @param __x A %map.
1085  * @param __y A %map of the same type as @a x.
1086  * @return True iff @a x is lexicographically less than @a y.
1087  *
1088  * This is a total ordering relation. It is linear in the size of the
1089  * maps. The elements must be comparable with @c <.
1090  *
1091  * See std::lexicographical_compare() for how the determination is made.
1092  */
1093  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1094  inline bool
1095  operator<(const map<_Key, _Tp, _Compare, _Alloc>& __x,
1097  { return __x._M_t < __y._M_t; }
1098 
1099  /// Based on operator==
1100  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1101  inline bool
1104  { return !(__x == __y); }
1105 
1106  /// Based on operator<
1107  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1108  inline bool
1111  { return __y < __x; }
1112 
1113  /// Based on operator<
1114  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1115  inline bool
1116  operator<=(const map<_Key, _Tp, _Compare, _Alloc>& __x,
1118  { return !(__y < __x); }
1119 
1120  /// Based on operator<
1121  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1122  inline bool
1125  { return !(__x < __y); }
1126 
1127  /// See std::map::swap().
1128  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1129  inline void
1132  { __x.swap(__y); }
1133 
1134 _GLIBCXX_END_NAMESPACE_CONTAINER
1135 } // namespace std
1136 
1137 #endif /* _STL_MAP_H */
const_reverse_iterator rbegin() const noexcept
Definition: stl_map.h:384
reverse_iterator rbegin() noexcept
Definition: stl_map.h:375
map(const allocator_type &__a)
Allocator-extended default constructor.
Definition: stl_map.h:220
std::pair< const_iterator, const_iterator > equal_range(const key_type &__x) const
Finds a subsequence matching given key.
Definition: stl_map.h:1039
key_compare key_comp() const
Definition: stl_map.h:819
map() noexcept(is_nothrow_default_constructible< allocator_type >::value &&is_nothrow_default_constructible< key_compare >::value)
Default constructor creates no elements.
Definition: stl_map.h:162
size_type size() const noexcept
Definition: stl_map.h:453
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:1045
allocator_type get_allocator() const noexcept
Get a copy of the memory allocation object.
Definition: stl_map.h:329
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:967
bool operator!=(const map< _Key, _Tp, _Compare, _Alloc > &__x, const map< _Key, _Tp, _Compare, _Alloc > &__y)
Based on operator==.
Definition: stl_map.h:1102
bool operator>=(const map< _Key, _Tp, _Compare, _Alloc > &__x, const map< _Key, _Tp, _Compare, _Alloc > &__y)
Based on operator<.
Definition: stl_map.h:1123
iterator erase(const_iterator __first, const_iterator __last)
Erases a [first,last) range of elements from a map.
Definition: stl_map.h:765
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:1016
bool empty() const noexcept
Definition: stl_map.h:448
mapped_type & at(const key_type &__k)
Access to map data.
Definition: stl_map.h:520
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:987
initializer_list
std::pair< iterator, bool > insert(const value_type &__x)
Attempts to insert a std::pair into the map.
Definition: stl_map.h:613
const_iterator end() const noexcept
Definition: stl_map.h:366
map & operator=(const map &__x)
Map assignment operator.
Definition: stl_map.h:297
void insert(std::initializer_list< value_type > __list)
Attempts to insert a list of std::pairs into the map.
Definition: stl_map.h:634
iterator emplace_hint(const_iterator __pos, _Args &&... __args)
Attempts to build and insert a std::pair into the map.
Definition: stl_map.h:589
size_type max_size() const noexcept
Definition: stl_map.h:458
const_iterator find(const key_type &__x) const
Tries to locate an element in a map.
Definition: stl_map.h:871
const_iterator cbegin() const noexcept
Definition: stl_map.h:412
const_reverse_iterator rend() const noexcept
Definition: stl_map.h:402
const_iterator cend() const noexcept
Definition: stl_map.h:421
mapped_type & operator[](const key_type &__k)
Subscript ( [] ) access to map data.
Definition: stl_map.h:475
map(const map &__x)
Map copy constructor.
Definition: stl_map.h:186
iterator begin() noexcept
Definition: stl_map.h:339
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:898
Uniform interface to C++98 and C++0x allocators.
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:922
void swap(map &__x) noexcept(_Alloc_traits::_S_nothrow_swap())
Swaps data with another map.
Definition: stl_map.h:797
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:228
ISO C++ entities toplevel namespace is std.
map(const map &__m, const allocator_type &__a)
Allocator-extended copy constructor.
Definition: stl_map.h:224
iterator upper_bound(const key_type &__x)
Finds the end of a subsequence matching given key.
Definition: stl_map.h:961
auto find(const _Kt &__x) -> decltype(_M_t._M_find_tr(__x))
Tries to locate an element in a map.
Definition: stl_map.h:852
map(_InputIterator __first, _InputIterator __last)
Builds a map from a range.
Definition: stl_map.h:257
Primary class template, tuple.
Definition: tuple:463
const_iterator lower_bound(const key_type &__x) const
Finds the beginning of a subsequence matching given key.
Definition: stl_map.h:941
size_type erase(const key_type &__x)
Erases elements according to the provided key.
Definition: stl_map.h:745
map(_InputIterator __first, _InputIterator __last, const allocator_type &__a)
Allocator-extended range constructor.
Definition: stl_map.h:240
map & operator=(initializer_list< value_type > __l)
Map list assignment operator.
Definition: stl_map.h:320
iterator insert(const_iterator __position, const value_type &__x)
Attempts to insert a std::pair into the map.
Definition: stl_map.h:663
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:212
constexpr piecewise_construct_t piecewise_construct
piecewise_construct
Definition: stl_pair.h:79
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:96
const_iterator upper_bound(const key_type &__x) const
Finds the end of a subsequence matching given key.
Definition: stl_map.h:981
map(_InputIterator __first, _InputIterator __last, const _Compare &__comp, const allocator_type &__a=allocator_type())
Builds a map from a range.
Definition: stl_map.h:274
A standard container made up of (key,value) pairs, which can be retrieved based on a key...
Definition: stl_map.h:96
map(initializer_list< value_type > __l, const allocator_type &__a)
Allocator-extended initialier-list constructor.
Definition: stl_map.h:234
std::pair< iterator, iterator > equal_range(const key_type &__x)
Finds a subsequence matching given key.
Definition: stl_map.h:1010
const_iterator begin() const noexcept
Definition: stl_map.h:348
iterator lower_bound(const key_type &__x)
Finds the beginning of a subsequence matching given key.
Definition: stl_map.h:916
bool operator>(const map< _Key, _Tp, _Compare, _Alloc > &__x, const map< _Key, _Tp, _Compare, _Alloc > &__y)
Based on operator<.
Definition: stl_map.h:1109
const_reverse_iterator crbegin() const noexcept
Definition: stl_map.h:430
map(map &&__x) noexcept(is_nothrow_copy_constructible< _Compare >::value)
Map move constructor.
Definition: stl_map.h:197
std::pair< iterator, bool > emplace(_Args &&... __args)
Attempts to build and insert a std::pair into the map.
Definition: stl_map.h:559
bool operator==(const map< _Key, _Tp, _Compare, _Alloc > &__x, const map< _Key, _Tp, _Compare, _Alloc > &__y)
Map equality comparison.
Definition: stl_map.h:1078
iterator end() noexcept
Definition: stl_map.h:357
reverse_iterator rend() noexcept
Definition: stl_map.h:393
iterator erase(const_iterator __position)
Erases an element from a map.
Definition: stl_map.h:709
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:947
void clear() noexcept
Definition: stl_map.h:810
const_reverse_iterator crend() const noexcept
Definition: stl_map.h:439
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:877
value_compare value_comp() const
Definition: stl_map.h:827
map(const _Compare &__comp, const allocator_type &__a=allocator_type())
Creates a map with no elements.
Definition: stl_map.h:175
_T1 first
second_type is the second bound type
Definition: stl_pair.h:101
void insert(_InputIterator __first, _InputIterator __last)
Template function that attempts to insert a range of elements.
Definition: stl_map.h:689
iterator find(const key_type &__x)
Tries to locate an element in a map.
Definition: stl_map.h:846
size_type count(const key_type &__x) const
Finds the number of elements with given key.
Definition: stl_map.h:892