aGrUM  0.13.2
hashTable.h
Go to the documentation of this file.
1 /***************************************************************************
2  * Copyright (C) 2005 by Christophe GONZALES and Pierre-Henri WUILLEMIN *
3  * {prenom.nom}_at_lip6.fr *
4  * *
5  * This program is free software; you can redistribute it and/or modify *
6  * it under the terms of the GNU General Public License as published by *
7  * the Free Software Foundation; either version 2 of the License, or *
8  * (at your option) any later version. *
9  * *
10  * This program is distributed in the hope that it will be useful, *
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of *
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
13  * GNU General Public License for more details. *
14  * *
15  * You should have received a copy of the GNU General Public License *
16  * along with this program; if not, write to the *
17  * Free Software Foundation, Inc., *
18  * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. *
19  ***************************************************************************/
27 #ifndef GUM_HASHTABLE_H
28 #define GUM_HASHTABLE_H
29 
30 #include <limits>
31 
32 #include <cstddef>
33 #include <initializer_list>
34 #include <iostream>
35 #include <string>
36 #include <utility>
37 #include <vector>
38 
39 #include <agrum/agrum.h>
40 #include <agrum/core/hashFunc.h>
41 
42 namespace gum {
43 
44 #ifndef DOXYGEN_SHOULD_SKIP_THIS
45 
46  // the templates used by this file
47  template < typename Key, typename Val, typename Alloc >
48  class HashTable;
49  template < typename Key, typename Val, typename Alloc >
50  class HashTableList;
51  template < typename Key, typename Val >
52  class HashTableIterator;
53  template < typename Key, typename Val >
54  class HashTableConstIterator;
55  template < typename Key, typename Val >
56  class HashTableIteratorSafe;
57  template < typename Key, typename Val >
58  class HashTableConstIteratorSafe;
59  template < typename T1, typename T2, typename Alloc >
60  class Bijection;
61 
62 #endif /* DOXYGEN_SHOULD_SKIP_THIS */
63 
70  struct HashTableConst {
77  static constexpr Size default_size{4};
78 
84  static constexpr unsigned int default_mean_val_by_slot{3};
85 
91  static constexpr bool default_resize_policy{true};
92 
99  static constexpr bool default_uniqueness_policy{true};
100  };
101 
102  // Doxygen raises warning with the following comment bloc
103  // @brief Prints the content of a gum::HashTableList in the stream.
104  // @ingroup hashtable_group
105  // @param s The s used to print the gum::HashTableList.
106  // @param list The gum::HashTableList to print.
107  // @return Returns the std::ostream s.
108  // @tparam Key The type of keys in the gum::HashTableList.
109  // @tparam Val The type of values in the gum::HashTableList.
110  // @tparam Alloc The gum::HashTableList allocator.
111 
116  template < typename Key, typename Val, typename Alloc >
117  std::ostream& operator<<(std::ostream& s,
119 
120  // Doxygen raises warning with the following comment bloc
121  // @brief Prints the content of a gum::HashTableList with pointers key in the
122  // stream.
123  // @ingroup hashtable_group
124  // @param s The s used to print the gum::HashTableList.
125  // @param list The gum::HashTableList to print.
126  // @return Returns the std::ostream s.
127  // @tparam Key The type of keys in the gum::HashTableList.
128  // @tparam Val The type of values in the gum::HashTableList.
129  // @tparam Alloc The gum::HashTableList allocator.
130  //
131 
137  template < typename Key, typename Val, typename Alloc >
138  std::ostream& operator<<(std::ostream& s,
140 
141  // Doxygen raises warning with the following comment bloc
142  // @brief Prints the content of a gum::HashTable in the stream.
143  // @ingroup hashtable_group
144  // @param s The stream used to print the gum::HashTable.
145  // @param table The gum::HashTable to print.
146  // @return Returns the std::ostream s.
147  // @tparam Key The type of keys in the gum::HashTable.
148  // @tparam Val The type of values in the gum::HashTable.
149  // @tparam Alloc The gum::HashTable allocator.
150 
155  template < typename Key, typename Val, typename Alloc >
156  std::ostream& operator<<(std::ostream& s,
157  const HashTable< Key, Val, Alloc >& table);
158 
159  // Doxygen raises warning with the following comment bloc
160  // @brief Prints the content of a gum::HashTable with pointers key in the
161  // stream.
162  // @ingroup hashtable_group
163  // @param s The stream used to print the gum::HashTable.
164  // @param table The gum::HashTable to print.
165  // @return Returns the std::ostream s.
166  // @tparam Key The type of keys in the gum::HashTable.
167  // @tparam Val The type of values in the gum::HashTable.
168  // @tparam Alloc The gum::HashTable allocator.
169 
175  template < typename Key, typename Val, typename Alloc >
176  std::ostream& operator<<(std::ostream& s,
177  const HashTable< Key*, Val, Alloc >& table);
178 
179  // ===========================================================================
180  // === LISTS SPECIFIC FOR SAVING ELEMENTS IN HASHTABLES ===
181  // ===========================================================================
182 
198  template < typename Key, typename Val >
201  std::pair< const Key, Val > pair;
202 
205 
208 
213  enum class Emplace { EMPLACE };
214 
219 
224  HashTableBucket(const HashTableBucket< Key, Val >& from) : pair{from.pair} {}
225 
231  HashTableBucket(const Key& k, const Val& v) : pair{k, v} {}
232 
238  HashTableBucket(Key&& k, Val&& v) : pair{std::move(k), std::move(v)} {}
239 
244  HashTableBucket(const std::pair< const Key, Val >& p) : pair(p) {}
245 
250  HashTableBucket(std::pair< const Key, Val >&& p) : pair(std::move(p)) {}
251 
258  template < typename... Args >
259  HashTableBucket(Emplace e, Args&&... args) :
260  // emplace (universal) constructor
261  pair(std::forward< Args >(args)...) {}
262 
267 
272  std::pair< const Key, Val >& elt() { return pair; }
273 
278  Key& key() { return const_cast< Key& >(pair.first); }
279 
284  Val& val() { return pair.second; }
285  };
286 
287  // ===========================================================================
288  // === DOUBLY CHAINED LISTS FOR STORING ELEMENTS IN HASH TABLES ===
289  // ===========================================================================
290 
301  template < typename Key, typename Val, typename Alloc >
303  public:
306  using key_type = Key;
307  using mapped_type = Val;
308  using value_type = std::pair< const Key, Val >;
310  using const_reference = const value_type&;
311  using pointer = value_type*;
312  using const_pointer = const value_type*;
313  using size_type = std::size_t;
314  using allocator_type = Alloc;
317 
319  using BucketAllocator = typename Alloc::template rebind< Bucket >::other;
320 
321  // ============================================================================
323  // ============================================================================
325 
335  HashTableList(BucketAllocator* allocator = nullptr) noexcept;
336 
348  HashTableList(const HashTableList< Key, Val, Alloc >& from);
349 
354  HashTableList(HashTableList< Key, Val, Alloc >&& from) noexcept;
355 
359  ~HashTableList();
360 
362  // ============================================================================
364  // ============================================================================
366 
384  HashTableList< Key, Val, Alloc >&
385  operator=(const HashTableList< Key, Val, Alloc >& from);
386 
404  template < typename OtherAlloc >
405  HashTableList< Key, Val, Alloc >&
406  operator=(const HashTableList< Key, Val, OtherAlloc >& from);
407 
414  HashTableList< Key, Val, Alloc >&
415  operator=(HashTableList< Key, Val, Alloc >&& from) noexcept;
416 
418  // ============================================================================
420  // ============================================================================
422 
431  value_type& at(unsigned int i);
432 
441  const value_type& at(unsigned int i) const;
442 
449  mapped_type& operator[](const key_type& key);
450 
457  const mapped_type& operator[](const key_type& key) const;
458 
466  bool exists(const key_type& key) const;
467 
474  void insert(Bucket* new_elt) noexcept;
475 
480  void erase(Bucket* ptr);
481 
485  void clear();
486 
491  bool empty() const noexcept;
492 
500  Bucket* bucket(const Key& key) const;
501 
506  void setAllocator(BucketAllocator& alloc);
507 
509 
510  private:
513  template < typename K, typename V, typename A >
514  friend class HashTableList;
515  friend class HashTable< Key, Val, Alloc >;
516  friend class HashTableIterator< Key, Val >;
517  friend class HashTableConstIterator< Key, Val >;
518  friend class HashTableIteratorSafe< Key, Val >;
519  friend class HashTableConstIteratorSafe< Key, Val >;
520  friend std::ostream& operator<<<>(std::ostream&,
521  const HashTableList< Key, Val, Alloc >&);
522  friend std::ostream& operator<<<>(std::ostream&,
523  const HashTableList< Key*, Val, Alloc >&);
524  friend std::ostream& operator<<<>(std::ostream&,
525  const HashTable< Key, Val, Alloc >&);
526  friend std::ostream& operator<<<>(std::ostream&,
527  const HashTable< Key*, Val, Alloc >&);
529 
531  HashTableBucket< Key, Val >* __deb_list{nullptr};
532 
534  HashTableBucket< Key, Val >* __end_list{nullptr};
535 
537  unsigned int __nb_elements{0};
538 
541 
552  template < typename OtherAlloc >
553  void __copy(const HashTableList< Key, Val, OtherAlloc >& from);
554  };
555 
556  // ===========================================================================
557  // === GENERIC HASH TABLES ===
558  // ===========================================================================
673  template < typename Key,
674  typename Val,
675  typename Alloc = std::allocator< std::pair< Key, Val > > >
676  class HashTable {
677  public:
680  using key_type = Key;
681  using mapped_type = Val;
682  using value_type = std::pair< const Key, Val >;
684  using const_reference = const value_type&;
685  using pointer = value_type*;
686  using const_pointer = const value_type*;
687  using size_type = std::size_t;
688  using difference_type = std::ptrdiff_t;
689  using allocator_type = Alloc;
695 
698 
700  using BucketAllocator = typename Alloc::template rebind< Bucket >::other;
701 
702  // ============================================================================
704  // ============================================================================
706 
724  explicit HashTable(
725  Size size_param = HashTableConst::default_size,
726  bool resize_pol = HashTableConst::default_resize_policy,
727  bool key_uniqueness_pol = HashTableConst::default_uniqueness_policy);
728 
733  explicit HashTable(std::initializer_list< std::pair< Key, Val > > list);
734 
748 
761  template < typename OtherAlloc >
763 
769 
773  ~HashTable();
774 
776  // ============================================================================
778  // ============================================================================
780 
791  const iterator& end() noexcept;
792 
805  const const_iterator& end() const noexcept;
806 
819  const const_iterator& cend() const noexcept;
820 
833  iterator begin();
834 
847  const_iterator begin() const;
848 
861  const_iterator cbegin() const;
862 
872  const iterator_safe& endSafe() noexcept;
873 
885  const const_iterator_safe& endSafe() const noexcept;
886 
898  const const_iterator_safe& cendSafe() const noexcept;
899 
911  iterator_safe beginSafe();
912 
924  const_iterator_safe beginSafe() const;
925 
937  const_iterator_safe cbeginSafe() const;
938 
976  static const iterator& end4Statics();
977 
1015  static const const_iterator& constEnd4Statics();
1016 
1054  static const iterator_safe& endSafe4Statics();
1055 
1093  static const const_iterator_safe& constEndSafe4Statics();
1094 
1096  // ============================================================================
1098  // ============================================================================
1100 
1113  HashTable< Key, Val, Alloc >&
1114  operator=(const HashTable< Key, Val, Alloc >& from);
1115 
1128  template < typename OtherAlloc >
1129  HashTable< Key, Val, Alloc >&
1130  operator=(const HashTable< Key, Val, OtherAlloc >& from);
1131 
1138  HashTable< Key, Val, Alloc >& operator=(HashTable< Key, Val, Alloc >&& from);
1139 
1151  Val& operator[](const Key& key);
1152 
1154 
1157  const Val& operator[](const Key& key) const;
1158 
1170  template < typename OtherAlloc >
1171  bool operator==(const HashTable< Key, Val, OtherAlloc >& from) const;
1172 
1174 
1185  template < typename OtherAlloc >
1186  bool operator!=(const HashTable< Key, Val, OtherAlloc >& from) const;
1187 
1189  // ============================================================================
1191  // ============================================================================
1193 
1203  Size capacity() const noexcept;
1204 
1206 
1223  void resize(Size new_size);
1224 
1242  void setResizePolicy(const bool new_policy) noexcept;
1243 
1248  bool resizePolicy() const noexcept;
1249 
1265  void setKeyUniquenessPolicy(const bool new_policy) noexcept;
1266 
1271  bool keyUniquenessPolicy() const noexcept;
1272 
1274  // ============================================================================
1276  // ============================================================================
1278 
1286  Size size() const noexcept;
1287 
1298  bool exists(const Key& key) const;
1299 
1320  value_type& insert(const Key& key, const Val& val);
1321 
1340  value_type& insert(Key&& key, Val&& val);
1341 
1361  value_type& insert(const std::pair< Key, Val >& elt);
1362 
1380  value_type& insert(std::pair< Key, Val >&& elt);
1381 
1398  template < typename... Args >
1399  value_type& emplace(Args&&... args);
1400 
1415  mapped_type& getWithDefault(const Key& key, const Val& default_value);
1416 
1431  mapped_type& getWithDefault(Key&& key, Val&& default_value);
1432 
1444  void set(const Key& key, const Val& default_value);
1445 
1455  void reset(const Key& key);
1456 
1471  void erase(const Key& key);
1472 
1483  void erase(const iterator_safe& iter);
1484 
1495  void erase(const const_iterator_safe& iter);
1496 
1513  void eraseByVal(const Val& val);
1514 
1525  const Key& keyByVal(const Val& val) const;
1526 
1539  const Key& key(const Key& key) const;
1540 
1553  void eraseAllVal(const Val& val);
1554 
1563  void clear();
1564 
1569  bool empty() const noexcept;
1570 
1591  template < typename Mount,
1592  typename OtherAlloc = typename Alloc::template rebind<
1593  std::pair< Key, Mount > >::other >
1594  HashTable< Key, Mount, OtherAlloc > map(
1595  Mount (*f)(Val),
1596  Size size = 0,
1597  bool resize_pol = HashTableConst::default_resize_policy,
1598  bool key_uniqueness_pol = HashTableConst::default_uniqueness_policy) const;
1599 
1620  template < typename Mount,
1621  typename OtherAlloc = typename Alloc::template rebind<
1622  std::pair< Key, Mount > >::other >
1623  HashTable< Key, Mount, OtherAlloc > map(
1624  Mount (*f)(Val&),
1625  Size size = 0,
1626  bool resize_pol = HashTableConst::default_resize_policy,
1627  bool key_uniqueness_pol = HashTableConst::default_uniqueness_policy) const;
1628 
1649  template < typename Mount,
1650  typename OtherAlloc = typename Alloc::template rebind<
1651  std::pair< Key, Mount > >::other >
1652  HashTable< Key, Mount, OtherAlloc > map(
1653  Mount (*f)(const Val&),
1654  Size size = 0,
1655  bool resize_pol = HashTableConst::default_resize_policy,
1656  bool key_uniqueness_pol = HashTableConst::default_uniqueness_policy) const;
1657 
1680  template < typename Mount,
1681  typename OtherAlloc = typename Alloc::template rebind<
1682  std::pair< Key, Mount > >::other >
1683  HashTable< Key, Mount, OtherAlloc > map(
1684  const Mount& val,
1685  Size size = 0,
1686  bool resize_pol = HashTableConst::default_resize_policy,
1687  bool key_uniqueness_pol = HashTableConst::default_uniqueness_policy) const;
1688 
1690 
1691  private:
1694  template < typename K, typename V, typename A >
1695  friend class HashTable;
1696  friend class HashTableIterator< Key, Val >;
1697  friend class HashTableConstIterator< Key, Val >;
1698  friend class HashTableIteratorSafe< Key, Val >;
1699  friend class HashTableConstIteratorSafe< Key, Val >;
1700 
1701  friend std::ostream& operator<<<>(std::ostream&,
1702  const HashTable< Key, Val, Alloc >&);
1703  friend std::ostream& operator<<<>(std::ostream& s,
1704  const HashTable< Key*, Val, Alloc >& table);
1705 
1707  template < typename T1, typename T2, typename A >
1708  friend class Bijection;
1710 
1715  std::vector< HashTableList< Key, Val, Alloc > > __nodes;
1716 
1718  Size __size;
1719 
1721  Size __nb_elements{0};
1722 
1725 
1727  bool __resize_policy{true};
1728 
1730  bool __key_uniqueness_policy{true};
1731 
1746  mutable Size __begin_index{std::numeric_limits< Size >::max()};
1747 
1749  mutable std::vector< HashTableConstIteratorSafe< Key, Val >* >
1751 
1761 
1763  void __erase(HashTableBucket< Key, Val >* bucket, Size index);
1764 
1780  template < typename OtherAlloc >
1781  void __copy(const HashTable< Key, Val, OtherAlloc >& table);
1782 
1787  void __create(Size size);
1788 
1792  void __clearIterators();
1793 
1810  void __insert(Bucket* bucket);
1811  };
1812 
1813 
1814  // ===========================================================================
1815  // === SAFE HASH TABLES CONST ITERATORS ===
1816  // ===========================================================================
1817 
1829  private:
1832 
1835 
1840  static const HashTableIterator< int, int >* end4Statics();
1841 
1846  static const HashTableConstIterator< int, int >* constEnd4Statics();
1847 
1853  static const HashTableIteratorSafe< int, int >* endSafe4Statics();
1854 
1860  static const HashTableConstIteratorSafe< int, int >* constEndSafe4Statics();
1861 
1863  template < typename Key, typename Val, typename Alloc >
1864  friend class HashTable;
1865  };
1866 
1867 
1868  // ===========================================================================
1869  // === SAFE HASH TABLES CONST ITERATORS ===
1870  // ===========================================================================
1914  template < typename Key, typename Val >
1916  public:
1919  using iterator_category = std::forward_iterator_tag;
1920  using key_type = Key;
1921  using mapped_type = Val;
1922  using value_type = std::pair< const Key, Val >;
1924  using const_reference = const value_type&;
1926  using const_pointer = const value_type*;
1927  using difference_type = std::ptrdiff_t;
1929 
1930  // ============================================================================
1932  // ============================================================================
1934 
1939 
1946  template < typename Alloc >
1948 
1950 
1962  template < typename Alloc >
1964  Size ind_elt);
1965 
1971 
1976  explicit HashTableConstIteratorSafe(
1978 
1984 
1988  ~HashTableConstIteratorSafe() noexcept;
1989 
1991  // ============================================================================
1993  // ============================================================================
1995 
2002  const key_type& key() const;
2003 
2005 
2011  const mapped_type& val() const;
2012 
2020  void clear() noexcept;
2021 
2023  // ============================================================================
2025  // ============================================================================
2027 
2033  HashTableConstIteratorSafe< Key, Val >&
2034  operator=(const HashTableConstIteratorSafe< Key, Val >& from);
2035 
2041  HashTableConstIteratorSafe< Key, Val >&
2042  operator=(const HashTableConstIterator< Key, Val >& from);
2043 
2049  HashTableConstIteratorSafe< Key, Val >&
2050  operator=(HashTableConstIteratorSafe< Key, Val >&& from) noexcept;
2051 
2067  HashTableConstIteratorSafe< Key, Val >& operator++() noexcept;
2068 
2075  HashTableConstIteratorSafe< Key, Val >& operator+=(unsigned int i) noexcept;
2076 
2084  HashTableConstIteratorSafe< Key, Val > operator+(unsigned int i) const;
2085 
2091  bool operator!=(const HashTableConstIteratorSafe< Key, Val >& from) const
2092  noexcept;
2093 
2099  bool operator==(const HashTableConstIteratorSafe< Key, Val >& from) const
2100  noexcept;
2101 
2108  const value_type& operator*() const;
2109 
2111 
2112  protected:
2119  template < typename K, typename V, typename A >
2120  friend class HashTable;
2121 
2123  const HashTable< Key, Val >* __table{nullptr};
2124 
2129  Size __index{0};
2130 
2132  HashTableBucket< Key, Val >* __bucket{nullptr};
2133 
2142  HashTableBucket< Key, Val >* __next_bucket{nullptr};
2143 
2145  HashTableBucket< Key, Val >* __getBucket() const noexcept;
2146 
2153  Size __getIndex() const noexcept;
2154 
2158  void __removeFromSafeList() const;
2159 
2163  void __insertIntoSafeList() const;
2164  };
2165 
2166  // ===========================================================================
2167  // === HASH TABLES ITERATORS ===
2168  // ===========================================================================
2169 
2216  template < typename Key, typename Val >
2218  public:
2221  using iterator_category = std::forward_iterator_tag;
2222  using key_type = Key;
2223  using mapped_type = Val;
2224  using value_type = std::pair< const Key, Val >;
2226  using const_reference = const value_type&;
2228  using const_pointer = const value_type*;
2229  using difference_type = std::ptrdiff_t;
2231 
2232  // ============================================================================
2234  // ============================================================================
2236 
2241 
2247  template < typename Alloc >
2249 
2262  template < typename Alloc >
2264 
2271 
2278 
2285 
2289  ~HashTableIteratorSafe() noexcept;
2290 
2292  // ============================================================================
2294  // ============================================================================
2296 
2299  using HashTableConstIteratorSafe< Key, Val >::key;
2300  using HashTableConstIteratorSafe< Key, Val >::val;
2301  using HashTableConstIteratorSafe< Key, Val >::clear;
2303 
2310  mapped_type& val();
2311 
2313  // ============================================================================
2315  // ============================================================================
2317 
2323  HashTableIteratorSafe< Key, Val >&
2324  operator=(const HashTableIteratorSafe< Key, Val >& from);
2325 
2331  HashTableIteratorSafe< Key, Val >&
2332  operator=(const HashTableIterator< Key, Val >& from);
2333 
2339  HashTableIteratorSafe< Key, Val >&
2340  operator=(HashTableIteratorSafe< Key, Val >&& from) noexcept;
2341 
2356  HashTableIteratorSafe< Key, Val >& operator++() noexcept;
2357 
2363  HashTableIteratorSafe< Key, Val >& operator+=(unsigned int i) noexcept;
2364 
2371  HashTableIteratorSafe< Key, Val > operator+(unsigned int i) const;
2372 
2379  bool operator!=(const HashTableIteratorSafe< Key, Val >& from) const noexcept;
2380 
2387  bool operator==(const HashTableIteratorSafe< Key, Val >& from) const noexcept;
2388 
2395  value_type& operator*();
2396 
2404  const value_type& operator*() const;
2405 
2407  };
2408 
2409  // ===========================================================================
2410  // === UNSAFE HASH TABLES CONST ITERATORS ===
2411  // ===========================================================================
2412 
2461  template < typename Key, typename Val >
2463  public:
2466  using iterator_category = std::forward_iterator_tag;
2467  using key_type = Key;
2468  using mapped_type = Val;
2469  using value_type = std::pair< const Key, Val >;
2471  using const_reference = const value_type&;
2473  using const_pointer = const value_type*;
2474  using difference_type = std::ptrdiff_t;
2476 
2477  // ============================================================================
2479  // ============================================================================
2481 
2485  HashTableConstIterator() noexcept;
2486 
2493  template < typename Alloc >
2494  HashTableConstIterator(const HashTable< Key, Val, Alloc >& tab) noexcept;
2495 
2507  template < typename Alloc >
2508  HashTableConstIterator(const HashTable< Key, Val, Alloc >& tab, Size ind_elt);
2509 
2514  HashTableConstIterator(
2515  const HashTableConstIterator< Key, Val >& from) noexcept;
2516 
2521  HashTableConstIterator(HashTableConstIterator< Key, Val >&& from) noexcept;
2522 
2526  ~HashTableConstIterator() noexcept;
2527 
2529  // ============================================================================
2531  // ============================================================================
2533 
2545  const key_type& key() const;
2546 
2556  const mapped_type& val() const;
2557 
2562  void clear() noexcept;
2563 
2565  // ============================================================================
2567  // ============================================================================
2569 
2575  HashTableConstIterator< Key, Val >&
2576  operator=(const HashTableConstIterator< Key, Val >& from) noexcept;
2577 
2583  HashTableConstIterator< Key, Val >&
2584  operator=(HashTableConstIterator< Key, Val >&& from) noexcept;
2585 
2587 
2603  HashTableConstIterator< Key, Val >& operator++() noexcept;
2604 
2610  HashTableConstIterator< Key, Val >& operator+=(unsigned int i) noexcept;
2611 
2619  HashTableConstIterator< Key, Val > operator+(unsigned int i) const noexcept;
2620 
2627  bool operator!=(const HashTableConstIterator< Key, Val >& from) const noexcept;
2628 
2635  bool operator==(const HashTableConstIterator< Key, Val >& from) const noexcept;
2636 
2637 
2647  const value_type& operator*() const;
2648 
2650 
2651  protected:
2662  template < typename K, typename V, typename A >
2663  friend class HashTable;
2664 
2666  friend class HashTableConstIteratorSafe< Key, Val >;
2667 
2669  const HashTable< Key, Val >* __table{nullptr};
2670 
2675  Size __index{0};
2676 
2678  typename HashTable< Key, Val >::Bucket* __bucket{nullptr};
2679 
2684  typename HashTable< Key, Val >::Bucket* __getBucket() const noexcept;
2685 
2692  Size __getIndex() const noexcept;
2693  };
2694 
2695  // ===========================================================================
2696  // === UNSAFE HASH TABLES ITERATORS ===
2697  // ===========================================================================
2698 
2746  template < typename Key, typename Val >
2747  class HashTableIterator : public HashTableConstIterator< Key, Val > {
2748  public:
2751  using iterator_category = std::forward_iterator_tag;
2752  using key_type = Key;
2753  using mapped_type = Val;
2754  using value_type = std::pair< const Key, Val >;
2756  using const_reference = const value_type&;
2758  using const_pointer = const value_type*;
2759  using difference_type = std::ptrdiff_t;
2761 
2762  // ############################################################################
2764  // ############################################################################
2766 
2770  HashTableIterator() noexcept;
2771 
2778  template < typename Alloc >
2779  HashTableIterator(const HashTable< Key, Val, Alloc >& tab) noexcept;
2780 
2782 
2794  template < typename Alloc >
2795  HashTableIterator(const HashTable< Key, Val, Alloc >& tab, Size ind_elt);
2796 
2801  HashTableIterator(const HashTableIterator< Key, Val >& from) noexcept;
2802 
2807  HashTableIterator(HashTableIterator< Key, Val >&& from) noexcept;
2808 
2812  ~HashTableIterator() noexcept;
2813 
2815  // ============================================================================
2817  // ============================================================================
2819 
2822  using HashTableConstIterator< Key, Val >::key;
2823  using HashTableConstIterator< Key, Val >::val;
2824  using HashTableConstIterator< Key, Val >::clear;
2826 
2836  mapped_type& val();
2837 
2839  // ============================================================================
2841  // ============================================================================
2843 
2849  HashTableIterator< Key, Val >&
2850  operator=(const HashTableIterator< Key, Val >& from) noexcept;
2851 
2857  HashTableIterator< Key, Val >&
2858  operator=(HashTableIterator< Key, Val >&& from) noexcept;
2859 
2876  HashTableIterator< Key, Val >& operator++() noexcept;
2877 
2883  HashTableIterator< Key, Val >& operator+=(unsigned int i) noexcept;
2884 
2890  HashTableIterator< Key, Val > operator+(unsigned int i) const noexcept;
2891 
2898  bool operator!=(const HashTableIterator< Key, Val >& from) const noexcept;
2899 
2906  bool operator==(const HashTableIterator< Key, Val >& from) const noexcept;
2907 
2917  value_type& operator*();
2918 
2928  const value_type& operator*() const;
2929 
2931  };
2932 
2933 } // namespace gum
2934 
2935 
2936 extern template class gum::HashTable< int, int >;
2937 extern template class gum::HashTable< int, std::string >;
2938 extern template class gum::HashTable< std::string, std::string >;
2939 extern template class gum::HashTable< std::string, int >;
2940 
2941 
2942 // always include the implementation of the templates
2943 #include <agrum/core/hashTable_tpl.h>
2944 
2945 #endif // GUM_HASHTABLE_H
const value_type & const_reference
Definition: hashTable.h:684
unsigned long Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:50
Key & key()
Returns the key part of the pair.
Definition: hashTable.h:278
Unsafe Const Iterators for hashtablesHashTableConstIterator provides a fast but unsafe way to parse H...
Definition: hashTable.h:2462
const value_type * const_pointer
Definition: hashTable.h:686
HashTableBucket()
Class constructor.
Definition: hashTable.h:218
typename std::allocator< std::pair< Val, unsigned long > >::template rebind< Bucket >::other BucketAllocator
The Bucket allocator.
Definition: hashTable.h:700
A recipient for a pair of key value in a gum::HashTableList.
Definition: hashTable.h:199
BucketAllocator __alloc
The allocator for the buckets.
Definition: hashTable.h:1760
Unsafe Iterators for hashtablesHashTableIterator provides a fast but unsafe way to parse HashTables...
Definition: hashTable.h:2747
HashTableBucket(const std::pair< const Key, Val > &p)
Constructor.
Definition: hashTable.h:244
HashFunc< Key > __hash_func
The function used to hash keys (may change when the table is resized).
Definition: hashTable.h:1724
Emplace
A dummy type for the emplace constructor.
Definition: hashTable.h:213
Safe Const Iterators for hashtables.
Definition: hashTable.h:1915
STL namespace.
static constexpr Size default_size
The default number of slots in hashtables.
Definition: hashTable.h:77
Classes providing basic hash functions for hash tables.
static const HashTableIterator< int, int > * __HashTableIterEnd
The unsafe iterator used by everyone.
Definition: hashTable.h:1831
Base class for discrete random variable.
Safe Iterators for hashtables.
Definition: hashTable.h:2217
gum is the global namespace for all aGrUM entities
Definition: agrum.h:25
BucketAllocator * __alloc_bucket
The allocator of the containing hashTable.
Definition: hashTable.h:540
std::vector< HashTableConstIteratorSafe< Key, Val > * > __safe_iterators
The list of safe iterators pointing to the hash table.
Definition: hashTable.h:1750
The class for generic Hash Tables.
Definition: hashTable.h:676
std::ostream & operator<<(std::ostream &output, const BayesNet< GUM_SCALAR > &bn)
Prints map&#39;s DAG in output using the Graphviz-dot format.
Definition: BayesNet_tpl.h:573
static const HashTableIteratorSafe< int, int > * __HashTableIterEndSafe
The safe iterator used by everyone.
Definition: hashTable.h:1834
Val key_type
Types for STL compliance.
Definition: hashTable.h:680
HashTableBucket(std::pair< const Key, Val > &&p)
Constructor.
Definition: hashTable.h:250
std::pair< const Val, unsigned long > value_type
Definition: hashTable.h:1922
static constexpr bool default_resize_policy
A Boolean indicating whether inserting too many values into the hashtable makes it resize itself auto...
Definition: hashTable.h:91
std::pair< const Key, Val > pair
The pair stored in this bucket.
Definition: hashTable.h:201
Parameters specifying the default behavior of the hashtables.
Definition: hashTable.h:70
std::forward_iterator_tag iterator_category
Types for STL compliance.
Definition: hashTable.h:2466
Set of pairs of elements with fast search for both elements.
Definition: bijection.h:1803
std::forward_iterator_tag iterator_category
Types for STL compliance.
Definition: hashTable.h:1919
A class used to create the static iterator used by HashTables.
Definition: hashTable.h:1828
HashTableBucket(const Key &k, const Val &v)
Constructor.
Definition: hashTable.h:231
Val & val()
Returns the value part of the pair.
Definition: hashTable.h:284
std::pair< const Val, unsigned long > value_type
Definition: hashTable.h:682
std::pair< const Key, bool > value_type
Definition: hashTable.h:2469
static constexpr bool default_uniqueness_policy
A Boolean indicating the default behavior when trying to insert more than once elements with identica...
Definition: hashTable.h:99
~HashTableBucket()
Class destructor.
Definition: hashTable.h:266
A chained list used by gum::HashTable.
Definition: hashTable.h:302
std::allocator< std::pair< Val, unsigned long > > allocator_type
Definition: hashTable.h:689
HashTableBucket(Key &&k, Val &&v)
Constructor.
Definition: hashTable.h:238
HashTableBucket(Emplace e, Args &&...args)
The emplace constructor.
Definition: hashTable.h:259
typename std::allocator< std::pair< const gum::DiscreteVariable *, unsigned long > >::template rebind< Bucket >::other BucketAllocator
The Bucket allocator.
Definition: hashTable.h:319
HashTableBucket(const HashTableBucket< Key, Val > &from)
Copy constructor.
Definition: hashTable.h:224
static constexpr unsigned int default_mean_val_by_slot
The average number of elements admissible by slots.
Definition: hashTable.h:84
std::pair< const Key, Val > & elt()
Returns the pair stored in this bucket.
Definition: hashTable.h:272