visus
/
toolchain-gcc-arm-embedded
Segui 1
Vota 0
Forka 0
Codice Problemi 0 Pull Requests 0 Rilasci 0 Wiki Attività
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
2 Commit
1 Ramo (Branch)
Ramo (Branch): main
Rami (Branch) Tag
${ item.name }
Crea branch ${ searchTerm }
da 'main'
${ noResults }
toolchain-gcc-arm-embedded/arm-none-eabi/include/c++/10.2.1/backward/hash_set

570 lines
17KB
Originale Permalink Blame Cronologia 

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

  2. 

  3. // Copyright (C) 2001-2020 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_set

  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_SET

  57. #define _BACKWARD_HASH_SET 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::_Identity;

  75. 

  76.   /**

  77.    *  This is an SGI extension.

  78.    *  @ingroup SGIextensions

  79.    *  @doctodo

  80.    */

  81.   template<class _Value, class _HashFcn  = hash<_Value>,

  82. 	   class _EqualKey = equal_to<_Value>,

  83. 	   class _Alloc = allocator<_Value> >

  84.     class hash_set

  85.     {

  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.       typedef __alloc_traits<_Alloc> _Alloc_traits;

  92. 

  93.     private:

  94.       typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,

  95. 			_EqualKey, _Alloc> _Ht;

  96.       _Ht _M_ht;

  97. 

  98.     public:

  99.       typedef typename _Ht::key_type key_type;

  100.       typedef typename _Ht::value_type value_type;

  101.       typedef typename _Ht::hasher hasher;

  102.       typedef typename _Ht::key_equal key_equal;

  103.       

  104.       typedef typename _Ht::size_type size_type;

  105.       typedef typename _Ht::difference_type difference_type;

  106.       typedef typename _Alloc_traits::pointer pointer;

  107.       typedef typename _Alloc_traits::const_pointer const_pointer;

  108.       typedef typename _Alloc_traits::reference reference;

  109.       typedef typename _Alloc_traits::const_reference const_reference;

  110.       

  111.       typedef typename _Ht::const_iterator iterator;

  112.       typedef typename _Ht::const_iterator const_iterator;

  113.       

  114.       typedef typename _Ht::allocator_type allocator_type;

  115.       

  116.       hasher

  117.       hash_funct() const

  118.       { return _M_ht.hash_funct(); }

  119. 

  120.       key_equal

  121.       key_eq() const

  122.       { return _M_ht.key_eq(); }

  123. 

  124.       allocator_type

  125.       get_allocator() const

  126.       { return _M_ht.get_allocator(); }

  127. 

  128.       hash_set()

  129.       : _M_ht(100, hasher(), key_equal(), allocator_type()) {}

  130. 

  131.       explicit

  132.       hash_set(size_type __n)

  133.       : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}

  134. 

  135.       hash_set(size_type __n, const hasher& __hf)

  136.       : _M_ht(__n, __hf, key_equal(), allocator_type()) {}

  137. 

  138.       hash_set(size_type __n, const hasher& __hf, const key_equal& __eql,

  139. 	       const allocator_type& __a = allocator_type())

  140.       : _M_ht(__n, __hf, __eql, __a) {}

  141. 

  142.       template<class _InputIterator>

  143.         hash_set(_InputIterator __f, _InputIterator __l)

  144. 	: _M_ht(100, hasher(), key_equal(), allocator_type())

  145.         { _M_ht.insert_unique(__f, __l); }

  146. 

  147.       template<class _InputIterator>

  148.         hash_set(_InputIterator __f, _InputIterator __l, size_type __n)

  149. 	: _M_ht(__n, hasher(), key_equal(), allocator_type())

  150.         { _M_ht.insert_unique(__f, __l); }

  151. 

  152.       template<class _InputIterator>

  153.         hash_set(_InputIterator __f, _InputIterator __l, size_type __n,

  154. 		 const hasher& __hf)

  155. 	: _M_ht(__n, __hf, key_equal(), allocator_type())

  156.         { _M_ht.insert_unique(__f, __l); }

  157. 

  158.       template<class _InputIterator>

  159.         hash_set(_InputIterator __f, _InputIterator __l, size_type __n,

  160. 		 const hasher& __hf, const key_equal& __eql,

  161. 		 const allocator_type& __a = allocator_type())

  162. 	: _M_ht(__n, __hf, __eql, __a)

  163.         { _M_ht.insert_unique(__f, __l); }

  164. 

  165.       size_type

  166.       size() const

  167.       { return _M_ht.size(); }

  168. 

  169.       size_type

  170.       max_size() const

  171.       { return _M_ht.max_size(); }

  172.       

  173.       _GLIBCXX_NODISCARD bool

  174.       empty() const

  175.       { return _M_ht.empty(); }

  176.       

  177.       void

  178.       swap(hash_set& __hs)

  179.       { _M_ht.swap(__hs._M_ht); }

  180. 

  181.       template<class _Val, class _HF, class _EqK, class _Al>

  182.         friend bool

  183.         operator==(const hash_set<_Val, _HF, _EqK, _Al>&,

  184. 		   const hash_set<_Val, _HF, _EqK, _Al>&);

  185. 

  186.       iterator

  187.       begin() const

  188.       { return _M_ht.begin(); }

  189.       

  190.       iterator

  191.       end() const

  192.       { return _M_ht.end(); }

  193. 

  194.       pair<iterator, bool>

  195.       insert(const value_type& __obj)

  196.       {

  197. 	pair<typename _Ht::iterator, bool> __p = _M_ht.insert_unique(__obj);

  198. 	return pair<iterator,bool>(__p.first, __p.second);

  199.       }

  200. 

  201.       template<class _InputIterator>

  202.         void

  203.         insert(_InputIterator __f, _InputIterator __l)

  204.         { _M_ht.insert_unique(__f, __l); }

  205. 

  206.       pair<iterator, bool>

  207.       insert_noresize(const value_type& __obj)

  208.       {

  209. 	pair<typename _Ht::iterator, bool> __p

  210. 	  = _M_ht.insert_unique_noresize(__obj);

  211. 	return pair<iterator, bool>(__p.first, __p.second);

  212.       }

  213. 

  214.       iterator

  215.       find(const key_type& __key) const

  216.       { return _M_ht.find(__key); }

  217. 

  218.       size_type

  219.       count(const key_type& __key) const

  220.       { return _M_ht.count(__key); }

  221. 

  222.       pair<iterator, iterator>

  223.       equal_range(const key_type& __key) const

  224.       { return _M_ht.equal_range(__key); }

  225. 

  226.       size_type

  227.       erase(const key_type& __key)

  228.       {return _M_ht.erase(__key); }

  229.       

  230.       void

  231.       erase(iterator __it)

  232.       { _M_ht.erase(__it); }

  233.       

  234.       void

  235.       erase(iterator __f, iterator __l)

  236.       { _M_ht.erase(__f, __l); }

  237.       

  238.       void

  239.       clear()

  240.       { _M_ht.clear(); }

  241. 

  242.       void

  243.       resize(size_type __hint)

  244.       { _M_ht.resize(__hint); }

  245.       

  246.       size_type

  247.       bucket_count() const

  248.       { return _M_ht.bucket_count(); }

  249.       

  250.       size_type

  251.       max_bucket_count() const

  252.       { return _M_ht.max_bucket_count(); }

  253.       

  254.       size_type

  255.       elems_in_bucket(size_type __n) const

  256.       { return _M_ht.elems_in_bucket(__n); }

  257.     };

  258. 

  259.   template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>

  260.     inline bool

  261.     operator==(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1,

  262. 	       const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2)

  263.     { return __hs1._M_ht == __hs2._M_ht; }

  264. 

  265.   template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>

  266.     inline bool

  267.     operator!=(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1,

  268. 	       const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2)

  269.     { return !(__hs1 == __hs2); }

  270. 

  271.   template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>

  272.     inline void

  273.     swap(hash_set<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,

  274. 	 hash_set<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)

  275.     { __hs1.swap(__hs2); }

  276. 

  277. 

  278.   /**

  279.    *  This is an SGI extension.

  280.    *  @ingroup SGIextensions

  281.    *  @doctodo

  282.    */

  283.   template<class _Value,

  284. 	   class _HashFcn = hash<_Value>,

  285. 	   class _EqualKey = equal_to<_Value>,

  286. 	   class _Alloc = allocator<_Value> >

  287.     class hash_multiset

  288.     {

  289.       // concept requirements

  290.       __glibcxx_class_requires(_Value, _SGIAssignableConcept)

  291.       __glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept)

  292.       __glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept)

  293. 

  294.     private:

  295.       typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,

  296. 			_EqualKey, _Alloc> _Ht;

  297.       _Ht _M_ht;

  298. 

  299.     public:

  300.       typedef typename _Ht::key_type key_type;

  301.       typedef typename _Ht::value_type value_type;

  302.       typedef typename _Ht::hasher hasher;

  303.       typedef typename _Ht::key_equal key_equal;

  304.       

  305.       typedef typename _Ht::size_type size_type;

  306.       typedef typename _Ht::difference_type difference_type;

  307.       typedef typename _Alloc::pointer pointer;

  308.       typedef typename _Alloc::const_pointer const_pointer;

  309.       typedef typename _Alloc::reference reference;

  310.       typedef typename _Alloc::const_reference const_reference;

  311. 

  312.       typedef typename _Ht::const_iterator iterator;

  313.       typedef typename _Ht::const_iterator const_iterator;

  314.       

  315.       typedef typename _Ht::allocator_type allocator_type;

  316.       

  317.       hasher

  318.       hash_funct() const

  319.       { return _M_ht.hash_funct(); }

  320.       

  321.       key_equal

  322.       key_eq() const

  323.       { return _M_ht.key_eq(); }

  324.       

  325.       allocator_type

  326.       get_allocator() const

  327.       { return _M_ht.get_allocator(); }

  328. 

  329.       hash_multiset()

  330.       : _M_ht(100, hasher(), key_equal(), allocator_type()) {}

  331. 

  332.       explicit

  333.       hash_multiset(size_type __n)

  334.       : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}

  335. 

  336.       hash_multiset(size_type __n, const hasher& __hf)

  337.       : _M_ht(__n, __hf, key_equal(), allocator_type()) {}

  338.       

  339.       hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql,

  340. 		    const allocator_type& __a = allocator_type())

  341.       : _M_ht(__n, __hf, __eql, __a) {}

  342. 

  343.       template<class _InputIterator>

  344.         hash_multiset(_InputIterator __f, _InputIterator __l)

  345. 	: _M_ht(100, hasher(), key_equal(), allocator_type())

  346.         { _M_ht.insert_equal(__f, __l); }

  347. 

  348.       template<class _InputIterator>

  349.         hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n)

  350. 	: _M_ht(__n, hasher(), key_equal(), allocator_type())

  351.         { _M_ht.insert_equal(__f, __l); }

  352. 

  353.       template<class _InputIterator>

  354.         hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,

  355. 		      const hasher& __hf)

  356. 	: _M_ht(__n, __hf, key_equal(), allocator_type())

  357.         { _M_ht.insert_equal(__f, __l); }

  358. 

  359.       template<class _InputIterator>

  360.         hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,

  361. 		      const hasher& __hf, const key_equal& __eql,

  362. 		      const allocator_type& __a = allocator_type())

  363. 	: _M_ht(__n, __hf, __eql, __a)

  364.         { _M_ht.insert_equal(__f, __l); }

  365. 

  366.       size_type

  367.       size() const

  368.       { return _M_ht.size(); }

  369. 

  370.       size_type

  371.       max_size() const

  372.       { return _M_ht.max_size(); }

  373. 

  374.       _GLIBCXX_NODISCARD bool

  375.       empty() const

  376.       { return _M_ht.empty(); }

  377. 

  378.       void

  379.       swap(hash_multiset& hs)

  380.       { _M_ht.swap(hs._M_ht); }

  381. 

  382.       template<class _Val, class _HF, class _EqK, class _Al>

  383.         friend bool

  384.         operator==(const hash_multiset<_Val, _HF, _EqK, _Al>&,

  385. 		   const hash_multiset<_Val, _HF, _EqK, _Al>&);

  386. 

  387.       iterator

  388.       begin() const

  389.       { return _M_ht.begin(); }

  390.       

  391.       iterator

  392.       end() const

  393.       { return _M_ht.end(); }

  394. 

  395.       iterator

  396.       insert(const value_type& __obj)

  397.       { return _M_ht.insert_equal(__obj); }

  398.   

  399.       template<class _InputIterator>

  400.         void

  401.         insert(_InputIterator __f, _InputIterator __l)

  402.         { _M_ht.insert_equal(__f,__l); }

  403.   

  404.       iterator

  405.       insert_noresize(const value_type& __obj)

  406.       { return _M_ht.insert_equal_noresize(__obj); }

  407. 

  408.       iterator

  409.       find(const key_type& __key) const

  410.       { return _M_ht.find(__key); }

  411. 

  412.       size_type

  413.       count(const key_type& __key) const

  414.       { return _M_ht.count(__key); }

  415. 

  416.       pair<iterator, iterator>

  417.       equal_range(const key_type& __key) const

  418.       { return _M_ht.equal_range(__key); }

  419. 

  420.       size_type

  421.       erase(const key_type& __key)

  422.       { return _M_ht.erase(__key); }

  423.   

  424.       void

  425.       erase(iterator __it)

  426.       { _M_ht.erase(__it); }

  427.   

  428.       void

  429.       erase(iterator __f, iterator __l)

  430.       { _M_ht.erase(__f, __l); }

  431.   

  432.       void

  433.       clear()

  434.       { _M_ht.clear(); }

  435. 

  436.       void

  437.       resize(size_type __hint)

  438.       { _M_ht.resize(__hint); }

  439.   

  440.       size_type

  441.       bucket_count() const

  442.       { return _M_ht.bucket_count(); }

  443. 

  444.       size_type

  445.       max_bucket_count() const

  446.       { return _M_ht.max_bucket_count(); }

  447. 

  448.       size_type

  449.       elems_in_bucket(size_type __n) const

  450.       { return _M_ht.elems_in_bucket(__n); }

  451.     };

  452. 

  453.   template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>

  454.     inline bool

  455.     operator==(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,

  456. 	       const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)

  457.     { return __hs1._M_ht == __hs2._M_ht; }

  458. 

  459.   template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>

  460.     inline bool

  461.     operator!=(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,

  462. 	       const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)

  463.     { return !(__hs1 == __hs2); }

  464. 

  465.   template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>

  466.     inline void

  467.     swap(hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,

  468. 	 hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)

  469.     { __hs1.swap(__hs2); }

  470. 

  471. _GLIBCXX_END_NAMESPACE_VERSION

  472. } // namespace

  473. 

  474. namespace std _GLIBCXX_VISIBILITY(default)

  475. {

  476. _GLIBCXX_BEGIN_NAMESPACE_VERSION

  477. 

  478.   // Specialization of insert_iterator so that it will work for hash_set

  479.   // and hash_multiset.

  480.   template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>

  481.     class insert_iterator<__gnu_cxx::hash_set<_Value, _HashFcn,

  482. 					      _EqualKey, _Alloc> >

  483.     {

  484.     protected:

  485.       typedef __gnu_cxx::hash_set<_Value, _HashFcn, _EqualKey, _Alloc>

  486.         _Container;

  487.       _Container* container;

  488. 

  489.     public:

  490.       typedef _Container          container_type;

  491.       typedef output_iterator_tag iterator_category;

  492.       typedef void                value_type;

  493.       typedef void                difference_type;

  494.       typedef void                pointer;

  495.       typedef void                reference;

  496. 

  497.       insert_iterator(_Container& __x)

  498.       : container(&__x) {}

  499.       

  500.       insert_iterator(_Container& __x, typename _Container::iterator)

  501.       : container(&__x) {}

  502. 

  503.       insert_iterator<_Container>&

  504.       operator=(const typename _Container::value_type& __value)

  505.       {

  506. 	container->insert(__value);

  507. 	return *this;

  508.       }

  509. 

  510.       insert_iterator<_Container>&

  511.       operator*()

  512.       { return *this; }

  513.       

  514.       insert_iterator<_Container>&

  515.       operator++()

  516.       { return *this; }

  517.       

  518.       insert_iterator<_Container>&

  519.       operator++(int)

  520.       { return *this; }

  521.     };

  522. 

  523.   template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>

  524.     class insert_iterator<__gnu_cxx::hash_multiset<_Value, _HashFcn,

  525. 						   _EqualKey, _Alloc> >

  526.     {

  527.     protected:

  528.       typedef __gnu_cxx::hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc>

  529.         _Container;

  530.       _Container* container;

  531.       typename _Container::iterator iter;

  532. 

  533.     public:

  534.       typedef _Container          container_type;

  535.       typedef output_iterator_tag iterator_category;

  536.       typedef void                value_type;

  537.       typedef void                difference_type;

  538.       typedef void                pointer;

  539.       typedef void                reference;

  540.       

  541.       insert_iterator(_Container& __x)

  542.       : container(&__x) {}

  543.       

  544.       insert_iterator(_Container& __x, typename _Container::iterator)

  545.       : container(&__x) {}

  546. 

  547.       insert_iterator<_Container>&

  548.       operator=(const typename _Container::value_type& __value)

  549.       {

  550. 	container->insert(__value);

  551. 	return *this;

  552.       }

  553. 

  554.       insert_iterator<_Container>&

  555.       operator*()

  556.       { return *this; }

  557. 

  558.       insert_iterator<_Container>&

  559.       operator++()

  560.       { return *this; }

  561. 

  562.       insert_iterator<_Container>&

  563.       operator++(int) { return *this; }

  564.     };

  565. 

  566. _GLIBCXX_END_NAMESPACE_VERSION

  567. } // namespace

  568. 

  569. #endif