stl_hash_map.h
上传用户:sichengcw
上传日期:2009-02-17
资源大小:202k
文件大小:13k
源码类别:

STL

开发平台:

Visual C++

  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. /* NOTE: This is an internal header file, included by other STL headers.
  27.  *   You should not attempt to use it directly.
  28.  */
  29. #ifndef __SGI_STL_INTERNAL_HASH_MAP_H
  30. #define __SGI_STL_INTERNAL_HASH_MAP_H
  31. __STL_BEGIN_NAMESPACE
  32. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  33. #pragma set woff 1174
  34. #endif
  35. #ifndef __STL_LIMITED_DEFAULT_TEMPLATES
  36. template <class Key, class T, class HashFcn = hash<Key>,
  37.           class EqualKey = equal_to<Key>,
  38.           class Alloc = alloc>
  39. #else
  40. template <class Key, class T, class HashFcn, class EqualKey, 
  41.           class Alloc = alloc>
  42. #endif
  43. class hash_map
  44. {
  45. private:
  46.   typedef hashtable<pair<const Key, T>, Key, HashFcn,
  47.                     select1st<pair<const Key, T> >, EqualKey, Alloc> ht;
  48.   ht rep;
  49. public:
  50.   typedef typename ht::key_type key_type;
  51.   typedef T data_type;
  52.   typedef T mapped_type;
  53.   typedef typename ht::value_type value_type;
  54.   typedef typename ht::hasher hasher;
  55.   typedef typename ht::key_equal key_equal;
  56.   typedef typename ht::size_type size_type;
  57.   typedef typename ht::difference_type difference_type;
  58.   typedef typename ht::pointer pointer;
  59.   typedef typename ht::const_pointer const_pointer;
  60.   typedef typename ht::reference reference;
  61.   typedef typename ht::const_reference const_reference;
  62.   typedef typename ht::iterator iterator;
  63.   typedef typename ht::const_iterator const_iterator;
  64.   hasher hash_funct() const { return rep.hash_funct(); }
  65.   key_equal key_eq() const { return rep.key_eq(); }
  66. public:
  67.   hash_map() : rep(100, hasher(), key_equal()) {}
  68.   explicit hash_map(size_type n) : rep(n, hasher(), key_equal()) {}
  69.   hash_map(size_type n, const hasher& hf) : rep(n, hf, key_equal()) {}
  70.   hash_map(size_type n, const hasher& hf, const key_equal& eql)
  71.     : rep(n, hf, eql) {}
  72. #ifdef __STL_MEMBER_TEMPLATES
  73.   template <class InputIterator>
  74.   hash_map(InputIterator f, InputIterator l)
  75.     : rep(100, hasher(), key_equal()) { rep.insert_unique(f, l); }
  76.   template <class InputIterator>
  77.   hash_map(InputIterator f, InputIterator l, size_type n)
  78.     : rep(n, hasher(), key_equal()) { rep.insert_unique(f, l); }
  79.   template <class InputIterator>
  80.   hash_map(InputIterator f, InputIterator l, size_type n,
  81.            const hasher& hf)
  82.     : rep(n, hf, key_equal()) { rep.insert_unique(f, l); }
  83.   template <class InputIterator>
  84.   hash_map(InputIterator f, InputIterator l, size_type n,
  85.            const hasher& hf, const key_equal& eql)
  86.     : rep(n, hf, eql) { rep.insert_unique(f, l); }
  87. #else
  88.   hash_map(const value_type* f, const value_type* l)
  89.     : rep(100, hasher(), key_equal()) { rep.insert_unique(f, l); }
  90.   hash_map(const value_type* f, const value_type* l, size_type n)
  91.     : rep(n, hasher(), key_equal()) { rep.insert_unique(f, l); }
  92.   hash_map(const value_type* f, const value_type* l, size_type n,
  93.            const hasher& hf)
  94.     : rep(n, hf, key_equal()) { rep.insert_unique(f, l); }
  95.   hash_map(const value_type* f, const value_type* l, size_type n,
  96.            const hasher& hf, const key_equal& eql)
  97.     : rep(n, hf, eql) { rep.insert_unique(f, l); }
  98.   hash_map(const_iterator f, const_iterator l)
  99.     : rep(100, hasher(), key_equal()) { rep.insert_unique(f, l); }
  100.   hash_map(const_iterator f, const_iterator l, size_type n)
  101.     : rep(n, hasher(), key_equal()) { rep.insert_unique(f, l); }
  102.   hash_map(const_iterator f, const_iterator l, size_type n,
  103.            const hasher& hf)
  104.     : rep(n, hf, key_equal()) { rep.insert_unique(f, l); }
  105.   hash_map(const_iterator f, const_iterator l, size_type n,
  106.            const hasher& hf, const key_equal& eql)
  107.     : rep(n, hf, eql) { rep.insert_unique(f, l); }
  108. #endif /*__STL_MEMBER_TEMPLATES */
  109. public:
  110.   size_type size() const { return rep.size(); }
  111.   size_type max_size() const { return rep.max_size(); }
  112.   bool empty() const { return rep.empty(); }
  113.   void swap(hash_map& hs) { rep.swap(hs.rep); }
  114.   friend bool
  115.   operator== __STL_NULL_TMPL_ARGS (const hash_map&, const hash_map&);
  116.   iterator begin() { return rep.begin(); }
  117.   iterator end() { return rep.end(); }
  118.   const_iterator begin() const { return rep.begin(); }
  119.   const_iterator end() const { return rep.end(); }
  120. public:
  121.   pair<iterator, bool> insert(const value_type& obj)
  122.     { return rep.insert_unique(obj); }
  123. #ifdef __STL_MEMBER_TEMPLATES
  124.   template <class InputIterator>
  125.   void insert(InputIterator f, InputIterator l) { rep.insert_unique(f,l); }
  126. #else
  127.   void insert(const value_type* f, const value_type* l) {
  128.     rep.insert_unique(f,l);
  129.   }
  130.   void insert(const_iterator f, const_iterator l) { rep.insert_unique(f, l); }
  131. #endif /*__STL_MEMBER_TEMPLATES */
  132.   pair<iterator, bool> insert_noresize(const value_type& obj)
  133.     { return rep.insert_unique_noresize(obj); }    
  134.   iterator find(const key_type& key) { return rep.find(key); }
  135.   const_iterator find(const key_type& key) const { return rep.find(key); }
  136.   T& operator[](const key_type& key) {
  137.     return rep.find_or_insert(value_type(key, T())).second;
  138.   }
  139.   size_type count(const key_type& key) const { return rep.count(key); }
  140.   
  141.   pair<iterator, iterator> equal_range(const key_type& key)
  142.     { return rep.equal_range(key); }
  143.   pair<const_iterator, const_iterator> equal_range(const key_type& key) const
  144.     { return rep.equal_range(key); }
  145.   size_type erase(const key_type& key) {return rep.erase(key); }
  146.   void erase(iterator it) { rep.erase(it); }
  147.   void erase(iterator f, iterator l) { rep.erase(f, l); }
  148.   void clear() { rep.clear(); }
  149. public:
  150.   void resize(size_type hint) { rep.resize(hint); }
  151.   size_type bucket_count() const { return rep.bucket_count(); }
  152.   size_type max_bucket_count() const { return rep.max_bucket_count(); }
  153.   size_type elems_in_bucket(size_type n) const
  154.     { return rep.elems_in_bucket(n); }
  155. };
  156. template <class Key, class T, class HashFcn, class EqualKey, class Alloc>
  157. inline bool operator==(const hash_map<Key, T, HashFcn, EqualKey, Alloc>& hm1,
  158.                        const hash_map<Key, T, HashFcn, EqualKey, Alloc>& hm2)
  159. {
  160.   return hm1.rep == hm2.rep;
  161. }
  162. #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
  163. template <class Key, class T, class HashFcn, class EqualKey, class Alloc>
  164. inline void swap(hash_map<Key, T, HashFcn, EqualKey, Alloc>& hm1,
  165.                  hash_map<Key, T, HashFcn, EqualKey, Alloc>& hm2)
  166. {
  167.   hm1.swap(hm2);
  168. }
  169. #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
  170. #ifndef __STL_LIMITED_DEFAULT_TEMPLATES
  171. template <class Key, class T, class HashFcn = hash<Key>,
  172.           class EqualKey = equal_to<Key>,
  173.           class Alloc = alloc>
  174. #else
  175. template <class Key, class T, class HashFcn, class EqualKey,
  176.           class Alloc = alloc>
  177. #endif
  178. class hash_multimap
  179. {
  180. private:
  181.   typedef hashtable<pair<const Key, T>, Key, HashFcn,
  182.                     select1st<pair<const Key, T> >, EqualKey, Alloc> ht;
  183.   ht rep;
  184. public:
  185.   typedef typename ht::key_type key_type;
  186.   typedef T data_type;
  187.   typedef T mapped_type;
  188.   typedef typename ht::value_type value_type;
  189.   typedef typename ht::hasher hasher;
  190.   typedef typename ht::key_equal key_equal;
  191.   typedef typename ht::size_type size_type;
  192.   typedef typename ht::difference_type difference_type;
  193.   typedef typename ht::pointer pointer;
  194.   typedef typename ht::const_pointer const_pointer;
  195.   typedef typename ht::reference reference;
  196.   typedef typename ht::const_reference const_reference;
  197.   typedef typename ht::iterator iterator;
  198.   typedef typename ht::const_iterator const_iterator;
  199.   hasher hash_funct() const { return rep.hash_funct(); }
  200.   key_equal key_eq() const { return rep.key_eq(); }
  201. public:
  202.   hash_multimap() : rep(100, hasher(), key_equal()) {}
  203.   explicit hash_multimap(size_type n) : rep(n, hasher(), key_equal()) {}
  204.   hash_multimap(size_type n, const hasher& hf) : rep(n, hf, key_equal()) {}
  205.   hash_multimap(size_type n, const hasher& hf, const key_equal& eql)
  206.     : rep(n, hf, eql) {}
  207. #ifdef __STL_MEMBER_TEMPLATES
  208.   template <class InputIterator>
  209.   hash_multimap(InputIterator f, InputIterator l)
  210.     : rep(100, hasher(), key_equal()) { rep.insert_equal(f, l); }
  211.   template <class InputIterator>
  212.   hash_multimap(InputIterator f, InputIterator l, size_type n)
  213.     : rep(n, hasher(), key_equal()) { rep.insert_equal(f, l); }
  214.   template <class InputIterator>
  215.   hash_multimap(InputIterator f, InputIterator l, size_type n,
  216.                 const hasher& hf)
  217.     : rep(n, hf, key_equal()) { rep.insert_equal(f, l); }
  218.   template <class InputIterator>
  219.   hash_multimap(InputIterator f, InputIterator l, size_type n,
  220.                 const hasher& hf, const key_equal& eql)
  221.     : rep(n, hf, eql) { rep.insert_equal(f, l); }
  222. #else
  223.   hash_multimap(const value_type* f, const value_type* l)
  224.     : rep(100, hasher(), key_equal()) { rep.insert_equal(f, l); }
  225.   hash_multimap(const value_type* f, const value_type* l, size_type n)
  226.     : rep(n, hasher(), key_equal()) { rep.insert_equal(f, l); }
  227.   hash_multimap(const value_type* f, const value_type* l, size_type n,
  228.                 const hasher& hf)
  229.     : rep(n, hf, key_equal()) { rep.insert_equal(f, l); }
  230.   hash_multimap(const value_type* f, const value_type* l, size_type n,
  231.                 const hasher& hf, const key_equal& eql)
  232.     : rep(n, hf, eql) { rep.insert_equal(f, l); }
  233.   hash_multimap(const_iterator f, const_iterator l)
  234.     : rep(100, hasher(), key_equal()) { rep.insert_equal(f, l); }
  235.   hash_multimap(const_iterator f, const_iterator l, size_type n)
  236.     : rep(n, hasher(), key_equal()) { rep.insert_equal(f, l); }
  237.   hash_multimap(const_iterator f, const_iterator l, size_type n,
  238.                 const hasher& hf)
  239.     : rep(n, hf, key_equal()) { rep.insert_equal(f, l); }
  240.   hash_multimap(const_iterator f, const_iterator l, size_type n,
  241.                 const hasher& hf, const key_equal& eql)
  242.     : rep(n, hf, eql) { rep.insert_equal(f, l); }
  243. #endif /*__STL_MEMBER_TEMPLATES */
  244. public:
  245.   size_type size() const { return rep.size(); }
  246.   size_type max_size() const { return rep.max_size(); }
  247.   bool empty() const { return rep.empty(); }
  248.   void swap(hash_multimap& hs) { rep.swap(hs.rep); }
  249.   friend bool
  250.   operator== __STL_NULL_TMPL_ARGS (const hash_multimap&, const hash_multimap&);
  251.   iterator begin() { return rep.begin(); }
  252.   iterator end() { return rep.end(); }
  253.   const_iterator begin() const { return rep.begin(); }
  254.   const_iterator end() const { return rep.end(); }
  255. public:
  256.   iterator insert(const value_type& obj) { return rep.insert_equal(obj); }
  257. #ifdef __STL_MEMBER_TEMPLATES
  258.   template <class InputIterator>
  259.   void insert(InputIterator f, InputIterator l) { rep.insert_equal(f,l); }
  260. #else
  261.   void insert(const value_type* f, const value_type* l) {
  262.     rep.insert_equal(f,l);
  263.   }
  264.   void insert(const_iterator f, const_iterator l) { rep.insert_equal(f, l); }
  265. #endif /*__STL_MEMBER_TEMPLATES */
  266.   iterator insert_noresize(const value_type& obj)
  267.     { return rep.insert_equal_noresize(obj); }    
  268.   iterator find(const key_type& key) { return rep.find(key); }
  269.   const_iterator find(const key_type& key) const { return rep.find(key); }
  270.   size_type count(const key_type& key) const { return rep.count(key); }
  271.   
  272.   pair<iterator, iterator> equal_range(const key_type& key)
  273.     { return rep.equal_range(key); }
  274.   pair<const_iterator, const_iterator> equal_range(const key_type& key) const
  275.     { return rep.equal_range(key); }
  276.   size_type erase(const key_type& key) {return rep.erase(key); }
  277.   void erase(iterator it) { rep.erase(it); }
  278.   void erase(iterator f, iterator l) { rep.erase(f, l); }
  279.   void clear() { rep.clear(); }
  280. public:
  281.   void resize(size_type hint) { rep.resize(hint); }
  282.   size_type bucket_count() const { return rep.bucket_count(); }
  283.   size_type max_bucket_count() const { return rep.max_bucket_count(); }
  284.   size_type elems_in_bucket(size_type n) const
  285.     { return rep.elems_in_bucket(n); }
  286. };
  287. template <class Key, class T, class HF, class EqKey, class Alloc>
  288. inline bool operator==(const hash_multimap<Key, T, HF, EqKey, Alloc>& hm1,
  289.                        const hash_multimap<Key, T, HF, EqKey, Alloc>& hm2)
  290. {
  291.   return hm1.rep == hm2.rep;
  292. }
  293. #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
  294. template <class Key, class T, class HashFcn, class EqualKey, class Alloc>
  295. inline void swap(hash_multimap<Key, T, HashFcn, EqualKey, Alloc>& hm1,
  296.                  hash_multimap<Key, T, HashFcn, EqualKey, Alloc>& hm2)
  297. {
  298.   hm1.swap(hm2);
  299. }
  300. #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
  301. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  302. #pragma reset woff 1174
  303. #endif
  304. __STL_END_NAMESPACE
  305. #endif /* __SGI_STL_INTERNAL_HASH_MAP_H */
  306. // Local Variables:
  307. // mode:C++
  308. // End: