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

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

// Copyright (C) 2001, 2002, 2004, 2005 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_set
 *  This file is a GNU extension to the Standard C++ Library (possibly
 *  containing extensions from the HP/SGI STL subset).
 */

#ifndef _HASH_SET
#define _HASH_SET 1

#include <ext/hashtable.h>
#include <bits/concept_check.h>

_GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)

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

  // Forward declaration of equality operator; needed for friend
  // declaration.
  template <class _Value, class _HashFcn  = hash<_Value>,
	    class _EqualKey = equal_to<_Value>,
	    class _Alloc = allocator<_Value> >
    class hash_set;

  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);

  /**
   *  This is an SGI extension.
   *  @ingroup SGIextensions
   *  @doctodo
   */
  template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
    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(); }

    public:
      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); }

    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_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(); }

    public:
      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(); }

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 _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); }

  template <class _Value,
	    class _HashFcn = hash<_Value>,
	    class _EqualKey = equal_to<_Value>,
	    class _Alloc = allocator<_Value> >
    class hash_multiset;

  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);


  /**
   *  This is an SGI extension.
   *  @ingroup SGIextensions
   *  @doctodo
   */
  template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
    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(); }

    public:
      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); }

    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_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(); }

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) 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(); }

    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 _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

_GLIBCXX_BEGIN_NAMESPACE(std)

  // 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

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

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