home *** CD-ROM | disk | FTP | other *** search
/ Beginning C++ Through Gam…rogramming (2nd Edition) / BCGP2E.ISO / bloodshed / devcpp-4.9.9.2_setup.exe / hash_map.h < prev    next >
C/C++ Source or Header  |  2005-01-29  |  9KB  |  271 lines
  1. // Debugging hash_map implementation -*- C++ -*-
  2.  
  3. // Copyright (C) 2003
  4. // Free Software Foundation, Inc.
  5. //
  6. // This file is part of the GNU ISO C++ Library.  This library is free
  7. // software; you can redistribute it and/or modify it under the
  8. // terms of the GNU General Public License as published by the
  9. // Free Software Foundation; either version 2, or (at your option)
  10. // any later version.
  11.  
  12. // This library is distributed in the hope that it will be useful,
  13. // but WITHOUT ANY WARRANTY; without even the implied warranty of
  14. // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15. // GNU General Public License for more details.
  16.  
  17. // You should have received a copy of the GNU General Public License along
  18. // with this library; see the file COPYING.  If not, write to the Free
  19. // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
  20. // USA.
  21.  
  22. // As a special exception, you may use this file as part of a free software
  23. // library without restriction.  Specifically, if other files instantiate
  24. // templates or use macros or inline functions from this file, or you compile
  25. // this file and link it with other files to produce an executable, this
  26. // file does not by itself cause the resulting executable to be covered by
  27. // the GNU General Public License.  This exception does not however
  28. // invalidate any other reasons why the executable file might be covered by
  29. // the GNU General Public License.
  30.  
  31. #ifndef _GLIBCXX_DEBUG_HASH_MAP_H
  32. #define _GLIBCXX_DEBUG_HASH_MAP_H 1
  33.  
  34. #include <debug/safe_sequence.h>
  35. #include <debug/safe_iterator.h>
  36.  
  37. namespace __gnu_debug_def
  38. {
  39.   template<typename _Value, typename _Tp,
  40.        typename _HashFcn  = __gnu_cxx::hash<_Value>,
  41.        typename _EqualKey = std::equal_to<_Value>,
  42.        typename _Alloc = std::allocator<_Value> >
  43.     class hash_map
  44.     : public __gnu_cxx::hash_map<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>,
  45.       public __gnu_debug::_Safe_sequence<hash_map<_Value, _Tp, _HashFcn,
  46.                          _EqualKey, _Alloc> >
  47.     {
  48.       typedef __gnu_cxx::hash_map<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>
  49.                                   _Base;
  50.       typedef __gnu_debug::_Safe_sequence<hash_map>     _Safe_base;
  51.  
  52.     public:
  53.       typedef typename _Base::key_type        key_type;
  54.       typedef typename _Base::data_type       data_type;
  55.       typedef typename _Base::mapped_type     mapped_type;
  56.       typedef typename _Base::value_type      value_type;
  57.       typedef typename _Base::hasher          hasher;
  58.       typedef typename _Base::key_equal       key_equal;
  59.       typedef typename _Base::size_type       size_type;
  60.       typedef typename _Base::difference_type difference_type;
  61.       typedef typename _Base::pointer         pointer;
  62.       typedef typename _Base::const_pointer   const_pointer;
  63.       typedef typename _Base::reference       reference;
  64.       typedef typename _Base::const_reference const_reference;
  65.  
  66.       typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, hash_map>
  67.                           iterator;
  68.       typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
  69.                       hash_map>
  70.                           const_iterator;
  71.  
  72.       typedef typename _Base::allocator_type  allocator_type;
  73.  
  74.       using _Base::hash_funct;
  75.       using _Base::key_eq;
  76.       using _Base::get_allocator;
  77.  
  78.       hash_map() { }
  79.  
  80.       explicit hash_map(size_type __n) : _Base(__n) { }
  81.  
  82.       hash_map(size_type __n, const hasher& __hf) : _Base(__n, __hf) { }
  83.  
  84.       hash_map(size_type __n, const hasher& __hf, const key_equal& __eql,
  85.            const allocator_type& __a = allocator_type())
  86.       : _Base(__n, __hf, __eql, __a) { }
  87.  
  88.       template<typename _InputIterator>
  89.         hash_map(_InputIterator __f, _InputIterator __l)
  90.         : _Base(__gnu_debug::__check_valid_range(__f, __l), __l) { }
  91.  
  92.       template<typename _InputIterator>
  93.         hash_map(_InputIterator __f, _InputIterator __l, size_type __n)
  94.     : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n) { }
  95.  
  96.       template<typename _InputIterator>
  97.         hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
  98.          const hasher& __hf)
  99.         : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n, __hf) { }
  100.  
  101.       template<typename _InputIterator>
  102.         hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
  103.          const hasher& __hf, const key_equal& __eql,
  104.          const allocator_type& __a = allocator_type())
  105.     : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n, __hf,
  106.         __eql, __a) { }
  107.  
  108.       hash_map(const _Base& __x) : _Base(__x), _Safe_base() { }
  109.  
  110.       using _Base::size;
  111.       using _Base::max_size;
  112.       using _Base::empty;
  113.  
  114.       void
  115.       swap(hash_map& __x)
  116.       {
  117.     _Base::swap(__x);
  118.     this->_M_swap(__x);
  119.       }
  120.  
  121.       iterator
  122.       begin() { return iterator(_Base::begin(), this); }
  123.  
  124.       iterator
  125.       end() { return iterator(_Base::end(),   this); }
  126.  
  127.       const_iterator
  128.       begin() const
  129.       { return const_iterator(_Base::begin(), this); }
  130.  
  131.       const_iterator
  132.       end() const
  133.       { return const_iterator(_Base::end(),   this); }
  134.  
  135.       std::pair<iterator, bool>
  136.       insert(const value_type& __obj)
  137.       {
  138.     std::pair<typename _Base::iterator, bool> __res = _Base::insert(__obj);
  139.     return std::make_pair(iterator(__res.first, this), __res.second);
  140.       }
  141.  
  142.       template <typename _InputIterator>
  143.         void
  144.         insert(_InputIterator __first, _InputIterator __last)
  145.         {
  146.       __glibcxx_check_valid_range(__first, __last);
  147.       _Base::insert(__first.base(), __last.base());
  148.     }
  149.  
  150.  
  151.       std::pair<iterator, bool>
  152.       insert_noresize(const value_type& __obj)
  153.       {
  154.     std::pair<typename _Base::iterator, bool> __res =
  155.                                             _Base::insert_noresize(__obj);
  156.     return std::make_pair(iterator(__res.first, this), __res.second);
  157.       }
  158.  
  159.       iterator
  160.       find(const key_type& __key)
  161.       { return iterator(_Base::find(__key), this); }
  162.  
  163.       const_iterator
  164.       find(const key_type& __key) const
  165.       { return const_iterator(_Base::find(__key), this); }
  166.  
  167.       using _Base::operator[];
  168.       using _Base::count;
  169.  
  170.       std::pair<iterator, iterator>
  171.       equal_range(const key_type& __key)
  172.       {
  173.     typedef typename _Base::iterator _Base_iterator;
  174.     std::pair<_Base_iterator, _Base_iterator> __res =
  175.                       _Base::equal_range(__key);
  176.     return std::make_pair(iterator(__res.first, this),
  177.                   iterator(__res.second, this));
  178.       }
  179.  
  180.       std::pair<const_iterator, const_iterator>
  181.       equal_range(const key_type& __key) const
  182.       {
  183.     typedef typename _Base::const_iterator _Base_iterator;
  184.     std::pair<_Base_iterator, _Base_iterator> __res =
  185.     _Base::equal_range(__key);
  186.     return std::make_pair(const_iterator(__res.first, this),
  187.                   const_iterator(__res.second, this));
  188.       }
  189.  
  190.       size_type
  191.       erase(const key_type& __key)
  192.       {
  193.     iterator __victim(_Base::find(__key), this);
  194.     if (__victim != end())
  195.       return this->erase(__victim), 1;
  196.     else
  197.       return 0;
  198.       }
  199.  
  200.       void
  201.       erase(iterator __it)
  202.       {
  203.     __glibcxx_check_erase(__it);
  204.     __it._M_invalidate();
  205.     _Base::erase(__it.base());
  206.       }
  207.  
  208.       void
  209.       erase(iterator __first, iterator __last)
  210.       {
  211.     __glibcxx_check_erase_range(__first, __last);
  212.     for (iterator __tmp = __first; __tmp != __last;)
  213.     {
  214.       iterator __victim = __tmp++;
  215.       __victim._M_invalidate();
  216.     }
  217.     _Base::erase(__first.base(), __last.base());
  218.       }
  219.  
  220.       void
  221.       clear()
  222.       {
  223.     _Base::clear();
  224.     this->_M_invalidate_all();
  225.       }
  226.  
  227.       using _Base::resize;
  228.       using _Base::bucket_count;
  229.       using _Base::max_bucket_count;
  230.       using _Base::elems_in_bucket;
  231.  
  232.       _Base&
  233.       _M_base()       { return *this; }
  234.  
  235.       const _Base&
  236.       _M_base() const { return *this; }
  237.  
  238.     private:
  239.       void
  240.       _M_invalidate_all()
  241.       {
  242.     typedef typename _Base::const_iterator _Base_const_iterator;
  243.     typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
  244.     this->_M_invalidate_if(_Not_equal(_M_base().end()));
  245.       }
  246.     };
  247.  
  248.   template<typename _Value, typename _Tp, typename _HashFcn,
  249.        typename _EqualKey, typename _Alloc>
  250.     inline bool
  251.     operator==(const hash_map<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>& __x,
  252.            const hash_map<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>& __y)
  253.     { return __x._M_base() == __y._M_base(); }
  254.  
  255.   template<typename _Value, typename _Tp, typename _HashFcn,
  256.        typename _EqualKey, typename _Alloc>
  257.     inline bool
  258.     operator!=(const hash_map<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>& __x,
  259.            const hash_map<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>& __y)
  260.     { return __x._M_base() != __y._M_base(); }
  261.  
  262.   template<typename _Value, typename _Tp, typename _HashFcn,
  263.        typename _EqualKey, typename _Alloc>
  264.     inline void
  265.     swap(hash_map<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>& __x,
  266.      hash_map<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>& __y)
  267.     { __x.swap(__y); }
  268. } // namespace __gnu_debug_def
  269.  
  270. #endif
  271.