libstdc++/stl/stl_set.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_SET_H
  32 #define __SGI_STL_INTERNAL_SET_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 Compare = less<Key>, class Alloc = alloc>
  42 #else
  43 template <class Key, class Compare, class Alloc = alloc>
  44 #endif
  45 class set {
  46 public:
  47   // typedefs:
  48
  49   typedef Key key_type;
  50   typedef Key value_type;
  51   typedef Compare key_compare;
  52   typedef Compare value_compare;
  53 private:
  54   typedef rb_tree<key_type, value_type,
  55                   identity<value_type>, key_compare, Alloc> rep_type;
  56   rep_type t;  // red-black tree representing set
  57 public:
  58   typedef typename rep_type::const_pointer pointer;
  59   typedef typename rep_type::const_pointer const_pointer;
  60   typedef typename rep_type::const_reference reference;
  61   typedef typename rep_type::const_reference const_reference;
  62   typedef typename rep_type::const_iterator iterator;
  63   typedef typename rep_type::const_iterator const_iterator;
  64   typedef typename rep_type::const_reverse_iterator reverse_iterator;
  65   typedef typename rep_type::const_reverse_iterator const_reverse_iterator;
  66   typedef typename rep_type::size_type size_type;
  67   typedef typename rep_type::difference_type difference_type;
  68
  69   // allocation/deallocation
  70
  71   set() : t(Compare()) {}
  72   explicit set(const Compare& comp) : t(comp) {}
  73
  74 #ifdef __STL_MEMBER_TEMPLATES
  75   template <class InputIterator>
  76   set(InputIterator first, InputIterator last)
  77     : t(Compare()) { t.insert_unique(first, last); }
  78
  79   template <class InputIterator>
  80   set(InputIterator first, InputIterator last, const Compare& comp)
  81     : t(comp) { t.insert_unique(first, last); }
  82 #else
  83   set(const value_type* first, const value_type* last)
  84     : t(Compare()) { t.insert_unique(first, last); }
  85   set(const value_type* first, const value_type* last, const Compare& comp)
  86     : t(comp) { t.insert_unique(first, last); }
  87
  88   set(const_iterator first, const_iterator last)
  89     : t(Compare()) { t.insert_unique(first, last); }
  90   set(const_iterator first, const_iterator last, const Compare& comp)
  91     : t(comp) { t.insert_unique(first, last); }
  92 #endif /* __STL_MEMBER_TEMPLATES */
  93
  94   set(const set<Key, Compare, Alloc>& x) : t(x.t) {}
  95   set<Key, Compare, Alloc>& operator=(const set<Key, Compare, Alloc>& x) {
  96     t = x.t;
  97     return *this;
  98   }
  99
 100   // accessors:
 101
 102   key_compare key_comp() const { return t.key_comp(); }
 103   value_compare value_comp() const { return t.key_comp(); }
 104   iterator begin() const { return t.begin(); }
 105   iterator end() const { return t.end(); }
 106   reverse_iterator rbegin() const { return t.rbegin(); }
 107   reverse_iterator rend() const { return t.rend(); }
 108   bool empty() const { return t.empty(); }
 109   size_type size() const { return t.size(); }
 110   size_type max_size() const { return t.max_size(); }
 111   void swap(set<Key, Compare, Alloc>& x) { t.swap(x.t); }
 112
 113   // insert/erase
 114   typedef  pair<iterator, bool> pair_iterator_bool;
 115   pair<iterator,bool> insert(const value_type& x) {
 116     pair<typename rep_type::iterator, bool> p = t.insert_unique(x);
 117     return pair<iterator, bool>(p.first, p.second);
 118   }
 119   iterator insert(iterator position, const value_type& x) {
 120     typedef typename rep_type::iterator rep_iterator;
 121     return t.insert_unique((rep_iterator&)position, x);
 122   }
 123 #ifdef __STL_MEMBER_TEMPLATES
 124   template <class InputIterator>
 125   void insert(InputIterator first, InputIterator last) {
 126     t.insert_unique(first, last);
 127   }
 128 #else
 129   void insert(const_iterator first, const_iterator last) {
 130     t.insert_unique(first, last);
 131   }
 132   void insert(const value_type* first, const value_type* last) {
 133     t.insert_unique(first, last);
 134   }
 135 #endif /* __STL_MEMBER_TEMPLATES */
 136   void erase(iterator position) {
 137     typedef typename rep_type::iterator rep_iterator;
 138     t.erase((rep_iterator&)position);
 139   }
 140   size_type erase(const key_type& x) {
 141     return t.erase(x);
 142   }
 143   void erase(iterator first, iterator last) {
 144     typedef typename rep_type::iterator rep_iterator;
 145     t.erase((rep_iterator&)first, (rep_iterator&)last);
 146   }
 147   void clear() { t.clear(); }
 148
 149   // set operations:
 150
 151   iterator find(const key_type& x) const { return t.find(x); }
 152   size_type count(const key_type& x) const { return t.count(x); }
 153   iterator lower_bound(const key_type& x) const {
 154     return t.lower_bound(x);
 155   }
 156   iterator upper_bound(const key_type& x) const {
 157     return t.upper_bound(x);
 158   }
 159   pair<iterator,iterator> equal_range(const key_type& x) const {
 160     return t.equal_range(x);
 161   }
 162   friend bool operator== __STL_NULL_TMPL_ARGS (const set&, const set&);
 163   friend bool operator< __STL_NULL_TMPL_ARGS (const set&, const set&);
 164 };
 165
 166 template <class Key, class Compare, class Alloc>
 167 inline bool operator==(const set<Key, Compare, Alloc>& x,
 168                        const set<Key, Compare, Alloc>& y) {
 169   return x.t == y.t;
 170 }
 171
 172 template <class Key, class Compare, class Alloc>
 173 inline bool operator<(const set<Key, Compare, Alloc>& x,
 174                       const set<Key, Compare, Alloc>& y) {
 175   return x.t < y.t;
 176 }
 177
 178 #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
 179
 180 template <class Key, class Compare, class Alloc>
 181 inline void swap(set<Key, Compare, Alloc>& x,
 182                  set<Key, Compare, Alloc>& y) {
 183   x.swap(y);
 184 }
 185
 186 #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
 187
 188 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
 189 #pragma reset woff 1174
 190 #endif
 191
 192 __STL_END_NAMESPACE
 193
 194 #endif /* __SGI_STL_INTERNAL_SET_H */
 195
 196 // Local Variables:
 197 // mode:C++
 198 // End: