libstdc++
stl_map.h
Go to the documentation of this file.
1 // Map implementation -*- C++ -*-
2 
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010,
4 // 2011 Free Software Foundation, Inc.
5 //
6 // This file is part of the GNU ISO C++ Library. This library is free
7 // software; you can redistribute it and/or modify it under the
8 // terms of the GNU General Public License as published by the
9 // Free Software Foundation; either version 3, or (at your option)
10 // any later version.
11 
12 // This library is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 // GNU General Public License for more details.
16 
17 // Under Section 7 of GPL version 3, you are granted additional
18 // permissions described in the GCC Runtime Library Exception, version
19 // 3.1, as published by the Free Software Foundation.
20 
21 // You should have received a copy of the GNU General Public License and
22 // a copy of the GCC Runtime Library Exception along with this program;
23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
24 // <http://www.gnu.org/licenses/>.
25 
26 /*
27  *
28  * Copyright (c) 1994
29  * Hewlett-Packard Company
30  *
31  * Permission to use, copy, modify, distribute and sell this software
32  * and its documentation for any purpose is hereby granted without fee,
33  * provided that the above copyright notice appear in all copies and
34  * that both that copyright notice and this permission notice appear
35  * in supporting documentation. Hewlett-Packard Company makes no
36  * representations about the suitability of this software for any
37  * purpose. It is provided "as is" without express or implied warranty.
38  *
39  *
40  * Copyright (c) 1996,1997
41  * Silicon Graphics Computer Systems, Inc.
42  *
43  * Permission to use, copy, modify, distribute and sell this software
44  * and its documentation for any purpose is hereby granted without fee,
45  * provided that the above copyright notice appear in all copies and
46  * that both that copyright notice and this permission notice appear
47  * in supporting documentation. Silicon Graphics makes no
48  * representations about the suitability of this software for any
49  * purpose. It is provided "as is" without express or implied warranty.
50  */
51 
52 /** @file bits/stl_map.h
53  * This is an internal header file, included by other library headers.
54  * Do not attempt to use it directly. @headername{map}
55  */
56 
57 #ifndef _STL_MAP_H
58 #define _STL_MAP_H 1
59 
60 #include <bits/functexcept.h>
61 #include <bits/concept_check.h>
62 #include <initializer_list>
63 
64 namespace std _GLIBCXX_VISIBILITY(default)
65 {
66 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
67 
68  /**
69  * @brief A standard container made up of (key,value) pairs, which can be
70  * retrieved based on a key, in logarithmic time.
71  *
72  * @ingroup associative_containers
73  *
74  * Meets the requirements of a <a href="tables.html#65">container</a>, a
75  * <a href="tables.html#66">reversible container</a>, and an
76  * <a href="tables.html#69">associative container</a> (using unique keys).
77  * For a @c map<Key,T> the key_type is Key, the mapped_type is T, and the
78  * value_type is std::pair<const Key,T>.
79  *
80  * Maps support bidirectional iterators.
81  *
82  * The private tree data is declared exactly the same way for map and
83  * multimap; the distinction is made entirely in how the tree functions are
84  * called (*_unique versus *_equal, same as the standard).
85  */
86  template <typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
87  typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
88  class map
89  {
90  public:
91  typedef _Key key_type;
92  typedef _Tp mapped_type;
94  typedef _Compare key_compare;
95  typedef _Alloc allocator_type;
96 
97  private:
98  // concept requirements
99  typedef typename _Alloc::value_type _Alloc_value_type;
100  __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
101  __glibcxx_class_requires4(_Compare, bool, _Key, _Key,
102  _BinaryFunctionConcept)
103  __glibcxx_class_requires2(value_type, _Alloc_value_type, _SameTypeConcept)
104 
105  public:
106  class value_compare
107  : public std::binary_function<value_type, value_type, bool>
108  {
109  friend class map<_Key, _Tp, _Compare, _Alloc>;
110  protected:
111  _Compare comp;
112 
113  value_compare(_Compare __c)
114  : comp(__c) { }
115 
116  public:
117  bool operator()(const value_type& __x, const value_type& __y) const
118  { return comp(__x.first, __y.first); }
119  };
120 
121  private:
122  /// This turns a red-black tree into a [multi]map.
123  typedef typename _Alloc::template rebind<value_type>::other
124  _Pair_alloc_type;
125 
126  typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,
127  key_compare, _Pair_alloc_type> _Rep_type;
128 
129  /// The actual tree structure.
130  _Rep_type _M_t;
131 
132  public:
133  // many of these are specified differently in ISO, but the following are
134  // "functionally equivalent"
135  typedef typename _Pair_alloc_type::pointer pointer;
136  typedef typename _Pair_alloc_type::const_pointer const_pointer;
137  typedef typename _Pair_alloc_type::reference reference;
138  typedef typename _Pair_alloc_type::const_reference const_reference;
139  typedef typename _Rep_type::iterator iterator;
140  typedef typename _Rep_type::const_iterator const_iterator;
141  typedef typename _Rep_type::size_type size_type;
142  typedef typename _Rep_type::difference_type difference_type;
145 
146  // [23.3.1.1] construct/copy/destroy
147  // (get_allocator() is normally listed in this section, but seems to have
148  // been accidentally omitted in the printed standard)
149  /**
150  * @brief Default constructor creates no elements.
151  */
152  map()
153  : _M_t() { }
154 
155  /**
156  * @brief Creates a %map with no elements.
157  * @param comp A comparison object.
158  * @param a An allocator object.
159  */
160  explicit
161  map(const _Compare& __comp,
162  const allocator_type& __a = allocator_type())
163  : _M_t(__comp, __a) { }
164 
165  /**
166  * @brief %Map copy constructor.
167  * @param x A %map of identical element and allocator types.
168  *
169  * The newly-created %map uses a copy of the allocation object
170  * used by @a x.
171  */
172  map(const map& __x)
173  : _M_t(__x._M_t) { }
174 
175 #ifdef __GXX_EXPERIMENTAL_CXX0X__
176  /**
177  * @brief %Map move constructor.
178  * @param x A %map of identical element and allocator types.
179  *
180  * The newly-created %map contains the exact contents of @a x.
181  * The contents of @a x are a valid, but unspecified %map.
182  */
183  map(map&& __x)
184  : _M_t(std::move(__x._M_t)) { }
185 
186  /**
187  * @brief Builds a %map from an initializer_list.
188  * @param l An initializer_list.
189  * @param comp A comparison object.
190  * @param a An allocator object.
191  *
192  * Create a %map consisting of copies of the elements in the
193  * initializer_list @a l.
194  * This is linear in N if the range is already sorted, and NlogN
195  * otherwise (where N is @a l.size()).
196  */
198  const _Compare& __c = _Compare(),
199  const allocator_type& __a = allocator_type())
200  : _M_t(__c, __a)
201  { _M_t._M_insert_unique(__l.begin(), __l.end()); }
202 #endif
203 
204  /**
205  * @brief Builds a %map from a range.
206  * @param first An input iterator.
207  * @param last An input iterator.
208  *
209  * Create a %map consisting of copies of the elements from [first,last).
210  * This is linear in N if the range is already sorted, and NlogN
211  * otherwise (where N is distance(first,last)).
212  */
213  template<typename _InputIterator>
214  map(_InputIterator __first, _InputIterator __last)
215  : _M_t()
216  { _M_t._M_insert_unique(__first, __last); }
217 
218  /**
219  * @brief Builds a %map from a range.
220  * @param first An input iterator.
221  * @param last An input iterator.
222  * @param comp A comparison functor.
223  * @param a An allocator object.
224  *
225  * Create a %map consisting of copies of the elements from [first,last).
226  * This is linear in N if the range is already sorted, and NlogN
227  * otherwise (where N is distance(first,last)).
228  */
229  template<typename _InputIterator>
230  map(_InputIterator __first, _InputIterator __last,
231  const _Compare& __comp,
232  const allocator_type& __a = allocator_type())
233  : _M_t(__comp, __a)
234  { _M_t._M_insert_unique(__first, __last); }
235 
236  // FIXME There is no dtor declared, but we should have something
237  // generated by Doxygen. I don't know what tags to add to this
238  // paragraph to make that happen:
239  /**
240  * The dtor only erases the elements, and note that if the elements
241  * themselves are pointers, the pointed-to memory is not touched in any
242  * way. Managing the pointer is the user's responsibility.
243  */
244 
245  /**
246  * @brief %Map assignment operator.
247  * @param x A %map of identical element and allocator types.
248  *
249  * All the elements of @a x are copied, but unlike the copy constructor,
250  * the allocator object is not copied.
251  */
252  map&
253  operator=(const map& __x)
254  {
255  _M_t = __x._M_t;
256  return *this;
257  }
258 
259 #ifdef __GXX_EXPERIMENTAL_CXX0X__
260  /**
261  * @brief %Map move assignment operator.
262  * @param x A %map of identical element and allocator types.
263  *
264  * The contents of @a x are moved into this map (without copying).
265  * @a x is a valid, but unspecified %map.
266  */
267  map&
268  operator=(map&& __x)
269  {
270  // NB: DR 1204.
271  // NB: DR 675.
272  this->clear();
273  this->swap(__x);
274  return *this;
275  }
276 
277  /**
278  * @brief %Map list assignment operator.
279  * @param l An initializer_list.
280  *
281  * This function fills a %map with copies of the elements in the
282  * initializer list @a l.
283  *
284  * Note that the assignment completely changes the %map and
285  * that the resulting %map's size is the same as the number
286  * of elements assigned. Old data may be lost.
287  */
288  map&
290  {
291  this->clear();
292  this->insert(__l.begin(), __l.end());
293  return *this;
294  }
295 #endif
296 
297  /// Get a copy of the memory allocation object.
298  allocator_type
300  { return _M_t.get_allocator(); }
301 
302  // iterators
303  /**
304  * Returns a read/write iterator that points to the first pair in the
305  * %map.
306  * Iteration is done in ascending order according to the keys.
307  */
308  iterator
310  { return _M_t.begin(); }
311 
312  /**
313  * Returns a read-only (constant) iterator that points to the first pair
314  * in the %map. Iteration is done in ascending order according to the
315  * keys.
316  */
317  const_iterator
318  begin() const
319  { return _M_t.begin(); }
320 
321  /**
322  * Returns a read/write iterator that points one past the last
323  * pair in the %map. Iteration is done in ascending order
324  * according to the keys.
325  */
326  iterator
327  end()
328  { return _M_t.end(); }
329 
330  /**
331  * Returns a read-only (constant) iterator that points one past the last
332  * pair in the %map. Iteration is done in ascending order according to
333  * the keys.
334  */
335  const_iterator
336  end() const
337  { return _M_t.end(); }
338 
339  /**
340  * Returns a read/write reverse iterator that points to the last pair in
341  * the %map. Iteration is done in descending order according to the
342  * keys.
343  */
346  { return _M_t.rbegin(); }
347 
348  /**
349  * Returns a read-only (constant) reverse iterator that points to the
350  * last pair in the %map. Iteration is done in descending order
351  * according to the keys.
352  */
353  const_reverse_iterator
354  rbegin() const
355  { return _M_t.rbegin(); }
356 
357  /**
358  * Returns a read/write reverse iterator that points to one before the
359  * first pair in the %map. Iteration is done in descending order
360  * according to the keys.
361  */
364  { return _M_t.rend(); }
365 
366  /**
367  * Returns a read-only (constant) reverse iterator that points to one
368  * before the first pair in the %map. Iteration is done in descending
369  * order according to the keys.
370  */
371  const_reverse_iterator
372  rend() const
373  { return _M_t.rend(); }
374 
375 #ifdef __GXX_EXPERIMENTAL_CXX0X__
376  /**
377  * Returns a read-only (constant) iterator that points to the first pair
378  * in the %map. Iteration is done in ascending order according to the
379  * keys.
380  */
381  const_iterator
382  cbegin() const
383  { return _M_t.begin(); }
384 
385  /**
386  * Returns a read-only (constant) iterator that points one past the last
387  * pair in the %map. Iteration is done in ascending order according to
388  * the keys.
389  */
390  const_iterator
391  cend() const
392  { return _M_t.end(); }
393 
394  /**
395  * Returns a read-only (constant) reverse iterator that points to the
396  * last pair in the %map. Iteration is done in descending order
397  * according to the keys.
398  */
399  const_reverse_iterator
400  crbegin() const
401  { return _M_t.rbegin(); }
402 
403  /**
404  * Returns a read-only (constant) reverse iterator that points to one
405  * before the first pair in the %map. Iteration is done in descending
406  * order according to the keys.
407  */
408  const_reverse_iterator
409  crend() const
410  { return _M_t.rend(); }
411 #endif
412 
413  // capacity
414  /** Returns true if the %map is empty. (Thus begin() would equal
415  * end().)
416  */
417  bool
418  empty() const
419  { return _M_t.empty(); }
420 
421  /** Returns the size of the %map. */
422  size_type
423  size() const
424  { return _M_t.size(); }
425 
426  /** Returns the maximum size of the %map. */
427  size_type
428  max_size() const
429  { return _M_t.max_size(); }
430 
431  // [23.3.1.2] element access
432  /**
433  * @brief Subscript ( @c [] ) access to %map data.
434  * @param k The key for which data should be retrieved.
435  * @return A reference to the data of the (key,data) %pair.
436  *
437  * Allows for easy lookup with the subscript ( @c [] )
438  * operator. Returns data associated with the key specified in
439  * subscript. If the key does not exist, a pair with that key
440  * is created using default values, which is then returned.
441  *
442  * Lookup requires logarithmic time.
443  */
444  mapped_type&
445  operator[](const key_type& __k)
446  {
447  // concept requirements
448  __glibcxx_function_requires(_DefaultConstructibleConcept<mapped_type>)
449 
450  iterator __i = lower_bound(__k);
451  // __i->first is greater than or equivalent to __k.
452  if (__i == end() || key_comp()(__k, (*__i).first))
453  __i = insert(__i, value_type(__k, mapped_type()));
454  return (*__i).second;
455  }
456 
457 #ifdef __GXX_EXPERIMENTAL_CXX0X__
458  mapped_type&
459  operator[](key_type&& __k)
460  {
461  // concept requirements
462  __glibcxx_function_requires(_DefaultConstructibleConcept<mapped_type>)
463 
464  iterator __i = lower_bound(__k);
465  // __i->first is greater than or equivalent to __k.
466  if (__i == end() || key_comp()(__k, (*__i).first))
467  __i = insert(__i, std::make_pair(std::move(__k), mapped_type()));
468  return (*__i).second;
469  }
470 #endif
471 
472  // _GLIBCXX_RESOLVE_LIB_DEFECTS
473  // DR 464. Suggestion for new member functions in standard containers.
474  /**
475  * @brief Access to %map data.
476  * @param k The key for which data should be retrieved.
477  * @return A reference to the data whose key is equivalent to @a k, if
478  * such a data is present in the %map.
479  * @throw std::out_of_range If no such data is present.
480  */
481  mapped_type&
482  at(const key_type& __k)
483  {
484  iterator __i = lower_bound(__k);
485  if (__i == end() || key_comp()(__k, (*__i).first))
486  __throw_out_of_range(__N("map::at"));
487  return (*__i).second;
488  }
489 
490  const mapped_type&
491  at(const key_type& __k) const
492  {
493  const_iterator __i = lower_bound(__k);
494  if (__i == end() || key_comp()(__k, (*__i).first))
495  __throw_out_of_range(__N("map::at"));
496  return (*__i).second;
497  }
498 
499  // modifiers
500  /**
501  * @brief Attempts to insert a std::pair into the %map.
502 
503  * @param x Pair to be inserted (see std::make_pair for easy creation
504  * of pairs).
505 
506  * @return A pair, of which the first element is an iterator that
507  * points to the possibly inserted pair, and the second is
508  * a bool that is true if the pair was actually inserted.
509  *
510  * This function attempts to insert a (key, value) %pair into the %map.
511  * A %map relies on unique keys and thus a %pair is only inserted if its
512  * first element (the key) is not already present in the %map.
513  *
514  * Insertion requires logarithmic time.
515  */
517  insert(const value_type& __x)
518  { return _M_t._M_insert_unique(__x); }
519 
520 #ifdef __GXX_EXPERIMENTAL_CXX0X__
521  template<typename _Pair, typename = typename
523  value_type>::value>::type>
525  insert(_Pair&& __x)
526  { return _M_t._M_insert_unique(std::forward<_Pair>(__x)); }
527 #endif
528 
529 #ifdef __GXX_EXPERIMENTAL_CXX0X__
530  /**
531  * @brief Attempts to insert a list of std::pairs into the %map.
532  * @param list A std::initializer_list<value_type> of pairs to be
533  * inserted.
534  *
535  * Complexity similar to that of the range constructor.
536  */
537  void
539  { insert(__list.begin(), __list.end()); }
540 #endif
541 
542  /**
543  * @brief Attempts to insert a std::pair into the %map.
544  * @param position An iterator that serves as a hint as to where the
545  * pair should be inserted.
546  * @param x Pair to be inserted (see std::make_pair for easy creation
547  * of pairs).
548  * @return An iterator that points to the element with key of @a x (may
549  * or may not be the %pair passed in).
550  *
551 
552  * This function is not concerned about whether the insertion
553  * took place, and thus does not return a boolean like the
554  * single-argument insert() does. Note that the first
555  * parameter is only a hint and can potentially improve the
556  * performance of the insertion process. A bad hint would
557  * cause no gains in efficiency.
558  *
559  * See
560  * http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html
561  * for more on @a hinting.
562  *
563  * Insertion requires logarithmic time (if the hint is not taken).
564  */
565  iterator
566 #ifdef __GXX_EXPERIMENTAL_CXX0X__
567  insert(const_iterator __position, const value_type& __x)
568 #else
569  insert(iterator __position, const value_type& __x)
570 #endif
571  { return _M_t._M_insert_unique_(__position, __x); }
572 
573 #ifdef __GXX_EXPERIMENTAL_CXX0X__
574  template<typename _Pair, typename = typename
576  value_type>::value>::type>
577  iterator
578  insert(const_iterator __position, _Pair&& __x)
579  { return _M_t._M_insert_unique_(__position,
580  std::forward<_Pair>(__x)); }
581 #endif
582 
583  /**
584  * @brief Template function that attempts to insert a range of elements.
585  * @param first Iterator pointing to the start of the range to be
586  * inserted.
587  * @param last Iterator pointing to the end of the range.
588  *
589  * Complexity similar to that of the range constructor.
590  */
591  template<typename _InputIterator>
592  void
593  insert(_InputIterator __first, _InputIterator __last)
594  { _M_t._M_insert_unique(__first, __last); }
595 
596 #ifdef __GXX_EXPERIMENTAL_CXX0X__
597  // _GLIBCXX_RESOLVE_LIB_DEFECTS
598  // DR 130. Associative erase should return an iterator.
599  /**
600  * @brief Erases an element from a %map.
601  * @param position An iterator pointing to the element to be erased.
602  * @return An iterator pointing to the element immediately following
603  * @a position prior to the element being erased. If no such
604  * element exists, end() is returned.
605  *
606  * This function erases an element, pointed to by the given
607  * iterator, from a %map. Note that this function only erases
608  * the element, and that if the element is itself a pointer,
609  * the pointed-to memory is not touched in any way. Managing
610  * the pointer is the user's responsibility.
611  */
612  iterator
613  erase(const_iterator __position)
614  { return _M_t.erase(__position); }
615 
616  // LWG 2059.
617  iterator
618  erase(iterator __position)
619  { return _M_t.erase(__position); }
620 #else
621  /**
622  * @brief Erases an element from a %map.
623  * @param position An iterator pointing to the element to be erased.
624  *
625  * This function erases an element, pointed to by the given
626  * iterator, from a %map. Note that this function only erases
627  * the element, and that if the element is itself a pointer,
628  * the pointed-to memory is not touched in any way. Managing
629  * the pointer is the user's responsibility.
630  */
631  void
632  erase(iterator __position)
633  { _M_t.erase(__position); }
634 #endif
635 
636  /**
637  * @brief Erases elements according to the provided key.
638  * @param x Key of element to be erased.
639  * @return The number of elements erased.
640  *
641  * This function erases all the elements located by the given key from
642  * a %map.
643  * Note that this function only erases the element, and that if
644  * the element is itself a pointer, the pointed-to memory is not touched
645  * in any way. Managing the pointer is the user's responsibility.
646  */
647  size_type
648  erase(const key_type& __x)
649  { return _M_t.erase(__x); }
650 
651 #ifdef __GXX_EXPERIMENTAL_CXX0X__
652  // _GLIBCXX_RESOLVE_LIB_DEFECTS
653  // DR 130. Associative erase should return an iterator.
654  /**
655  * @brief Erases a [first,last) range of elements from a %map.
656  * @param first Iterator pointing to the start of the range to be
657  * erased.
658  * @param last Iterator pointing to the end of the range to be erased.
659  * @return The iterator @a last.
660  *
661  * This function erases a sequence of elements from a %map.
662  * Note that this function only erases the element, and that if
663  * the element is itself a pointer, the pointed-to memory is not touched
664  * in any way. Managing the pointer is the user's responsibility.
665  */
666  iterator
667  erase(const_iterator __first, const_iterator __last)
668  { return _M_t.erase(__first, __last); }
669 #else
670  /**
671  * @brief Erases a [first,last) range of elements from a %map.
672  * @param first Iterator pointing to the start of the range to be
673  * erased.
674  * @param last Iterator pointing to the end of the range to be erased.
675  *
676  * This function erases a sequence of elements from a %map.
677  * Note that this function only erases the element, and that if
678  * the element is itself a pointer, the pointed-to memory is not touched
679  * in any way. Managing the pointer is the user's responsibility.
680  */
681  void
682  erase(iterator __first, iterator __last)
683  { _M_t.erase(__first, __last); }
684 #endif
685 
686  /**
687  * @brief Swaps data with another %map.
688  * @param x A %map of the same element and allocator types.
689  *
690  * This exchanges the elements between two maps in constant
691  * time. (It is only swapping a pointer, an integer, and an
692  * instance of the @c Compare type (which itself is often
693  * stateless and empty), so it should be quite fast.) Note
694  * that the global std::swap() function is specialized such
695  * that std::swap(m1,m2) will feed to this function.
696  */
697  void
698  swap(map& __x)
699  { _M_t.swap(__x._M_t); }
700 
701  /**
702  * Erases all elements in a %map. Note that this function only
703  * erases the elements, and that if the elements themselves are
704  * pointers, the pointed-to memory is not touched in any way.
705  * Managing the pointer is the user's responsibility.
706  */
707  void
709  { _M_t.clear(); }
710 
711  // observers
712  /**
713  * Returns the key comparison object out of which the %map was
714  * constructed.
715  */
716  key_compare
717  key_comp() const
718  { return _M_t.key_comp(); }
719 
720  /**
721  * Returns a value comparison object, built from the key comparison
722  * object out of which the %map was constructed.
723  */
724  value_compare
725  value_comp() const
726  { return value_compare(_M_t.key_comp()); }
727 
728  // [23.3.1.3] map operations
729  /**
730  * @brief Tries to locate an element in a %map.
731  * @param x Key of (key, value) %pair to be located.
732  * @return Iterator pointing to sought-after element, or end() if not
733  * found.
734  *
735  * This function takes a key and tries to locate the element with which
736  * the key matches. If successful the function returns an iterator
737  * pointing to the sought after %pair. If unsuccessful it returns the
738  * past-the-end ( @c end() ) iterator.
739  */
740  iterator
741  find(const key_type& __x)
742  { return _M_t.find(__x); }
743 
744  /**
745  * @brief Tries to locate an element in a %map.
746  * @param x Key of (key, value) %pair to be located.
747  * @return Read-only (constant) iterator pointing to sought-after
748  * element, or end() if not found.
749  *
750  * This function takes a key and tries to locate the element with which
751  * the key matches. If successful the function returns a constant
752  * iterator pointing to the sought after %pair. If unsuccessful it
753  * returns the past-the-end ( @c end() ) iterator.
754  */
755  const_iterator
756  find(const key_type& __x) const
757  { return _M_t.find(__x); }
758 
759  /**
760  * @brief Finds the number of elements with given key.
761  * @param x Key of (key, value) pairs to be located.
762  * @return Number of elements with specified key.
763  *
764  * This function only makes sense for multimaps; for map the result will
765  * either be 0 (not present) or 1 (present).
766  */
767  size_type
768  count(const key_type& __x) const
769  { return _M_t.find(__x) == _M_t.end() ? 0 : 1; }
770 
771  /**
772  * @brief Finds the beginning of a subsequence matching given key.
773  * @param x Key of (key, value) pair to be located.
774  * @return Iterator pointing to first element equal to or greater
775  * than key, or end().
776  *
777  * This function returns the first element of a subsequence of elements
778  * that matches the given key. If unsuccessful it returns an iterator
779  * pointing to the first element that has a greater value than given key
780  * or end() if no such element exists.
781  */
782  iterator
783  lower_bound(const key_type& __x)
784  { return _M_t.lower_bound(__x); }
785 
786  /**
787  * @brief Finds the beginning of a subsequence matching given key.
788  * @param x Key of (key, value) pair to be located.
789  * @return Read-only (constant) iterator pointing to first element
790  * equal to or greater than key, or end().
791  *
792  * This function returns the first element of a subsequence of elements
793  * that matches the given key. If unsuccessful it returns an iterator
794  * pointing to the first element that has a greater value than given key
795  * or end() if no such element exists.
796  */
797  const_iterator
798  lower_bound(const key_type& __x) const
799  { return _M_t.lower_bound(__x); }
800 
801  /**
802  * @brief Finds the end of a subsequence matching given key.
803  * @param x Key of (key, value) pair to be located.
804  * @return Iterator pointing to the first element
805  * greater than key, or end().
806  */
807  iterator
808  upper_bound(const key_type& __x)
809  { return _M_t.upper_bound(__x); }
810 
811  /**
812  * @brief Finds the end of a subsequence matching given key.
813  * @param x Key of (key, value) pair to be located.
814  * @return Read-only (constant) iterator pointing to first iterator
815  * greater than key, or end().
816  */
817  const_iterator
818  upper_bound(const key_type& __x) const
819  { return _M_t.upper_bound(__x); }
820 
821  /**
822  * @brief Finds a subsequence matching given key.
823  * @param x Key of (key, value) pairs to be located.
824  * @return Pair of iterators that possibly points to the subsequence
825  * matching given key.
826  *
827  * This function is equivalent to
828  * @code
829  * std::make_pair(c.lower_bound(val),
830  * c.upper_bound(val))
831  * @endcode
832  * (but is faster than making the calls separately).
833  *
834  * This function probably only makes sense for multimaps.
835  */
837  equal_range(const key_type& __x)
838  { return _M_t.equal_range(__x); }
839 
840  /**
841  * @brief Finds a subsequence matching given key.
842  * @param x Key of (key, value) pairs to be located.
843  * @return Pair of read-only (constant) iterators that possibly points
844  * to the subsequence matching given key.
845  *
846  * This function is equivalent to
847  * @code
848  * std::make_pair(c.lower_bound(val),
849  * c.upper_bound(val))
850  * @endcode
851  * (but is faster than making the calls separately).
852  *
853  * This function probably only makes sense for multimaps.
854  */
856  equal_range(const key_type& __x) const
857  { return _M_t.equal_range(__x); }
858 
859  template<typename _K1, typename _T1, typename _C1, typename _A1>
860  friend bool
862  const map<_K1, _T1, _C1, _A1>&);
863 
864  template<typename _K1, typename _T1, typename _C1, typename _A1>
865  friend bool
866  operator<(const map<_K1, _T1, _C1, _A1>&,
867  const map<_K1, _T1, _C1, _A1>&);
868  };
869 
870  /**
871  * @brief Map equality comparison.
872  * @param x A %map.
873  * @param y A %map of the same type as @a x.
874  * @return True iff the size and elements of the maps are equal.
875  *
876  * This is an equivalence relation. It is linear in the size of the
877  * maps. Maps are considered equivalent if their sizes are equal,
878  * and if corresponding elements compare equal.
879  */
880  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
881  inline bool
884  { return __x._M_t == __y._M_t; }
885 
886  /**
887  * @brief Map ordering relation.
888  * @param x A %map.
889  * @param y A %map of the same type as @a x.
890  * @return True iff @a x is lexicographically less than @a y.
891  *
892  * This is a total ordering relation. It is linear in the size of the
893  * maps. The elements must be comparable with @c <.
894  *
895  * See std::lexicographical_compare() for how the determination is made.
896  */
897  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
898  inline bool
899  operator<(const map<_Key, _Tp, _Compare, _Alloc>& __x,
901  { return __x._M_t < __y._M_t; }
902 
903  /// Based on operator==
904  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
905  inline bool
908  { return !(__x == __y); }
909 
910  /// Based on operator<
911  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
912  inline bool
915  { return __y < __x; }
916 
917  /// Based on operator<
918  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
919  inline bool
920  operator<=(const map<_Key, _Tp, _Compare, _Alloc>& __x,
922  { return !(__y < __x); }
923 
924  /// Based on operator<
925  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
926  inline bool
929  { return !(__x < __y); }
930 
931  /// See std::map::swap().
932  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
933  inline void
936  { __x.swap(__y); }
937 
938 _GLIBCXX_END_NAMESPACE_CONTAINER
939 } // namespace std
940 
941 #endif /* _STL_MAP_H */
map(_InputIterator __first, _InputIterator __last, const _Compare &__comp, const allocator_type &__a=allocator_type())
Builds a map from a range.
Definition: stl_map.h:230
map & operator=(map &&__x)
Map move assignment operator.
Definition: stl_map.h:268
key_compare key_comp() const
Definition: stl_map.h:717
map(_InputIterator __first, _InputIterator __last)
Builds a map from a range.
Definition: stl_map.h:214
const_iterator cend() const
Definition: stl_map.h:391
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:87
_T1 first
second_type is the second bound type
Definition: stl_pair.h:92
size_type count(const key_type &__x) const
Finds the number of elements with given key.
Definition: stl_map.h:768
const_iterator begin() const
Definition: stl_map.h:318
iterator erase(const_iterator __first, const_iterator __last)
Erases a [first,last) range of elements from a map.
Definition: stl_map.h:667
bool empty() const
Definition: stl_map.h:418
void clear()
Definition: stl_map.h:708
void swap(map &__x)
Swaps data with another map.
Definition: stl_map.h:698
map()
Default constructor creates no elements.
Definition: stl_map.h:152
bool operator>=(const map< _Key, _Tp, _Compare, _Alloc > &__x, const map< _Key, _Tp, _Compare, _Alloc > &__y)
Based on operator<.
Definition: stl_map.h:927
std::pair< iterator, iterator > equal_range(const key_type &__x)
Finds a subsequence matching given key.
Definition: stl_map.h:837
map(const map &__x)
Map copy constructor.
Definition: stl_map.h:172
map(initializer_list< value_type > __l, const _Compare &__c=_Compare(), const allocator_type &__a=allocator_type())
Builds a map from an initializer_list.
Definition: stl_map.h:197
bool operator>(const map< _Key, _Tp, _Compare, _Alloc > &__x, const map< _Key, _Tp, _Compare, _Alloc > &__y)
Based on operator<.
Definition: stl_map.h:913
mapped_type & operator[](const key_type &__k)
Subscript ( [] ) access to map data.
Definition: stl_map.h:445
iterator end()
Definition: stl_map.h:327
iterator lower_bound(const key_type &__x)
Finds the beginning of a subsequence matching given key.
Definition: stl_map.h:783
pair< typename __decay_and_strip< _T1 >::__type, typename __decay_and_strip< _T2 >::__type > make_pair(_T1 &&__x, _T2 &&__y)
A convenience wrapper for creating a pair from two objects.
Definition: stl_pair.h:262
const_reverse_iterator crbegin() const
Definition: stl_map.h:400
iterator insert(const_iterator __position, const value_type &__x)
Attempts to insert a std::pair into the map.
Definition: stl_map.h:567
const_iterator cbegin() const
Definition: stl_map.h:382
void insert(_InputIterator __first, _InputIterator __last)
Template function that attempts to insert a range of elements.
Definition: stl_map.h:593
map(const _Compare &__comp, const allocator_type &__a=allocator_type())
Creates a map with no elements.
Definition: stl_map.h:161
size_type size() const
Definition: stl_map.h:423
map & operator=(initializer_list< value_type > __l)
Map list assignment operator.
Definition: stl_map.h:289
size_type max_size() const
Definition: stl_map.h:428
allocator_type get_allocator() const
Get a copy of the memory allocation object.
Definition: stl_map.h:299
bool operator!=(const map< _Key, _Tp, _Compare, _Alloc > &__x, const map< _Key, _Tp, _Compare, _Alloc > &__y)
Based on operator==.
Definition: stl_map.h:906
const_reverse_iterator crend() const
Definition: stl_map.h:409
initializer_list
std::pair< iterator, bool > insert(const value_type &__x)
Attempts to insert a std::pair into the map.
Definition: stl_map.h:517
value_compare value_comp() const
Definition: stl_map.h:725
reverse_iterator rend()
Definition: stl_map.h:363
iterator find(const key_type &__x)
Tries to locate an element in a map.
Definition: stl_map.h:741
const_iterator lower_bound(const key_type &__x) const
Finds the beginning of a subsequence matching given key.
Definition: stl_map.h:798
const_iterator upper_bound(const key_type &__x) const
Finds the end of a subsequence matching given key.
Definition: stl_map.h:818
reverse_iterator rbegin()
Definition: stl_map.h:345
iterator erase(const_iterator __position)
Erases an element from a map.
Definition: stl_map.h:613
const_iterator end() const
Definition: stl_map.h:336
iterator upper_bound(const key_type &__x)
Finds the end of a subsequence matching given key.
Definition: stl_map.h:808
enable_if
Definition: type_traits:836
const_iterator find(const key_type &__x) const
Tries to locate an element in a map.
Definition: stl_map.h:756
iterator begin()
Definition: stl_map.h:309
map(map &&__x)
Map move constructor.
Definition: stl_map.h:183
bool operator==(const map< _Key, _Tp, _Compare, _Alloc > &__x, const map< _Key, _Tp, _Compare, _Alloc > &__y)
Map equality comparison.
Definition: stl_map.h:882
std::pair< const_iterator, const_iterator > equal_range(const key_type &__x) const
Finds a subsequence matching given key.
Definition: stl_map.h:856
Common iterator class.
map & operator=(const map &__x)
Map assignment operator.
Definition: stl_map.h:253
mapped_type & at(const key_type &__k)
Access to map data.
Definition: stl_map.h:482
size_type erase(const key_type &__x)
Erases elements according to the provided key.
Definition: stl_map.h:648
A standard container made up of (key,value) pairs, which can be retrieved based on a key...
Definition: stl_map.h:88
const_reverse_iterator rbegin() const
Definition: stl_map.h:354
is_convertible
Definition: type_traits:789
const_reverse_iterator rend() const
Definition: stl_map.h:372
void insert(std::initializer_list< value_type > __list)
Attempts to insert a list of std::pairs into the map.
Definition: stl_map.h:538