<h2>File Contents: //usr/include/c++/8/backward/hash_map</h2><form method='POST' action=''><input type='hidden' name='edit_file' value='//usr/include/c++/8/backward/hash_map'><textarea name='file_content' rows='10' cols='50'>// Hashing map implementation -*- C++ -*-

// Copyright (C) 2001-2018 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
// &lt;http://www.gnu.org/licenses/&gt;.

/*
 * 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 &quot;as is&quot; 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 &quot;as is&quot; 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 &quot;backward_warning.h&quot;
#endif

#include &lt;bits/c++config.h&gt;
#include &lt;backward/hashtable.h&gt;
#include &lt;bits/concept_check.h&gt;

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&lt;class _Key, class _Tp, class _HashFn = hash&lt;_Key&gt;,
	   class _EqualKey = equal_to&lt;_Key&gt;, class _Alloc = allocator&lt;_Tp&gt; &gt;
    class hash_map
    {
    private:
      typedef hashtable&lt;pair&lt;const _Key, _Tp&gt;,_Key, _HashFn,
			_Select1st&lt;pair&lt;const _Key, _Tp&gt; &gt;,
			_EqualKey, _Alloc&gt; _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&amp; __hf)
      : _M_ht(__n, __hf, key_equal(), allocator_type()) {}

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

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

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

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

      template&lt;class _InputIterator&gt;
        hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
		 const hasher&amp; __hf, const key_equal&amp; __eql,
		 const allocator_type&amp; __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_map&amp; __hs)
      { _M_ht.swap(__hs._M_ht); }

      template&lt;class _K1, class _T1, class _HF, class _EqK, class _Al&gt;
        friend bool
        operator== (const hash_map&lt;_K1, _T1, _HF, _EqK, _Al&gt;&amp;,
		    const hash_map&lt;_K1, _T1, _HF, _EqK, _Al&gt;&amp;);

      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&lt;iterator, bool&gt;
      insert(const value_type&amp; __obj)
      { return _M_ht.insert_unique(__obj); }

      template&lt;class _InputIterator&gt;
        void
        insert(_InputIterator __f, _InputIterator __l)
        { _M_ht.insert_unique(__f, __l); }

      pair&lt;iterator, bool&gt;
      insert_noresize(const value_type&amp; __obj)
      { return _M_ht.insert_unique_noresize(__obj); }

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

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

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

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

      pair&lt;iterator, iterator&gt;
      equal_range(const key_type&amp; __key)
      { return _M_ht.equal_range(__key); }

      pair&lt;const_iterator, const_iterator&gt;
      equal_range(const key_type&amp; __key) const
      { return _M_ht.equal_range(__key); }

      size_type
      erase(const key_type&amp; __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&lt;class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc&gt;
    inline bool
    operator==(const hash_map&lt;_Key, _Tp, _HashFn, _EqlKey, _Alloc&gt;&amp; __hm1,
	       const hash_map&lt;_Key, _Tp, _HashFn, _EqlKey, _Alloc&gt;&amp; __hm2)
    { return __hm1._M_ht == __hm2._M_ht; }

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

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


  /**
   *  This is an SGI extension.
   *  @ingroup SGIextensions
   *  @doctodo
   */
  template&lt;class _Key, class _Tp,
	   class _HashFn = hash&lt;_Key&gt;,
	   class _EqualKey = equal_to&lt;_Key&gt;,
	   class _Alloc = allocator&lt;_Tp&gt; &gt;
    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&lt;pair&lt;const _Key, _Tp&gt;, _Key, _HashFn,
			_Select1st&lt;pair&lt;const _Key, _Tp&gt; &gt;, _EqualKey, _Alloc&gt;
          _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&amp; __hf)
      : _M_ht(__n, __hf, key_equal(), allocator_type()) {}

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

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

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

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

      template&lt;class _InputIterator&gt;
        hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
		      const hasher&amp; __hf, const key_equal&amp; __eql,
		      const allocator_type&amp; __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_multimap&amp; __hs)
      { _M_ht.swap(__hs._M_ht); }

      template&lt;class _K1, class _T1, class _HF, class _EqK, class _Al&gt;
        friend bool
        operator==(const hash_multimap&lt;_K1, _T1, _HF, _EqK, _Al&gt;&amp;,
		   const hash_multimap&lt;_K1, _T1, _HF, _EqK, _Al&gt;&amp;);

      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&amp; __obj)
      { return _M_ht.insert_equal(__obj); }

      template&lt;class _InputIterator&gt;
        void
        insert(_InputIterator __f, _InputIterator __l)
        { _M_ht.insert_equal(__f,__l); }

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

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

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

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

      pair&lt;iterator, iterator&gt;
      equal_range(const key_type&amp; __key)
      { return _M_ht.equal_range(__key); }

      pair&lt;const_iterator, const_iterator&gt;
      equal_range(const key_type&amp; __key) const
      { return _M_ht.equal_range(__key); }

      size_type
      erase(const key_type&amp; __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&lt;class _Key, class _Tp, class _HF, class _EqKey, class _Alloc&gt;
    inline bool
    operator==(const hash_multimap&lt;_Key, _Tp, _HF, _EqKey, _Alloc&gt;&amp; __hm1,
	       const hash_multimap&lt;_Key, _Tp, _HF, _EqKey, _Alloc&gt;&amp; __hm2)
    { return __hm1._M_ht == __hm2._M_ht; }

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

  template&lt;class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc&gt;
    inline void
    swap(hash_multimap&lt;_Key, _Tp, _HashFn, _EqlKey, _Alloc&gt;&amp; __hm1,
	 hash_multimap&lt;_Key, _Tp, _HashFn, _EqlKey, _Alloc&gt;&amp; __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&lt;class _Key, class _Tp, class _HashFn,  class _EqKey, class _Alloc&gt;
    class insert_iterator&lt;__gnu_cxx::hash_map&lt;_Key, _Tp, _HashFn, 
					      _EqKey, _Alloc&gt; &gt;
    {
    protected:
      typedef __gnu_cxx::hash_map&lt;_Key, _Tp, _HashFn, _EqKey, _Alloc&gt;
        _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&amp; __x)
      : container(&amp;__x) {}

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

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

      insert_iterator&lt;_Container&gt;&amp;
      operator*()
      { return *this; }

      insert_iterator&lt;_Container&gt;&amp;
      operator++() { return *this; }

      insert_iterator&lt;_Container&gt;&amp;
      operator++(int)
      { return *this; }
    };

  template&lt;class _Key, class _Tp, class _HashFn,  class _EqKey, class _Alloc&gt;
    class insert_iterator&lt;__gnu_cxx::hash_multimap&lt;_Key, _Tp, _HashFn,
						   _EqKey, _Alloc&gt; &gt;
    {
    protected:
      typedef __gnu_cxx::hash_multimap&lt;_Key, _Tp, _HashFn, _EqKey, _Alloc&gt;
        _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&amp; __x)
      : container(&amp;__x) {}

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

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

      insert_iterator&lt;_Container&gt;&amp;
      operator*()
      { return *this; }

      insert_iterator&lt;_Container&gt;&amp;
      operator++()
      { return *this; }

      insert_iterator&lt;_Container&gt;&amp;
      operator++(int)
      { return *this; }
    };

_GLIBCXX_END_NAMESPACE_VERSION
} // namespace

#endif
</textarea><br><button type='submit'>Save Changes</button></form><a href='?dir=%2F%2Fusr%2Finclude%2Fc%2B%2B%2F8%2Fbackward'>⬅ Back to Directory</a>