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

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

// Copyright (C) 2001-2019 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
Commit	Line	Data
42526146 PE	1	// Hashing set implementation -- C++ --
42526146 PE	2
a5544970	3	// Copyright (C) 2001-2019 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
748086b7	8	// Free Software Foundation; either version 3, or (at your option)
42526146 PE	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
748086b7 JJ	16	// Under Section 7 of GPL version 3, you are granted additional
	17	// permissions described in the GCC Runtime Library Exception, version
	18	// 3.1, as published by the Free Software Foundation.
42526146	19
748086b7 JJ	20	// You should have received a copy of the GNU General Public License and
	21	// a copy of the GCC Runtime Library Exception along with this program;
	22	// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
	23	// <http://www.gnu.org/licenses/>.
42526146	24
725dc051 BK	25	/*
	26	* Copyright (c) 1996
	27	* Silicon Graphics Computer Systems, Inc.
	28	*
	29	* Permission to use, copy, modify, distribute and sell this software
	30	* and its documentation for any purpose is hereby granted without fee,
	31	* provided that the above copyright notice appear in all copies and
	32	* that both that copyright notice and this permission notice appear
	33	* in supporting documentation. Silicon Graphics makes no
	34	* representations about the suitability of this software for any
	35	* purpose. It is provided "as is" without express or implied warranty.
	36	*
	37	*
	38	* Copyright (c) 1994
	39	* Hewlett-Packard Company
	40	*
	41	* Permission to use, copy, modify, distribute and sell this software
	42	* and its documentation for any purpose is hereby granted without fee,
	43	* provided that the above copyright notice appear in all copies and
	44	* that both that copyright notice and this permission notice appear
	45	* in supporting documentation. Hewlett-Packard Company makes no
	46	* representations about the suitability of this software for any
	47	* purpose. It is provided "as is" without express or implied warranty.
	48	*
	49	*/
	50
e63637ea	51	/** @file backward/hash_set
ffe94f83	52	* This file is a GNU extension to the Standard C++ Library (possibly
0aa06b18	53	* containing extensions from the HP/SGI STL subset).
725dc051 BK	54	*/
725dc051 BK	55
5ecfce5c PC	56	#ifndef _BACKWARD_HASH_SET
5ecfce5c PC	57	#define _BACKWARD_HASH_SET 1
725dc051	58
896e7917	59	#ifndef _GLIBCXX_PERMIT_BACKWARD_HASH
e63637ea	60	#include "backward_warning.h"
896e7917 ILT	61	#endif
896e7917 ILT	62
45f388bb	63	#include <bits/c++config.h>
e63637ea	64	#include <backward/hashtable.h>
30a20a1e	65	#include <bits/concept_check.h>
725dc051	66
12ffa228 BK	67	namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
	68	{
	69	_GLIBCXX_BEGIN_NAMESPACE_VERSION
3cbc7af0	70
b2acb86f BK	71	using std::equal_to;
	72	using std::allocator;
	73	using std::pair;
	74	using std::_Identity;
	75
d962e073 PC	76	/**
	77	* This is an SGI extension.
	78	* @ingroup SGIextensions
	79	* @doctodo
	80	*/
7ffb61d5 PC	81	template<class _Value, class _HashFcn = hash<_Value>,
	82	class _EqualKey = equal_to<_Value>,
	83	class _Alloc = allocator<_Value> >
d962e073	84	class hash_set
725dc051	85	{
d962e073 PC	86	// concept requirements
	87	__glibcxx_class_requires(_Value, _SGIAssignableConcept)
	88	__glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept)
	89	__glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept)
	90
	91	private:
	92	typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
	93	_EqualKey, _Alloc> _Ht;
	94	_Ht _M_ht;
	95
	96	public:
	97	typedef typename _Ht::key_type key_type;
	98	typedef typename _Ht::value_type value_type;
	99	typedef typename _Ht::hasher hasher;
	100	typedef typename _Ht::key_equal key_equal;
	101
	102	typedef typename _Ht::size_type size_type;
	103	typedef typename _Ht::difference_type difference_type;
	104	typedef typename _Alloc::pointer pointer;
	105	typedef typename _Alloc::const_pointer const_pointer;
	106	typedef typename _Alloc::reference reference;
	107	typedef typename _Alloc::const_reference const_reference;
	108
	109	typedef typename _Ht::const_iterator iterator;
	110	typedef typename _Ht::const_iterator const_iterator;
	111
	112	typedef typename _Ht::allocator_type allocator_type;
	113
	114	hasher
	115	hash_funct() const
	116	{ return _M_ht.hash_funct(); }
	117
	118	key_equal
	119	key_eq() const
	120	{ return _M_ht.key_eq(); }
	121
	122	allocator_type
	123	get_allocator() const
	124	{ return _M_ht.get_allocator(); }
	125
d962e073 PC	126	hash_set()
	127	: _M_ht(100, hasher(), key_equal(), allocator_type()) {}
	128
	129	explicit
	130	hash_set(size_type __n)
	131	: _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
	132
	133	hash_set(size_type __n, const hasher& __hf)
	134	: _M_ht(__n, __hf, key_equal(), allocator_type()) {}
	135
	136	hash_set(size_type __n, const hasher& __hf, const key_equal& __eql,
	137	const allocator_type& __a = allocator_type())
	138	: _M_ht(__n, __hf, __eql, __a) {}
	139
45f388bb	140	template<class _InputIterator>
d962e073 PC	141	hash_set(_InputIterator __f, _InputIterator __l)
	142	: _M_ht(100, hasher(), key_equal(), allocator_type())
	143	{ _M_ht.insert_unique(__f, __l); }
	144
45f388bb	145	template<class _InputIterator>
d962e073 PC	146	hash_set(_InputIterator __f, _InputIterator __l, size_type __n)
	147	: _M_ht(__n, hasher(), key_equal(), allocator_type())
	148	{ _M_ht.insert_unique(__f, __l); }
	149
45f388bb	150	template<class _InputIterator>
d962e073 PC	151	hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
	152	const hasher& __hf)
	153	: _M_ht(__n, __hf, key_equal(), allocator_type())
	154	{ _M_ht.insert_unique(__f, __l); }
	155
45f388bb	156	template<class _InputIterator>
d962e073 PC	157	hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
	158	const hasher& __hf, const key_equal& __eql,
	159	const allocator_type& __a = allocator_type())
	160	: _M_ht(__n, __hf, __eql, __a)
	161	{ _M_ht.insert_unique(__f, __l); }
	162
d962e073 PC	163	size_type
	164	size() const
	165	{ return _M_ht.size(); }
	166
	167	size_type
	168	max_size() const
	169	{ return _M_ht.max_size(); }
	170
	171	bool
	172	empty() const
	173	{ return _M_ht.empty(); }
	174
	175	void
	176	swap(hash_set& __hs)
	177	{ _M_ht.swap(__hs._M_ht); }
	178
45f388bb	179	template<class _Val, class _HF, class _EqK, class _Al>
d962e073 PC	180	friend bool
	181	operator==(const hash_set<_Val, _HF, _EqK, _Al>&,
	182	const hash_set<_Val, _HF, _EqK, _Al>&);
	183
	184	iterator
	185	begin() const
	186	{ return _M_ht.begin(); }
	187
	188	iterator
	189	end() const
	190	{ return _M_ht.end(); }
	191
d962e073 PC	192	pair<iterator, bool>
	193	insert(const value_type& __obj)
	194	{
	195	pair<typename _Ht::iterator, bool> __p = _M_ht.insert_unique(__obj);
	196	return pair<iterator,bool>(__p.first, __p.second);
	197	}
	198
45f388bb	199	template<class _InputIterator>
d962e073 PC	200	void
	201	insert(_InputIterator __f, _InputIterator __l)
	202	{ _M_ht.insert_unique(__f, __l); }
	203
	204	pair<iterator, bool>
	205	insert_noresize(const value_type& __obj)
	206	{
	207	pair<typename _Ht::iterator, bool> __p
	208	= _M_ht.insert_unique_noresize(__obj);
	209	return pair<iterator, bool>(__p.first, __p.second);
	210	}
	211
	212	iterator
	213	find(const key_type& __key) const
	214	{ return _M_ht.find(__key); }
	215
	216	size_type
	217	count(const key_type& __key) const
	218	{ return _M_ht.count(__key); }
	219
	220	pair<iterator, iterator>
	221	equal_range(const key_type& __key) const
	222	{ return _M_ht.equal_range(__key); }
	223
	224	size_type
	225	erase(const key_type& __key)
	226	{return _M_ht.erase(__key); }
	227
	228	void
	229	erase(iterator __it)
	230	{ _M_ht.erase(__it); }
	231
	232	void
	233	erase(iterator __f, iterator __l)
	234	{ _M_ht.erase(__f, __l); }
	235
	236	void
	237	clear()
	238	{ _M_ht.clear(); }
725dc051	239
d962e073 PC	240	void
	241	resize(size_type __hint)
	242	{ _M_ht.resize(__hint); }
	243
	244	size_type
	245	bucket_count() const
	246	{ return _M_ht.bucket_count(); }
	247
	248	size_type
	249	max_bucket_count() const
	250	{ return _M_ht.max_bucket_count(); }
	251
	252	size_type
	253	elems_in_bucket(size_type __n) const
	254	{ return _M_ht.elems_in_bucket(__n); }
	255	};
725dc051	256
45f388bb	257	template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
d962e073 PC	258	inline bool
	259	operator==(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1,
	260	const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2)
	261	{ return __hs1._M_ht == __hs2._M_ht; }
725dc051	262
45f388bb	263	template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
d962e073 PC	264	inline bool
	265	operator!=(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1,
	266	const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2)
	267	{ return !(__hs1 == __hs2); }
	268
45f388bb	269	template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
d962e073 PC	270	inline void
	271	swap(hash_set<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
	272	hash_set<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
	273	{ __hs1.swap(__hs2); }
	274
725dc051	275
d962e073 PC	276	/**
	277	* This is an SGI extension.
	278	* @ingroup SGIextensions
	279	* @doctodo
	280	*/
7ffb61d5 PC	281	template<class _Value,
	282	class _HashFcn = hash<_Value>,
	283	class _EqualKey = equal_to<_Value>,
	284	class _Alloc = allocator<_Value> >
d962e073 PC	285	class hash_multiset
	286	{
	287	// concept requirements
	288	__glibcxx_class_requires(_Value, _SGIAssignableConcept)
	289	__glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept)
	290	__glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept)
	291
	292	private:
	293	typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
	294	_EqualKey, _Alloc> _Ht;
	295	_Ht _M_ht;
	296
	297	public:
	298	typedef typename _Ht::key_type key_type;
	299	typedef typename _Ht::value_type value_type;
	300	typedef typename _Ht::hasher hasher;
	301	typedef typename _Ht::key_equal key_equal;
	302
	303	typedef typename _Ht::size_type size_type;
	304	typedef typename _Ht::difference_type difference_type;
	305	typedef typename _Alloc::pointer pointer;
	306	typedef typename _Alloc::const_pointer const_pointer;
	307	typedef typename _Alloc::reference reference;
	308	typedef typename _Alloc::const_reference const_reference;
	309
	310	typedef typename _Ht::const_iterator iterator;
	311	typedef typename _Ht::const_iterator const_iterator;
	312
	313	typedef typename _Ht::allocator_type allocator_type;
	314
	315	hasher
	316	hash_funct() const
	317	{ return _M_ht.hash_funct(); }
	318
	319	key_equal
	320	key_eq() const
	321	{ return _M_ht.key_eq(); }
	322
	323	allocator_type
	324	get_allocator() const
	325	{ return _M_ht.get_allocator(); }
	326
d962e073 PC	327	hash_multiset()
	328	: _M_ht(100, hasher(), key_equal(), allocator_type()) {}
	329
	330	explicit
	331	hash_multiset(size_type __n)
	332	: _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
	333
	334	hash_multiset(size_type __n, const hasher& __hf)
	335	: _M_ht(__n, __hf, key_equal(), allocator_type()) {}
	336
	337	hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql,
	338	const allocator_type& __a = allocator_type())
	339	: _M_ht(__n, __hf, __eql, __a) {}
	340
45f388bb	341	template<class _InputIterator>
d962e073 PC	342	hash_multiset(_InputIterator __f, _InputIterator __l)
	343	: _M_ht(100, hasher(), key_equal(), allocator_type())
	344	{ _M_ht.insert_equal(__f, __l); }
	345
45f388bb	346	template<class _InputIterator>
d962e073 PC	347	hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n)
	348	: _M_ht(__n, hasher(), key_equal(), allocator_type())
	349	{ _M_ht.insert_equal(__f, __l); }
	350
45f388bb	351	template<class _InputIterator>
d962e073 PC	352	hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
	353	const hasher& __hf)
	354	: _M_ht(__n, __hf, key_equal(), allocator_type())
	355	{ _M_ht.insert_equal(__f, __l); }
	356
45f388bb	357	template<class _InputIterator>
d962e073 PC	358	hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
	359	const hasher& __hf, const key_equal& __eql,
	360	const allocator_type& __a = allocator_type())
	361	: _M_ht(__n, __hf, __eql, __a)
	362	{ _M_ht.insert_equal(__f, __l); }
	363
d962e073 PC	364	size_type
	365	size() const
	366	{ return _M_ht.size(); }
	367
	368	size_type
	369	max_size() const
	370	{ return _M_ht.max_size(); }
	371
	372	bool
	373	empty() const
	374	{ return _M_ht.empty(); }
	375
	376	void
	377	swap(hash_multiset& hs)
	378	{ _M_ht.swap(hs._M_ht); }
	379
45f388bb	380	template<class _Val, class _HF, class _EqK, class _Al>
d962e073 PC	381	friend bool
	382	operator==(const hash_multiset<_Val, _HF, _EqK, _Al>&,
	383	const hash_multiset<_Val, _HF, _EqK, _Al>&);
	384
	385	iterator
	386	begin() const
	387	{ return _M_ht.begin(); }
	388
	389	iterator
	390	end() const
	391	{ return _M_ht.end(); }
725dc051	392
d962e073 PC	393	iterator
	394	insert(const value_type& __obj)
	395	{ return _M_ht.insert_equal(__obj); }
	396
45f388bb	397	template<class _InputIterator>
d962e073 PC	398	void
	399	insert(_InputIterator __f, _InputIterator __l)
	400	{ _M_ht.insert_equal(__f,__l); }
	401
	402	iterator
	403	insert_noresize(const value_type& __obj)
	404	{ return _M_ht.insert_equal_noresize(__obj); }
	405
	406	iterator
	407	find(const key_type& __key) const
	408	{ return _M_ht.find(__key); }
	409
	410	size_type
	411	count(const key_type& __key) const
	412	{ return _M_ht.count(__key); }
	413
	414	pair<iterator, iterator>
	415	equal_range(const key_type& __key) const
	416	{ return _M_ht.equal_range(__key); }
	417
	418	size_type
	419	erase(const key_type& __key)
	420	{ return _M_ht.erase(__key); }
	421
	422	void
	423	erase(iterator __it)
	424	{ _M_ht.erase(__it); }
	425
	426	void
	427	erase(iterator __f, iterator __l)
	428	{ _M_ht.erase(__f, __l); }
	429
	430	void
	431	clear()
	432	{ _M_ht.clear(); }
	433
d962e073 PC	434	void
	435	resize(size_type __hint)
	436	{ _M_ht.resize(__hint); }
	437
	438	size_type
	439	bucket_count() const
	440	{ return _M_ht.bucket_count(); }
	441
	442	size_type
	443	max_bucket_count() const
	444	{ return _M_ht.max_bucket_count(); }
	445
	446	size_type
	447	elems_in_bucket(size_type __n) const
	448	{ return _M_ht.elems_in_bucket(__n); }
	449	};
	450
45f388bb	451	template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
d962e073 PC	452	inline bool
	453	operator==(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
	454	const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
	455	{ return __hs1._M_ht == __hs2._M_ht; }
fa30fe72	456
45f388bb	457	template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
d962e073 PC	458	inline bool
	459	operator!=(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
	460	const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
	461	{ return !(__hs1 == __hs2); }
725dc051	462
45f388bb	463	template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
d962e073 PC	464	inline void
	465	swap(hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
	466	hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
	467	{ __hs1.swap(__hs2); }
725dc051	468
12ffa228 BK	469	_GLIBCXX_END_NAMESPACE_VERSION
12ffa228 BK	470	} // namespace
3cbc7af0	471
12ffa228 BK	472	namespace std _GLIBCXX_VISIBILITY(default)
	473	{
	474	_GLIBCXX_BEGIN_NAMESPACE_VERSION
e538847e	475
d962e073 PC	476	// Specialization of insert_iterator so that it will work for hash_set
d962e073 PC	477	// and hash_multiset.
45f388bb	478	template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
d962e073 PC	479	class insert_iterator<__gnu_cxx::hash_set<_Value, _HashFcn,
	480	_EqualKey, _Alloc> >
	481	{
	482	protected:
	483	typedef __gnu_cxx::hash_set<_Value, _HashFcn, _EqualKey, _Alloc>
	484	_Container;
	485	_Container* container;
	486
	487	public:
	488	typedef _Container container_type;
	489	typedef output_iterator_tag iterator_category;
	490	typedef void value_type;
	491	typedef void difference_type;
	492	typedef void pointer;
	493	typedef void reference;
	494
	495	insert_iterator(_Container& __x)
	496	: container(&__x) {}
	497
	498	insert_iterator(_Container& __x, typename _Container::iterator)
	499	: container(&__x) {}
	500
	501	insert_iterator<_Container>&
	502	operator=(const typename _Container::value_type& __value)
	503	{
	504	container->insert(__value);
	505	return *this;
	506	}
	507
	508	insert_iterator<_Container>&
	509	operator*()
	510	{ return *this; }
	511
	512	insert_iterator<_Container>&
	513	operator++()
	514	{ return *this; }
	515
	516	insert_iterator<_Container>&
	517	operator++(int)
	518	{ return *this; }
	519	};
725dc051	520
45f388bb	521	template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
d962e073 PC	522	class insert_iterator<__gnu_cxx::hash_multiset<_Value, _HashFcn,
	523	_EqualKey, _Alloc> >
	524	{
	525	protected:
	526	typedef __gnu_cxx::hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc>
	527	_Container;
	528	_Container* container;
	529	typename _Container::iterator iter;
	530
	531	public:
	532	typedef _Container container_type;
	533	typedef output_iterator_tag iterator_category;
	534	typedef void value_type;
	535	typedef void difference_type;
	536	typedef void pointer;
	537	typedef void reference;
	538
	539	insert_iterator(_Container& __x)
	540	: container(&__x) {}
	541
	542	insert_iterator(_Container& __x, typename _Container::iterator)
	543	: container(&__x) {}
	544
	545	insert_iterator<_Container>&
	546	operator=(const typename _Container::value_type& __value)
	547	{
	548	container->insert(__value);
	549	return *this;
	550	}
	551
	552	insert_iterator<_Container>&
	553	operator*()
	554	{ return *this; }
	555
	556	insert_iterator<_Container>&
	557	operator++()
	558	{ return *this; }
	559
	560	insert_iterator<_Container>&
	561	operator++(int) { return *this; }
	562	};
3cbc7af0	563
12ffa228 BK	564	_GLIBCXX_END_NAMESPACE_VERSION
12ffa228 BK	565	} // namespace
d2763ab5	566
fa30fe72	567	#endif