STLdoc
STLdocumentation
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
stl_multimap.h
Go to the documentation of this file.
1 // Multimap 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_MULTIMAP_H
57 #define _STL_MULTIMAP_H 1
58 
59 #include <bits/concept_check.h>
60 #if __cplusplus >= 201103L
61 #include <initializer_list>
62 #endif
63 
64 namespace std _GLIBCXX_VISIBILITY(default)
65 {
66 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
67 
92  template <typename _Key, typename _Tp,
93  typename _Compare = std::less<_Key>,
94  typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
95  class multimap
96  {
97  public:
98  typedef _Key key_type;
99  typedef _Tp mapped_type;
100  typedef std::pair<const _Key, _Tp> value_type;
101  typedef _Compare key_compare;
102  typedef _Alloc allocator_type;
103 
104  private:
105  // concept requirements
106  typedef typename _Alloc::value_type _Alloc_value_type;
107  __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
108  __glibcxx_class_requires4(_Compare, bool, _Key, _Key,
109  _BinaryFunctionConcept)
110  __glibcxx_class_requires2(value_type, _Alloc_value_type, _SameTypeConcept)
111 
112  public:
113  class value_compare
114  : public std::binary_function<value_type, value_type, bool>
115  {
116  friend class multimap<_Key, _Tp, _Compare, _Alloc>;
117  protected:
118  _Compare comp;
119 
120  value_compare(_Compare __c)
121  : comp(__c) { }
122 
123  public:
124  bool operator()(const value_type& __x, const value_type& __y) const
125  { return comp(__x.first, __y.first); }
126  };
127 
128  private:
130  typedef typename _Alloc::template rebind<value_type>::other
131  _Pair_alloc_type;
132 
133  typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,
134  key_compare, _Pair_alloc_type> _Rep_type;
136  _Rep_type _M_t;
137 
138  public:
139  // many of these are specified differently in ISO, but the following are
140  // "functionally equivalent"
141  typedef typename _Pair_alloc_type::pointer pointer;
142  typedef typename _Pair_alloc_type::const_pointer const_pointer;
143  typedef typename _Pair_alloc_type::reference reference;
144  typedef typename _Pair_alloc_type::const_reference const_reference;
145  typedef typename _Rep_type::iterator iterator;
146  typedef typename _Rep_type::const_iterator const_iterator;
147  typedef typename _Rep_type::size_type size_type;
148  typedef typename _Rep_type::difference_type difference_type;
149  typedef typename _Rep_type::reverse_iterator reverse_iterator;
150  typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
151 
152  // [23.3.2] construct/copy/destroy
153  // (get_allocator() is also listed in this section)
157  multimap()
158  : _M_t() { }
159 
165  explicit
166  multimap(const _Compare& __comp,
167  const allocator_type& __a = allocator_type())
168  : _M_t(__comp, _Pair_alloc_type(__a)) { }
169 
177  multimap(const multimap& __x)
178  : _M_t(__x._M_t) { }
179 
180 #if __cplusplus >= 201103L
181 
188  multimap(multimap&& __x)
189  noexcept(is_nothrow_copy_constructible<_Compare>::value)
190  : _M_t(std::move(__x._M_t)) { }
191 
202  multimap(initializer_list<value_type> __l,
203  const _Compare& __comp = _Compare(),
204  const allocator_type& __a = allocator_type())
205  : _M_t(__comp, _Pair_alloc_type(__a))
206  { _M_t._M_insert_equal(__l.begin(), __l.end()); }
207 #endif
208 
218  template<typename _InputIterator>
219  multimap(_InputIterator __first, _InputIterator __last)
220  : _M_t()
221  { _M_t._M_insert_equal(__first, __last); }
222 
234  template<typename _InputIterator>
235  multimap(_InputIterator __first, _InputIterator __last,
236  const _Compare& __comp,
237  const allocator_type& __a = allocator_type())
238  : _M_t(__comp, _Pair_alloc_type(__a))
239  { _M_t._M_insert_equal(__first, __last); }
240 
241  // FIXME There is no dtor declared, but we should have something generated
242  // by Doxygen. I don't know what tags to add to this paragraph to make
243  // that happen:
257  multimap&
258  operator=(const multimap& __x)
259  {
260  _M_t = __x._M_t;
261  return *this;
262  }
263 
264 #if __cplusplus >= 201103L
265 
272  multimap&
273  operator=(multimap&& __x)
274  {
275  // NB: DR 1204.
276  // NB: DR 675.
277  this->clear();
278  this->swap(__x);
279  return *this;
280  }
281 
293  multimap&
294  operator=(initializer_list<value_type> __l)
295  {
296  this->clear();
297  this->insert(__l.begin(), __l.end());
298  return *this;
299  }
300 #endif
301 
303  allocator_type
304  get_allocator() const _GLIBCXX_NOEXCEPT
305  { return allocator_type(_M_t.get_allocator()); }
306 
307  // iterators
313  iterator
314  begin() _GLIBCXX_NOEXCEPT
315  { return _M_t.begin(); }
316 
322  const_iterator
323  begin() const _GLIBCXX_NOEXCEPT
324  { return _M_t.begin(); }
325 
331  iterator
332  end() _GLIBCXX_NOEXCEPT
333  { return _M_t.end(); }
334 
340  const_iterator
341  end() const _GLIBCXX_NOEXCEPT
342  { return _M_t.end(); }
343 
349  reverse_iterator
350  rbegin() _GLIBCXX_NOEXCEPT
351  { return _M_t.rbegin(); }
352 
358  const_reverse_iterator
359  rbegin() const _GLIBCXX_NOEXCEPT
360  { return _M_t.rbegin(); }
361 
367  reverse_iterator
368  rend() _GLIBCXX_NOEXCEPT
369  { return _M_t.rend(); }
370 
376  const_reverse_iterator
377  rend() const _GLIBCXX_NOEXCEPT
378  { return _M_t.rend(); }
379 
380 #if __cplusplus >= 201103L
381 
386  const_iterator
387  cbegin() const noexcept
388  { return _M_t.begin(); }
389 
395  const_iterator
396  cend() const noexcept
397  { return _M_t.end(); }
398 
404  const_reverse_iterator
405  crbegin() const noexcept
406  { return _M_t.rbegin(); }
407 
413  const_reverse_iterator
414  crend() const noexcept
415  { return _M_t.rend(); }
416 #endif
417 
418  // capacity
420  bool
421  empty() const _GLIBCXX_NOEXCEPT
422  { return _M_t.empty(); }
423 
425  size_type
426  size() const _GLIBCXX_NOEXCEPT
427  { return _M_t.size(); }
428 
430  size_type
431  max_size() const _GLIBCXX_NOEXCEPT
432  { return _M_t.max_size(); }
433 
434  // modifiers
435 #if __cplusplus >= 201103L
436 
452  template<typename... _Args>
453  iterator
454  emplace(_Args&&... __args)
455  { return _M_t._M_emplace_equal(std::forward<_Args>(__args)...); }
456 
479  template<typename... _Args>
480  iterator
481  emplace_hint(const_iterator __pos, _Args&&... __args)
482  {
483  return _M_t._M_emplace_hint_equal(__pos,
484  std::forward<_Args>(__args)...);
485  }
486 #endif
487 
500  iterator
501  insert(const value_type& __x)
502  { return _M_t._M_insert_equal(__x); }
503 
504 #if __cplusplus >= 201103L
505  template<typename _Pair, typename = typename
506  std::enable_if<std::is_constructible<value_type,
507  _Pair&&>::value>::type>
508  iterator
509  insert(_Pair&& __x)
510  { return _M_t._M_insert_equal(std::forward<_Pair>(__x)); }
511 #endif
512 
533  iterator
534 #if __cplusplus >= 201103L
535  insert(const_iterator __position, const value_type& __x)
536 #else
537  insert(iterator __position, const value_type& __x)
538 #endif
539  { return _M_t._M_insert_equal_(__position, __x); }
540 
541 #if __cplusplus >= 201103L
542  template<typename _Pair, typename = typename
543  std::enable_if<std::is_constructible<value_type,
544  _Pair&&>::value>::type>
545  iterator
546  insert(const_iterator __position, _Pair&& __x)
547  { return _M_t._M_insert_equal_(__position,
548  std::forward<_Pair>(__x)); }
549 #endif
550 
560  template<typename _InputIterator>
561  void
562  insert(_InputIterator __first, _InputIterator __last)
563  { _M_t._M_insert_equal(__first, __last); }
564 
565 #if __cplusplus >= 201103L
566 
573  void
574  insert(initializer_list<value_type> __l)
575  { this->insert(__l.begin(), __l.end()); }
576 #endif
577 
578 #if __cplusplus >= 201103L
579  // _GLIBCXX_RESOLVE_LIB_DEFECTS
580  // DR 130. Associative erase should return an iterator.
594  iterator
595  erase(const_iterator __position)
596  { return _M_t.erase(__position); }
597 
598  // LWG 2059.
599  _GLIBCXX_ABI_TAG_CXX11
600  iterator
601  erase(iterator __position)
602  { return _M_t.erase(__position); }
603 #else
604 
614  void
615  erase(iterator __position)
616  { _M_t.erase(__position); }
617 #endif
618 
630  size_type
631  erase(const key_type& __x)
632  { return _M_t.erase(__x); }
633 
634 #if __cplusplus >= 201103L
635  // _GLIBCXX_RESOLVE_LIB_DEFECTS
636  // DR 130. Associative erase should return an iterator.
651  iterator
652  erase(const_iterator __first, const_iterator __last)
653  { return _M_t.erase(__first, __last); }
654 #else
655  // _GLIBCXX_RESOLVE_LIB_DEFECTS
656  // DR 130. Associative erase should return an iterator.
670  void
671  erase(iterator __first, iterator __last)
672  { _M_t.erase(__first, __last); }
673 #endif
674 
686  void
687  swap(multimap& __x)
688  { _M_t.swap(__x._M_t); }
689 
696  void
697  clear() _GLIBCXX_NOEXCEPT
698  { _M_t.clear(); }
699 
700  // observers
705  key_compare
706  key_comp() const
707  { return _M_t.key_comp(); }
708 
713  value_compare
714  value_comp() const
715  { return value_compare(_M_t.key_comp()); }
716 
717  // multimap operations
729  iterator
730  find(const key_type& __x)
731  { return _M_t.find(__x); }
732 
744  const_iterator
745  find(const key_type& __x) const
746  { return _M_t.find(__x); }
747 
753  size_type
754  count(const key_type& __x) const
755  { return _M_t.count(__x); }
756 
768  iterator
769  lower_bound(const key_type& __x)
770  { return _M_t.lower_bound(__x); }
771 
783  const_iterator
784  lower_bound(const key_type& __x) const
785  { return _M_t.lower_bound(__x); }
786 
793  iterator
794  upper_bound(const key_type& __x)
795  { return _M_t.upper_bound(__x); }
796 
803  const_iterator
804  upper_bound(const key_type& __x) const
805  { return _M_t.upper_bound(__x); }
806 
820  std::pair<iterator, iterator>
821  equal_range(const key_type& __x)
822  { return _M_t.equal_range(__x); }
823 
837  std::pair<const_iterator, const_iterator>
838  equal_range(const key_type& __x) const
839  { return _M_t.equal_range(__x); }
840 
841  template<typename _K1, typename _T1, typename _C1, typename _A1>
842  friend bool
843  operator==(const multimap<_K1, _T1, _C1, _A1>&,
844  const multimap<_K1, _T1, _C1, _A1>&);
845 
846  template<typename _K1, typename _T1, typename _C1, typename _A1>
847  friend bool
848  operator<(const multimap<_K1, _T1, _C1, _A1>&,
849  const multimap<_K1, _T1, _C1, _A1>&);
850  };
851 
862  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
863  inline bool
864  operator==(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
865  const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
866  { return __x._M_t == __y._M_t; }
867 
879  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
880  inline bool
881  operator<(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
882  const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
883  { return __x._M_t < __y._M_t; }
884 
886  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
887  inline bool
888  operator!=(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
889  const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
890  { return !(__x == __y); }
891 
893  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
894  inline bool
895  operator>(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
896  const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
897  { return __y < __x; }
898 
900  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
901  inline bool
902  operator<=(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
903  const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
904  { return !(__y < __x); }
905 
907  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
908  inline bool
909  operator>=(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
910  const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
911  { return !(__x < __y); }
912 
914  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
915  inline void
916  swap(multimap<_Key, _Tp, _Compare, _Alloc>& __x,
917  multimap<_Key, _Tp, _Compare, _Alloc>& __y)
918  { __x.swap(__y); }
919 
920 _GLIBCXX_END_NAMESPACE_CONTAINER
921 } // namespace std
922 
923 #endif /* _STL_MULTIMAP_H */
__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_multimap.h:64
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