mips-qca-linux-uclibc/include/c++/4.9.2/ext/hash_set - toolchains/windcharger - Git at Google

 // Hashing set implementation -*- C++ -*-

 // Copyright (C) 2001-2014 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 3, 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.

 // Under Section 7 of GPL version 3, you are granted additional
 // permissions described in the GCC Runtime Library Exception, version
 // 3.1, as published by the Free Software Foundation.

 // You should have received a copy of the GNU General Public License and
 // a copy of the GCC Runtime Library Exception along with this program;
 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
 // <http://www.gnu.org/licenses/>.

 /*
  * 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 backward/hash_set
  *  This file is a GNU extension to the Standard C++ Library (possibly
  *  containing extensions from the HP/SGI STL subset).
  */

 #ifndef _BACKWARD_HASH_SET
 #define _BACKWARD_HASH_SET 1

 #ifndef _GLIBCXX_PERMIT_BACKWARD_HASH
 #include "backward_warning.h"
 #endif

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

 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
 {
 _GLIBCXX_BEGIN_NAMESPACE_VERSION

   using std::equal_to;
   using std::allocator;
   using std::pair;
   using std::_Identity;

   /**
    *  This is an SGI extension.
    *  @ingroup SGIextensions
    *  @doctodo
    */
   template<class _Value, class _HashFcn  = hash<_Value>,
 	   class _EqualKey = equal_to<_Value>,
 	   class _Alloc = allocator<_Value> >
     class hash_set
     {
       // concept requirements
       __glibcxx_class_requires(_Value, _SGIAssignableConcept)
       __glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept)
       __glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept)

     private:
       typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
 			_EqualKey, _Alloc> _Ht;
       _Ht _M_ht;

     public:
       typedef typename _Ht::key_type key_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 _Alloc::pointer pointer;
       typedef typename _Alloc::const_pointer const_pointer;
       typedef typename _Alloc::reference reference;
       typedef typename _Alloc::const_reference const_reference;

       typedef typename _Ht::const_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(); }

       hash_set()
       : _M_ht(100, hasher(), key_equal(), allocator_type()) {}

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

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

       hash_set(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_set(_InputIterator __f, _InputIterator __l)
 	: _M_ht(100, hasher(), key_equal(), allocator_type())
         { _M_ht.insert_unique(__f, __l); }

       template<class _InputIterator>
         hash_set(_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_set(_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_set(_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); }

       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_set& __hs)
       { _M_ht.swap(__hs._M_ht); }

       template<class _Val, class _HF, class _EqK, class _Al>
         friend bool
         operator==(const hash_set<_Val, _HF, _EqK, _Al>&,
 		   const hash_set<_Val, _HF, _EqK, _Al>&);

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

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

       pair<iterator, bool>
       insert(const value_type& __obj)
       {
 	pair<typename _Ht::iterator, bool> __p = _M_ht.insert_unique(__obj);
 	return pair<iterator,bool>(__p.first, __p.second);
       }

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

       pair<iterator, bool>
       insert_noresize(const value_type& __obj)
       {
 	pair<typename _Ht::iterator, bool> __p
 	  = _M_ht.insert_unique_noresize(__obj);
 	return pair<iterator, bool>(__p.first, __p.second);
       }

       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) 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 _Value, class _HashFcn, class _EqualKey, class _Alloc>
     inline bool
     operator==(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1,
 	       const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2)
     { return __hs1._M_ht == __hs2._M_ht; }

   template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
     inline bool
     operator!=(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1,
 	       const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2)
     { return !(__hs1 == __hs2); }

   template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
     inline void
     swap(hash_set<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
 	 hash_set<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
     { __hs1.swap(__hs2); }


   /**
    *  This is an SGI extension.
    *  @ingroup SGIextensions
    *  @doctodo
    */
   template<class _Value,
 	   class _HashFcn = hash<_Value>,
 	   class _EqualKey = equal_to<_Value>,
 	   class _Alloc = allocator<_Value> >
     class hash_multiset
     {
       // concept requirements
       __glibcxx_class_requires(_Value, _SGIAssignableConcept)
       __glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept)
       __glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept)

     private:
       typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
 			_EqualKey, _Alloc> _Ht;
       _Ht _M_ht;

     public:
       typedef typename _Ht::key_type key_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 _Alloc::pointer pointer;
       typedef typename _Alloc::const_pointer const_pointer;
       typedef typename _Alloc::reference reference;
       typedef typename _Alloc::const_reference const_reference;

       typedef typename _Ht::const_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(); }

       hash_multiset()
       : _M_ht(100, hasher(), key_equal(), allocator_type()) {}

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

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

       hash_multiset(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_multiset(_InputIterator __f, _InputIterator __l)
 	: _M_ht(100, hasher(), key_equal(), allocator_type())
         { _M_ht.insert_equal(__f, __l); }

       template<class _InputIterator>
         hash_multiset(_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_multiset(_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_multiset(_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); }

       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_multiset& hs)
       { _M_ht.swap(hs._M_ht); }

       template<class _Val, class _HF, class _EqK, class _Al>
         friend bool
         operator==(const hash_multiset<_Val, _HF, _EqK, _Al>&,
 		   const hash_multiset<_Val, _HF, _EqK, _Al>&);

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

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

       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) 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) 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 _Val, class _HashFcn, class _EqualKey, class _Alloc>
     inline bool
     operator==(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
 	       const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
     { return __hs1._M_ht == __hs2._M_ht; }

   template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
     inline bool
     operator!=(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
 	       const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
     { return !(__hs1 == __hs2); }

   template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
     inline void
     swap(hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
 	 hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
     { __hs1.swap(__hs2); }

 _GLIBCXX_END_NAMESPACE_VERSION
 } // namespace

 namespace std _GLIBCXX_VISIBILITY(default)
 {
 _GLIBCXX_BEGIN_NAMESPACE_VERSION

   // Specialization of insert_iterator so that it will work for hash_set
   // and hash_multiset.
   template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
     class insert_iterator<__gnu_cxx::hash_set<_Value, _HashFcn,
 					      _EqualKey, _Alloc> >
     {
     protected:
       typedef __gnu_cxx::hash_set<_Value, _HashFcn, _EqualKey, _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 _Value, class _HashFcn, class _EqualKey, class _Alloc>
     class insert_iterator<__gnu_cxx::hash_multiset<_Value, _HashFcn,
 						   _EqualKey, _Alloc> >
     {
     protected:
       typedef __gnu_cxx::hash_multiset<_Value, _HashFcn, _EqualKey, _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_VERSION
 } // namespace

 #endif
	// Hashing set implementation -- C++ --

	// Copyright (C) 2001-2014 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 3, 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.

	// Under Section 7 of GPL version 3, you are granted additional
	// permissions described in the GCC Runtime Library Exception, version
	// 3.1, as published by the Free Software Foundation.

	// You should have received a copy of the GNU General Public License and
	// a copy of the GCC Runtime Library Exception along with this program;
	// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
	// <http://www.gnu.org/licenses/>.

	/*
	* 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 backward/hash_set
	* This file is a GNU extension to the Standard C++ Library (possibly
	* containing extensions from the HP/SGI STL subset).
	*/

	#ifndef _BACKWARD_HASH_SET
	#define _BACKWARD_HASH_SET 1

	#ifndef _GLIBCXX_PERMIT_BACKWARD_HASH
	#include "backward_warning.h"
	#endif

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

	namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
	{
	_GLIBCXX_BEGIN_NAMESPACE_VERSION

	using std::equal_to;
	using std::allocator;
	using std::pair;
	using std::_Identity;

	/**
	* This is an SGI extension.
	* @ingroup SGIextensions
	* @doctodo
	*/
	template<class _Value, class _HashFcn = hash<_Value>,
	class _EqualKey = equal_to<_Value>,
	class _Alloc = allocator<_Value> >
	class hash_set
	{
	// concept requirements
	__glibcxx_class_requires(_Value, _SGIAssignableConcept)
	__glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept)
	__glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept)

	private:
	typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
	_EqualKey, _Alloc> _Ht;
	_Ht _M_ht;

	public:
	typedef typename _Ht::key_type key_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 _Alloc::pointer pointer;
	typedef typename _Alloc::const_pointer const_pointer;
	typedef typename _Alloc::reference reference;
	typedef typename _Alloc::const_reference const_reference;

	typedef typename _Ht::const_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(); }

	hash_set()
	: _M_ht(100, hasher(), key_equal(), allocator_type()) {}

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

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

	hash_set(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_set(_InputIterator __f, _InputIterator __l)
	: _M_ht(100, hasher(), key_equal(), allocator_type())
	{ _M_ht.insert_unique(__f, __l); }

	template<class _InputIterator>
	hash_set(_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_set(_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_set(_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); }

	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_set& __hs)
	{ _M_ht.swap(__hs._M_ht); }

	template<class _Val, class _HF, class _EqK, class _Al>
	friend bool
	operator==(const hash_set<_Val, _HF, _EqK, _Al>&,
	const hash_set<_Val, _HF, _EqK, _Al>&);

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

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

	pair<iterator, bool>
	insert(const value_type& __obj)
	{
	pair<typename _Ht::iterator, bool> __p = _M_ht.insert_unique(__obj);
	return pair<iterator,bool>(__p.first, __p.second);
	}

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

	pair<iterator, bool>
	insert_noresize(const value_type& __obj)
	{
	pair<typename _Ht::iterator, bool> __p
	= _M_ht.insert_unique_noresize(__obj);
	return pair<iterator, bool>(__p.first, __p.second);
	}

	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) 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 _Value, class _HashFcn, class _EqualKey, class _Alloc>
	inline bool
	operator==(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1,
	const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2)
	{ return __hs1._M_ht == __hs2._M_ht; }

	template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
	inline bool
	operator!=(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1,
	const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2)
	{ return !(__hs1 == __hs2); }

	template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
	inline void
	swap(hash_set<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
	hash_set<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
	{ __hs1.swap(__hs2); }


	/**
	* This is an SGI extension.
	* @ingroup SGIextensions
	* @doctodo
	*/
	template<class _Value,
	class _HashFcn = hash<_Value>,
	class _EqualKey = equal_to<_Value>,
	class _Alloc = allocator<_Value> >
	class hash_multiset
	{
	// concept requirements
	__glibcxx_class_requires(_Value, _SGIAssignableConcept)
	__glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept)
	__glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept)

	private:
	typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
	_EqualKey, _Alloc> _Ht;
	_Ht _M_ht;

	public:
	typedef typename _Ht::key_type key_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 _Alloc::pointer pointer;
	typedef typename _Alloc::const_pointer const_pointer;
	typedef typename _Alloc::reference reference;
	typedef typename _Alloc::const_reference const_reference;

	typedef typename _Ht::const_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(); }

	hash_multiset()
	: _M_ht(100, hasher(), key_equal(), allocator_type()) {}

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

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

	hash_multiset(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_multiset(_InputIterator __f, _InputIterator __l)
	: _M_ht(100, hasher(), key_equal(), allocator_type())
	{ _M_ht.insert_equal(__f, __l); }

	template<class _InputIterator>
	hash_multiset(_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_multiset(_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_multiset(_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); }

	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_multiset& hs)
	{ _M_ht.swap(hs._M_ht); }

	template<class _Val, class _HF, class _EqK, class _Al>
	friend bool
	operator==(const hash_multiset<_Val, _HF, _EqK, _Al>&,
	const hash_multiset<_Val, _HF, _EqK, _Al>&);

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

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

	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) 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) 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 _Val, class _HashFcn, class _EqualKey, class _Alloc>
	inline bool
	operator==(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
	const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
	{ return __hs1._M_ht == __hs2._M_ht; }

	template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
	inline bool
	operator!=(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
	const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
	{ return !(__hs1 == __hs2); }

	template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
	inline void
	swap(hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
	hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
	{ __hs1.swap(__hs2); }

	_GLIBCXX_END_NAMESPACE_VERSION
	} // namespace

	namespace std _GLIBCXX_VISIBILITY(default)
	{
	_GLIBCXX_BEGIN_NAMESPACE_VERSION

	// Specialization of insert_iterator so that it will work for hash_set
	// and hash_multiset.
	template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
	class insert_iterator<__gnu_cxx::hash_set<_Value, _HashFcn,
	_EqualKey, _Alloc> >
	{
	protected:
	typedef __gnu_cxx::hash_set<_Value, _HashFcn, _EqualKey, _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 _Value, class _HashFcn, class _EqualKey, class _Alloc>
	class insert_iterator<__gnu_cxx::hash_multiset<_Value, _HashFcn,
	_EqualKey, _Alloc> >
	{
	protected:
	typedef __gnu_cxx::hash_multiset<_Value, _HashFcn, _EqualKey, _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_VERSION
	} // namespace

	#endif