home *** CD-ROM | disk | FTP | other *** search
/ H4CK3R 14 / hacker14.iso / programacao / cwin / c.exe / $INSTDIR / include / c++ / ext / hash_map < prev    next >
Encoding:
Text File  |  2003-12-15  |  16.9 KB  |  455 lines
  1. // Hashing map implementation -*- C++ -*-
  2.  
  3. // Copyright (C) 2001, 2002 Free Software Foundation, Inc.
  4. //
  5. // This file is part of the GNU ISO C++ Library.  This library is free
  6. // software; you can redistribute it and/or modify it under the
  7. // terms of the GNU General Public License as published by the
  8. // Free Software Foundation; either version 2, or (at your option)
  9. // any later version.
  10.  
  11. // This library is distributed in the hope that it will be useful,
  12. // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14. // GNU General Public License for more details.
  15.  
  16. // You should have received a copy of the GNU General Public License along
  17. // with this library; see the file COPYING.  If not, write to the Free
  18. // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
  19. // USA.
  20.  
  21. // As a special exception, you may use this file as part of a free software
  22. // library without restriction.  Specifically, if other files instantiate
  23. // templates or use macros or inline functions from this file, or you compile
  24. // this file and link it with other files to produce an executable, this
  25. // file does not by itself cause the resulting executable to be covered by
  26. // the GNU General Public License.  This exception does not however
  27. // invalidate any other reasons why the executable file might be covered by
  28. // the GNU General Public License.
  29.  
  30. /*
  31.  * Copyright (c) 1996
  32.  * Silicon Graphics Computer Systems, Inc.
  33.  *
  34.  * Permission to use, copy, modify, distribute and sell this software
  35.  * and its documentation for any purpose is hereby granted without fee,
  36.  * provided that the above copyright notice appear in all copies and
  37.  * that both that copyright notice and this permission notice appear
  38.  * in supporting documentation.  Silicon Graphics makes no
  39.  * representations about the suitability of this software for any
  40.  * purpose.  It is provided "as is" without express or implied warranty.
  41.  *
  42.  *
  43.  * Copyright (c) 1994
  44.  * Hewlett-Packard Company
  45.  *
  46.  * Permission to use, copy, modify, distribute and sell this software
  47.  * and its documentation for any purpose is hereby granted without fee,
  48.  * provided that the above copyright notice appear in all copies and
  49.  * that both that copyright notice and this permission notice appear
  50.  * in supporting documentation.  Hewlett-Packard Company makes no
  51.  * representations about the suitability of this software for any
  52.  * purpose.  It is provided "as is" without express or implied warranty.
  53.  *
  54.  */
  55.  
  56. /** @file ext/hash_map
  57.  *  This file is a GNU extension to the Standard C++ Library (possibly
  58.  *  containing extensions from the HP/SGI STL subset).  You should only
  59.  *  include this header if you are using GCC 3 or later.
  60.  */
  61.  
  62. #ifndef __SGI_STL_INTERNAL_HASH_MAP_H
  63. #define __SGI_STL_INTERNAL_HASH_MAP_H
  64.  
  65. #include <ext/stl_hashtable.h>
  66. #include <bits/concept_check.h>
  67.  
  68. namespace __gnu_cxx
  69. {
  70. using std::equal_to;
  71. using std::allocator;
  72. using std::pair;
  73. using std::_Select1st;
  74.  
  75. // Forward declaration of equality operator; needed for friend declaration.
  76.  
  77. template <class _Key, class _Tp,
  78.           class _HashFcn  = hash<_Key>,
  79.           class _EqualKey = equal_to<_Key>,
  80.           class _Alloc =  allocator<_Tp> >
  81. class hash_map;
  82.  
  83. template <class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc>
  84. inline bool operator==(const hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>&,
  85.                        const hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>&);
  86. /**
  87.  *  This is an SGI extension.
  88.  *  @ingroup SGIextensions
  89.  *  @doctodo
  90. */
  91. template <class _Key, class _Tp, class _HashFcn, class _EqualKey,
  92.           class _Alloc>
  93. class hash_map
  94. {
  95. private:
  96.   typedef hashtable<pair<const _Key,_Tp>,_Key,_HashFcn,
  97.                     _Select1st<pair<const _Key,_Tp> >,_EqualKey,_Alloc> _Ht;
  98.   _Ht _M_ht;
  99.  
  100. public:
  101.   typedef typename _Ht::key_type key_type;
  102.   typedef _Tp data_type;
  103.   typedef _Tp mapped_type;
  104.   typedef typename _Ht::value_type value_type;
  105.   typedef typename _Ht::hasher hasher;
  106.   typedef typename _Ht::key_equal key_equal;
  107.   
  108.   typedef typename _Ht::size_type size_type;
  109.   typedef typename _Ht::difference_type difference_type;
  110.   typedef typename _Ht::pointer pointer;
  111.   typedef typename _Ht::const_pointer const_pointer;
  112.   typedef typename _Ht::reference reference;
  113.   typedef typename _Ht::const_reference const_reference;
  114.  
  115.   typedef typename _Ht::iterator iterator;
  116.   typedef typename _Ht::const_iterator const_iterator;
  117.  
  118.   typedef typename _Ht::allocator_type allocator_type;
  119.  
  120.   hasher hash_funct() const { return _M_ht.hash_funct(); }
  121.   key_equal key_eq() const { return _M_ht.key_eq(); }
  122.   allocator_type get_allocator() const { return _M_ht.get_allocator(); }
  123.  
  124. public:
  125.   hash_map() : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
  126.   explicit hash_map(size_type __n)
  127.     : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
  128.   hash_map(size_type __n, const hasher& __hf)
  129.     : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
  130.   hash_map(size_type __n, const hasher& __hf, const key_equal& __eql,
  131.            const allocator_type& __a = allocator_type())
  132.     : _M_ht(__n, __hf, __eql, __a) {}
  133.  
  134.   template <class _InputIterator>
  135.   hash_map(_InputIterator __f, _InputIterator __l)
  136.     : _M_ht(100, hasher(), key_equal(), allocator_type())
  137.     { _M_ht.insert_unique(__f, __l); }
  138.   template <class _InputIterator>
  139.   hash_map(_InputIterator __f, _InputIterator __l, size_type __n)
  140.     : _M_ht(__n, hasher(), key_equal(), allocator_type())
  141.     { _M_ht.insert_unique(__f, __l); }
  142.   template <class _InputIterator>
  143.   hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
  144.            const hasher& __hf)
  145.     : _M_ht(__n, __hf, key_equal(), allocator_type())
  146.     { _M_ht.insert_unique(__f, __l); }
  147.   template <class _InputIterator>
  148.   hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
  149.            const hasher& __hf, const key_equal& __eql,
  150.            const allocator_type& __a = allocator_type())
  151.     : _M_ht(__n, __hf, __eql, __a)
  152.     { _M_ht.insert_unique(__f, __l); }
  153.  
  154. public:
  155.   size_type size() const { return _M_ht.size(); }
  156.   size_type max_size() const { return _M_ht.max_size(); }
  157.   bool empty() const { return _M_ht.empty(); }
  158.   void swap(hash_map& __hs) { _M_ht.swap(__hs._M_ht); }
  159.  
  160.   template <class _K1, class _T1, class _HF, class _EqK, class _Al>
  161.   friend bool operator== (const hash_map<_K1, _T1, _HF, _EqK, _Al>&,
  162.                           const hash_map<_K1, _T1, _HF, _EqK, _Al>&);
  163.  
  164.   iterator begin() { return _M_ht.begin(); }
  165.   iterator end() { return _M_ht.end(); }
  166.   const_iterator begin() const { return _M_ht.begin(); }
  167.   const_iterator end() const { return _M_ht.end(); }
  168.  
  169. public:
  170.   pair<iterator,bool> insert(const value_type& __obj)
  171.     { return _M_ht.insert_unique(__obj); }
  172.   template <class _InputIterator>
  173.   void insert(_InputIterator __f, _InputIterator __l)
  174.     { _M_ht.insert_unique(__f,__l); }
  175.   pair<iterator,bool> insert_noresize(const value_type& __obj)
  176.     { return _M_ht.insert_unique_noresize(__obj); }    
  177.  
  178.   iterator find(const key_type& __key) { return _M_ht.find(__key); }
  179.   const_iterator find(const key_type& __key) const 
  180.     { return _M_ht.find(__key); }
  181.  
  182.   _Tp& operator[](const key_type& __key) {
  183.     return _M_ht.find_or_insert(value_type(__key, _Tp())).second;
  184.   }
  185.  
  186.   size_type count(const key_type& __key) const { return _M_ht.count(__key); }
  187.   
  188.   pair<iterator, iterator> equal_range(const key_type& __key)
  189.     { return _M_ht.equal_range(__key); }
  190.   pair<const_iterator, const_iterator>
  191.   equal_range(const key_type& __key) const
  192.     { return _M_ht.equal_range(__key); }
  193.  
  194.   size_type erase(const key_type& __key) {return _M_ht.erase(__key); }
  195.   void erase(iterator __it) { _M_ht.erase(__it); }
  196.   void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
  197.   void clear() { _M_ht.clear(); }
  198.  
  199.   void resize(size_type __hint) { _M_ht.resize(__hint); }
  200.   size_type bucket_count() const { return _M_ht.bucket_count(); }
  201.   size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
  202.   size_type elems_in_bucket(size_type __n) const
  203.     { return _M_ht.elems_in_bucket(__n); }
  204. };
  205.  
  206. template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc>
  207. inline bool 
  208. operator==(const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1,
  209.            const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2)
  210. {
  211.   return __hm1._M_ht == __hm2._M_ht;
  212. }
  213.  
  214. template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc>
  215. inline bool 
  216. operator!=(const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1,
  217.            const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2) {
  218.   return !(__hm1 == __hm2);
  219. }
  220.  
  221. template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc>
  222. inline void 
  223. swap(hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1,
  224.      hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2)
  225. {
  226.   __hm1.swap(__hm2);
  227. }
  228.  
  229. // Forward declaration of equality operator; needed for friend declaration.
  230.  
  231. template <class _Key, class _Tp,
  232.           class _HashFcn  = hash<_Key>,
  233.           class _EqualKey = equal_to<_Key>,
  234.           class _Alloc =  allocator<_Tp> >
  235. class hash_multimap;
  236.  
  237. template <class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
  238. inline bool 
  239. operator==(const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm1,
  240.            const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm2);
  241.  
  242. /**
  243.  *  This is an SGI extension.
  244.  *  @ingroup SGIextensions
  245.  *  @doctodo
  246. */
  247. template <class _Key, class _Tp, class _HashFcn, class _EqualKey, class _Alloc>
  248. class hash_multimap
  249. {
  250.   // concept requirements
  251.   __glibcpp_class_requires(_Key, _SGIAssignableConcept)
  252.   __glibcpp_class_requires(_Tp, _SGIAssignableConcept)
  253.   __glibcpp_class_requires3(_HashFcn, size_t, _Key, _UnaryFunctionConcept);
  254.   __glibcpp_class_requires3(_EqualKey, _Key, _Key, _BinaryPredicateConcept);
  255.  
  256. private:
  257.   typedef hashtable<pair<const _Key, _Tp>, _Key, _HashFcn,
  258.                     _Select1st<pair<const _Key, _Tp> >, _EqualKey, _Alloc> 
  259.           _Ht;
  260.   _Ht _M_ht;
  261.  
  262. public:
  263.   typedef typename _Ht::key_type key_type;
  264.   typedef _Tp data_type;
  265.   typedef _Tp mapped_type;
  266.   typedef typename _Ht::value_type value_type;
  267.   typedef typename _Ht::hasher hasher;
  268.   typedef typename _Ht::key_equal key_equal;
  269.  
  270.   typedef typename _Ht::size_type size_type;
  271.   typedef typename _Ht::difference_type difference_type;
  272.   typedef typename _Ht::pointer pointer;
  273.   typedef typename _Ht::const_pointer const_pointer;
  274.   typedef typename _Ht::reference reference;
  275.   typedef typename _Ht::const_reference const_reference;
  276.  
  277.   typedef typename _Ht::iterator iterator;
  278.   typedef typename _Ht::const_iterator const_iterator;
  279.  
  280.   typedef typename _Ht::allocator_type allocator_type;
  281.  
  282.   hasher hash_funct() const { return _M_ht.hash_funct(); }
  283.   key_equal key_eq() const { return _M_ht.key_eq(); }
  284.   allocator_type get_allocator() const { return _M_ht.get_allocator(); }
  285.  
  286. public:
  287.   hash_multimap() : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
  288.   explicit hash_multimap(size_type __n)
  289.     : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
  290.   hash_multimap(size_type __n, const hasher& __hf)
  291.     : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
  292.   hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql,
  293.                 const allocator_type& __a = allocator_type())
  294.     : _M_ht(__n, __hf, __eql, __a) {}
  295.  
  296.   template <class _InputIterator>
  297.   hash_multimap(_InputIterator __f, _InputIterator __l)
  298.     : _M_ht(100, hasher(), key_equal(), allocator_type())
  299.     { _M_ht.insert_equal(__f, __l); }
  300.   template <class _InputIterator>
  301.   hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n)
  302.     : _M_ht(__n, hasher(), key_equal(), allocator_type())
  303.     { _M_ht.insert_equal(__f, __l); }
  304.   template <class _InputIterator>
  305.   hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
  306.                 const hasher& __hf)
  307.     : _M_ht(__n, __hf, key_equal(), allocator_type())
  308.     { _M_ht.insert_equal(__f, __l); }
  309.   template <class _InputIterator>
  310.   hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
  311.                 const hasher& __hf, const key_equal& __eql,
  312.                 const allocator_type& __a = allocator_type())
  313.     : _M_ht(__n, __hf, __eql, __a)
  314.     { _M_ht.insert_equal(__f, __l); }
  315.  
  316. public:
  317.   size_type size() const { return _M_ht.size(); }
  318.   size_type max_size() const { return _M_ht.max_size(); }
  319.   bool empty() const { return _M_ht.empty(); }
  320.   void swap(hash_multimap& __hs) { _M_ht.swap(__hs._M_ht); }
  321.  
  322.   template <class _K1, class _T1, class _HF, class _EqK, class _Al>
  323.   friend bool operator== (const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&,
  324.                           const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&);
  325.  
  326.   iterator begin() { return _M_ht.begin(); }
  327.   iterator end() { return _M_ht.end(); }
  328.   const_iterator begin() const { return _M_ht.begin(); }
  329.   const_iterator end() const { return _M_ht.end(); }
  330.  
  331. public:
  332.   iterator insert(const value_type& __obj) 
  333.     { return _M_ht.insert_equal(__obj); }
  334.   template <class _InputIterator>
  335.   void insert(_InputIterator __f, _InputIterator __l) 
  336.     { _M_ht.insert_equal(__f,__l); }
  337.   iterator insert_noresize(const value_type& __obj)
  338.     { return _M_ht.insert_equal_noresize(__obj); }    
  339.  
  340.   iterator find(const key_type& __key) { return _M_ht.find(__key); }
  341.   const_iterator find(const key_type& __key) const 
  342.     { return _M_ht.find(__key); }
  343.  
  344.   size_type count(const key_type& __key) const { return _M_ht.count(__key); }
  345.   
  346.   pair<iterator, iterator> equal_range(const key_type& __key)
  347.     { return _M_ht.equal_range(__key); }
  348.   pair<const_iterator, const_iterator>
  349.   equal_range(const key_type& __key) const
  350.     { return _M_ht.equal_range(__key); }
  351.  
  352.   size_type erase(const key_type& __key) {return _M_ht.erase(__key); }
  353.   void erase(iterator __it) { _M_ht.erase(__it); }
  354.   void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
  355.   void clear() { _M_ht.clear(); }
  356.  
  357. public:
  358.   void resize(size_type __hint) { _M_ht.resize(__hint); }
  359.   size_type bucket_count() const { return _M_ht.bucket_count(); }
  360.   size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
  361.   size_type elems_in_bucket(size_type __n) const
  362.     { return _M_ht.elems_in_bucket(__n); }
  363. };
  364.  
  365. template <class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
  366. inline bool 
  367. operator==(const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm1,
  368.            const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm2)
  369. {
  370.   return __hm1._M_ht == __hm2._M_ht;
  371. }
  372.  
  373. template <class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
  374. inline bool 
  375. operator!=(const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm1,
  376.            const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm2) {
  377.   return !(__hm1 == __hm2);
  378. }
  379.  
  380. template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc>
  381. inline void 
  382. swap(hash_multimap<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1,
  383.      hash_multimap<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2)
  384. {
  385.   __hm1.swap(__hm2);
  386. }
  387.  
  388. } // namespace __gnu_cxx
  389.  
  390. namespace std
  391. {
  392. // Specialization of insert_iterator so that it will work for hash_map
  393. // and hash_multimap.
  394.  
  395. template <class _Key, class _Tp, class _HashFn,  class _EqKey, class _Alloc>
  396. class insert_iterator<__gnu_cxx::hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc> > {
  397. protected:
  398.   typedef __gnu_cxx::hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc> _Container;
  399.   _Container* container;
  400. public:
  401.   typedef _Container          container_type;
  402.   typedef output_iterator_tag iterator_category;
  403.   typedef void                value_type;
  404.   typedef void                difference_type;
  405.   typedef void                pointer;
  406.   typedef void                reference;
  407.  
  408.   insert_iterator(_Container& __x) : container(&__x) {}
  409.   insert_iterator(_Container& __x, typename _Container::iterator)
  410.     : container(&__x) {}
  411.   insert_iterator<_Container>&
  412.   operator=(const typename _Container::value_type& __value) { 
  413.     container->insert(__value);
  414.     return *this;
  415.   }
  416.   insert_iterator<_Container>& operator*() { return *this; }
  417.   insert_iterator<_Container>& operator++() { return *this; }
  418.   insert_iterator<_Container>& operator++(int) { return *this; }
  419. };
  420.  
  421. template <class _Key, class _Tp, class _HashFn,  class _EqKey, class _Alloc>
  422. class insert_iterator<__gnu_cxx::hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc> > {
  423. protected:
  424.   typedef __gnu_cxx::hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc> _Container;
  425.   _Container* container;
  426.   typename _Container::iterator iter;
  427. public:
  428.   typedef _Container          container_type;
  429.   typedef output_iterator_tag iterator_category;
  430.   typedef void                value_type;
  431.   typedef void                difference_type;
  432.   typedef void                pointer;
  433.   typedef void                reference;
  434.  
  435.   insert_iterator(_Container& __x) : container(&__x) {}
  436.   insert_iterator(_Container& __x, typename _Container::iterator)
  437.     : container(&__x) {}
  438.   insert_iterator<_Container>&
  439.   operator=(const typename _Container::value_type& __value) { 
  440.     container->insert(__value);
  441.     return *this;
  442.   }
  443.   insert_iterator<_Container>& operator*() { return *this; }
  444.   insert_iterator<_Container>& operator++() { return *this; }
  445.   insert_iterator<_Container>& operator++(int) { return *this; }
  446. };
  447.  
  448. } // namespace std
  449.  
  450. #endif /* __SGI_STL_INTERNAL_HASH_MAP_H */
  451.  
  452. // Local Variables:
  453. // mode:C++
  454. // End:
  455.