[thirdparty/gcc.git] / libstdc++-v3 / include / ext / hash_map

// Hashing map implementation -*- C++ -*-

// Copyright (C) 2001, 2002, 2004, 2005, 2006 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 2, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License along
// with this library; see the file COPYING.  If not, write to the Free
// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
// USA.

// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the GNU General Public License.

/*
 * Copyright (c) 1996
 * Silicon Graphics Computer Systems, Inc.
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Silicon Graphics makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 *
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Hewlett-Packard Company makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 *
 */

/** @file ext/hash_map
 *  This file is a GNU extension to the Standard C++ Library (possibly
 *  containing extensions from the HP/SGI STL subset).
 */

#ifndef _HASH_MAP
#define _HASH_MAP 1

#include <bits/c++config.h>
#include <ext/hashtable.h>
#include <bits/concept_check.h>

_GLIBCXX_BEGIN_NESTED_NAMESPACE(__gnu_cxx, _GLIBCXX_EXT_D)

  using std::equal_to;
  using std::allocator;
  using std::pair;
  using std::_Select1st;

  /**
   *  This is an SGI extension.
   *  @ingroup SGIextensions
   *  @doctodo
   */
  template<class _Key, class _Tp, class _HashFn = hash<_Key>,
	   class _EqualKey = equal_to<_Key>, class _Alloc = allocator<_Tp> >
    class hash_map
    {
    private:
      typedef hashtable<pair<const _Key, _Tp>,_Key, _HashFn,
			_Select1st<pair<const _Key, _Tp> >,
			_EqualKey, _Alloc> _Ht;

      _Ht _M_ht;

    public:
      typedef typename _Ht::key_type key_type;
      typedef _Tp data_type;
      typedef _Tp mapped_type;
      typedef typename _Ht::value_type value_type;
      typedef typename _Ht::hasher hasher;
      typedef typename _Ht::key_equal key_equal;
      
      typedef typename _Ht::size_type size_type;
      typedef typename _Ht::difference_type difference_type;
      typedef typename _Ht::pointer pointer;
      typedef typename _Ht::const_pointer const_pointer;
      typedef typename _Ht::reference reference;
      typedef typename _Ht::const_reference const_reference;
      
      typedef typename _Ht::iterator iterator;
      typedef typename _Ht::const_iterator const_iterator;
      
      typedef typename _Ht::allocator_type allocator_type;
      
      hasher
      hash_funct() const
      { return _M_ht.hash_funct(); }

      key_equal
      key_eq() const
      { return _M_ht.key_eq(); }

      allocator_type
      get_allocator() const
      { return _M_ht.get_allocator(); }

    public:
      hash_map()
      : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
  
      explicit
      hash_map(size_type __n)
      : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}

      hash_map(size_type __n, const hasher& __hf)
      : _M_ht(__n, __hf, key_equal(), allocator_type()) {}

      hash_map(size_type __n, const hasher& __hf, const key_equal& __eql,
	       const allocator_type& __a = allocator_type())
      : _M_ht(__n, __hf, __eql, __a) {}

      template<class _InputIterator>
        hash_map(_InputIterator __f, _InputIterator __l)
	: _M_ht(100, hasher(), key_equal(), allocator_type())
        { _M_ht.insert_unique(__f, __l); }

      template<class _InputIterator>
        hash_map(_InputIterator __f, _InputIterator __l, size_type __n)
	: _M_ht(__n, hasher(), key_equal(), allocator_type())
        { _M_ht.insert_unique(__f, __l); }

      template<class _InputIterator>
        hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
		 const hasher& __hf)
	: _M_ht(__n, __hf, key_equal(), allocator_type())
        { _M_ht.insert_unique(__f, __l); }

      template<class _InputIterator>
        hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
		 const hasher& __hf, const key_equal& __eql,
		 const allocator_type& __a = allocator_type())
	: _M_ht(__n, __hf, __eql, __a)
        { _M_ht.insert_unique(__f, __l); }

    public:
      size_type
      size() const
      { return _M_ht.size(); }
      
      size_type
      max_size() const
      { return _M_ht.max_size(); }
      
      bool
      empty() const
      { return _M_ht.empty(); }
  
      void
      swap(hash_map& __hs)
      { _M_ht.swap(__hs._M_ht); }

      template<class _K1, class _T1, class _HF, class _EqK, class _Al>
        friend bool
        operator== (const hash_map<_K1, _T1, _HF, _EqK, _Al>&,
		    const hash_map<_K1, _T1, _HF, _EqK, _Al>&);

      iterator
      begin()
      { return _M_ht.begin(); }

      iterator
      end()
      { return _M_ht.end(); }

      const_iterator
      begin() const
      { return _M_ht.begin(); }

      const_iterator
      end() const
      { return _M_ht.end(); }

    public:
      pair<iterator, bool>
      insert(const value_type& __obj)
      { return _M_ht.insert_unique(__obj); }

      template<class _InputIterator>
        void
        insert(_InputIterator __f, _InputIterator __l)
        { _M_ht.insert_unique(__f, __l); }

      pair<iterator, bool>
      insert_noresize(const value_type& __obj)
      { return _M_ht.insert_unique_noresize(__obj); }

      iterator
      find(const key_type& __key)
      { return _M_ht.find(__key); }

      const_iterator
      find(const key_type& __key) const
      { return _M_ht.find(__key); }

      _Tp&
      operator[](const key_type& __key)
      { return _M_ht.find_or_insert(value_type(__key, _Tp())).second; }

      size_type
      count(const key_type& __key) const
      { return _M_ht.count(__key); }

      pair<iterator, iterator>
      equal_range(const key_type& __key)
      { return _M_ht.equal_range(__key); }

      pair<const_iterator, const_iterator>
      equal_range(const key_type& __key) const
      { return _M_ht.equal_range(__key); }

      size_type
      erase(const key_type& __key)
      {return _M_ht.erase(__key); }

      void
      erase(iterator __it)
      { _M_ht.erase(__it); }

      void
      erase(iterator __f, iterator __l)
      { _M_ht.erase(__f, __l); }

      void
      clear()
      { _M_ht.clear(); }

      void
      resize(size_type __hint)
      { _M_ht.resize(__hint); }

      size_type
      bucket_count() const
      { return _M_ht.bucket_count(); }

      size_type
      max_bucket_count() const
      { return _M_ht.max_bucket_count(); }

      size_type
      elems_in_bucket(size_type __n) const
      { return _M_ht.elems_in_bucket(__n); }
    };

  template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
    inline bool
    operator==(const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
	       const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
    { return __hm1._M_ht == __hm2._M_ht; }

  template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
    inline bool
    operator!=(const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
	       const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
    { return !(__hm1 == __hm2); }

  template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
    inline void
    swap(hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
	 hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
    { __hm1.swap(__hm2); }


  /**
   *  This is an SGI extension.
   *  @ingroup SGIextensions
   *  @doctodo
   */
  template<class _Key, class _Tp,
	   class _HashFn = hash<_Key>,
	   class _EqualKey = equal_to<_Key>,
	   class _Alloc = allocator<_Tp> >
    class hash_multimap
    {
      // concept requirements
      __glibcxx_class_requires(_Key, _SGIAssignableConcept)
      __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
      __glibcxx_class_requires3(_HashFn, size_t, _Key, _UnaryFunctionConcept)
      __glibcxx_class_requires3(_EqualKey, _Key, _Key, _BinaryPredicateConcept)
	
    private:
      typedef hashtable<pair<const _Key, _Tp>, _Key, _HashFn,
			_Select1st<pair<const _Key, _Tp> >, _EqualKey, _Alloc>
          _Ht;

      _Ht _M_ht;

    public:
      typedef typename _Ht::key_type key_type;
      typedef _Tp data_type;
      typedef _Tp mapped_type;
      typedef typename _Ht::value_type value_type;
      typedef typename _Ht::hasher hasher;
      typedef typename _Ht::key_equal key_equal;
      
      typedef typename _Ht::size_type size_type;
      typedef typename _Ht::difference_type difference_type;
      typedef typename _Ht::pointer pointer;
      typedef typename _Ht::const_pointer const_pointer;
      typedef typename _Ht::reference reference;
      typedef typename _Ht::const_reference const_reference;
      
      typedef typename _Ht::iterator iterator;
      typedef typename _Ht::const_iterator const_iterator;
      
      typedef typename _Ht::allocator_type allocator_type;
      
      hasher
      hash_funct() const
      { return _M_ht.hash_funct(); }

      key_equal
      key_eq() const
      { return _M_ht.key_eq(); }

      allocator_type
      get_allocator() const
      { return _M_ht.get_allocator(); }

    public:
      hash_multimap()
      : _M_ht(100, hasher(), key_equal(), allocator_type()) {}

      explicit
      hash_multimap(size_type __n)
      : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}

      hash_multimap(size_type __n, const hasher& __hf)
      : _M_ht(__n, __hf, key_equal(), allocator_type()) {}

      hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql,
		    const allocator_type& __a = allocator_type())
      : _M_ht(__n, __hf, __eql, __a) {}

      template<class _InputIterator>
        hash_multimap(_InputIterator __f, _InputIterator __l)
	: _M_ht(100, hasher(), key_equal(), allocator_type())
        { _M_ht.insert_equal(__f, __l); }

      template<class _InputIterator>
        hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n)
	: _M_ht(__n, hasher(), key_equal(), allocator_type())
        { _M_ht.insert_equal(__f, __l); }

      template<class _InputIterator>
        hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
		      const hasher& __hf)
	: _M_ht(__n, __hf, key_equal(), allocator_type())
        { _M_ht.insert_equal(__f, __l); }

      template<class _InputIterator>
        hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
		      const hasher& __hf, const key_equal& __eql,
		      const allocator_type& __a = allocator_type())
	: _M_ht(__n, __hf, __eql, __a)
        { _M_ht.insert_equal(__f, __l); }

    public:
      size_type
      size() const
      { return _M_ht.size(); }

      size_type
      max_size() const
      { return _M_ht.max_size(); }

      bool
      empty() const
      { return _M_ht.empty(); }

      void
      swap(hash_multimap& __hs)
      { _M_ht.swap(__hs._M_ht); }

      template<class _K1, class _T1, class _HF, class _EqK, class _Al>
        friend bool
        operator==(const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&,
		   const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&);

      iterator
      begin()
      { return _M_ht.begin(); }

      iterator
      end()
      { return _M_ht.end(); }

      const_iterator
      begin() const
      { return _M_ht.begin(); }

      const_iterator
      end() const
      { return _M_ht.end(); }

    public:
      iterator
      insert(const value_type& __obj)
      { return _M_ht.insert_equal(__obj); }

      template<class _InputIterator>
        void
        insert(_InputIterator __f, _InputIterator __l)
        { _M_ht.insert_equal(__f,__l); }

      iterator
      insert_noresize(const value_type& __obj)
      { return _M_ht.insert_equal_noresize(__obj); }

      iterator
      find(const key_type& __key)
      { return _M_ht.find(__key); }

      const_iterator
      find(const key_type& __key) const
      { return _M_ht.find(__key); }

      size_type
      count(const key_type& __key) const
      { return _M_ht.count(__key); }

      pair<iterator, iterator>
      equal_range(const key_type& __key)
      { return _M_ht.equal_range(__key); }

      pair<const_iterator, const_iterator>
      equal_range(const key_type& __key) const
      { return _M_ht.equal_range(__key); }

      size_type
      erase(const key_type& __key)
      { return _M_ht.erase(__key); }

      void
      erase(iterator __it)
      { _M_ht.erase(__it); }

      void
      erase(iterator __f, iterator __l)
      { _M_ht.erase(__f, __l); }

      void
      clear()
      { _M_ht.clear(); }

    public:
      void
      resize(size_type __hint)
      { _M_ht.resize(__hint); }

      size_type
      bucket_count() const
      { return _M_ht.bucket_count(); }

      size_type
      max_bucket_count() const
      { return _M_ht.max_bucket_count(); }
      
      size_type
      elems_in_bucket(size_type __n) const
      { return _M_ht.elems_in_bucket(__n); }
    };

  template<class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
    inline bool
    operator==(const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm1,
	       const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm2)
    { return __hm1._M_ht == __hm2._M_ht; }

  template<class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
    inline bool
    operator!=(const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm1,
	       const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm2)
    { return !(__hm1 == __hm2); }

  template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
    inline void
    swap(hash_multimap<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
	 hash_multimap<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
    { __hm1.swap(__hm2); }

_GLIBCXX_END_NESTED_NAMESPACE

#ifdef _GLIBCXX_DEBUG
# include <debug/hash_map>
#endif

_GLIBCXX_BEGIN_NAMESPACE(std)

  // Specialization of insert_iterator so that it will work for hash_map
  // and hash_multimap.
  template<class _Key, class _Tp, class _HashFn,  class _EqKey, class _Alloc>
    class insert_iterator<__gnu_cxx::hash_map<_Key, _Tp, _HashFn, 
					      _EqKey, _Alloc> >
    {
    protected:
      typedef __gnu_cxx::hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>
        _Container;
      _Container* container;

    public:
      typedef _Container          container_type;
      typedef output_iterator_tag iterator_category;
      typedef void                value_type;
      typedef void                difference_type;
      typedef void                pointer;
      typedef void                reference;
      
      insert_iterator(_Container& __x)
      : container(&__x) {}

      insert_iterator(_Container& __x, typename _Container::iterator)
      : container(&__x) {}

      insert_iterator<_Container>&
      operator=(const typename _Container::value_type& __value)
      {
	container->insert(__value);
	return *this;
      }

      insert_iterator<_Container>&
      operator*()
      { return *this; }

      insert_iterator<_Container>&
      operator++() { return *this; }

      insert_iterator<_Container>&
      operator++(int)
      { return *this; }
    };

  template<class _Key, class _Tp, class _HashFn,  class _EqKey, class _Alloc>
    class insert_iterator<__gnu_cxx::hash_multimap<_Key, _Tp, _HashFn,
						   _EqKey, _Alloc> >
    {
    protected:
      typedef __gnu_cxx::hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc>
        _Container;
      _Container* container;
      typename _Container::iterator iter;

    public:
      typedef _Container          container_type;
      typedef output_iterator_tag iterator_category;
      typedef void                value_type;
      typedef void                difference_type;
      typedef void                pointer;
      typedef void                reference;

      insert_iterator(_Container& __x)
      : container(&__x) {}

      insert_iterator(_Container& __x, typename _Container::iterator)
      : container(&__x) {}

      insert_iterator<_Container>&
      operator=(const typename _Container::value_type& __value)
      {
	container->insert(__value);
	return *this;
      }

      insert_iterator<_Container>&
      operator*()
      { return *this; }

      insert_iterator<_Container>&
      operator++()
      { return *this; }

      insert_iterator<_Container>&
      operator++(int)
      { return *this; }
    };

_GLIBCXX_END_NAMESPACE

#endif
Commit	Line	Data
42526146 PE	1	// Hashing map implementation -- C++ --
42526146 PE	2
45f388bb	3	// Copyright (C) 2001, 2002, 2004, 2005, 2006 Free Software Foundation, Inc.
42526146 PE	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
83f51799	18	// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
42526146 PE	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
725dc051 BK	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
ffe94f83 PE	56	/** @file ext/hash_map
ffe94f83 PE	57	* This file is a GNU extension to the Standard C++ Library (possibly
0aa06b18	58	* containing extensions from the HP/SGI STL subset).
725dc051 BK	59	*/
725dc051 BK	60
fa30fe72	61	#ifndef _HASH_MAP
b2acb86f	62	#define _HASH_MAP 1
725dc051	63
45f388bb	64	#include <bits/c++config.h>
b2acb86f	65	#include <ext/hashtable.h>
30a20a1e	66	#include <bits/concept_check.h>
725dc051	67
c2ba9709	68	_GLIBCXX_BEGIN_NESTED_NAMESPACE(__gnu_cxx, _GLIBCXX_EXT_D)
3cbc7af0	69
b2acb86f BK	70	using std::equal_to;
	71	using std::allocator;
	72	using std::pair;
	73	using std::_Select1st;
	74
d962e073 PC	75	/**
	76	* This is an SGI extension.
	77	* @ingroup SGIextensions
	78	* @doctodo
	79	*/
7ffb61d5 PC	80	template<class _Key, class _Tp, class _HashFn = hash<_Key>,
7ffb61d5 PC	81	class _EqualKey = equal_to<_Key>, class _Alloc = allocator<_Tp> >
d962e073 PC	82	class hash_map
	83	{
	84	private:
45f388bb	85	typedef hashtable<pair<const _Key, _Tp>,_Key, _HashFn,
d962e073 PC	86	_Select1st<pair<const _Key, _Tp> >,
	87	_EqualKey, _Alloc> _Ht;
	88
	89	_Ht _M_ht;
	90
	91	public:
	92	typedef typename _Ht::key_type key_type;
	93	typedef _Tp data_type;
	94	typedef _Tp mapped_type;
	95	typedef typename _Ht::value_type value_type;
	96	typedef typename _Ht::hasher hasher;
	97	typedef typename _Ht::key_equal key_equal;
	98
	99	typedef typename _Ht::size_type size_type;
	100	typedef typename _Ht::difference_type difference_type;
	101	typedef typename _Ht::pointer pointer;
	102	typedef typename _Ht::const_pointer const_pointer;
	103	typedef typename _Ht::reference reference;
	104	typedef typename _Ht::const_reference const_reference;
	105
	106	typedef typename _Ht::iterator iterator;
	107	typedef typename _Ht::const_iterator const_iterator;
	108
	109	typedef typename _Ht::allocator_type allocator_type;
	110
	111	hasher
	112	hash_funct() const
	113	{ return _M_ht.hash_funct(); }
	114
	115	key_equal
	116	key_eq() const
	117	{ return _M_ht.key_eq(); }
	118
	119	allocator_type
	120	get_allocator() const
	121	{ return _M_ht.get_allocator(); }
	122
	123	public:
	124	hash_map()
	125	: _M_ht(100, hasher(), key_equal(), allocator_type()) {}
	126
	127	explicit
	128	hash_map(size_type __n)
	129	: _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
	130
	131	hash_map(size_type __n, const hasher& __hf)
	132	: _M_ht(__n, __hf, key_equal(), allocator_type()) {}
	133
	134	hash_map(size_type __n, const hasher& __hf, const key_equal& __eql,
	135	const allocator_type& __a = allocator_type())
	136	: _M_ht(__n, __hf, __eql, __a) {}
	137
45f388bb	138	template<class _InputIterator>
d962e073 PC	139	hash_map(_InputIterator __f, _InputIterator __l)
	140	: _M_ht(100, hasher(), key_equal(), allocator_type())
	141	{ _M_ht.insert_unique(__f, __l); }
	142
45f388bb	143	template<class _InputIterator>
d962e073 PC	144	hash_map(_InputIterator __f, _InputIterator __l, size_type __n)
	145	: _M_ht(__n, hasher(), key_equal(), allocator_type())
	146	{ _M_ht.insert_unique(__f, __l); }
	147
45f388bb	148	template<class _InputIterator>
d962e073 PC	149	hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
	150	const hasher& __hf)
	151	: _M_ht(__n, __hf, key_equal(), allocator_type())
	152	{ _M_ht.insert_unique(__f, __l); }
	153
45f388bb	154	template<class _InputIterator>
d962e073 PC	155	hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
	156	const hasher& __hf, const key_equal& __eql,
	157	const allocator_type& __a = allocator_type())
	158	: _M_ht(__n, __hf, __eql, __a)
	159	{ _M_ht.insert_unique(__f, __l); }
	160
	161	public:
	162	size_type
	163	size() const
	164	{ return _M_ht.size(); }
	165
	166	size_type
	167	max_size() const
	168	{ return _M_ht.max_size(); }
	169
	170	bool
	171	empty() const
	172	{ return _M_ht.empty(); }
	173
	174	void
	175	swap(hash_map& __hs)
	176	{ _M_ht.swap(__hs._M_ht); }
	177
45f388bb	178	template<class _K1, class _T1, class _HF, class _EqK, class _Al>
d962e073 PC	179	friend bool
	180	operator== (const hash_map<_K1, _T1, _HF, _EqK, _Al>&,
	181	const hash_map<_K1, _T1, _HF, _EqK, _Al>&);
	182
	183	iterator
	184	begin()
	185	{ return _M_ht.begin(); }
	186
	187	iterator
	188	end()
	189	{ return _M_ht.end(); }
	190
	191	const_iterator
	192	begin() const
	193	{ return _M_ht.begin(); }
	194
	195	const_iterator
	196	end() const
	197	{ return _M_ht.end(); }
	198
	199	public:
	200	pair<iterator, bool>
	201	insert(const value_type& __obj)
	202	{ return _M_ht.insert_unique(__obj); }
	203
45f388bb	204	template<class _InputIterator>
d962e073 PC	205	void
	206	insert(_InputIterator __f, _InputIterator __l)
	207	{ _M_ht.insert_unique(__f, __l); }
	208
	209	pair<iterator, bool>
	210	insert_noresize(const value_type& __obj)
	211	{ return _M_ht.insert_unique_noresize(__obj); }
	212
	213	iterator
	214	find(const key_type& __key)
	215	{ return _M_ht.find(__key); }
	216
	217	const_iterator
	218	find(const key_type& __key) const
	219	{ return _M_ht.find(__key); }
	220
	221	_Tp&
	222	operator[](const key_type& __key)
	223	{ return _M_ht.find_or_insert(value_type(__key, _Tp())).second; }
	224
	225	size_type
	226	count(const key_type& __key) const
	227	{ return _M_ht.count(__key); }
	228
	229	pair<iterator, iterator>
	230	equal_range(const key_type& __key)
	231	{ return _M_ht.equal_range(__key); }
	232
	233	pair<const_iterator, const_iterator>
	234	equal_range(const key_type& __key) const
	235	{ return _M_ht.equal_range(__key); }
	236
	237	size_type
	238	erase(const key_type& __key)
	239	{return _M_ht.erase(__key); }
	240
	241	void
	242	erase(iterator __it)
	243	{ _M_ht.erase(__it); }
	244
	245	void
	246	erase(iterator __f, iterator __l)
	247	{ _M_ht.erase(__f, __l); }
	248
	249	void
	250	clear()
	251	{ _M_ht.clear(); }
	252
	253	void
	254	resize(size_type __hint)
	255	{ _M_ht.resize(__hint); }
	256
	257	size_type
	258	bucket_count() const
	259	{ return _M_ht.bucket_count(); }
	260
	261	size_type
	262	max_bucket_count() const
	263	{ return _M_ht.max_bucket_count(); }
	264
	265	size_type
	266	elems_in_bucket(size_type __n) const
	267	{ return _M_ht.elems_in_bucket(__n); }
	268	};
269
45f388bb	270	template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
d962e073	271	inline bool
45f388bb BK	272	operator==(const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
45f388bb BK	273	const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
d962e073 PC	274	{ return __hm1._M_ht == __hm2._M_ht; }
d962e073 PC	275
45f388bb	276	template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
d962e073	277	inline bool
45f388bb BK	278	operator!=(const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
45f388bb BK	279	const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
d962e073 PC	280	{ return !(__hm1 == __hm2); }
d962e073 PC	281
45f388bb	282	template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
d962e073	283	inline void
45f388bb BK	284	swap(hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
45f388bb BK	285	hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
d962e073 PC	286	{ __hm1.swap(__hm2); }
d962e073 PC	287
d962e073 PC	288
	289	/**
	290	* This is an SGI extension.
	291	* @ingroup SGIextensions
	292	* @doctodo
	293	*/
7ffb61d5 PC	294	template<class _Key, class _Tp,
	295	class _HashFn = hash<_Key>,
	296	class _EqualKey = equal_to<_Key>,
	297	class _Alloc = allocator<_Tp> >
d962e073 PC	298	class hash_multimap
	299	{
	300	// concept requirements
	301	__glibcxx_class_requires(_Key, _SGIAssignableConcept)
	302	__glibcxx_class_requires(_Tp, _SGIAssignableConcept)
45f388bb	303	__glibcxx_class_requires3(_HashFn, size_t, _Key, _UnaryFunctionConcept)
d962e073 PC	304	__glibcxx_class_requires3(_EqualKey, _Key, _Key, _BinaryPredicateConcept)
	305
	306	private:
45f388bb	307	typedef hashtable<pair<const _Key, _Tp>, _Key, _HashFn,
d962e073	308	_Select1st<pair<const _Key, _Tp> >, _EqualKey, _Alloc>
725dc051	309	_Ht;
725dc051	310
d962e073 PC	311	_Ht _M_ht;
	312
	313	public:
	314	typedef typename _Ht::key_type key_type;
	315	typedef _Tp data_type;
	316	typedef _Tp mapped_type;
	317	typedef typename _Ht::value_type value_type;
	318	typedef typename _Ht::hasher hasher;
	319	typedef typename _Ht::key_equal key_equal;
	320
	321	typedef typename _Ht::size_type size_type;
	322	typedef typename _Ht::difference_type difference_type;
	323	typedef typename _Ht::pointer pointer;
	324	typedef typename _Ht::const_pointer const_pointer;
	325	typedef typename _Ht::reference reference;
	326	typedef typename _Ht::const_reference const_reference;
	327
	328	typedef typename _Ht::iterator iterator;
	329	typedef typename _Ht::const_iterator const_iterator;
	330
	331	typedef typename _Ht::allocator_type allocator_type;
	332
	333	hasher
	334	hash_funct() const
	335	{ return _M_ht.hash_funct(); }
	336
	337	key_equal
	338	key_eq() const
	339	{ return _M_ht.key_eq(); }
	340
	341	allocator_type
	342	get_allocator() const
	343	{ return _M_ht.get_allocator(); }
	344
	345	public:
	346	hash_multimap()
	347	: _M_ht(100, hasher(), key_equal(), allocator_type()) {}
	348
	349	explicit
	350	hash_multimap(size_type __n)
	351	: _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
	352
	353	hash_multimap(size_type __n, const hasher& __hf)
	354	: _M_ht(__n, __hf, key_equal(), allocator_type()) {}
	355
	356	hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql,
	357	const allocator_type& __a = allocator_type())
	358	: _M_ht(__n, __hf, __eql, __a) {}
	359
45f388bb	360	template<class _InputIterator>
d962e073 PC	361	hash_multimap(_InputIterator __f, _InputIterator __l)
	362	: _M_ht(100, hasher(), key_equal(), allocator_type())
	363	{ _M_ht.insert_equal(__f, __l); }
	364
45f388bb	365	template<class _InputIterator>
d962e073 PC	366	hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n)
	367	: _M_ht(__n, hasher(), key_equal(), allocator_type())
	368	{ _M_ht.insert_equal(__f, __l); }
	369
45f388bb	370	template<class _InputIterator>
d962e073 PC	371	hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
	372	const hasher& __hf)
	373	: _M_ht(__n, __hf, key_equal(), allocator_type())
	374	{ _M_ht.insert_equal(__f, __l); }
	375
45f388bb	376	template<class _InputIterator>
d962e073 PC	377	hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
	378	const hasher& __hf, const key_equal& __eql,
	379	const allocator_type& __a = allocator_type())
	380	: _M_ht(__n, __hf, __eql, __a)
	381	{ _M_ht.insert_equal(__f, __l); }
	382
	383	public:
	384	size_type
	385	size() const
	386	{ return _M_ht.size(); }
	387
	388	size_type
	389	max_size() const
	390	{ return _M_ht.max_size(); }
	391
	392	bool
	393	empty() const
	394	{ return _M_ht.empty(); }
	395
	396	void
	397	swap(hash_multimap& __hs)
	398	{ _M_ht.swap(__hs._M_ht); }
	399
45f388bb	400	template<class _K1, class _T1, class _HF, class _EqK, class _Al>
d962e073 PC	401	friend bool
	402	operator==(const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&,
	403	const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&);
	404
	405	iterator
	406	begin()
	407	{ return _M_ht.begin(); }
	408
	409	iterator
	410	end()
	411	{ return _M_ht.end(); }
	412
	413	const_iterator
	414	begin() const
	415	{ return _M_ht.begin(); }
	416
	417	const_iterator
	418	end() const
	419	{ return _M_ht.end(); }
725dc051	420
3cbc7af0	421	public:
d962e073 PC	422	iterator
	423	insert(const value_type& __obj)
	424	{ return _M_ht.insert_equal(__obj); }
	425
45f388bb	426	template<class _InputIterator>
d962e073 PC	427	void
	428	insert(_InputIterator __f, _InputIterator __l)
	429	{ _M_ht.insert_equal(__f,__l); }
	430
	431	iterator
	432	insert_noresize(const value_type& __obj)
	433	{ return _M_ht.insert_equal_noresize(__obj); }
	434
	435	iterator
	436	find(const key_type& __key)
	437	{ return _M_ht.find(__key); }
	438
	439	const_iterator
	440	find(const key_type& __key) const
	441	{ return _M_ht.find(__key); }
	442
	443	size_type
	444	count(const key_type& __key) const
	445	{ return _M_ht.count(__key); }
	446
	447	pair<iterator, iterator>
	448	equal_range(const key_type& __key)
	449	{ return _M_ht.equal_range(__key); }
	450
	451	pair<const_iterator, const_iterator>
	452	equal_range(const key_type& __key) const
	453	{ return _M_ht.equal_range(__key); }
	454
	455	size_type
	456	erase(const key_type& __key)
	457	{ return _M_ht.erase(__key); }
	458
	459	void
	460	erase(iterator __it)
	461	{ _M_ht.erase(__it); }
	462
	463	void
	464	erase(iterator __f, iterator __l)
	465	{ _M_ht.erase(__f, __l); }
	466
	467	void
	468	clear()
	469	{ _M_ht.clear(); }
	470
	471	public:
	472	void
	473	resize(size_type __hint)
	474	{ _M_ht.resize(__hint); }
	475
	476	size_type
	477	bucket_count() const
	478	{ return _M_ht.bucket_count(); }
	479
	480	size_type
	481	max_bucket_count() const
	482	{ return _M_ht.max_bucket_count(); }
	483
	484	size_type
	485	elems_in_bucket(size_type __n) const
	486	{ return _M_ht.elems_in_bucket(__n); }
3cbc7af0	487	};
725dc051	488
45f388bb	489	template<class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
d962e073 PC	490	inline bool
	491	operator==(const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm1,
	492	const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm2)
	493	{ return __hm1._M_ht == __hm2._M_ht; }
725dc051	494
45f388bb	495	template<class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
d962e073 PC	496	inline bool
	497	operator!=(const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm1,
	498	const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm2)
	499	{ return !(__hm1 == __hm2); }
725dc051	500
45f388bb	501	template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
d962e073	502	inline void
45f388bb BK	503	swap(hash_multimap<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
45f388bb BK	504	hash_multimap<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
d962e073	505	{ __hm1.swap(__hm2); }
725dc051	506
45f388bb BK	507	_GLIBCXX_END_NESTED_NAMESPACE
	508
	509	#ifdef _GLIBCXX_DEBUG
	510	# include <debug/hash_map>
	511	#endif
725dc051	512
3cbc7af0	513	_GLIBCXX_BEGIN_NAMESPACE(std)
725dc051	514
3cbc7af0 BK	515	// Specialization of insert_iterator so that it will work for hash_map
3cbc7af0 BK	516	// and hash_multimap.
45f388bb BK	517	template<class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc>
45f388bb BK	518	class insert_iterator<__gnu_cxx::hash_map<_Key, _Tp, _HashFn,
d962e073 PC	519	_EqKey, _Alloc> >
	520	{
	521	protected:
	522	typedef __gnu_cxx::hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>
	523	_Container;
	524	_Container* container;
	525
	526	public:
	527	typedef _Container container_type;
	528	typedef output_iterator_tag iterator_category;
	529	typedef void value_type;
	530	typedef void difference_type;
	531	typedef void pointer;
	532	typedef void reference;
	533
	534	insert_iterator(_Container& __x)
	535	: container(&__x) {}
	536
	537	insert_iterator(_Container& __x, typename _Container::iterator)
	538	: container(&__x) {}
	539
	540	insert_iterator<_Container>&
	541	operator=(const typename _Container::value_type& __value)
	542	{
	543	container->insert(__value);
	544	return *this;
	545	}
	546
	547	insert_iterator<_Container>&
	548	operator*()
	549	{ return *this; }
	550
	551	insert_iterator<_Container>&
	552	operator++() { return *this; }
	553
	554	insert_iterator<_Container>&
	555	operator++(int)
	556	{ return *this; }
	557	};
	558
45f388bb	559	template<class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc>
d962e073 PC	560	class insert_iterator<__gnu_cxx::hash_multimap<_Key, _Tp, _HashFn,
	561	_EqKey, _Alloc> >
	562	{
	563	protected:
	564	typedef __gnu_cxx::hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc>
	565	_Container;
	566	_Container* container;
	567	typename _Container::iterator iter;
	568
	569	public:
	570	typedef _Container container_type;
	571	typedef output_iterator_tag iterator_category;
	572	typedef void value_type;
	573	typedef void difference_type;
	574	typedef void pointer;
	575	typedef void reference;
	576
	577	insert_iterator(_Container& __x)
	578	: container(&__x) {}
	579
	580	insert_iterator(_Container& __x, typename _Container::iterator)
	581	: container(&__x) {}
	582
	583	insert_iterator<_Container>&
	584	operator=(const typename _Container::value_type& __value)
	585	{
	586	container->insert(__value);
	587	return *this;
	588	}
	589
	590	insert_iterator<_Container>&
	591	operator*()
	592	{ return *this; }
	593
	594	insert_iterator<_Container>&
	595	operator++()
	596	{ return *this; }
	597
	598	insert_iterator<_Container>&
	599	operator++(int)
	600	{ return *this; }
	601	};
3cbc7af0 BK	602
3cbc7af0 BK	603	_GLIBCXX_END_NAMESPACE
d2763ab5	604
b2acb86f	605	#endif