libstdc++/stl/stl_multimap.h

   1 /*
   2  *
   3  * Copyright (c) 1994
   4  * Hewlett-Packard Company
   5  *
   6  * Permission to use, copy, modify, distribute and sell this software
   7  * and its documentation for any purpose is hereby granted without fee,
   8  * provided that the above copyright notice appear in all copies and
   9  * that both that copyright notice and this permission notice appear
  10  * in supporting documentation.  Hewlett-Packard Company makes no
  11  * representations about the suitability of this software for any
  12  * purpose.  It is provided "as is" without express or implied warranty.
  13  *
  14  *
  15  * Copyright (c) 1996,1997
  16  * Silicon Graphics Computer Systems, Inc.
  17  *
  18  * Permission to use, copy, modify, distribute and sell this software
  19  * and its documentation for any purpose is hereby granted without fee,
  20  * provided that the above copyright notice appear in all copies and
  21  * that both that copyright notice and this permission notice appear
  22  * in supporting documentation.  Silicon Graphics makes no
  23  * representations about the suitability of this software for any
  24  * purpose.  It is provided "as is" without express or implied warranty.
  25  */
  26
  27 /* NOTE: This is an internal header file, included by other STL headers.
  28  *   You should not attempt to use it directly.
  29  */
  30
  31 #ifndef __SGI_STL_INTERNAL_MULTIMAP_H
  32 #define __SGI_STL_INTERNAL_MULTIMAP_H
  33
  34 __STL_BEGIN_NAMESPACE
  35
  36 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  37 #pragma set woff 1174
  38 #endif
  39
  40 #ifndef __STL_LIMITED_DEFAULT_TEMPLATES
  41 template <class Key, class T, class Compare = less<Key>, class Alloc = alloc>
  42 #else
  43 template <class Key, class T, class Compare, class Alloc = alloc>
  44 #endif
  45 class multimap {
  46 public:
  47
  48 // typedefs:
  49
  50   typedef Key key_type;
  51   typedef T data_type;
  52   typedef T mapped_type;
  53   typedef pair<const Key, T> value_type;
  54   typedef Compare key_compare;
  55
  56   class value_compare : public binary_function<value_type, value_type, bool> {
  57   friend class multimap<Key, T, Compare, Alloc>;
  58   protected:
  59     Compare comp;
  60     value_compare(Compare c) : comp(c) {}
  61   public:
  62     bool operator()(const value_type& x, const value_type& y) const {
  63       return comp(x.first, y.first);
  64     }
  65   };
  66
  67 private:
  68   typedef rb_tree<key_type, value_type,
  69                   select1st<value_type>, key_compare, Alloc> rep_type;
  70   rep_type t;  // red-black tree representing multimap
  71 public:
  72   typedef typename rep_type::pointer pointer;
  73   typedef typename rep_type::const_pointer const_pointer;
  74   typedef typename rep_type::reference reference;
  75   typedef typename rep_type::const_reference const_reference;
  76   typedef typename rep_type::iterator iterator;
  77   typedef typename rep_type::const_iterator const_iterator;
  78   typedef typename rep_type::reverse_iterator reverse_iterator;
  79   typedef typename rep_type::const_reverse_iterator const_reverse_iterator;
  80   typedef typename rep_type::size_type size_type;
  81   typedef typename rep_type::difference_type difference_type;
  82
  83 // allocation/deallocation
  84
  85   multimap() : t(Compare()) { }
  86   explicit multimap(const Compare& comp) : t(comp) { }
  87
  88 #ifdef __STL_MEMBER_TEMPLATES
  89   template <class InputIterator>
  90   multimap(InputIterator first, InputIterator last)
  91     : t(Compare()) { t.insert_equal(first, last); }
  92
  93   template <class InputIterator>
  94   multimap(InputIterator first, InputIterator last, const Compare& comp)
  95     : t(comp) { t.insert_equal(first, last); }
  96 #else
  97   multimap(const value_type* first, const value_type* last)
  98     : t(Compare()) { t.insert_equal(first, last); }
  99   multimap(const value_type* first, const value_type* last,
 100            const Compare& comp)
 101     : t(comp) { t.insert_equal(first, last); }
 102
 103   multimap(const_iterator first, const_iterator last)
 104     : t(Compare()) { t.insert_equal(first, last); }
 105   multimap(const_iterator first, const_iterator last, const Compare& comp)
 106     : t(comp) { t.insert_equal(first, last); }
 107 #endif /* __STL_MEMBER_TEMPLATES */
 108
 109   multimap(const multimap<Key, T, Compare, Alloc>& x) : t(x.t) { }
 110   multimap<Key, T, Compare, Alloc>&
 111   operator=(const multimap<Key, T, Compare, Alloc>& x) {
 112     t = x.t;
 113     return *this;
 114   }
 115
 116   // accessors:
 117
 118   key_compare key_comp() const { return t.key_comp(); }
 119   value_compare value_comp() const { return value_compare(t.key_comp()); }
 120   iterator begin() { return t.begin(); }
 121   const_iterator begin() const { return t.begin(); }
 122   iterator end() { return t.end(); }
 123   const_iterator end() const { return t.end(); }
 124   reverse_iterator rbegin() { return t.rbegin(); }
 125   const_reverse_iterator rbegin() const { return t.rbegin(); }
 126   reverse_iterator rend() { return t.rend(); }
 127   const_reverse_iterator rend() const { return t.rend(); }
 128   bool empty() const { return t.empty(); }
 129   size_type size() const { return t.size(); }
 130   size_type max_size() const { return t.max_size(); }
 131   void swap(multimap<Key, T, Compare, Alloc>& x) { t.swap(x.t); }
 132
 133   // insert/erase
 134
 135   iterator insert(const value_type& x) { return t.insert_equal(x); }
 136   iterator insert(iterator position, const value_type& x) {
 137     return t.insert_equal(position, x);
 138   }
 139 #ifdef __STL_MEMBER_TEMPLATES
 140   template <class InputIterator>
 141   void insert(InputIterator first, InputIterator last) {
 142     t.insert_equal(first, last);
 143   }
 144 #else
 145   void insert(const value_type* first, const value_type* last) {
 146     t.insert_equal(first, last);
 147   }
 148   void insert(const_iterator first, const_iterator last) {
 149     t.insert_equal(first, last);
 150   }
 151 #endif /* __STL_MEMBER_TEMPLATES */
 152   void erase(iterator position) { t.erase(position); }
 153   size_type erase(const key_type& x) { return t.erase(x); }
 154   void erase(iterator first, iterator last) { t.erase(first, last); }
 155   void clear() { t.clear(); }
 156
 157   // multimap operations:
 158
 159   iterator find(const key_type& x) { return t.find(x); }
 160   const_iterator find(const key_type& x) const { return t.find(x); }
 161   size_type count(const key_type& x) const { return t.count(x); }
 162   iterator lower_bound(const key_type& x) {return t.lower_bound(x); }
 163   const_iterator lower_bound(const key_type& x) const {
 164     return t.lower_bound(x);
 165   }
 166   iterator upper_bound(const key_type& x) {return t.upper_bound(x); }
 167   const_iterator upper_bound(const key_type& x) const {
 168     return t.upper_bound(x);
 169   }
 170    pair<iterator,iterator> equal_range(const key_type& x) {
 171     return t.equal_range(x);
 172   }
 173   pair<const_iterator,const_iterator> equal_range(const key_type& x) const {
 174     return t.equal_range(x);
 175   }
 176   friend bool operator== __STL_NULL_TMPL_ARGS (const multimap&,
 177                                                const multimap&);
 178   friend bool operator< __STL_NULL_TMPL_ARGS (const multimap&,
 179                                               const multimap&);
 180 };
 181
 182 template <class Key, class T, class Compare, class Alloc>
 183 inline bool operator==(const multimap<Key, T, Compare, Alloc>& x,
 184                        const multimap<Key, T, Compare, Alloc>& y) {
 185   return x.t == y.t;
 186 }
 187
 188 template <class Key, class T, class Compare, class Alloc>
 189 inline bool operator<(const multimap<Key, T, Compare, Alloc>& x,
 190                       const multimap<Key, T, Compare, Alloc>& y) {
 191   return x.t < y.t;
 192 }
 193
 194 #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
 195
 196 template <class Key, class T, class Compare, class Alloc>
 197 inline void swap(multimap<Key, T, Compare, Alloc>& x,
 198                  multimap<Key, T, Compare, Alloc>& y) {
 199   x.swap(y);
 200 }
 201
 202 #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
 203
 204 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
 205 #pragma reset woff 1174
 206 #endif
 207
 208 __STL_END_NAMESPACE
 209
 210 #endif /* __SGI_STL_INTERNAL_MULTIMAP_H */
 211
 212 // Local Variables:
 213 // mode:C++
 214 // End: