STLdoc
STLdocumentation
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
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 
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 
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;
101  typedef std::pair<const _Key, _Tp> value_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:
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 
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;
151  typedef typename _Rep_type::reverse_iterator reverse_iterator;
152  typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
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)
160  map()
161  : _M_t() { }
162 
168  explicit
169  map(const _Compare& __comp,
170  const allocator_type& __a = allocator_type())
171  : _M_t(__comp, _Pair_alloc_type(__a)) { }
172 
180  map(const map& __x)
181  : _M_t(__x._M_t) { }
182 
183 #if __cplusplus >= 201103L
184 
191  map(map&& __x)
192  noexcept(is_nothrow_copy_constructible<_Compare>::value)
193  : _M_t(std::move(__x._M_t)) { }
194 
206  map(initializer_list<value_type> __l,
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 
223  template<typename _InputIterator>
224  map(_InputIterator __first, _InputIterator __last)
225  : _M_t()
226  { _M_t._M_insert_unique(__first, __last); }
227 
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:
263  map&
264  operator=(const map& __x)
265  {
266  _M_t = __x._M_t;
267  return *this;
268  }
269 
270 #if __cplusplus >= 201103L
271 
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 
299  map&
300  operator=(initializer_list<value_type> __l)
301  {
302  this->clear();
303  this->insert(__l.begin(), __l.end());
304  return *this;
305  }
306 #endif
307 
309  allocator_type
310  get_allocator() const _GLIBCXX_NOEXCEPT
311  { return allocator_type(_M_t.get_allocator()); }
312 
313  // iterators
319  iterator
320  begin() _GLIBCXX_NOEXCEPT
321  { return _M_t.begin(); }
322 
328  const_iterator
329  begin() const _GLIBCXX_NOEXCEPT
330  { return _M_t.begin(); }
331 
337  iterator
338  end() _GLIBCXX_NOEXCEPT
339  { return _M_t.end(); }
340 
346  const_iterator
347  end() const _GLIBCXX_NOEXCEPT
348  { return _M_t.end(); }
349 
355  reverse_iterator
356  rbegin() _GLIBCXX_NOEXCEPT
357  { return _M_t.rbegin(); }
358 
364  const_reverse_iterator
365  rbegin() const _GLIBCXX_NOEXCEPT
366  { return _M_t.rbegin(); }
367 
373  reverse_iterator
374  rend() _GLIBCXX_NOEXCEPT
375  { return _M_t.rend(); }
376 
382  const_reverse_iterator
383  rend() const _GLIBCXX_NOEXCEPT
384  { return _M_t.rend(); }
385 
386 #if __cplusplus >= 201103L
387 
392  const_iterator
393  cbegin() const noexcept
394  { return _M_t.begin(); }
395 
401  const_iterator
402  cend() const noexcept
403  { return _M_t.end(); }
404 
410  const_reverse_iterator
411  crbegin() const noexcept
412  { return _M_t.rbegin(); }
413 
419  const_reverse_iterator
420  crend() const noexcept
421  { return _M_t.rend(); }
422 #endif
423 
424  // capacity
428  bool
429  empty() const _GLIBCXX_NOEXCEPT
430  { return _M_t.empty(); }
431 
433  size_type
434  size() const _GLIBCXX_NOEXCEPT
435  { return _M_t.size(); }
436 
438  size_type
439  max_size() const _GLIBCXX_NOEXCEPT
440  { return _M_t.max_size(); }
441 
442  // [23.3.1.2] element access
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,
466  std::tuple<const key_type&>(__k),
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.
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 
538  template<typename... _Args>
539  std::pair<iterator, bool>
540  emplace(_Args&&... __args)
541  { return _M_t._M_emplace_unique(std::forward<_Args>(__args)...); }
542 
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 
593  std::pair<iterator, bool>
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
599  std::enable_if<std::is_constructible<value_type,
600  _Pair&&>::value>::type>
601  std::pair<iterator, bool>
602  insert(_Pair&& __x)
603  { return _M_t._M_insert_unique(std::forward<_Pair>(__x)); }
604 #endif
605 
606 #if __cplusplus >= 201103L
607 
614  void
615  insert(std::initializer_list<value_type> __list)
616  { insert(__list.begin(), __list.end()); }
617 #endif
618 
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
652  std::enable_if<std::is_constructible<value_type,
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 
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.
689  iterator
690  erase(const_iterator __position)
691  { return _M_t.erase(__position); }
692 
693  // LWG 2059
694  _GLIBCXX_ABI_TAG_CXX11
695  iterator
696  erase(iterator __position)
697  { return _M_t.erase(__position); }
698 #else
699 
709  void
710  erase(iterator __position)
711  { _M_t.erase(__position); }
712 #endif
713 
725  size_type
726  erase(const key_type& __x)
727  { return _M_t.erase(__x); }
728 
729 #if __cplusplus >= 201103L
730  // _GLIBCXX_RESOLVE_LIB_DEFECTS
731  // DR 130. Associative erase should return an iterator.
745  iterator
746  erase(const_iterator __first, const_iterator __last)
747  { return _M_t.erase(__first, __last); }
748 #else
749 
761  void
762  erase(iterator __first, iterator __last)
763  { _M_t.erase(__first, __last); }
764 #endif
765 
777  void
778  swap(map& __x)
779  { _M_t.swap(__x._M_t); }
780 
787  void
788  clear() _GLIBCXX_NOEXCEPT
789  { _M_t.clear(); }
790 
791  // observers
796  key_compare
797  key_comp() const
798  { return _M_t.key_comp(); }
799 
804  value_compare
805  value_comp() const
806  { return value_compare(_M_t.key_comp()); }
807 
808  // [23.3.1.3] map operations
820  iterator
821  find(const key_type& __x)
822  { return _M_t.find(__x); }
823 
835  const_iterator
836  find(const key_type& __x) const
837  { return _M_t.find(__x); }
838 
847  size_type
848  count(const key_type& __x) const
849  { return _M_t.find(__x) == _M_t.end() ? 0 : 1; }
850 
862  iterator
863  lower_bound(const key_type& __x)
864  { return _M_t.lower_bound(__x); }
865 
877  const_iterator
878  lower_bound(const key_type& __x) const
879  { return _M_t.lower_bound(__x); }
880 
887  iterator
888  upper_bound(const key_type& __x)
889  { return _M_t.upper_bound(__x); }
890 
897  const_iterator
898  upper_bound(const key_type& __x) const
899  { return _M_t.upper_bound(__x); }
900 
916  std::pair<iterator, iterator>
917  equal_range(const key_type& __x)
918  { return _M_t.equal_range(__x); }
919 
935  std::pair<const_iterator, const_iterator>
936  equal_range(const key_type& __x) const
937  { return _M_t.equal_range(__x); }
938 
939  template<typename _K1, typename _T1, typename _C1, typename _A1>
940  friend bool
941  operator==(const map<_K1, _T1, _C1, _A1>&,
942  const map<_K1, _T1, _C1, _A1>&);
943 
944  template<typename _K1, typename _T1, typename _C1, typename _A1>
945  friend bool
946  operator<(const map<_K1, _T1, _C1, _A1>&,
947  const map<_K1, _T1, _C1, _A1>&);
948  };
949 
960  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
961  inline bool
962  operator==(const map<_Key, _Tp, _Compare, _Alloc>& __x,
963  const map<_Key, _Tp, _Compare, _Alloc>& __y)
964  { return __x._M_t == __y._M_t; }
965 
977  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
978  inline bool
979  operator<(const map<_Key, _Tp, _Compare, _Alloc>& __x,
980  const map<_Key, _Tp, _Compare, _Alloc>& __y)
981  { return __x._M_t < __y._M_t; }
982 
984  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
985  inline bool
986  operator!=(const map<_Key, _Tp, _Compare, _Alloc>& __x,
987  const map<_Key, _Tp, _Compare, _Alloc>& __y)
988  { return !(__x == __y); }
989 
991  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
992  inline bool
993  operator>(const map<_Key, _Tp, _Compare, _Alloc>& __x,
994  const map<_Key, _Tp, _Compare, _Alloc>& __y)
995  { return __y < __x; }
996 
998  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
999  inline bool
1000  operator<=(const map<_Key, _Tp, _Compare, _Alloc>& __x,
1001  const map<_Key, _Tp, _Compare, _Alloc>& __y)
1002  { return !(__y < __x); }
1003 
1005  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1006  inline bool
1007  operator>=(const map<_Key, _Tp, _Compare, _Alloc>& __x,
1008  const map<_Key, _Tp, _Compare, _Alloc>& __y)
1009  { return !(__x < __y); }
1010 
1012  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1013  inline void
1014  swap(map<_Key, _Tp, _Compare, _Alloc>& __x,
1015  map<_Key, _Tp, _Compare, _Alloc>& __y)
1016  { __x.swap(__y); }
1017 
1018 _GLIBCXX_END_NAMESPACE_CONTAINER
1019 } // namespace std
1020 
1021 #endif /* _STL_MAP_H */
__glibcxx_function_requires
#define __glibcxx_function_requires(...)
Definition: concept_check.h:47
__gnu_debug::operator>=
bool operator>=(const _Safe_iterator< _IteratorL, _Sequence > &__lhs, const _Safe_iterator< _IteratorR, _Sequence > &__rhs)
Definition: safe_iterator.h:644
std::__exception_ptr::operator==
bool operator==(const exception_ptr &, const exception_ptr &) _GLIBCXX_USE_NOEXCEPT __attribute__((__pure__))
concept_check.h
__glibcxx_class_requires
#define __glibcxx_class_requires(_a, _b)
Definition: concept_check.h:48
__gnu_debug::operator>
bool operator>(const _Safe_iterator< _IteratorL, _Sequence > &__lhs, const _Safe_iterator< _IteratorR, _Sequence > &__rhs)
Definition: safe_iterator.h:612
__glibcxx_class_requires2
#define __glibcxx_class_requires2(_a, _b, _c)
Definition: concept_check.h:49
std::__exception_ptr::operator!=
bool operator!=(const exception_ptr &, const exception_ptr &) _GLIBCXX_USE_NOEXCEPT __attribute__((__pure__))
initializer_list
_GLIBCXX_VISIBILITY
namespace std _GLIBCXX_VISIBILITY(default)
Definition: stl_map.h:66
std::__exception_ptr::swap
void swap(exception_ptr &__lhs, exception_ptr &__rhs)
Definition: exception_ptr.h:160
__glibcxx_class_requires4
#define __glibcxx_class_requires4(_a, _b, _c, _d, _e)
Definition: concept_check.h:51
Generated on Sat Jul 22 2017 14:40:09 for STLdoc by   doxygen 1.8.6