libstdc++/stl/multiset.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
  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 #ifndef __SGI_STL_MULTISET_H
  28 #define __SGI_STL_MULTISET_H
  29
  30 #include <tree.h>
  31
  32 #ifndef __STL_LIMITED_DEFAULT_TEMPLATES
  33 template <class Key, class Compare = less<Key>, class Alloc = alloc>
  34 #else
  35 template <class Key, class Compare, class Alloc = alloc>
  36 #endif
  37 class multiset {
  38 public:
  39   // typedefs:
  40
  41   typedef Key key_type;
  42   typedef Key value_type;
  43   typedef Compare key_compare;
  44   typedef Compare value_compare;
  45 private:
  46   typedef rb_tree<key_type, value_type,
  47                   identity<value_type>, key_compare, Alloc> rep_type;
  48   rep_type t;  // red-black tree representing multiset
  49 public:
  50   typedef rep_type::const_pointer pointer;
  51   typedef rep_type::const_reference reference;
  52   typedef rep_type::const_reference const_reference;
  53   typedef rep_type::const_iterator iterator;
  54   typedef rep_type::const_iterator const_iterator;
  55   typedef rep_type::const_reverse_iterator reverse_iterator;
  56   typedef rep_type::const_reverse_iterator const_reverse_iterator;
  57   typedef rep_type::size_type size_type;
  58   typedef rep_type::difference_type difference_type;
  59
  60   // allocation/deallocation
  61
  62   multiset() : t(Compare()) {}
  63   explicit multiset(const Compare& comp) : t(comp) {}
  64
  65 #ifdef __STL_MEMBER_TEMPLATES
  66   template <class InputIterator>
  67   multiset(InputIterator first, InputIterator last)
  68     : t(Compare()) { t.insert_equal(first, last); }
  69   template <class InputIterator>
  70   multiset(InputIterator first, InputIterator last, const Compare& comp)
  71     : t(comp) { t.insert_equal(first, last); }
  72 #else
  73   multiset(const value_type* first, const value_type* last)
  74     : t(Compare()) { t.insert_equal(first, last); }
  75   multiset(const value_type* first, const value_type* last,
  76            const Compare& comp)
  77     : t(comp) { t.insert_equal(first, last); }
  78
  79   multiset(const_iterator first, const_iterator last)
  80     : t(Compare()) { t.insert_equal(first, last); }
  81   multiset(const_iterator first, const_iterator last, const Compare& comp)
  82     : t(comp) { t.insert_equal(first, last); }
  83 #endif /* __STL_MEMBER_TEMPLATES */
  84
  85   multiset(const multiset<Key, Compare, Alloc>& x) : t(x.t) {}
  86   multiset<Key, Compare, Alloc>&
  87   operator=(const multiset<Key, Compare, Alloc>& x) {
  88     t = x.t;
  89     return *this;
  90   }
  91
  92   // accessors:
  93
  94   key_compare key_comp() const { return t.key_comp(); }
  95   value_compare value_comp() const { return t.key_comp(); }
  96   iterator begin() const { return t.begin(); }
  97   iterator end() const { return t.end(); }
  98   reverse_iterator rbegin() const { return t.rbegin(); }
  99   reverse_iterator rend() const { return t.rend(); }
 100   bool empty() const { return t.empty(); }
 101   size_type size() const { return t.size(); }
 102   size_type max_size() const { return t.max_size(); }
 103   void swap(multiset<Key, Compare, Alloc>& x) { t.swap(x.t); }
 104
 105   // insert/erase
 106   iterator insert(const value_type& x) {
 107     return t.insert_equal(x);
 108   }
 109   iterator insert(iterator position, const value_type& x) {
 110     return t.insert_equal((rep_type::iterator&)position, x);
 111   }
 112
 113 #ifdef __STL_MEMBER_TEMPLATES
 114   template <class InputIterator>
 115   void insert(InputIterator first, InputIterator last) {
 116     t.insert_equal(first, last);
 117   }
 118 #else
 119   void insert(const value_type* first, const value_type* last) {
 120     t.insert_equal(first, last);
 121   }
 122   void insert(const_iterator first, const_iterator last) {
 123     t.insert_equal(first, last);
 124   }
 125 #endif /* __STL_MEMBER_TEMPLATES */
 126   void erase(iterator position) {
 127     t.erase((rep_type::iterator&)position);
 128   }
 129   size_type erase(const key_type& x) {
 130     return t.erase(x);
 131   }
 132   void erase(iterator first, iterator last) {
 133     t.erase((rep_type::iterator&)first,
 134             (rep_type::iterator&)last);
 135   }
 136   void clear() { t.clear(); }
 137
 138   // multiset operations:
 139
 140   iterator find(const key_type& x) const { return t.find(x); }
 141   size_type count(const key_type& x) const { return t.count(x); }
 142   iterator lower_bound(const key_type& x) const {
 143     return t.lower_bound(x);
 144   }
 145   iterator upper_bound(const key_type& x) const {
 146     return t.upper_bound(x);
 147   }
 148   pair<iterator,iterator> equal_range(const key_type& x) const {
 149     return t.equal_range(x);
 150   }
 151   friend bool operator==(const multiset&, const multiset&);
 152   friend bool operator<(const multiset&, const multiset&);
 153 };
 154
 155 template <class Key, class Compare, class Alloc>
 156 inline bool operator==(const multiset<Key, Compare, Alloc>& x,
 157                        const multiset<Key, Compare, Alloc>& y) {
 158   return x.t == y.t;
 159 }
 160
 161 template <class Key, class Compare, class Alloc>
 162 inline bool operator<(const multiset<Key, Compare, Alloc>& x,
 163                       const multiset<Key, Compare, Alloc>& y) {
 164   return x.t < y.t;
 165 }
 166
 167 #endif /* __SGI_STL_MULTISET_H */