home *** CD-ROM | disk | FTP | other *** search
/ Sams Teach Yourself C in 21 Days (6th Edition) / STYC216E.ISO / mac / Dev-C++ / _SETUP.6 / Group14 / stl_hash_set.h < prev    next >
C/C++ Source or Header  |  2000-01-21  |  15KB  |  402 lines
  1. /*
  2.  * Copyright (c) 1996
  3.  * Silicon Graphics Computer Systems, Inc.
  4.  *
  5.  * Permission to use, copy, modify, distribute and sell this software
  6.  * and its documentation for any purpose is hereby granted without fee,
  7.  * provided that the above copyright notice appear in all copies and
  8.  * that both that copyright notice and this permission notice appear
  9.  * in supporting documentation.  Silicon Graphics makes no
  10.  * representations about the suitability of this software for any
  11.  * purpose.  It is provided "as is" without express or implied warranty.
  12.  *
  13.  *
  14.  * Copyright (c) 1994
  15.  * Hewlett-Packard Company
  16.  *
  17.  * Permission to use, copy, modify, distribute and sell this software
  18.  * and its documentation for any purpose is hereby granted without fee,
  19.  * provided that the above copyright notice appear in all copies and
  20.  * that both that copyright notice and this permission notice appear
  21.  * in supporting documentation.  Hewlett-Packard Company makes no
  22.  * representations about the suitability of this software for any
  23.  * purpose.  It is provided "as is" without express or implied warranty.
  24.  *
  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_HASH_SET_H
  32. #define __SGI_STL_INTERNAL_HASH_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. #pragma set woff 1375
  39. #endif
  40.  
  41. #ifndef __STL_LIMITED_DEFAULT_TEMPLATES
  42. template <class _Value, class _HashFcn = hash<_Value>,
  43.           class _EqualKey = equal_to<_Value>,
  44.           class _Alloc = __STL_DEFAULT_ALLOCATOR(_Value) >
  45. #else
  46. template <class _Value, class _HashFcn, class _EqualKey, 
  47.           class _Alloc = __STL_DEFAULT_ALLOCATOR(_Value) >
  48. #endif
  49. class hash_set
  50. {
  51. private:
  52.   typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>, 
  53.                     _EqualKey, _Alloc> _Ht;
  54.   _Ht _M_ht;
  55.  
  56. public:
  57.   typedef typename _Ht::key_type key_type;
  58.   typedef typename _Ht::value_type value_type;
  59.   typedef typename _Ht::hasher hasher;
  60.   typedef typename _Ht::key_equal key_equal;
  61.  
  62.   typedef typename _Ht::size_type size_type;
  63.   typedef typename _Ht::difference_type difference_type;
  64.   typedef typename _Ht::const_pointer pointer;
  65.   typedef typename _Ht::const_pointer const_pointer;
  66.   typedef typename _Ht::const_reference reference;
  67.   typedef typename _Ht::const_reference const_reference;
  68.  
  69.   typedef typename _Ht::const_iterator iterator;
  70.   typedef typename _Ht::const_iterator const_iterator;
  71.  
  72.   typedef typename _Ht::allocator_type allocator_type;
  73.  
  74.   hasher hash_funct() const { return _M_ht.hash_funct(); }
  75.   key_equal key_eq() const { return _M_ht.key_eq(); }
  76.   allocator_type get_allocator() const { return _M_ht.get_allocator(); }
  77.  
  78. public:
  79.   hash_set()
  80.     : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
  81.   explicit hash_set(size_type __n)
  82.     : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
  83.   hash_set(size_type __n, const hasher& __hf)
  84.     : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
  85.   hash_set(size_type __n, const hasher& __hf, const key_equal& __eql,
  86.            const allocator_type& __a = allocator_type())
  87.     : _M_ht(__n, __hf, __eql, __a) {}
  88.  
  89. #ifdef __STL_MEMBER_TEMPLATES
  90.   template <class _InputIterator>
  91.   hash_set(_InputIterator __f, _InputIterator __l)
  92.     : _M_ht(100, hasher(), key_equal(), allocator_type())
  93.     { _M_ht.insert_unique(__f, __l); }
  94.   template <class _InputIterator>
  95.   hash_set(_InputIterator __f, _InputIterator __l, size_type __n)
  96.     : _M_ht(__n, hasher(), key_equal(), allocator_type())
  97.     { _M_ht.insert_unique(__f, __l); }
  98.   template <class _InputIterator>
  99.   hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
  100.            const hasher& __hf)
  101.     : _M_ht(__n, __hf, key_equal(), allocator_type())
  102.     { _M_ht.insert_unique(__f, __l); }
  103.   template <class _InputIterator>
  104.   hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
  105.            const hasher& __hf, const key_equal& __eql,
  106.            const allocator_type& __a = allocator_type())
  107.     : _M_ht(__n, __hf, __eql, __a)
  108.     { _M_ht.insert_unique(__f, __l); }
  109. #else
  110.  
  111.   hash_set(const value_type* __f, const value_type* __l)
  112.     : _M_ht(100, hasher(), key_equal(), allocator_type())
  113.     { _M_ht.insert_unique(__f, __l); }
  114.   hash_set(const value_type* __f, const value_type* __l, size_type __n)
  115.     : _M_ht(__n, hasher(), key_equal(), allocator_type())
  116.     { _M_ht.insert_unique(__f, __l); }
  117.   hash_set(const value_type* __f, const value_type* __l, size_type __n,
  118.            const hasher& __hf)
  119.     : _M_ht(__n, __hf, key_equal(), allocator_type())
  120.     { _M_ht.insert_unique(__f, __l); }
  121.   hash_set(const value_type* __f, const value_type* __l, size_type __n,
  122.            const hasher& __hf, const key_equal& __eql,
  123.            const allocator_type& __a = allocator_type())
  124.     : _M_ht(__n, __hf, __eql, __a)
  125.     { _M_ht.insert_unique(__f, __l); }
  126.  
  127.   hash_set(const_iterator __f, const_iterator __l)
  128.     : _M_ht(100, hasher(), key_equal(), allocator_type())
  129.     { _M_ht.insert_unique(__f, __l); }
  130.   hash_set(const_iterator __f, const_iterator __l, size_type __n)
  131.     : _M_ht(__n, hasher(), key_equal(), allocator_type())
  132.     { _M_ht.insert_unique(__f, __l); }
  133.   hash_set(const_iterator __f, const_iterator __l, size_type __n,
  134.            const hasher& __hf)
  135.     : _M_ht(__n, __hf, key_equal(), allocator_type())
  136.     { _M_ht.insert_unique(__f, __l); }
  137.   hash_set(const_iterator __f, const_iterator __l, size_type __n,
  138.            const hasher& __hf, const key_equal& __eql,
  139.            const allocator_type& __a = allocator_type())
  140.     : _M_ht(__n, __hf, __eql, __a)
  141.     { _M_ht.insert_unique(__f, __l); }
  142. #endif /*__STL_MEMBER_TEMPLATES */
  143.  
  144. public:
  145.   size_type size() const { return _M_ht.size(); }
  146.   size_type max_size() const { return _M_ht.max_size(); }
  147.   bool empty() const { return _M_ht.empty(); }
  148.   void swap(hash_set& __hs) { _M_ht.swap(__hs._M_ht); }
  149.   friend bool operator== __STL_NULL_TMPL_ARGS (const hash_set&,
  150.                                                const hash_set&);
  151.  
  152.   iterator begin() const { return _M_ht.begin(); }
  153.   iterator end() const { return _M_ht.end(); }
  154.  
  155. public:
  156.   pair<iterator, bool> insert(const value_type& __obj)
  157.     {
  158.       pair<typename _Ht::iterator, bool> __p = _M_ht.insert_unique(__obj);
  159.       return pair<iterator,bool>(__p.first, __p.second);
  160.     }
  161. #ifdef __STL_MEMBER_TEMPLATES
  162.   template <class _InputIterator>
  163.   void insert(_InputIterator __f, _InputIterator __l) 
  164.     { _M_ht.insert_unique(__f,__l); }
  165. #else
  166.   void insert(const value_type* __f, const value_type* __l) {
  167.     _M_ht.insert_unique(__f,__l);
  168.   }
  169.   void insert(const_iterator __f, const_iterator __l) 
  170.     {_M_ht.insert_unique(__f, __l); }
  171. #endif /*__STL_MEMBER_TEMPLATES */
  172.   pair<iterator, bool> insert_noresize(const value_type& __obj)
  173.   {
  174.     pair<typename _Ht::iterator, bool> __p = 
  175.       _M_ht.insert_unique_noresize(__obj);
  176.     return pair<iterator, bool>(__p.first, __p.second);
  177.   }
  178.  
  179.   iterator find(const key_type& __key) const { return _M_ht.find(__key); }
  180.  
  181.   size_type count(const key_type& __key) const { return _M_ht.count(__key); }
  182.   
  183.   pair<iterator, iterator> equal_range(const key_type& __key) const
  184.     { return _M_ht.equal_range(__key); }
  185.  
  186.   size_type erase(const key_type& __key) {return _M_ht.erase(__key); }
  187.   void erase(iterator __it) { _M_ht.erase(__it); }
  188.   void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
  189.   void clear() { _M_ht.clear(); }
  190.  
  191. public:
  192.   void resize(size_type __hint) { _M_ht.resize(__hint); }
  193.   size_type bucket_count() const { return _M_ht.bucket_count(); }
  194.   size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
  195.   size_type elems_in_bucket(size_type __n) const
  196.     { return _M_ht.elems_in_bucket(__n); }
  197. };
  198.  
  199. template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
  200. inline bool 
  201. operator==(const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs1,
  202.            const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs2)
  203. {
  204.   return __hs1._M_ht == __hs2._M_ht;
  205. }
  206.  
  207. #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
  208.  
  209. template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
  210. inline void 
  211. swap(hash_set<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1,
  212.      hash_set<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2)
  213. {
  214.   __hs1.swap(__hs2);
  215. }
  216.  
  217. #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
  218.  
  219.  
  220. #ifndef __STL_LIMITED_DEFAULT_TEMPLATES
  221. template <class _Value, class _HashFcn = hash<_Value>,
  222.           class _EqualKey = equal_to<_Value>,
  223.           class _Alloc = __STL_DEFAULT_ALLOCATOR(_Value) >
  224. #else
  225. template <class _Value, class _HashFcn, class _EqualKey, 
  226.           class _Alloc = __STL_DEFAULT_ALLOCATOR(_Value) >
  227. #endif
  228. class hash_multiset
  229. {
  230. private:
  231.   typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>, 
  232.                     _EqualKey, _Alloc> _Ht;
  233.   _Ht _M_ht;
  234.  
  235. public:
  236.   typedef typename _Ht::key_type key_type;
  237.   typedef typename _Ht::value_type value_type;
  238.   typedef typename _Ht::hasher hasher;
  239.   typedef typename _Ht::key_equal key_equal;
  240.  
  241.   typedef typename _Ht::size_type size_type;
  242.   typedef typename _Ht::difference_type difference_type;
  243.   typedef typename _Ht::const_pointer pointer;
  244.   typedef typename _Ht::const_pointer const_pointer;
  245.   typedef typename _Ht::const_reference reference;
  246.   typedef typename _Ht::const_reference const_reference;
  247.  
  248.   typedef typename _Ht::const_iterator iterator;
  249.   typedef typename _Ht::const_iterator const_iterator;
  250.  
  251.   typedef typename _Ht::allocator_type allocator_type;
  252.  
  253.   hasher hash_funct() const { return _M_ht.hash_funct(); }
  254.   key_equal key_eq() const { return _M_ht.key_eq(); }
  255.   allocator_type get_allocator() const { return _M_ht.get_allocator(); }
  256.  
  257. public:
  258.   hash_multiset()
  259.     : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
  260.   explicit hash_multiset(size_type __n)
  261.     : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
  262.   hash_multiset(size_type __n, const hasher& __hf)
  263.     : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
  264.   hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql,
  265.                 const allocator_type& __a = allocator_type())
  266.     : _M_ht(__n, __hf, __eql, __a) {}
  267.  
  268. #ifdef __STL_MEMBER_TEMPLATES
  269.   template <class _InputIterator>
  270.   hash_multiset(_InputIterator __f, _InputIterator __l)
  271.     : _M_ht(100, hasher(), key_equal(), allocator_type())
  272.     { _M_ht.insert_equal(__f, __l); }
  273.   template <class _InputIterator>
  274.   hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n)
  275.     : _M_ht(__n, hasher(), key_equal(), allocator_type())
  276.     { _M_ht.insert_equal(__f, __l); }
  277.   template <class _InputIterator>
  278.   hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
  279.                 const hasher& __hf)
  280.     : _M_ht(__n, __hf, key_equal(), allocator_type())
  281.     { _M_ht.insert_equal(__f, __l); }
  282.   template <class _InputIterator>
  283.   hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
  284.                 const hasher& __hf, const key_equal& __eql,
  285.                 const allocator_type& __a = allocator_type())
  286.     : _M_ht(__n, __hf, __eql, __a)
  287.     { _M_ht.insert_equal(__f, __l); }
  288. #else
  289.  
  290.   hash_multiset(const value_type* __f, const value_type* __l)
  291.     : _M_ht(100, hasher(), key_equal(), allocator_type())
  292.     { _M_ht.insert_equal(__f, __l); }
  293.   hash_multiset(const value_type* __f, const value_type* __l, size_type __n)
  294.     : _M_ht(__n, hasher(), key_equal(), allocator_type())
  295.     { _M_ht.insert_equal(__f, __l); }
  296.   hash_multiset(const value_type* __f, const value_type* __l, size_type __n,
  297.                 const hasher& __hf)
  298.     : _M_ht(__n, __hf, key_equal(), allocator_type())
  299.     { _M_ht.insert_equal(__f, __l); }
  300.   hash_multiset(const value_type* __f, const value_type* __l, size_type __n,
  301.                 const hasher& __hf, const key_equal& __eql,
  302.                 const allocator_type& __a = allocator_type())
  303.     : _M_ht(__n, __hf, __eql, __a)
  304.     { _M_ht.insert_equal(__f, __l); }
  305.  
  306.   hash_multiset(const_iterator __f, const_iterator __l)
  307.     : _M_ht(100, hasher(), key_equal(), allocator_type())
  308.     { _M_ht.insert_equal(__f, __l); }
  309.   hash_multiset(const_iterator __f, const_iterator __l, size_type __n)
  310.     : _M_ht(__n, hasher(), key_equal(), allocator_type())
  311.     { _M_ht.insert_equal(__f, __l); }
  312.   hash_multiset(const_iterator __f, const_iterator __l, size_type __n,
  313.                 const hasher& __hf)
  314.     : _M_ht(__n, __hf, key_equal(), allocator_type())
  315.     { _M_ht.insert_equal(__f, __l); }
  316.   hash_multiset(const_iterator __f, const_iterator __l, size_type __n,
  317.                 const hasher& __hf, const key_equal& __eql,
  318.                 const allocator_type& __a = allocator_type())
  319.     : _M_ht(__n, __hf, __eql, __a)
  320.     { _M_ht.insert_equal(__f, __l); }
  321. #endif /*__STL_MEMBER_TEMPLATES */
  322.  
  323. public:
  324.   size_type size() const { return _M_ht.size(); }
  325.   size_type max_size() const { return _M_ht.max_size(); }
  326.   bool empty() const { return _M_ht.empty(); }
  327.   void swap(hash_multiset& hs) { _M_ht.swap(hs._M_ht); }
  328.   friend bool operator== __STL_NULL_TMPL_ARGS (const hash_multiset&,
  329.                                                const hash_multiset&);
  330.  
  331.   iterator begin() const { return _M_ht.begin(); }
  332.   iterator end() const { return _M_ht.end(); }
  333.  
  334. public:
  335.   iterator insert(const value_type& __obj)
  336.     { return _M_ht.insert_equal(__obj); }
  337. #ifdef __STL_MEMBER_TEMPLATES
  338.   template <class _InputIterator>
  339.   void insert(_InputIterator __f, _InputIterator __l) 
  340.     { _M_ht.insert_equal(__f,__l); }
  341. #else
  342.   void insert(const value_type* __f, const value_type* __l) {
  343.     _M_ht.insert_equal(__f,__l);
  344.   }
  345.   void insert(const_iterator __f, const_iterator __l) 
  346.     { _M_ht.insert_equal(__f, __l); }
  347. #endif /*__STL_MEMBER_TEMPLATES */
  348.   iterator insert_noresize(const value_type& __obj)
  349.     { return _M_ht.insert_equal_noresize(__obj); }    
  350.  
  351.   iterator find(const key_type& __key) const { return _M_ht.find(__key); }
  352.  
  353.   size_type count(const key_type& __key) const { return _M_ht.count(__key); }
  354.   
  355.   pair<iterator, iterator> equal_range(const key_type& __key) const
  356.     { return _M_ht.equal_range(__key); }
  357.  
  358.   size_type erase(const key_type& __key) {return _M_ht.erase(__key); }
  359.   void erase(iterator __it) { _M_ht.erase(__it); }
  360.   void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
  361.   void clear() { _M_ht.clear(); }
  362.  
  363. public:
  364.   void resize(size_type __hint) { _M_ht.resize(__hint); }
  365.   size_type bucket_count() const { return _M_ht.bucket_count(); }
  366.   size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
  367.   size_type elems_in_bucket(size_type __n) const
  368.     { return _M_ht.elems_in_bucket(__n); }
  369. };
  370.  
  371. template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
  372. inline bool 
  373. operator==(const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1,
  374.            const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2)
  375. {
  376.   return __hs1._M_ht == __hs2._M_ht;
  377. }
  378.  
  379. #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
  380.  
  381. template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
  382. inline void 
  383. swap(hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1,
  384.      hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2) {
  385.   __hs1.swap(__hs2);
  386. }
  387.  
  388. #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
  389.  
  390. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  391. #pragma reset woff 1174
  392. #pragma reset woff 1375
  393. #endif
  394.  
  395. __STL_END_NAMESPACE
  396.  
  397. #endif /* __SGI_STL_INTERNAL_HASH_SET_H */
  398.  
  399. // Local Variables:
  400. // mode:C++
  401. // End:
  402.