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