aGrUM  0.15.1
hashTable.h
Go to the documentation of this file.
1 
30 #ifndef GUM_HASHTABLE_H
31 #define GUM_HASHTABLE_H
32 
33 #include <limits>
34 
35 #include <cstddef>
36 #include <initializer_list>
37 #include <iostream>
38 #include <string>
39 #include <utility>
40 #include <vector>
41 
42 #include <agrum/agrum.h>
43 #include <agrum/core/hashFunc.h>
44 
45 namespace gum {
46 
47 #ifndef DOXYGEN_SHOULD_SKIP_THIS
48 
49  // the templates used by this file
50  template < typename Key, typename Val, typename Alloc >
51  class HashTable;
52  template < typename Key, typename Val, typename Alloc >
53  class HashTableList;
54  template < typename Key, typename Val >
55  class HashTableIterator;
56  template < typename Key, typename Val >
57  class HashTableConstIterator;
58  template < typename Key, typename Val >
59  class HashTableIteratorSafe;
60  template < typename Key, typename Val >
61  class HashTableConstIteratorSafe;
62  template < typename T1, typename T2, typename Alloc >
63  class Bijection;
64 
65 #endif /* DOXYGEN_SHOULD_SKIP_THIS */
66 
73  struct HashTableConst {
80  static constexpr Size default_size{Size(4)};
81 
87  static constexpr Size default_mean_val_by_slot{Size(3)};
88 
94  static constexpr bool default_resize_policy{true};
95 
102  static constexpr bool default_uniqueness_policy{true};
103  };
104 
105  // Doxygen raises warning with the following comment bloc
106  // @brief Prints the content of a gum::HashTableList in the stream.
107  // @ingroup hashtable_group
108  // @param s The s used to print the gum::HashTableList.
109  // @param list The gum::HashTableList to print.
110  // @return Returns the std::ostream s.
111  // @tparam Key The type of keys in the gum::HashTableList.
112  // @tparam Val The type of values in the gum::HashTableList.
113  // @tparam Alloc The gum::HashTableList allocator.
114 
119  template < typename Key, typename Val, typename Alloc >
120  std::ostream& operator<<(std::ostream& s,
122 
123  // Doxygen raises warning with the following comment bloc
124  // @brief Prints the content of a gum::HashTableList with pointers key in the
125  // stream.
126  // @ingroup hashtable_group
127  // @param s The s used to print the gum::HashTableList.
128  // @param list The gum::HashTableList to print.
129  // @return Returns the std::ostream s.
130  // @tparam Key The type of keys in the gum::HashTableList.
131  // @tparam Val The type of values in the gum::HashTableList.
132  // @tparam Alloc The gum::HashTableList allocator.
133  //
134 
140  template < typename Key, typename Val, typename Alloc >
141  std::ostream& operator<<(std::ostream& s,
143 
144  // Doxygen raises warning with the following comment bloc
145  // @brief Prints the content of a gum::HashTable in the stream.
146  // @ingroup hashtable_group
147  // @param s The stream used to print the gum::HashTable.
148  // @param table The gum::HashTable to print.
149  // @return Returns the std::ostream s.
150  // @tparam Key The type of keys in the gum::HashTable.
151  // @tparam Val The type of values in the gum::HashTable.
152  // @tparam Alloc The gum::HashTable allocator.
153 
158  template < typename Key, typename Val, typename Alloc >
159  std::ostream& operator<<(std::ostream& s,
160  const HashTable< Key, Val, Alloc >& table);
161 
162  // Doxygen raises warning with the following comment bloc
163  // @brief Prints the content of a gum::HashTable with pointers key in the
164  // stream.
165  // @ingroup hashtable_group
166  // @param s The stream used to print the gum::HashTable.
167  // @param table The gum::HashTable to print.
168  // @return Returns the std::ostream s.
169  // @tparam Key The type of keys in the gum::HashTable.
170  // @tparam Val The type of values in the gum::HashTable.
171  // @tparam Alloc The gum::HashTable allocator.
172 
178  template < typename Key, typename Val, typename Alloc >
179  std::ostream& operator<<(std::ostream& s,
180  const HashTable< Key*, Val, Alloc >& table);
181 
182  // ===========================================================================
183  // === LISTS SPECIFIC FOR SAVING ELEMENTS IN HASHTABLES ===
184  // ===========================================================================
185 
201  template < typename Key, typename Val >
204  std::pair< const Key, Val > pair;
205 
208 
211 
216  enum class Emplace { EMPLACE };
217 
222 
227  HashTableBucket(const HashTableBucket< Key, Val >& from) : pair{from.pair} {}
228 
234  HashTableBucket(const Key& k, const Val& v) : pair{k, v} {}
235 
241  HashTableBucket(Key&& k, Val&& v) : pair{std::move(k), std::move(v)} {}
242 
247  HashTableBucket(const std::pair< const Key, Val >& p) : pair(p) {}
248 
253  HashTableBucket(std::pair< const Key, Val >&& p) : pair(std::move(p)) {}
254 
261  template < typename... Args >
262  HashTableBucket(Emplace e, Args&&... args) :
263  // emplace (universal) constructor
264  pair(std::forward< Args >(args)...) {}
265 
270 
275  std::pair< const Key, Val >& elt() { return pair; }
276 
281  Key& key() { return const_cast< Key& >(pair.first); }
282 
287  Val& val() { return pair.second; }
288  };
289 
290  // ===========================================================================
291  // === DOUBLY CHAINED LISTS FOR STORING ELEMENTS IN HASH TABLES ===
292  // ===========================================================================
293 
304  template < typename Key, typename Val, typename Alloc >
306  public:
309  using key_type = Key;
310  using mapped_type = Val;
311  using value_type = std::pair< const Key, Val >;
313  using const_reference = const value_type&;
314  using pointer = value_type*;
315  using const_pointer = const value_type*;
316  using size_type = Size;
317  using allocator_type = Alloc;
320 
322  using BucketAllocator = typename Alloc::template rebind< Bucket >::other;
323 
324  // ============================================================================
326  // ============================================================================
328 
338  HashTableList(BucketAllocator* allocator = nullptr) noexcept;
339 
351  HashTableList(const HashTableList< Key, Val, Alloc >& from);
352 
357  HashTableList(HashTableList< Key, Val, Alloc >&& from) noexcept;
358 
362  ~HashTableList();
363 
365  // ============================================================================
367  // ============================================================================
369 
387  HashTableList< Key, Val, Alloc >&
388  operator=(const HashTableList< Key, Val, Alloc >& from);
389 
407  template < typename OtherAlloc >
408  HashTableList< Key, Val, Alloc >&
409  operator=(const HashTableList< Key, Val, OtherAlloc >& from);
410 
417  HashTableList< Key, Val, Alloc >&
418  operator=(HashTableList< Key, Val, Alloc >&& from) noexcept;
419 
421  // ============================================================================
423  // ============================================================================
425 
434  value_type& at(Size i);
435 
444  const value_type& at(Size i) const;
445 
452  mapped_type& operator[](const key_type& key);
453 
460  const mapped_type& operator[](const key_type& key) const;
461 
469  bool exists(const key_type& key) const;
470 
477  void insert(Bucket* new_elt) noexcept;
478 
483  void erase(Bucket* ptr);
484 
488  void clear();
489 
494  bool empty() const noexcept;
495 
503  Bucket* bucket(const Key& key) const;
504 
509  void setAllocator(BucketAllocator& alloc);
510 
512 
513  private:
516  template < typename K, typename V, typename A >
517  friend class HashTableList;
518  friend class HashTable< Key, Val, Alloc >;
519  friend class HashTableIterator< Key, Val >;
520  friend class HashTableConstIterator< Key, Val >;
521  friend class HashTableIteratorSafe< Key, Val >;
522  friend class HashTableConstIteratorSafe< Key, Val >;
523  friend std::ostream& operator<<<>(std::ostream&,
524  const HashTableList< Key, Val, Alloc >&);
525  friend std::ostream& operator<<<>(std::ostream&,
526  const HashTableList< Key*, Val, Alloc >&);
527  friend std::ostream& operator<<<>(std::ostream&,
528  const HashTable< Key, Val, Alloc >&);
529  friend std::ostream& operator<<<>(std::ostream&,
530  const HashTable< Key*, Val, Alloc >&);
532 
534  HashTableBucket< Key, Val >* __deb_list{nullptr};
535 
537  HashTableBucket< Key, Val >* __end_list{nullptr};
538 
540  Size __nb_elements{Size(0)};
541 
544 
555  template < typename OtherAlloc >
556  void __copy(const HashTableList< Key, Val, OtherAlloc >& from);
557  };
558 
559  // ===========================================================================
560  // === GENERIC HASH TABLES ===
561  // ===========================================================================
676  template < typename Key,
677  typename Val,
678  typename Alloc = std::allocator< std::pair< Key, Val > > >
679  class HashTable {
680  public:
683  using key_type = Key;
684  using mapped_type = Val;
685  using value_type = std::pair< const Key, Val >;
687  using const_reference = const value_type&;
688  using pointer = value_type*;
689  using const_pointer = const value_type*;
690  using size_type = Size;
691  using difference_type = std::ptrdiff_t;
692  using allocator_type = Alloc;
698 
701 
703  using BucketAllocator = typename Alloc::template rebind< Bucket >::other;
704 
705  // ============================================================================
707  // ============================================================================
709 
727  explicit HashTable(
728  Size size_param = HashTableConst::default_size,
729  bool resize_pol = HashTableConst::default_resize_policy,
730  bool key_uniqueness_pol = HashTableConst::default_uniqueness_policy);
731 
736  explicit HashTable(std::initializer_list< std::pair< Key, Val > > list);
737 
751 
764  template < typename OtherAlloc >
766 
772 
776  ~HashTable();
777 
779  // ============================================================================
781  // ============================================================================
783 
794  const iterator& end() noexcept;
795 
808  const const_iterator& end() const noexcept;
809 
822  const const_iterator& cend() const noexcept;
823 
836  iterator begin();
837 
850  const_iterator begin() const;
851 
864  const_iterator cbegin() const;
865 
875  const iterator_safe& endSafe() noexcept;
876 
888  const const_iterator_safe& endSafe() const noexcept;
889 
901  const const_iterator_safe& cendSafe() const noexcept;
902 
914  iterator_safe beginSafe();
915 
927  const_iterator_safe beginSafe() const;
928 
940  const_iterator_safe cbeginSafe() const;
941 
979  static const iterator& end4Statics();
980 
1018  static const const_iterator& constEnd4Statics();
1019 
1057  static const iterator_safe& endSafe4Statics();
1058 
1096  static const const_iterator_safe& constEndSafe4Statics();
1097 
1099  // ============================================================================
1101  // ============================================================================
1103 
1116  HashTable< Key, Val, Alloc >&
1117  operator=(const HashTable< Key, Val, Alloc >& from);
1118 
1131  template < typename OtherAlloc >
1132  HashTable< Key, Val, Alloc >&
1133  operator=(const HashTable< Key, Val, OtherAlloc >& from);
1134 
1141  HashTable< Key, Val, Alloc >& operator=(HashTable< Key, Val, Alloc >&& from);
1142 
1154  Val& operator[](const Key& key);
1155 
1157 
1160  const Val& operator[](const Key& key) const;
1161 
1173  template < typename OtherAlloc >
1174  bool operator==(const HashTable< Key, Val, OtherAlloc >& from) const;
1175 
1177 
1188  template < typename OtherAlloc >
1189  bool operator!=(const HashTable< Key, Val, OtherAlloc >& from) const;
1190 
1192  // ============================================================================
1194  // ============================================================================
1196 
1206  Size capacity() const noexcept;
1207 
1209 
1226  void resize(Size new_size);
1227 
1245  void setResizePolicy(const bool new_policy) noexcept;
1246 
1251  bool resizePolicy() const noexcept;
1252 
1268  void setKeyUniquenessPolicy(const bool new_policy) noexcept;
1269 
1274  bool keyUniquenessPolicy() const noexcept;
1275 
1277  // ============================================================================
1279  // ============================================================================
1281 
1289  Size size() const noexcept;
1290 
1301  bool exists(const Key& key) const;
1302 
1323  value_type& insert(const Key& key, const Val& val);
1324 
1343  value_type& insert(Key&& key, Val&& val);
1344 
1364  value_type& insert(const std::pair< Key, Val >& elt);
1365 
1383  value_type& insert(std::pair< Key, Val >&& elt);
1384 
1401  template < typename... Args >
1402  value_type& emplace(Args&&... args);
1403 
1418  mapped_type& getWithDefault(const Key& key, const Val& default_value);
1419 
1434  mapped_type& getWithDefault(Key&& key, Val&& default_value);
1435 
1447  void set(const Key& key, const Val& default_value);
1448 
1458  void reset(const Key& key);
1459 
1474  void erase(const Key& key);
1475 
1486  void erase(const iterator_safe& iter);
1487 
1498  void erase(const const_iterator_safe& iter);
1499 
1516  void eraseByVal(const Val& val);
1517 
1528  const Key& keyByVal(const Val& val) const;
1529 
1542  const Key& key(const Key& key) const;
1543 
1556  void eraseAllVal(const Val& val);
1557 
1566  void clear();
1567 
1572  bool empty() const noexcept;
1573 
1594  template < typename Mount,
1595  typename OtherAlloc = typename Alloc::template rebind<
1596  std::pair< Key, Mount > >::other >
1597  HashTable< Key, Mount, OtherAlloc > map(
1598  Mount (*f)(Val),
1599  Size size = Size(0),
1600  bool resize_pol = HashTableConst::default_resize_policy,
1601  bool key_uniqueness_pol = HashTableConst::default_uniqueness_policy) const;
1602 
1623  template < typename Mount,
1624  typename OtherAlloc = typename Alloc::template rebind<
1625  std::pair< Key, Mount > >::other >
1626  HashTable< Key, Mount, OtherAlloc > map(
1627  Mount (*f)(Val&),
1628  Size size = Size(0),
1629  bool resize_pol = HashTableConst::default_resize_policy,
1630  bool key_uniqueness_pol = HashTableConst::default_uniqueness_policy) const;
1631 
1652  template < typename Mount,
1653  typename OtherAlloc = typename Alloc::template rebind<
1654  std::pair< Key, Mount > >::other >
1655  HashTable< Key, Mount, OtherAlloc > map(
1656  Mount (*f)(const Val&),
1657  Size size = Size(0),
1658  bool resize_pol = HashTableConst::default_resize_policy,
1659  bool key_uniqueness_pol = HashTableConst::default_uniqueness_policy) const;
1660 
1683  template < typename Mount,
1684  typename OtherAlloc = typename Alloc::template rebind<
1685  std::pair< Key, Mount > >::other >
1686  HashTable< Key, Mount, OtherAlloc > map(
1687  const Mount& val,
1688  Size size = Size(0),
1689  bool resize_pol = HashTableConst::default_resize_policy,
1690  bool key_uniqueness_pol = HashTableConst::default_uniqueness_policy) const;
1691 
1693 
1694  private:
1697  template < typename K, typename V, typename A >
1698  friend class HashTable;
1699  friend class HashTableIterator< Key, Val >;
1700  friend class HashTableConstIterator< Key, Val >;
1701  friend class HashTableIteratorSafe< Key, Val >;
1702  friend class HashTableConstIteratorSafe< Key, Val >;
1703 
1704  friend std::ostream& operator<<<>(std::ostream&,
1705  const HashTable< Key, Val, Alloc >&);
1706  friend std::ostream& operator<<<>(std::ostream& s,
1707  const HashTable< Key*, Val, Alloc >& table);
1708 
1710  template < typename T1, typename T2, typename A >
1711  friend class Bijection;
1713 
1718  std::vector< HashTableList< Key, Val, Alloc > > __nodes;
1719 
1721  Size __size;
1722 
1724  Size __nb_elements{Size(0)};
1725 
1728 
1730  bool __resize_policy{true};
1731 
1733  bool __key_uniqueness_policy{true};
1734 
1749  mutable Size __begin_index{std::numeric_limits< Size >::max()};
1750 
1752  mutable std::vector< HashTableConstIteratorSafe< Key, Val >* >
1754 
1764 
1766  void __erase(HashTableBucket< Key, Val >* bucket, Size index);
1767 
1783  template < typename OtherAlloc >
1784  void __copy(const HashTable< Key, Val, OtherAlloc >& table);
1785 
1790  void __create(Size size);
1791 
1795  void __clearIterators();
1796 
1813  void __insert(Bucket* bucket);
1814  };
1815 
1816 
1817  // ===========================================================================
1818  // === SAFE HASH TABLES CONST ITERATORS ===
1819  // ===========================================================================
1820 
1832  private:
1835 
1838 
1843  static const HashTableIterator< int, int >* end4Statics();
1844 
1849  static const HashTableConstIterator< int, int >* constEnd4Statics();
1850 
1856  static const HashTableIteratorSafe< int, int >* endSafe4Statics();
1857 
1863  static const HashTableConstIteratorSafe< int, int >* constEndSafe4Statics();
1864 
1866  template < typename Key, typename Val, typename Alloc >
1867  friend class HashTable;
1868  };
1869 
1870 
1871  // ===========================================================================
1872  // === SAFE HASH TABLES CONST ITERATORS ===
1873  // ===========================================================================
1917  template < typename Key, typename Val >
1919  public:
1922  using iterator_category = std::forward_iterator_tag;
1923  using key_type = Key;
1924  using mapped_type = Val;
1925  using value_type = std::pair< const Key, Val >;
1927  using const_reference = const value_type&;
1929  using const_pointer = const value_type*;
1930  using difference_type = std::ptrdiff_t;
1932 
1933  // ============================================================================
1935  // ============================================================================
1937 
1942 
1949  template < typename Alloc >
1951 
1953 
1965  template < typename Alloc >
1967  Size ind_elt);
1968 
1974 
1979  explicit HashTableConstIteratorSafe(
1981 
1987 
1991  ~HashTableConstIteratorSafe() noexcept;
1992 
1994  // ============================================================================
1996  // ============================================================================
1998 
2005  const key_type& key() const;
2006 
2008 
2014  const mapped_type& val() const;
2015 
2023  void clear() noexcept;
2024 
2026  // ============================================================================
2028  // ============================================================================
2030 
2036  HashTableConstIteratorSafe< Key, Val >&
2037  operator=(const HashTableConstIteratorSafe< Key, Val >& from);
2038 
2044  HashTableConstIteratorSafe< Key, Val >&
2045  operator=(const HashTableConstIterator< Key, Val >& from);
2046 
2052  HashTableConstIteratorSafe< Key, Val >&
2053  operator=(HashTableConstIteratorSafe< Key, Val >&& from) noexcept;
2054 
2070  HashTableConstIteratorSafe< Key, Val >& operator++() noexcept;
2071 
2078  HashTableConstIteratorSafe< Key, Val >& operator+=(Size i) noexcept;
2079 
2087  HashTableConstIteratorSafe< Key, Val > operator+(Size i) const;
2088 
2094  bool operator!=(const HashTableConstIteratorSafe< Key, Val >& from) const
2095  noexcept;
2096 
2102  bool operator==(const HashTableConstIteratorSafe< Key, Val >& from) const
2103  noexcept;
2104 
2111  const value_type& operator*() const;
2112 
2114 
2115  protected:
2122  template < typename K, typename V, typename A >
2123  friend class HashTable;
2124 
2126  const HashTable< Key, Val >* __table{nullptr};
2127 
2132  Size __index{Size(0)};
2133 
2135  HashTableBucket< Key, Val >* __bucket{nullptr};
2136 
2145  HashTableBucket< Key, Val >* __next_bucket{nullptr};
2146 
2148  HashTableBucket< Key, Val >* __getBucket() const noexcept;
2149 
2156  Size __getIndex() const noexcept;
2157 
2161  void __removeFromSafeList() const;
2162 
2166  void __insertIntoSafeList() const;
2167  };
2168 
2169  // ===========================================================================
2170  // === HASH TABLES ITERATORS ===
2171  // ===========================================================================
2172 
2219  template < typename Key, typename Val >
2221  public:
2224  using iterator_category = std::forward_iterator_tag;
2225  using key_type = Key;
2226  using mapped_type = Val;
2227  using value_type = std::pair< const Key, Val >;
2229  using const_reference = const value_type&;
2231  using const_pointer = const value_type*;
2232  using difference_type = std::ptrdiff_t;
2234 
2235  // ============================================================================
2237  // ============================================================================
2239 
2244 
2250  template < typename Alloc >
2252 
2265  template < typename Alloc >
2267 
2274 
2281 
2288 
2292  ~HashTableIteratorSafe() noexcept;
2293 
2295  // ============================================================================
2297  // ============================================================================
2299 
2302  using HashTableConstIteratorSafe< Key, Val >::key;
2303  using HashTableConstIteratorSafe< Key, Val >::val;
2304  using HashTableConstIteratorSafe< Key, Val >::clear;
2306 
2313  mapped_type& val();
2314 
2316  // ============================================================================
2318  // ============================================================================
2320 
2326  HashTableIteratorSafe< Key, Val >&
2327  operator=(const HashTableIteratorSafe< Key, Val >& from);
2328 
2334  HashTableIteratorSafe< Key, Val >&
2335  operator=(const HashTableIterator< Key, Val >& from);
2336 
2342  HashTableIteratorSafe< Key, Val >&
2343  operator=(HashTableIteratorSafe< Key, Val >&& from) noexcept;
2344 
2359  HashTableIteratorSafe< Key, Val >& operator++() noexcept;
2360 
2366  HashTableIteratorSafe< Key, Val >& operator+=(Size i) noexcept;
2367 
2374  HashTableIteratorSafe< Key, Val > operator+(Size i) const;
2375 
2382  bool operator!=(const HashTableIteratorSafe< Key, Val >& from) const noexcept;
2383 
2390  bool operator==(const HashTableIteratorSafe< Key, Val >& from) const noexcept;
2391 
2398  value_type& operator*();
2399 
2407  const value_type& operator*() const;
2408 
2410  };
2411 
2412  // ===========================================================================
2413  // === UNSAFE HASH TABLES CONST ITERATORS ===
2414  // ===========================================================================
2415 
2464  template < typename Key, typename Val >
2466  public:
2469  using iterator_category = std::forward_iterator_tag;
2470  using key_type = Key;
2471  using mapped_type = Val;
2472  using value_type = std::pair< const Key, Val >;
2474  using const_reference = const value_type&;
2476  using const_pointer = const value_type*;
2477  using difference_type = std::ptrdiff_t;
2479 
2480  // ============================================================================
2482  // ============================================================================
2484 
2488  HashTableConstIterator() noexcept;
2489 
2496  template < typename Alloc >
2497  HashTableConstIterator(const HashTable< Key, Val, Alloc >& tab) noexcept;
2498 
2510  template < typename Alloc >
2511  HashTableConstIterator(const HashTable< Key, Val, Alloc >& tab, Size ind_elt);
2512 
2517  HashTableConstIterator(
2518  const HashTableConstIterator< Key, Val >& from) noexcept;
2519 
2524  HashTableConstIterator(HashTableConstIterator< Key, Val >&& from) noexcept;
2525 
2529  ~HashTableConstIterator() noexcept;
2530 
2532  // ============================================================================
2534  // ============================================================================
2536 
2548  const key_type& key() const;
2549 
2559  const mapped_type& val() const;
2560 
2565  void clear() noexcept;
2566 
2568  // ============================================================================
2570  // ============================================================================
2572 
2578  HashTableConstIterator< Key, Val >&
2579  operator=(const HashTableConstIterator< Key, Val >& from) noexcept;
2580 
2586  HashTableConstIterator< Key, Val >&
2587  operator=(HashTableConstIterator< Key, Val >&& from) noexcept;
2588 
2590 
2606  HashTableConstIterator< Key, Val >& operator++() noexcept;
2607 
2613  HashTableConstIterator< Key, Val >& operator+=(Size i) noexcept;
2614 
2622  HashTableConstIterator< Key, Val > operator+(Size i) const noexcept;
2623 
2630  bool operator!=(const HashTableConstIterator< Key, Val >& from) const noexcept;
2631 
2638  bool operator==(const HashTableConstIterator< Key, Val >& from) const noexcept;
2639 
2640 
2650  const value_type& operator*() const;
2651 
2653 
2654  protected:
2665  template < typename K, typename V, typename A >
2666  friend class HashTable;
2667 
2669  friend class HashTableConstIteratorSafe< Key, Val >;
2670 
2672  const HashTable< Key, Val >* __table{nullptr};
2673 
2678  Size __index{Size(0)};
2679 
2681  typename HashTable< Key, Val >::Bucket* __bucket{nullptr};
2682 
2687  typename HashTable< Key, Val >::Bucket* __getBucket() const noexcept;
2688 
2695  Size __getIndex() const noexcept;
2696  };
2697 
2698  // ===========================================================================
2699  // === UNSAFE HASH TABLES ITERATORS ===
2700  // ===========================================================================
2701 
2749  template < typename Key, typename Val >
2750  class HashTableIterator : public HashTableConstIterator< Key, Val > {
2751  public:
2754  using iterator_category = std::forward_iterator_tag;
2755  using key_type = Key;
2756  using mapped_type = Val;
2757  using value_type = std::pair< const Key, Val >;
2759  using const_reference = const value_type&;
2761  using const_pointer = const value_type*;
2762  using difference_type = std::ptrdiff_t;
2764 
2765  // ############################################################################
2767  // ############################################################################
2769 
2773  HashTableIterator() noexcept;
2774 
2781  template < typename Alloc >
2782  HashTableIterator(const HashTable< Key, Val, Alloc >& tab) noexcept;
2783 
2785 
2797  template < typename Alloc >
2798  HashTableIterator(const HashTable< Key, Val, Alloc >& tab, Size ind_elt);
2799 
2804  HashTableIterator(const HashTableIterator< Key, Val >& from) noexcept;
2805 
2810  HashTableIterator(HashTableIterator< Key, Val >&& from) noexcept;
2811 
2815  ~HashTableIterator() noexcept;
2816 
2818  // ============================================================================
2820  // ============================================================================
2822 
2825  using HashTableConstIterator< Key, Val >::key;
2826  using HashTableConstIterator< Key, Val >::val;
2827  using HashTableConstIterator< Key, Val >::clear;
2829 
2839  mapped_type& val();
2840 
2842  // ============================================================================
2844  // ============================================================================
2846 
2852  HashTableIterator< Key, Val >&
2853  operator=(const HashTableIterator< Key, Val >& from) noexcept;
2854 
2860  HashTableIterator< Key, Val >&
2861  operator=(HashTableIterator< Key, Val >&& from) noexcept;
2862 
2879  HashTableIterator< Key, Val >& operator++() noexcept;
2880 
2886  HashTableIterator< Key, Val >& operator+=(Size i) noexcept;
2887 
2893  HashTableIterator< Key, Val > operator+(Size i) const noexcept;
2894 
2901  bool operator!=(const HashTableIterator< Key, Val >& from) const noexcept;
2902 
2909  bool operator==(const HashTableIterator< Key, Val >& from) const noexcept;
2910 
2920  value_type& operator*();
2921 
2931  const value_type& operator*() const;
2932 
2934  };
2935 
2936 } // namespace gum
2937 
2938 
2939 #ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
2940 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
2941 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
2942 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
2943 extern template class gum::HashTable< int, int >;
2944 # endif
2945 # endif
2946 # endif
2947 #endif
2948 #ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
2949 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
2950 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
2951 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
2952 extern template class gum::HashTable< int, std::string >;
2953 # endif
2954 # endif
2955 # endif
2956 #endif
2957 #ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
2958 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
2959 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
2960 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
2961 extern template class gum::HashTable< std::string, std::string >;
2962 # endif
2963 # endif
2964 # endif
2965 #endif
2966 #ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
2967 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
2968 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
2969 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
2970 extern template class gum::HashTable< std::string, int >;
2971 # endif
2972 # endif
2973 # endif
2974 #endif
2975 
2976 
2977 // always include the implementation of the templates
2978 #include <agrum/core/hashTable_tpl.h>
2979 
2980 #endif // GUM_HASHTABLE_H
Key & key()
Returns the key part of the pair.
Definition: hashTable.h:281
Unsafe Const Iterators for hashtablesHashTableConstIterator provides a fast but unsafe way to parse H...
Definition: hashTable.h:2465
HashTableBucket()
Class constructor.
Definition: hashTable.h:221
Val key_type
types for STL compliance
Definition: hashTable.h:309
typename IndexAllocator ::template rebind< Bucket >::other BucketAllocator
The Bucket allocator.
Definition: hashTable.h:703
A recipient for a pair of key value in a gum::HashTableList.
Definition: hashTable.h:202
static constexpr Size default_mean_val_by_slot
The average number of elements admissible by slots.
Definition: hashTable.h:87
BucketAllocator __alloc
The allocator for the buckets.
Definition: hashTable.h:1763
Unsafe Iterators for hashtablesHashTableIterator provides a fast but unsafe way to parse HashTables...
Definition: hashTable.h:2750
HashTableBucket(const std::pair< const Key, Val > &p)
Constructor.
Definition: hashTable.h:247
HashFunc< Key > __hash_func
The function used to hash keys (may change when the table is resized).
Definition: hashTable.h:1727
Emplace
A dummy type for the emplace constructor.
Definition: hashTable.h:216
Safe Const Iterators for hashtables.
Definition: hashTable.h:1918
STL namespace.
static constexpr Size default_size
The default number of slots in hashtables.
Definition: hashTable.h:80
Copyright 2005-2019 Pierre-Henri WUILLEMIN et Christophe GONZALES (LIP6) {prenom.nom}_at_lip6.fr.
static const HashTableIterator< int, int > * __HashTableIterEnd
The unsafe iterator used by everyone.
Definition: hashTable.h:1834
Base class for discrete random variable.
Safe Iterators for hashtables.
Definition: hashTable.h:2220
Copyright 2005-2019 Pierre-Henri WUILLEMIN et Christophe GONZALES (LIP6) {prenom.nom}_at_lip6.fr.
Definition: agrum.h:25
BucketAllocator * __alloc_bucket
The allocator of the containing hashTable.
Definition: hashTable.h:543
std::vector< HashTableConstIteratorSafe< Key, Val > *> __safe_iterators
The list of safe iterators pointing to the hash table.
Definition: hashTable.h:1753
The class for generic Hash Tables.
Definition: hashTable.h:679
std::pair< const Val, Size > value_type
Definition: hashTable.h:311
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:586
static const HashTableIteratorSafe< int, int > * __HashTableIterEndSafe
The safe iterator used by everyone.
Definition: hashTable.h:1837
Copyright 2005-2019 Pierre-Henri WUILLEMIN et Christophe GONZALES (LIP6) {prenom.nom}_at_lip6.fr.
Val key_type
Types for STL compliance.
Definition: hashTable.h:683
HashTableBucket(std::pair< const Key, Val > &&p)
Constructor.
Definition: hashTable.h:253
std::pair< const const gum::DiscreteVariable *, Idx > value_type
Definition: hashTable.h:1925
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:94
std::pair< const Key, Val > pair
The pair stored in this bucket.
Definition: hashTable.h:204
Parameters specifying the default behavior of the hashtables.
Definition: hashTable.h:73
std::forward_iterator_tag iterator_category
Types for STL compliance.
Definition: hashTable.h:2469
Set of pairs of elements with fast search for both elements.
Definition: bijection.h:1805
std::forward_iterator_tag iterator_category
Types for STL compliance.
Definition: hashTable.h:1922
HashTableBucket(Emplace e, Args &&... args)
The emplace constructor.
Definition: hashTable.h:262
A class used to create the static iterator used by HashTables.
Definition: hashTable.h:1831
HashTableBucket(const Key &k, const Val &v)
Constructor.
Definition: hashTable.h:234
Val & val()
Returns the value part of the pair.
Definition: hashTable.h:287
std::pair< const Val, Size > value_type
Definition: hashTable.h:685
std::pair< const Key, bool > value_type
Definition: hashTable.h:2472
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:102
~HashTableBucket()
Class destructor.
Definition: hashTable.h:269
A chained list used by gum::HashTable.
Definition: hashTable.h:305
HashTableBucket(Key &&k, Val &&v)
Constructor.
Definition: hashTable.h:241
std::size_t Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:48
typename IndexAllocator ::template rebind< Bucket >::other BucketAllocator
The Bucket allocator.
Definition: hashTable.h:322
HashTableBucket(const HashTableBucket< Key, Val > &from)
Copy constructor.
Definition: hashTable.h:227
std::pair< const Key, Val > & elt()
Returns the pair stored in this bucket.
Definition: hashTable.h:275