The C and C++ Include Header Files

/usr/include/c++/11/backward/hash_map


$ cat -n /usr/include/c++/11/backward/hash_map

     1	// Hashing map implementation -*- C++ -*-
     2	
     3	// Copyright (C) 2001-2021 Free Software Foundation, Inc.
     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 3, 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	// 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.
    19	
    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/>.
    24	
    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	
    51	/** @file backward/hash_map
    52	 *  This file is a GNU extension to the Standard C++ Library (possibly
    53	 *  containing extensions from the HP/SGI STL subset).
    54	 */
    55	
    56	#ifndef _BACKWARD_HASH_MAP
    57	#define _BACKWARD_HASH_MAP 1
    58	
    59	#ifndef _GLIBCXX_PERMIT_BACKWARD_HASH
    60	#include <backward/backward_warning.h>
    61	#endif
    62	
    63	#include <bits/c++config.h>
    64	#include <backward/hashtable.h>
    65	#include <bits/concept_check.h>
    66	
    67	namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
    68	{
    69	_GLIBCXX_BEGIN_NAMESPACE_VERSION
    70	
    71	  using std::equal_to;
    72	  using std::allocator;
    73	  using std::pair;
    74	  using std::_Select1st;
    75	
    76	  /**
    77	   *  This is an SGI extension.
    78	   *  @ingroup SGIextensions
    79	   *  @doctodo
    80	   */
    81	  template<class _Key, class _Tp, class _HashFn = hash<_Key>,
    82		   class _EqualKey = equal_to<_Key>, class _Alloc = allocator<_Tp> >
    83	    class hash_map
    84	    {
    85	    private:
    86	      typedef hashtable<pair<const _Key, _Tp>,_Key, _HashFn,
    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	
   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	
   138	      template<class _InputIterator>
   139	        hash_map(_InputIterator __f, _InputIterator __l)
   140		: _M_ht(100, hasher(), key_equal(), allocator_type())
   141	        { _M_ht.insert_unique(__f, __l); }
   142	
   143	      template<class _InputIterator>
   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	
   148	      template<class _InputIterator>
   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	
   154	      template<class _InputIterator>
   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	
   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	      
   169	      _GLIBCXX_NODISCARD bool
   170	      empty() const
   171	      { return _M_ht.empty(); }
   172	  
   173	      void
   174	      swap(hash_map& __hs)
   175	      { _M_ht.swap(__hs._M_ht); }
   176	
   177	      template<class _K1, class _T1, class _HF, class _EqK, class _Al>
   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	
   198	      pair<iterator, bool>
   199	      insert(const value_type& __obj)
   200	      { return _M_ht.insert_unique(__obj); }
   201	
   202	      template<class _InputIterator>
   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	
   268	  template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
   269	    inline bool
   270	    operator==(const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
   271		       const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
   272	    { return __hm1._M_ht == __hm2._M_ht; }
   273	
   274	  template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
   275	    inline bool
   276	    operator!=(const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
   277		       const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
   278	    { return !(__hm1 == __hm2); }
   279	
   280	  template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
   281	    inline void
   282	    swap(hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
   283		 hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
   284	    { __hm1.swap(__hm2); }
   285	
   286	
   287	  /**
   288	   *  This is an SGI extension.
   289	   *  @ingroup SGIextensions
   290	   *  @doctodo
   291	   */
   292	  template<class _Key, class _Tp,
   293		   class _HashFn = hash<_Key>,
   294		   class _EqualKey = equal_to<_Key>,
   295		   class _Alloc = allocator<_Tp> >
   296	    class hash_multimap
   297	    {
   298	      // concept requirements
   299	      __glibcxx_class_requires(_Key, _SGIAssignableConcept)
   300	      __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
   301	      __glibcxx_class_requires3(_HashFn, size_t, _Key, _UnaryFunctionConcept)
   302	      __glibcxx_class_requires3(_EqualKey, _Key, _Key, _BinaryPredicateConcept)
   303		
   304	    private:
   305	      typedef hashtable<pair<const _Key, _Tp>, _Key, _HashFn,
   306				_Select1st<pair<const _Key, _Tp> >, _EqualKey, _Alloc>
   307	          _Ht;
   308	
   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	
   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	
   357	      template<class _InputIterator>
   358	        hash_multimap(_InputIterator __f, _InputIterator __l)
   359		: _M_ht(100, hasher(), key_equal(), allocator_type())
   360	        { _M_ht.insert_equal(__f, __l); }
   361	
   362	      template<class _InputIterator>
   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	
   367	      template<class _InputIterator>
   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	
   373	      template<class _InputIterator>
   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	
   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	
   388	      _GLIBCXX_NODISCARD bool
   389	      empty() const
   390	      { return _M_ht.empty(); }
   391	
   392	      void
   393	      swap(hash_multimap& __hs)
   394	      { _M_ht.swap(__hs._M_ht); }
   395	
   396	      template<class _K1, class _T1, class _HF, class _EqK, class _Al>
   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(); }
   416	
   417	      iterator
   418	      insert(const value_type& __obj)
   419	      { return _M_ht.insert_equal(__obj); }
   420	
   421	      template<class _InputIterator>
   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	
   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); }
   481	    };
   482	
   483	  template<class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
   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; }
   488	
   489	  template<class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
   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); }
   494	
   495	  template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
   496	    inline void
   497	    swap(hash_multimap<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
   498		 hash_multimap<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
   499	    { __hm1.swap(__hm2); }
   500	
   501	_GLIBCXX_END_NAMESPACE_VERSION
   502	} // namespace
   503	
   504	namespace std _GLIBCXX_VISIBILITY(default)
   505	{
   506	_GLIBCXX_BEGIN_NAMESPACE_VERSION
   507	
   508	  // Specialization of insert_iterator so that it will work for hash_map
   509	  // and hash_multimap.
   510	  template<class _Key, class _Tp, class _HashFn,  class _EqKey, class _Alloc>
   511	    class insert_iterator<__gnu_cxx::hash_map<_Key, _Tp, _HashFn, 
   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	
   552	  template<class _Key, class _Tp, class _HashFn,  class _EqKey, class _Alloc>
   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	    };
   595	
   596	_GLIBCXX_END_NAMESPACE_VERSION
   597	} // namespace
   598	
   599	#endif