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

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

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

#ifndef _BACKWARD_HASH_MAP
#define _BACKWARD_HASH_MAP 1

#ifndef _GLIBCXX_PERMIT_BACKWARD_HASH
#include <backward/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::_Select1st;

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

      _Ht _M_ht;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

      _Ht _M_ht;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

_GLIBCXX_END_NAMESPACE_VERSION
} // namespace

namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

_GLIBCXX_END_NAMESPACE_VERSION
} // namespace

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