1 /** 2 * 3 * Copyright (c) 2005-2021 by Pierre-Henri WUILLEMIN(_at_LIP6) & Christophe GONZALES(_at_AMU) 4 * info_at_agrum_dot_org 5 * 6 * This library is free software: you can redistribute it and/or modify 7 * it under the terms of the GNU Lesser General Public License as published by 8 * the Free Software Foundation, either version 3 of the License, or 9 * (at your option) 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 Lesser General Public License for more details. 15 * 16 * You should have received a copy of the GNU Lesser General Public License 17 * along with this library. If not, see <http://www.gnu.org/licenses/>. 18 * 19 */ 20 21 22 /** 23 * @file 24 * @brief Class hash tables iterators 25 * 26 * @author Christophe GONZALES(_at_AMU) and Pierre-Henri WUILLEMIN(_at_LIP6) 27 */ 28 29 #ifndef GUM_HASHTABLE_H 30 #define GUM_HASHTABLE_H 31 32 #include <limits> 33 34 #include <cstddef> 35 #include <initializer_list> 36 #include <iostream> 37 #include <string> 38 #include <utility> 39 #include <vector> 40 41 #include <agrum/agrum.h> 42 #include <agrum/tools/core/hashFunc.h> 43 44 namespace gum { 45 46 #ifndef DOXYGEN_SHOULD_SKIP_THIS 47 48 // the templates used by this file 49 template < typename Key, typename Val, typename Alloc > 50 class HashTable; 51 template < typename Key, typename Val, typename Alloc > 52 class HashTableList; 53 template < typename Key, typename Val > 54 class HashTableIterator; 55 template < typename Key, typename Val > 56 class HashTableConstIterator; 57 template < typename Key, typename Val > 58 class HashTableIteratorSafe; 59 template < typename Key, typename Val > 60 class HashTableConstIteratorSafe; 61 template < typename T1, typename T2, typename Alloc > 62 class Bijection; 63 64 #endif /* DOXYGEN_SHOULD_SKIP_THIS */ 65 66 /** 67 * @class HashTableConst 68 * @headerfile hashTable.h <agrum/tools/core/hashTable.h> 69 * @brief Parameters specifying the default behavior of the hashtables. 70 * @ingroup hashtable_group 71 */ 72 struct HashTableConst { 73 /** 74 * The default number of slots in hashtables. By default, hashtables can 75 * store up to thrice the number of slots elements before their size is 76 * increased To each slot corresponds a chained list of elements with the 77 * same hashed key. 78 */ 79 static constexpr Size default_size{Size(4)}; 80 81 /** 82 * The average number of elements admissible by slots. Once this number is 83 * reached, the size of the hashtable is automatically doubled if we are in 84 * automatic resize mode. 85 */ 86 static constexpr Size default_mean_val_by_slot{Size(3)}; 87 88 /** 89 * A Boolean indicating whether inserting too many values into the 90 * hashtable makes it resize itself automatically. true = automatic, false 91 * = manual. 92 */ 93 static constexpr bool default_resize_policy{true}; 94 95 /** 96 * A Boolean indicating the default behavior when trying to insert more 97 * than once elements with identical keys. true = do not insert the 98 * elements but the first one and throw an exception after the first 99 * insertion; false = insert the elements without complaining. 100 */ 101 static constexpr bool default_uniqueness_policy{true}; 102 }; 103 104 // Doxygen raises warning with the following comment bloc 105 // @brief Prints the content of a gum::HashTableList in the stream. 106 // @ingroup hashtable_group 107 // @param s The s used to print the gum::HashTableList. 108 // @param list The gum::HashTableList to print. 109 // @return Returns the std::ostream s. 110 // @tparam Key The type of keys in the gum::HashTableList. 111 // @tparam Val The type of values in the gum::HashTableList. 112 // @tparam Alloc The gum::HashTableList allocator. 113 114 /** 115 * @brief Prints the content of a gum::HashTableList in the stream. 116 * @ingroup hashtable_group 117 */ 118 template < typename Key, typename Val, typename Alloc > 119 std::ostream& operator<<(std::ostream& s, const HashTableList< Key, Val, Alloc >& list); 120 121 // Doxygen raises warning with the following comment bloc 122 // @brief Prints the content of a gum::HashTableList with pointers key in the 123 // stream. 124 // @ingroup hashtable_group 125 // @param s The s used to print the gum::HashTableList. 126 // @param list The gum::HashTableList to print. 127 // @return Returns the std::ostream s. 128 // @tparam Key The type of keys in the gum::HashTableList. 129 // @tparam Val The type of values in the gum::HashTableList. 130 // @tparam Alloc The gum::HashTableList allocator. 131 // 132 133 /** 134 * @brief Prints the content of a gum::HashTableList with pointers key in 135 * the stream. 136 * @ingroup hashtable_group 137 */ 138 template < typename Key, typename Val, typename Alloc > 139 std::ostream& operator<<(std::ostream& s, const HashTableList< Key*, Val, Alloc >& list); 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 151 /** 152 * @brief Prints the content of a gum::HashTable in the stream. 153 * @ingroup hashtable_group 154 */ 155 template < typename Key, typename Val, typename Alloc > 156 std::ostream& operator<<(std::ostream& s, const HashTable< Key, Val, Alloc >& table); 157 158 // Doxygen raises warning with the following comment bloc 159 // @brief Prints the content of a gum::HashTable with pointers key in the 160 // stream. 161 // @ingroup hashtable_group 162 // @param s The stream used to print the gum::HashTable. 163 // @param table The gum::HashTable to print. 164 // @return Returns the std::ostream s. 165 // @tparam Key The type of keys in the gum::HashTable. 166 // @tparam Val The type of values in the gum::HashTable. 167 // @tparam Alloc The gum::HashTable allocator. 168 169 /** 170 * @brief Prints the content of a gum::HashTable with pointers key in the 171 * stream. 172 * @ingroup hashtable_group 173 */ 174 template < typename Key, typename Val, typename Alloc > 175 std::ostream& operator<<(std::ostream& s, const HashTable< Key*, Val, Alloc >& table); 176 177 // =========================================================================== 178 // === LISTS SPECIFIC FOR SAVING ELEMENTS IN HASHTABLES === 179 // =========================================================================== 180 181 /** 182 * @class HashTableBucket 183 * @headerfile hashTable.h <agrum/tools/core/hashTable.h> 184 * @brief A recipient for a pair of key value in a gum::HashTableList. 185 * @ingroup hashtable_group 186 * 187 * In aGrUM, hashtables are vectors of chained lists. Each list corresponds 188 * to the pairs (key,val) the keys of which have the same hashed value. Each 189 * box of the list is called a bucket. Lists are doubly linked so as to 190 * enable efficient begin/end iterators and efficient insert/erase 191 * operations. 192 * 193 * @tparam Key The type for keys in a gum::HashTable. 194 * @tparam Val The type for values in a gum::HashTable. 195 */ 196 template < typename Key, typename Val > 197 struct HashTableBucket { 198 /// The pair stored in this bucket. 199 std::pair< const Key, Val > pair; 200 201 /// A pointer toward the previous bucket in the gum::HashTableList. 202 HashTableBucket< Key, Val >* prev{nullptr}; 203 204 /// A pointer toward the next bucket in the gum::HashTableList. 205 HashTableBucket< Key, Val >* next{nullptr}; 206 207 /** 208 * @brief A dummy type for the emplace constructor. 209 * This type is used to prevent the Bucket emplace (int,...) to compile. 210 */ 211 enum class Emplace 212 { 213 EMPLACE 214 }; 215 216 /** 217 * Class constructor. 218 */ HashTableBucketHashTableBucket219 HashTableBucket() {} 220 221 /** 222 * Copy constructor. 223 * @param from The gum::HashTableBucket to copy. 224 */ HashTableBucketHashTableBucket225 HashTableBucket(const HashTableBucket< Key, Val >& from) : pair{from.pair} {} 226 227 /** 228 * Constructor. 229 * @param k The key part of the pair. 230 * @param v The value part of the pair. 231 */ HashTableBucketHashTableBucket232 HashTableBucket(const Key& k, const Val& v) : pair{k, v} {} 233 234 /** 235 * Constructor. 236 * @param k The key part of the pair. 237 * @param v The value part of the pair. 238 */ HashTableBucketHashTableBucket239 HashTableBucket(Key&& k, Val&& v) : pair{std::move(k), std::move(v)} {} 240 241 /** 242 * Constructor. 243 * @param p The pair to store. 244 */ HashTableBucketHashTableBucket245 HashTableBucket(const std::pair< const Key, Val >& p) : pair(p) {} 246 247 /** 248 * Constructor. 249 * @param p The pair to store. 250 */ HashTableBucketHashTableBucket251 HashTableBucket(std::pair< const Key, Val >&& p) : pair(std::move(p)) {} 252 253 /** 254 * The emplace constructor. 255 * @param e The emplace. 256 * @param args A construction list. 257 * @tparam args The types in the construction list. 258 */ 259 template < typename... Args > HashTableBucketHashTableBucket260 HashTableBucket(Emplace e, Args&&... args) : 261 // emplace (universal) constructor 262 pair(std::forward< Args >(args)...) {} 263 264 /** 265 * Class destructor. 266 */ ~HashTableBucketHashTableBucket267 ~HashTableBucket() {} 268 269 /** 270 * @brief Returns the pair stored in this bucket. 271 * @return Returns the pair stored in this bucket. 272 */ eltHashTableBucket273 std::pair< const Key, Val >& elt() { return pair; } 274 275 /** 276 * @brief Returns the key part of the pair. 277 * @return Returns the key part of the pair. 278 */ keyHashTableBucket279 Key& key() { return const_cast< Key& >(pair.first); } 280 281 /** 282 * @brief Returns the value part of the pair. 283 * @return Returns value key part of the pair. 284 */ valHashTableBucket285 Val& val() { return pair.second; } 286 }; 287 288 // =========================================================================== 289 // === DOUBLY CHAINED LISTS FOR STORING ELEMENTS IN HASH TABLES === 290 // =========================================================================== 291 292 /** 293 * @class HashTableList 294 * @headerfile hashTable.h <agrum/tools/core/hashTable.h> 295 * @brief A chained list used by gum::HashTable. 296 * @ingroup hashtable_group 297 * 298 * @tparam Key The type for keys in a gum::HashTable. 299 * @tparam Val The type for values in a gum::HashTable. 300 * @tparam Alloc The gum::HashTable allocator. 301 */ 302 template < typename Key, typename Val, typename Alloc > 303 class HashTableList { 304 public: 305 /// types for STL compliance 306 /// @{ 307 using key_type = Key; 308 using mapped_type = Val; 309 using value_type = std::pair< const Key, Val >; 310 using reference = value_type&; 311 using const_reference = const value_type&; 312 using pointer = value_type*; 313 using const_pointer = const value_type*; 314 using size_type = Size; 315 using allocator_type = Alloc; 316 using Bucket = HashTableBucket< Key, Val >; 317 /// @} 318 319 /// The Bucket allocator. 320 using BucketAllocator = typename Alloc::template rebind< Bucket >::other; 321 322 // ============================================================================ 323 /// @name Constructors / Destructors 324 // ============================================================================ 325 /// @{ 326 327 /** 328 * @brief Basic constructor that creates an empty list. 329 * 330 * This is what is used basically by gum::HashTable. 331 * 332 * @warning If the allocator is not passed in argument, do not forget to 333 * use method setAllocator after the creation. 334 * @param allocator The gum::HashTableBucket allocator. 335 */ 336 HashTableList(BucketAllocator* allocator = nullptr) noexcept; 337 338 /** 339 * @brief Copy constructor. 340 * 341 * The new list and that which is copied do not share elements: the new 342 * list contains new instances of the keys and values stored in the copied 343 * list. Of course, if these values are pointers, the new values point 344 * toward the same elements. 345 * 346 * @warning Both from and this will share the same allocator. 347 * @param from The gum::HashTableList to copy. 348 */ 349 HashTableList(const HashTableList< Key, Val, Alloc >& from); 350 351 /** 352 * @brief Move constructor. 353 * @param from The gum::HashTableList to move. 354 */ 355 HashTableList(HashTableList< Key, Val, Alloc >&& from) noexcept; 356 357 /** 358 * @brief Class destructor. 359 */ 360 ~HashTableList(); 361 362 /// @} 363 // ============================================================================ 364 /// @name Operators 365 // ============================================================================ 366 /// @{ 367 368 /** 369 * @brief Assignment operator. 370 * 371 * The new list and that which is copied do not share elements: the new 372 * list contains new instances of the keys and values stored in the copied 373 * list. Of course, if these values are pointers, the new values point 374 * toward the same elements. 375 * 376 * If some allocation problem occurs or if copying the Val elements cannot 377 * be performed properly, exceptions may be raised. In this case, the 378 * function guarantees that no memory leak occurs and that the list is kept 379 * in a coherent state (that of an empty list). 380 * 381 * @warning operator= does not change the current allocator of *this 382 * @param from The gum::HashTableList to copy. 383 * @return Returns this gum::HashTableList. 384 */ 385 HashTableList< Key, Val, Alloc >& operator=(const HashTableList< Key, Val, Alloc >& from); 386 387 /** 388 * @brief Generalized assignment operator. 389 * 390 * The new list and that which is copied do not share elements: the new 391 * list contains new instances of the keys and values stored in the copied 392 * list. Of course, if these values are pointers, the new values point 393 * toward the same elements. 394 * 395 * If some allocation problem occurs or if copying the Val elements cannot 396 * be performed properly, exceptions may be raised. In this case, the 397 * function guarantees that no memory leak occurs and that the list is kept 398 * in a coherent state (that of an empty list). 399 * 400 * @warning operator= does not change the current allocator of *this 401 * @param from The gum::HashTableList to copy. 402 * @return Returns this gum::HashTableList. 403 */ 404 template < typename OtherAlloc > 405 HashTableList< Key, Val, Alloc >& operator=(const HashTableList< Key, Val, OtherAlloc >& from); 406 407 /** 408 * @brief Move operator. 409 * @warning operator= does not change the current allocator of *this 410 * @param from The gum::HashTableList to copy. 411 * @return Returns this gum::HashTableList. 412 */ 413 HashTableList< Key, Val, Alloc >& operator=(HashTableList< Key, Val, Alloc >&& from) noexcept; 414 415 /// @} 416 // ============================================================================ 417 /// @name Accessors / Modifiers 418 // ============================================================================ 419 /// @{ 420 421 /** 422 * @brief Function at returns the ith element in the current chained list. 423 * 424 * The first element has index 0. 425 * @param i The index to look up. 426 * @return Returns the value at index i. 427 * @throw NotFound Raised if the list has fewer than i elements. 428 */ 429 value_type& at(Size i); 430 431 /** 432 * @brief Function at returns the ith element in the current chained list. 433 * 434 * The first element has index 0. 435 * @param i The index to look up. 436 * @return Returns the value at index i. 437 * @throw NotFound Raised if the list has fewer than i elements. 438 */ 439 const value_type& at(Size i) const; 440 441 /** 442 * @brief Returns the value corresponding to a given key. 443 * @param key The key for which a value is returned. 444 * @return Returns the value corresponding to a given key. 445 * @throw NotFound is raised if the element cannot be found 446 */ 447 mapped_type& operator[](const key_type& key); 448 449 /** 450 * @brief Returns the value corresponding to a given key. 451 * @param key The key for which a value is returned. 452 * @return Returns the value corresponding to a given key. 453 * @throw NotFound is raised if the element cannot be found 454 */ 455 const mapped_type& operator[](const key_type& key) const; 456 457 /** 458 * @brief Returns true if a value with the given key exists. 459 * 460 * Checks whether there exists an element with a given key in the list. 461 * @param key The key to test for existence. 462 * @return Returns true if a value with the given key exists. 463 */ 464 bool exists(const key_type& key) const; 465 466 /** 467 * @brief Inserts a new element in the chained list. 468 * 469 * The element is inserted at the beginning of the list. 470 * @param new_elt The element to add in the gum::HashTableList. 471 */ 472 void insert(Bucket* new_elt) noexcept; 473 474 /** 475 * @brief Removes an element from this chained list. 476 * @param ptr The element to remove. 477 */ 478 void erase(Bucket* ptr); 479 480 /** 481 * @brief Removes all the elements of this chained list. 482 */ 483 void clear(); 484 485 /** 486 * @brief Returns true if this chained list is empty. 487 * @return Returns true if this chained list is empty. 488 */ 489 bool empty() const noexcept; 490 491 /** 492 * @brief A method to get the bucket corresponding to a given key. 493 * 494 * This enables efficient removals of buckets. 495 * @param key The key of the bucket to return. 496 * @return Returns the buckket matching key. 497 */ 498 Bucket* bucket(const Key& key) const; 499 500 /** 501 * @brief Sets a new allocator. 502 * @param alloc The new allocator. 503 */ 504 void setAllocator(BucketAllocator& alloc); 505 506 /// @} 507 508 private: 509 /// Friend for faster access. 510 /// @{ 511 template < typename K, typename V, typename A > 512 friend class HashTableList; 513 friend class HashTable< Key, Val, Alloc >; 514 friend class HashTableIterator< Key, Val >; 515 friend class HashTableConstIterator< Key, Val >; 516 friend class HashTableIteratorSafe< Key, Val >; 517 friend class HashTableConstIteratorSafe< Key, Val >; 518 friend std::ostream& operator<<<>(std::ostream&, const HashTableList< Key, Val, Alloc >&); 519 friend std::ostream& operator<<<>(std::ostream&, const HashTableList< Key*, Val, Alloc >&); 520 friend std::ostream& operator<<<>(std::ostream&, const HashTable< Key, Val, Alloc >&); 521 friend std::ostream& operator<<<>(std::ostream&, const HashTable< Key*, Val, Alloc >&); 522 /// @} 523 524 /// A pointer on the first element of the chained list. 525 HashTableBucket< Key, Val >* _deb_list_{nullptr}; 526 527 /// A pointer on the last element of the chained list. 528 HashTableBucket< Key, Val >* _end_list_{nullptr}; 529 530 /// The number of elements in the chained list. 531 Size _nb_elements_{Size(0)}; 532 533 /// The allocator of the containing hashTable. 534 mutable BucketAllocator* _alloc_bucket_; 535 536 /** 537 * @brief A function used to perform copies of HashTableLists. 538 * 539 * This code is shared by the copy constructor and the copy operator. If it 540 * cannot perform the necessary allocations, no memory leak occurs and the 541 * list is set to the empty list. 542 * 543 * @param from The gum::HashTableList to copy. 544 * @tparam OtherAlloc The other gum::HashTableList allocator. 545 */ 546 template < typename OtherAlloc > 547 void _copy_(const HashTableList< Key, Val, OtherAlloc >& from); 548 }; 549 550 // =========================================================================== 551 // === GENERIC HASH TABLES === 552 // =========================================================================== 553 /** 554 * @class HashTable 555 * @headerfile hashTable.h <agrum/tools/core/hashTable.h> 556 * @brief The class for generic Hash Tables. 557 * @ingroup basicstruct_group 558 * @ingroup hashtable_group 559 * 560 * In aGrUM, a hashtable is a vector of chained lists (collision problems are 561 * fixed by chaining). Each slot of the vector contains a list of elements 562 * sharing the same hashed value. To be computationally efficient, the hash 563 * table should not contain too many elements as compared to its number of 564 * slots. Therefore, it is sometimes useful to resize the chained lists 565 * vector. aGrUM's hash tables are designed to automatically double their 566 * size when there is in average more than 3 elements per slot. However, when 567 * memory consumption is a concern, this feature can be turned off either by 568 * passing false as an optional resize_pol argument to the constructor of the 569 * hash table or by using method setResizePolicy when the instance of the 570 * class has already been constructed. Similarly, the default number of 571 * slots of the hash table may be parameterized as an optional argument of 572 * the constructor (size_param). Beware: when inserting elements of a given 573 * class into a hash table, unless the element is an r-value, only a copy of 574 * this element is stored into the table (this is compulsory if the hashtable 575 * is to be generic and can be used to store both complex classes and 576 * built-in types like integers). HashTable have different kinds of 577 * iterators: HashTableIteratorSafe and HashTableConstIteratorSafe (a.k.a. 578 * HashTable<>::iterator_safe and HashTable<>::const_iterator_safe) allow 579 * safe parsing of the hash tables. By safe, we mean that whenever the 580 * element pointed to by such an iterator is removed from the hashtable, 581 * accessing it through the iterator (*iter) does not result in a 582 * segmentation fault but rather in an exception being thrown. This safety is 583 * ensured at a very low cost (actually, our experiments show that our 584 * HashTables and HashTable's safe iterators significantly outperform the 585 * standard library unordered_maps). Of course, if there is no possibility 586 * for an iterator to point to a deleted element, the user can use "unsafe" 587 * iterators HashTableIterator and HashTableConstIterator (a.k.a. 588 * HashTable<>::iterator and HashTable<>::const_iterator). These iterators 589 * are slightly faster than their safe counterparts. However, as in the 590 * standard library, accessing through them a deleted element usually results 591 * in a mess (most probably a segfault). 592 * 593 * @warning HashTables @b guarantee that any element stored within them will 594 * have the @b same @b location in memory until it is removed from the 595 * hashtable (and this holds whatever operation is performed on the hashtable 596 * like new insertions, deletions, resizing, etc.). 597 * 598 * @par Usage example: 599 * @code 600 * // creation of an empty hash table 601 * HashTable<int,string> table1; 602 * 603 * // insert two elements into the hash table 604 * table1.insert (10,"xxx"); 605 * table1.insert (20,"yyy"); 606 * table1.emplace (30,"zzz"); 607 * 608 * // creation of a nonempty hashtable using initializer lists 609 * HashTable<int,bool> table { std::make_pair(3,true), std::make_pair(2,false) 610 * }; 611 * 612 * // display the content of the hash table 613 * cerr << table1; 614 * 615 * // get the number of elements stored into the hash table 616 * cerr << "number of elements in table1 = " << table1.size () << endl; 617 * 618 * // create two copies of the hash table 619 * HashTable<int,string> table2, table3 = table1; 620 * table2 = table3; 621 * 622 * // get the element whose key is 10 623 * cerr << table1[10] << " = xxx" << endl; 624 * 625 * // check whether there exists an element with key 20 626 * if (table1.exists (20)) cerr << "element found" << endl; 627 * 628 * // transform the hashtable of string into a hashtable of int assuming f is 629 * // defined as: int f (const string& str) { return str.size (); } 630 * HashTable<int,int> table = table1.map (f); 631 * 632 * // remove two elements from table1 and table2 633 * table1.erase (10); // key = 10 634 * table1.eraseByVal ("yyy"); // val = "yyy" 635 * table2.clear (); 636 * 637 * // check whether the hash table is empty 638 * if (!table1.empty ()) cerr << "table not empty" << endl; 639 * 640 * // check whether hashtables contain the same elements 641 * if ((table1 == table2) && (table1 != table3)) 642 * cerr << "check for equality/inequality" << endl; 643 * 644 * // parse the content of a hashtable using an unsafe iterator 645 * for (HashTable<int,string>::const_iterator iter = table1.cbegin(); 646 * iter != table1.cend(); ++iter) 647 * cerr << *iter; 648 * HashTable<int,string>::iterator iter = table1.begin(); 649 * iter += 2; 650 * cerr << iter.key () << " " << iter.val (); 651 * 652 * // use an iterator to point the element we wish to erase 653 * HashTable<int,string>::iterator_safe iterS = table1.beginSafe (); 654 * table1.erase ( table1.beginSafe () + 4 ); 655 * table1.erase ( iterS ); // this is safe because the iterator is safe 656 * 657 * // check for iterator's safety 658 * for (HashTable<int,string>::iterator_safe iter = table1.beginSafe (); 659 * iter != table1.endSafe (); ++iter ) 660 * table1.eraseByVal ( *iter ); 661 * @endcode 662 * 663 * @tparam Key The type for keys in a gum::HashTable. 664 * @tparam Val The type for values in a gum::HashTable. 665 * @tparam Alloc The gum::HashTable allocator. 666 */ 667 template < typename Key, typename Val, typename Alloc = std::allocator< std::pair< Key, Val > > > 668 class HashTable { 669 public: 670 /// Types for STL compliance. 671 /// @{ 672 using key_type = Key; 673 using mapped_type = Val; 674 using value_type = std::pair< const Key, Val >; 675 using reference = value_type&; 676 using const_reference = const value_type&; 677 using pointer = value_type*; 678 using const_pointer = const value_type*; 679 using size_type = Size; 680 using difference_type = std::ptrdiff_t; 681 using allocator_type = Alloc; 682 using iterator = HashTableIterator< Key, Val >; 683 using const_iterator = HashTableConstIterator< Key, Val >; 684 using iterator_safe = HashTableIteratorSafe< Key, Val >; 685 using const_iterator_safe = HashTableConstIteratorSafe< Key, Val >; 686 /// @} 687 688 /// The buckets where data are stored. 689 using Bucket = HashTableBucket< Key, Val >; 690 691 /// The Bucket allocator. 692 using BucketAllocator = typename Alloc::template rebind< Bucket >::other; 693 694 // ============================================================================ 695 /// @name Constructors / Destructors 696 // ============================================================================ 697 /// @{ 698 699 /** 700 * @brief Default constructor. 701 * 702 * The true capacity (vector's size) of the hashtable will be the lowest 703 * number greater than or equal to size_param that is also a power of 2. 704 * The second optional argument is the resizing policy. By default, each 705 * time there is an average of 3 elements by node, the size of the 706 * hashtable is automatically multiplied by 2. But the user may pass false 707 * as argument to resize_pol to disable this feature. 708 * 709 * @param size_param The initial size of the gum::HashTable. 710 * @param resize_pol The policy for resizing the hashtable when new 711 * elements are added (possible values: true = automatic resize and false = 712 * manual resize). 713 * @param key_uniqueness_pol Uniqueness policy : should we prevent inserting 714 * the same key more than once in the table? 715 */ 716 explicit HashTable(Size size_param = HashTableConst::default_size, 717 bool resize_pol = HashTableConst::default_resize_policy, 718 bool key_uniqueness_pol = HashTableConst::default_uniqueness_policy); 719 720 /** 721 * @brief Initializer list constructor. 722 * @param list The initialized list. 723 */ 724 explicit HashTable(std::initializer_list< std::pair< Key, Val > > list); 725 726 /** 727 * @brief Copy constructor. 728 * 729 * This creates a new hashtable the content of which is similar to that of 730 * the table passed in argument. Beware: similar does not mean that both 731 * tables share the same objects, but rather that the objects stored in the 732 * newly created table are copies of those of the table passed in argument. 733 * In particular, the new hash table inherits the parameters (resize 734 * policy, uniqueness policy) of table 'from'. 735 * 736 * @param from The gum::HashTable to copy. 737 */ 738 HashTable(const HashTable< Key, Val, Alloc >& from); 739 740 /** 741 * @brief Generalized copy constructor. 742 * 743 * This creates a new hashtable the content of which is similar to that of 744 * the table passed in argument. Beware: similar does not mean that both 745 * tables share the same objects, but rather that the objects stored in the 746 * newly created table are copies of those of the table passed in argument. 747 * In particular, the new hash table inherits the parameters (resize 748 * policy, uniqueness policy) of table 'table' 749 * 750 * @param from The gum::HashTable to copy. 751 */ 752 template < typename OtherAlloc > 753 HashTable(const HashTable< Key, Val, OtherAlloc >& from); 754 755 /** 756 * @brief Move constructor. 757 * @param from The gum::HashTable to move. 758 */ 759 HashTable(HashTable< Key, Val, Alloc >&& from); 760 761 /** 762 * @brief Class destructor. 763 */ 764 ~HashTable(); 765 766 /// @} 767 // ============================================================================ 768 /// @name Iterators 769 // ============================================================================ 770 /// @{ 771 772 /** 773 * @brief Returns the unsafe iterator pointing to the end of the hashtable. 774 * 775 * Unsafe iterators are slightly faster than safe iterators. However, BE 776 * CAREFUL when using them: they should ONLY be used when you have the 777 * guarantee that they will never point to a deleted element. If unsure, 778 * prefer using the safe iterators (those are only slightly slower). 779 * 780 * @return Returns the unsafe iterator pointing to the end of the hashtable. 781 */ 782 const iterator& end() noexcept; 783 784 /** 785 * @brief Returns the unsafe const_iterator pointing to the end of the 786 * hashtable. 787 * 788 * Unsafe iterators are slightly faster than safe iterators. However, BE 789 * CAREFUL when using them: they should ONLY be used when you have the 790 * guarantee that they will never point to a deleted element. If unsure, 791 * prefer using the safe iterators (those are only slightly slower). 792 * 793 * @return Returns the unsafe const_iterator pointing to the end of the 794 * hashtable. 795 */ 796 const const_iterator& end() const noexcept; 797 798 /** 799 * @brief Returns the unsafe const_iterator pointing to the end of the 800 * hashtable. 801 * 802 * Unsafe iterators are slightly faster than safe iterators. However, 803 * BE CAREFUL when using them: they should ONLY be used when you have the 804 * guarantee that they will never point to a deleted element. If unsure, 805 * prefer using the safe iterators (those are only slightly slower). 806 * 807 * @return Returns the unsafe const_iterator pointing to the end of the 808 * hashtable. 809 */ 810 const const_iterator& cend() const noexcept; 811 812 /** 813 * @brief Returns an unsafe iterator pointing to the beginning of the 814 * hashtable. 815 * 816 * Unsafe iterators are slightly faster than safe iterators. However, 817 * BE CAREFUL when using them: they should ONLY be used when you have the 818 * guarantee that they will never point to a deleted element. If unsure, 819 * prefer using the safe iterators (those are only slightly slower). 820 * 821 * @return Returns an unsafe iterator pointing to the beginning of the 822 * hashtable. 823 */ 824 iterator begin(); 825 826 /** 827 * @brief Returns an unsafe const_iterator pointing to the beginning of the 828 * hashtable. 829 * 830 * Unsafe iterators are slightly faster than safe iterators. However, 831 * BE CAREFUL when using them: they should ONLY be used when you have the 832 * guarantee that they will never point to a deleted element. If unsure, 833 * prefer using the safe iterators (those are only slightly slower). 834 * 835 * @return Returns an unsafe const_iterator pointing to the beginning of 836 * the hashtable. 837 */ 838 const_iterator begin() const; 839 840 /** 841 * @brief Returns an unsafe const_iterator pointing to the beginning of the 842 * hashtable. 843 * 844 * Unsafe iterators are slightly faster than safe iterators. However, 845 * BE CAREFUL when using them: they should ONLY be used when you have the 846 * guarantee that they will never point to a deleted element. If unsure, 847 * prefer using the safe iterators (those are only slightly slower). 848 * 849 * @return Returns an unsafe const_iterator pointing to the beginning of the 850 * hashtable. 851 */ 852 const_iterator cbegin() const; 853 854 /** 855 * @brief Returns the safe iterator pointing to the end of the hashtable. 856 * 857 * Safe iterators are slightly slower than unsafe ones but they guarantee 858 * that you will never get a segfault if they try to access to a deleted 859 * element or if they try a ++ operation from a deleted element. 860 * 861 * @return Returns the safe iterator pointing to the end of the hashtable. 862 */ 863 const iterator_safe& endSafe() noexcept; 864 865 /** 866 * @brief Returns the safe const_iterator pointing to the end of the 867 * hashtable. 868 * 869 * Safe iterators are slightly slower than unsafe ones but they guarantee 870 * that you will never get a segfault if they try to access to a deleted 871 * element or if they try a ++ operation from a deleted element. 872 * 873 * @return Returns the safe const_iterator pointing to the end of the 874 * hashtable. 875 */ 876 const const_iterator_safe& endSafe() const noexcept; 877 878 /** 879 * @brief Returns the safe const_iterator pointing to the end of the 880 * hashtable. 881 * 882 * Safe iterators are slightly slower than unsafe ones but they guarantee 883 * that you will never get a segfault if they try to access to a deleted 884 * element or if they try a ++ operation from a deleted element. 885 * 886 * @return Returns the safe const_iterator pointing to the end of the 887 * hashtable. 888 */ 889 const const_iterator_safe& cendSafe() const noexcept; 890 891 /** 892 * @brief Returns the safe iterator pointing to the beginning of the 893 * hashtable. 894 * 895 * Safe iterators are slightly slower than unsafe ones but they guarantee 896 * that you will never get a segfault if they try to access to a deleted 897 * element or if they try a ++ operation from a deleted element. 898 * 899 * @return Returns the safe iterator pointing to the beginning of the 900 * hashtable. 901 */ 902 iterator_safe beginSafe(); 903 904 /** 905 * @brief Returns the safe const_iterator pointing to the beginning of the 906 * hashtable. 907 * 908 * Safe iterators are slightly slower than unsafe ones but they guarantee 909 * that you will never get a segfault if they try to access to a deleted 910 * element or if they try a ++ operation from a deleted element. 911 * 912 * @return Returns the safe const_iterator pointing to the beginning of the 913 * hashtable. 914 */ 915 const_iterator_safe beginSafe() const; 916 917 /** 918 * @brief Returns the safe const_iterator pointing to the beginning of the 919 * hashtable. 920 * 921 * Safe iterators are slightly slower than unsafe ones but they guarantee 922 * that you will never get a segfault if they try to access to a deleted 923 * element or if they try a ++ operation from a deleted element. 924 * 925 * @return Returns the safe const_iterator pointing to the beginning of the 926 * hashtable. 927 */ 928 const_iterator_safe cbeginSafe() const; 929 930 /** 931 * @brief Returns the end iterator for other classes' statics (read the 932 * detailed description of this method). 933 * 934 * To reduce memory consumption of hash tables (which are heavily used in 935 * aGrUM) while allowing fast for(iter=begin(); iter!=end();++iter) loops, 936 * end iterators are created just once as a static member of a non-template 937 * hashtable. While this scheme is efficient and it works quite effectively 938 * when manipulating hashtables, it has a drawback: other classes with 939 * static members using the HashTable's end() iterator may fail to work due 940 * to the well known "static initialization order fiasco" (see Marshall 941 * Cline's C++ FAQ for more details about this C++ feature). OK, so what is 942 * the problem? Consider for instance class Set. A Set contains a hashtable 943 * that stores all its elements in a convenient way. To reduce memory 944 * consumption, Set::end iterator is a static member that is initialized 945 * with a HashTable's end iterator. If the compiler decides to initialize 946 * Set::end before initializing HashTable::end, then Set::end will be in an 947 * incoherent state. Unfortunately, we cannot know for sure in which order 948 * static members will be initialized (the order is a compiler's decision). 949 * Hence, we shall enforce the fact that HashTable::end is initialized 950 * before Set::end. Using method HashTable::end4Statics will ensure this 951 * fact: it uses the C++ "construct on first use" idiom (see the C++ FAQ) 952 * that ensures that the order fiasco is avoided. More precisely, 953 * end4Statics initializes a global variable that is the very end iterator 954 * used by all hashtables. Now, this induces a small overhead. So, we also 955 * provide a HashTable::end() method that returns the end iterator without 956 * this small overhead, but assuming that function end4Statics has already 957 * been called once (which is always the case) when a hashtable has been 958 * created. 959 * 960 * So, to summarize: when initializing static members, use end4Statics() 961 * rather than end(). In all the other cases, use simply the usual method 962 * end(). 963 * 964 * @return Returns the end iterator for other classes' statics (read the 965 * detailed description of this method). 966 */ 967 static const iterator& end4Statics(); 968 969 /** 970 * @brief Returns the end iterator for other classes' statics (read the 971 * detailed description of this method). 972 * 973 * To reduce memory consumption of hash tables (which are heavily used in 974 * aGrUM) while allowing fast for(iter=begin(); iter!=end();++iter) loops, 975 * end iterators are created just once as a static member of a non-template 976 * hashtable. While this scheme is efficient and it works quite effectively 977 * when manipulating hashtables, it has a drawback: other classes with 978 * static members using the HashTable's end() iterator may fail to work due 979 * to the well known "static initialization order fiasco" (see Marshall 980 * Cline's C++ FAQ for more details about this C++ feature). OK, so what is 981 * the problem? Consider for instance class Set. A Set contains a hashtable 982 * that stores all its elements in a convenient way. To reduce memory 983 * consumption, Set::end iterator is a static member that is initialized 984 * with a HashTable's end iterator. If the compiler decides to initialize 985 * Set::end before initializing HashTable::end, then Set::end will be in an 986 * incoherent state. Unfortunately, we cannot know for sure in which order 987 * static members will be initialized (the order is a compiler's decision). 988 * Hence, we shall enforce the fact that HashTable::end is initialized 989 * before Set::end. Using method HashTable::end4Statics will ensure this 990 * fact: it uses the C++ "construct on first use" idiom (see the C++ FAQ) 991 * that ensures that the order fiasco is avoided. More precisely, 992 * end4Statics initializes a global variable that is the very end iterator 993 * used by all hashtables. Now, this induces a small overhead. So, we also 994 * provide a HashTable::end() method that returns the end iterator without 995 * this small overhead, but assuming that function end4Statics has already 996 * been called once (which is always the case) when a hashtable has been 997 * created. 998 * 999 * So, to summarize: when initializing static members, use 1000 * constEnd4Statics() rather than cend(). In all the other cases, use 1001 * simply the usual method cend(). 1002 * 1003 * @return Returns the end iterator for other classes' statics (read the 1004 * detailed description of this method). 1005 */ 1006 static const const_iterator& constEnd4Statics(); 1007 1008 /** 1009 * @brief Returns the end iterator for other classes' statics (read the 1010 * detailed description of this method). 1011 * 1012 * To reduce memory consumption of hash tables (which are heavily used in 1013 * aGrUM) while allowing fast for(iter=begin(); iter!=end();++iter) loops, 1014 * end iterators are created just once as a static member of a non-template 1015 * hashtable. While this scheme is efficient and it works quite effectively 1016 * when manipulating hashtables, it has a drawback: other classes with 1017 * static members using the HashTable's end() iterator may fail to work due 1018 * to the well known "static initialization order fiasco" (see Marshall 1019 * Cline's C++ FAQ for more details about this C++ feature). OK, so what is 1020 * the problem? Consider for instance class Set. A Set contains a hashtable 1021 * that stores all its elements in a convenient way. To reduce memory 1022 * consumption, Set::end iterator is a static member that is initialized 1023 * with a HashTable's end iterator. If the compiler decides to initialize 1024 * Set::end before initializing HashTable::end, then Set::end will be in an 1025 * incoherent state. Unfortunately, we cannot know for sure in which order 1026 * static members will be initialized (the order is a compiler's decision). 1027 * Hence, we shall enforce the fact that HashTable::end is initialized 1028 * before Set::end. Using method HashTable::end4Statics will ensure this 1029 * fact: it uses the C++ "construct on first use" idiom (see the C++ FAQ) 1030 * that ensures that the order fiasco is avoided. More precisely, 1031 * end4Statics initializes a global variable that is the very end iterator 1032 * used by all hashtables. Now, this induces a small overhead. So, we also 1033 * provide a HashTable::end() method that returns the end iterator without 1034 * this small overhead, but assuming that function end4Statics has already 1035 * been called once (which is always the case) when a hashtable has been 1036 * created. 1037 * 1038 * So, to summarize: when initializing static members, use 1039 * endSafe4Statics() rather than endSafe(). In all the other cases, use 1040 * simply the usual method endSafe(). 1041 * 1042 * @return Returns the end iterator for other classes' statics (read the 1043 * detailed description of this method). 1044 */ 1045 static const iterator_safe& endSafe4Statics(); 1046 1047 /** 1048 * @brief Returns the end iterator for other classes' statics (read the 1049 * detailed description of this method). 1050 * 1051 * To reduce memory consumption of hash tables (which are heavily used in 1052 * aGrUM) while allowing fast for(iter=begin(); iter!=end();++iter) loops, 1053 * end iterators are created just once as a static member of a non-template 1054 * hashtable. While this scheme is efficient and it works quite effectively 1055 * when manipulating hashtables, it has a drawback: other classes with 1056 * static members using the HashTable's end() iterator may fail to work due 1057 * to the well known "static initialization order fiasco" (see Marshall 1058 * Cline's C++ FAQ for more details about this C++ feature). OK, so what is 1059 * the problem? Consider for instance class Set. A Set contains a hashtable 1060 * that stores all its elements in a convenient way. To reduce memory 1061 * consumption, Set::end iterator is a static member that is initialized 1062 * with a HashTable's end iterator. If the compiler decides to initialize 1063 * Set::end before initializing HashTable::end, then Set::end will be in an 1064 * incoherent state. Unfortunately, we cannot know for sure in which order 1065 * static members will be initialized (the order is a compiler's decision). 1066 * Hence, we shall enforce the fact that HashTable::end is initialized 1067 * before Set::end. Using method HashTable::end4Statics will ensure this 1068 * fact: it uses the C++ "construct on first use" idiom (see the C++ FAQ) 1069 * that ensures that the order fiasco is avoided. More precisely, 1070 * end4Statics initializes a global variable that is the very end iterator 1071 * used by all hashtables. Now, this induces a small overhead. So, we also 1072 * provide a HashTable::end() method that returns the end iterator without 1073 * this small overhead, but assuming that function end4Statics has already 1074 * been called once (which is always the case) when a hashtable has been 1075 * created. 1076 * 1077 * So, to summarize: when initializing static members, use 1078 * constEndSafe4Statics() rather than cendSafe(). In all the other cases, 1079 * use simply the usual method cendSafe(). 1080 * 1081 * @return Returns the end iterator for other classes' statics (read the 1082 * detailed description of this method). 1083 */ 1084 static const const_iterator_safe& constEndSafe4Statics(); 1085 1086 /// @} 1087 // ============================================================================ 1088 /// @name Operators 1089 // ============================================================================ 1090 /// @{ 1091 1092 /** 1093 * @brief Copy operator. 1094 * 1095 * The copy operators ensures that whenever a memory allocation problem 1096 * occurs, no memory leak occurs as well and it also guarantees that in 1097 * this case the hashtable returned is in a coherent state (it is an empty 1098 * hashtable). Note that the copy not only involves copying pairs 1099 * (key,value) but also the copy of the resize and key uniqueness policies. 1100 * 1101 * @param from The gum::HashTable to copy. 1102 * @return Returns this gum::HashTable. 1103 */ 1104 HashTable< Key, Val, Alloc >& operator=(const HashTable< Key, Val, Alloc >& from); 1105 1106 /** 1107 * @brief Generalized copy operator. 1108 * 1109 * The copy operators ensures that whenever a memory allocation problem 1110 * occurs, no memory leak occurs as well and it also guarantees that in 1111 * this case the hashtable returned is in a coherent state (it is an empty 1112 * hashtable). Note that the copy not only involves copying pairs 1113 * (key,value) but also the copy of the resize and key uniqueness policies. 1114 * 1115 * @param from The gum::HashTable to copy. 1116 * @return Returns this gum::HashTable. 1117 */ 1118 template < typename OtherAlloc > 1119 HashTable< Key, Val, Alloc >& operator=(const HashTable< Key, Val, OtherAlloc >& from); 1120 1121 /** 1122 * Move operator. 1123 * 1124 * @param from The gum::HashTable to move. 1125 * @return Returns this gum::HashTable. 1126 */ 1127 HashTable< Key, Val, Alloc >& operator=(HashTable< Key, Val, Alloc >&& from); 1128 1129 /** 1130 * @brief Returns a reference on the value the key of which is passed in 1131 * argument. 1132 * 1133 * In case of multiple identical keys in the hash table, the first value 1134 * encountered is returned. The method runs in constant time. 1135 * 1136 * @param key The key of the value to return. 1137 * @return Returns the value matching the given key. 1138 * @throws NotFound exception is thrown if the element cannot be found. 1139 */ 1140 Val& operator[](const Key& key); 1141 1142 /// returns a reference on the value the key of which is passed in argument 1143 /** In case of multiple identical keys in the hash table, the first value 1144 * encountered is returned. The method runs in constant time. 1145 * @throws NotFound exception is thrown if the element cannot be found. */ 1146 const Val& operator[](const Key& key) const; 1147 1148 /** 1149 * @brief Checks whether two hashtables contain the same elements. 1150 * 1151 * Two hashtables are considered equal if they contain the identical pairs 1152 * (key,val). Two pairs are identical if their keys have the same hashed 1153 * value, these two keys are equal in the sense of ==, and their val's are 1154 * also equal in the sense of ==. 1155 * 1156 * @param from The gum::HashTable to test for equality. 1157 * @return True if this and from are equal. 1158 */ 1159 template < typename OtherAlloc > 1160 bool operator==(const HashTable< Key, Val, OtherAlloc >& from) const; 1161 1162 /// 1163 /** 1164 * @brief Checks whether two hashtables contain different sets of elements. 1165 * 1166 * Two hashtables are considered different if they contain different pairs 1167 * (key,val). Two pairs are different if their keys have different hashed 1168 * values, or if they are different in the sense of !=, or if their val's 1169 * are different in the sense of !=. 1170 * 1171 * @param from The gum::HashTable to test for inequality. 1172 * @return True if this and from are not equal. 1173 */ 1174 template < typename OtherAlloc > 1175 bool operator!=(const HashTable< Key, Val, OtherAlloc >& from) const; 1176 1177 /// @} 1178 // ============================================================================ 1179 /// @name Fine tuning 1180 // ============================================================================ 1181 /// @{ 1182 1183 /** 1184 * @brief Returns the number of slots in the 'nodes' vector of the 1185 * hashtable. 1186 * 1187 * The method runs in constant time. 1188 * 1189 * @return Returns the number of slots in the 'nodes' vector of the 1190 * hashtable. 1191 */ 1192 Size capacity() const noexcept; 1193 1194 /// 1195 /** 1196 * @brief Changes the number of slots in the 'nodes' vector of the hash 1197 * table. 1198 * 1199 * Usually, method resize enables the user to resize manually the 1200 * hashtable. When in automatic resize mode, the function will actually 1201 * resize the table only if resizing policy is compatible with the new 1202 * size, i.e., the new size is not so small that there would be too many 1203 * elements per slot in the table (this would lead to a significant loss in 1204 * performance). However, the resizing policy may be changed by using 1205 * method setResizePolicy. The method runs in linear time in the size of 1206 * the hashtable. Upon memory allocation problem, the fuction guarantees 1207 * that no data is lost and that the hash table and its iterators are in a 1208 * coherent state. In such a case, a bad_alloc exception is thrown. 1209 * 1210 * @param new_size The new number of slots in the gum::HashTable. 1211 */ 1212 void resize(Size new_size); 1213 1214 /** 1215 * @brief Enables the user to change dynamically the resizing policy. 1216 * 1217 * In most cases, this should be useless. However, when available memory 1218 * becomes rare, avoiding automatic resizing may speed-up new insertions in 1219 * the table. 1220 * 1221 * @warning This function never resizes the hashtable by itself: even if 1222 * you set the new policy to be an automatic resizing and the number of 1223 * elements in the table is sufficiently high that we should resize the 1224 * table, function setResizePolicy won't perform this resizing. The 1225 * resizing will happen only if you insert a new element or if use method 1226 * resize. 1227 * 1228 * @param new_policy The new resizing policy, true implies automatic 1229 * resizing. 1230 */ 1231 void setResizePolicy(const bool new_policy) noexcept; 1232 1233 /** 1234 * @brief Returns the current resizing policy. 1235 * @return Returns the current resizing policy. 1236 */ 1237 bool resizePolicy() const noexcept; 1238 1239 /** 1240 * @brief Enables the user to change dynamically the policy for checking 1241 * whether there can exist several elements in the table with identical 1242 * keys. 1243 * 1244 * By default, we should always check that there does not exist duplicate 1245 * keys. However, this test slows the insertion of elements in the table. 1246 * So, when we know for sure that no duplicate key will be entered into the 1247 * table, we may avoid uniqueness checks. 1248 * 1249 * @warning When setting the key policy to "uniqueness", the function does 1250 * not check whether there are already different elements with identical 1251 * keys in the table. It thus only ensures that elements inserted from now 1252 * on will have unique keys. 1253 */ 1254 void setKeyUniquenessPolicy(const bool new_policy) noexcept; 1255 1256 /** 1257 * @brief Returns the current checking policy. 1258 * @return Returns the current checking policy. 1259 */ 1260 bool keyUniquenessPolicy() const noexcept; 1261 1262 /// @} 1263 // ============================================================================ 1264 /// @name Accessors / Modifiers 1265 // ============================================================================ 1266 /// @{ 1267 1268 /** 1269 * @brief Returns the number of elements stored into the hashtable. 1270 * 1271 * The method runs in constant time. 1272 * 1273 * @return Returns the number of elements stored into the hashtable. 1274 */ 1275 Size size() const noexcept; 1276 1277 /** 1278 * @brief Checks whether there exists an element with a given key in the 1279 * hashtable. 1280 * 1281 * The method runs in average in constant time if the resizing policy 1282 * is set. 1283 * 1284 * @param key The key to test for existence. 1285 * @return True if key is in this gum::HashTable. 1286 */ 1287 bool exists(const Key& key) const; 1288 1289 /** 1290 * @brief Adds a new element (actually a copy of this element) into the 1291 * hash table. 1292 * 1293 * If there already exists an element with the same key in the table and the 1294 * uniqueness policy prevents multiple identical keys to belong to the same 1295 * hashtable, an exception DuplicateElement is thrown. If the uniqueness 1296 * policy is not set, the method runs in the worst case in constant time, 1297 * else if the automatic resizing policy is set, it runs in constant time in 1298 * average linear in the number of elements by slot. @return As only a copy 1299 * of val is inserted into the hashtable, the method returns a reference on 1300 * a copy of the pair (key,val). @throw DuplicateElement is thrown when 1301 * attempting to insert a pair (key,val) in a hash table containing already 1302 * a pair with the same key and when the hash table's uniqueness policy is 1303 * set. 1304 * 1305 * @param key The key to add. 1306 * @param val The value to add. 1307 * @return The value added by copy to this gum::HashTable. 1308 */ 1309 value_type& insert(const Key& key, const Val& val); 1310 1311 /** 1312 * @brief Moves a new element in the hash table. 1313 * 1314 * If there already exists an element with the same key in the table and 1315 * the uniqueness policy prevents multiple identical keys to belong to the 1316 * same hashtable, an exception DuplicateElement is thrown. If the 1317 * uniqueness policy is not set, the method runs in the worst case in 1318 * constant time, else if the automatic resizing policy is set, it runs in 1319 * constant time in average linear in the number of elements by slot. 1320 * @return a reference to the pair (key,val) in the hashtable. @throw 1321 * DuplicateElement is thrown when attempting to insert a pair (key,val) in 1322 * a hash table containing already a pair with the same key and when the 1323 * hash table's uniqueness policy is set. 1324 * 1325 * @param key The key to move. 1326 * @param val The value to move. 1327 * @return The value moved to this gum::HashTable. 1328 */ 1329 value_type& insert(Key&& key, Val&& val); 1330 1331 /** 1332 * @brief Adds a new element (actually a copy of this element) into the 1333 * hash table. 1334 * 1335 * If there already exists an element with the same key in the table and 1336 * the uniqueness policy prevents multiple identical keys to belong to the 1337 * same hashtable, an exception DuplicateElement is thrown. If the 1338 * uniqueness policy is not set, the method runs in the worst case in 1339 * constant time, else if the automatic resizing policy is set, it runs in 1340 * constant time in average linear in the number of elements by slot. 1341 * @return As only a copy of val is inserted into the hashtable, the method 1342 * returns a reference on a copy of the pair (key,val). @throw 1343 * DuplicateElement is thrown when attempting to insert a pair (key,val) in 1344 * a hash table containing already a pair with the same key and when the 1345 * hash table's uniqueness policy is set. 1346 * 1347 * @param elt The pair of key value to add. 1348 * @return The value added by copy to this gum::HashTable. 1349 */ 1350 value_type& insert(const std::pair< Key, Val >& elt); 1351 1352 /** 1353 * @brief Moves a new element in the hash table. 1354 * 1355 * If there already exists an element with the same key in the table and 1356 * the uniqueness policy prevents multiple identical keys to belong to the 1357 * same hashtable, an exception DuplicateElement is thrown. If the 1358 * uniqueness policy is not set, the method runs in the worst case in 1359 * constant time, else if the automatic resizing policy is set, it runs in 1360 * constant time in average linear in the number of elements by slot. 1361 * @return a reference to the pair (key,val) in the hashtable. @throw 1362 * DuplicateElement is thrown when attempting to insert a pair (key,val) in 1363 * a hash table containing already a pair with the same key and when the 1364 * hash table's uniqueness policy is set. 1365 * 1366 * @param elt The pair of key value to move in this gum::HashTable. 1367 * @return The value moved to this gum::HashTable. 1368 */ 1369 value_type& insert(std::pair< Key, Val >&& elt); 1370 1371 /** 1372 * @brief Emplace a new element into the hashTable. 1373 * 1374 * If there already exists an element with the same key in the list and the 1375 * uniqueness policy prevents multiple identical keys to belong to the same 1376 * hashtable, an exception DuplicateElement is thrown. If the uniqueness 1377 * policy is not set, the method runs in the worst case in constant time, 1378 * else if the automatic resizing policy is set, it runs in constant time 1379 * in average linear in the number of elements by slot. @return a 1380 * reference to the pair (key,val) inserted in the hash table. @throw 1381 * DuplicateElement is thrown when attempting to insert a pair (key,val) in 1382 * a hash table containing already a pair with the same key and when the 1383 * hash table's uniqueness policy is set. 1384 * 1385 * @param args The element to emplace. 1386 */ 1387 template < typename... Args > 1388 value_type& emplace(Args&&... args); 1389 1390 /** 1391 * @brief Returns a reference on the element the key of which is passed in 1392 * argument. 1393 * 1394 * In case of multiple identical keys in the hash table, the first value 1395 * encountered is returned. The method runs in constant time. 1396 * In case of not found key, (key,default_value) is inserted in *this. 1397 * 1398 * @param key The key for wich we want the value. 1399 * @param default_value The default value to return if key does not match 1400 * any value. 1401 * @return Returns a reference on the element the key of which is passed in 1402 * argument. 1403 */ 1404 mapped_type& getWithDefault(const Key& key, const Val& default_value); 1405 1406 /** 1407 * @brief Returns a reference on the element the key of which is passed in 1408 * argument. 1409 * 1410 * In case of multiple identical keys in the hash table, the first value 1411 * encountered is returned. The method runs in constant time. In case of 1412 * not found key, (key,default_value) is inserted in *this. 1413 * 1414 * @param key The key for wich we want the value. 1415 * @param default_value The default value to return if key does not match 1416 * any value. 1417 * @return Returns a reference on the element the key of which is passed in 1418 * argument. 1419 */ 1420 mapped_type& getWithDefault(Key&& key, Val&& default_value); 1421 1422 /** 1423 * @brief Add a new property or modify it if it already existed. 1424 * 1425 * When used as a "dynamic property list", it may be convenient to use this 1426 * function. Function set inserts a new pair (key,val) if the key does not 1427 * already exists, or it changes the value associated with key if a pair 1428 * (key,val) already exists in the hash table. 1429 * 1430 * @param key The key of the value to add or set. 1431 * @param default_value The value to set or add. 1432 */ 1433 void set(const Key& key, const Val& default_value); 1434 1435 /** 1436 * @brief Removes a property (i.e., remove an element). 1437 * 1438 * Reset removes a property (i.e., a pair (key,val)) if it exists. This is 1439 * an alias for erase but it is quite convenient when dealing with "dynamic 1440 * property lists". 1441 * 1442 * @param key The property to remove. 1443 */ 1444 void reset(const Key& key); 1445 1446 /** 1447 * @brief Removes a given element from the hash table. 1448 * 1449 * The element is the first one encountered in the list (from begin() to 1450 * end()) having the specified key. If no such element can be found, 1451 * nothing is done (in particular, it does not throw any exception). The 1452 * function never resizes the nodes vector (even if the resizing policy 1453 * would enable to decrease this size). The method runs in average in time 1454 * linear to the number of iterators pointing to the table if the automatic 1455 * resizing policy is set (else it is in linear time in the number of 1456 * elements of the hash table plus the number of iterators). 1457 * 1458 * @param key The key of the element to remove. 1459 */ 1460 void erase(const Key& key); 1461 1462 /** 1463 * @brief Removes a given element from the hash table. 1464 * 1465 * This method updates all the safe iterators pointing to the deleted 1466 * element, i.e., when trying to dereference those iterators, an exception 1467 * will be raised because they will know that the element they point to no 1468 * longer exists. 1469 * 1470 * @param iter An iterator over the element to remove. 1471 */ 1472 void erase(const iterator_safe& iter); 1473 1474 /** 1475 * @brief Removes a given element from the hash table. 1476 * 1477 * This method updates all the safe iterators pointing to the deleted 1478 * element, i.e., when trying to dereference those iterators, an exception 1479 * will be raised because they will know that the element they point to no 1480 * longer exists. 1481 * 1482 * @param iter An iterator over the element to remove. 1483 */ 1484 void erase(const const_iterator_safe& iter); 1485 1486 /** 1487 * @brief Removes a given element from the hash table. 1488 * 1489 * The element is the first one encountered in the list (from begin() to 1490 * end()) having the specified value. If no such element can be found, 1491 * nothing is done (in particular, it does not throw any exception). The 1492 * function never resizes the nodes vector (even if the resizing policy 1493 * would enable to decrease this size). Comparisons between Val instances 1494 * are performed through == operators. Logically, this method should have 1495 * been named "erase", however, this would have prevented creating hash 1496 * tables where both keys and vals have the same type. Hence we chose to 1497 * add "ByVal" after erase to make a difference between erasing by key and 1498 * erasing by val. 1499 * 1500 * @param val The value to remove. 1501 */ 1502 void eraseByVal(const Val& val); 1503 1504 /** 1505 * @brief Returns a reference on the key given a value. 1506 * 1507 * In case of multiple identical values in the hash table, the first key 1508 * encountered is returned. The method runs in linear time. 1509 * 1510 * @param val The value for which the key is returned. 1511 * @return Returns a reference on the key given a value. 1512 * @throws NotFound Raised if the element cannot be found. 1513 */ 1514 const Key& keyByVal(const Val& val) const; 1515 1516 /** 1517 * @brief Returns a reference on a given key. 1518 * 1519 * Some complex structures use pointers on keys of hashtables. These 1520 * structures thus require that we do not only get a copy of a given key, 1521 * but the key stored in the hashtable itself. This is the very purpose of 1522 * this function. 1523 * 1524 * @param key The key to return. 1525 * @return Returns a reference on a given key. 1526 * @throw NotFound Raised if the element cannot be found. 1527 */ 1528 const Key& key(const Key& key) const; 1529 1530 /** 1531 * @brief Removes all the elements having a certain value from the hash 1532 * table. 1533 * 1534 * If no such element can be found, nothing is done (in particular, it does 1535 * not throw any exception). The function never resizes the nodes vector 1536 * (even if the resizing policy would enable to decrease this size). 1537 * Comparisons between Val instances are performed through == operators. 1538 * 1539 * @param val The value to remove. 1540 * 1541 */ 1542 void eraseAllVal(const Val& val); 1543 1544 /** 1545 * @brief Removes all the elements in the hash table. 1546 * 1547 * The function does not resize the nodes vector (even if the size of this 1548 * one has been increased after the creation of the hash table) and it 1549 * resets the iterators on the hash table to end. The method runs in linear 1550 * time w.r.t. the number of iterators pointing to the hash table. 1551 */ 1552 void clear(); 1553 1554 /** 1555 * @brief Indicates whether the hash table is empty. 1556 * @return Returns true if the gum::HashTable is empty. 1557 */ 1558 bool empty() const noexcept; 1559 1560 /** 1561 * @brief Transforms a hashtable of vals into a hashtable of mountains. 1562 * 1563 * @warning Although the resulting hashtable has the same number of 1564 * elements as the original hashtable, by default, the size of the former 1565 * may not be equal to that of the latter. Hence iterators on the original 1566 * hashtable may not parse it in the same order as iterators on the 1567 * resulting hashtable. To guarrantee that both hashtables have the same 1568 * size (and thus have the elements in the same order), set the @e size 1569 * argument to the size of the original hashtable. 1570 * 1571 * @param f A function that maps any Val element into a Mount. 1572 * @param size The size of the resulting hashtable. When equal to 0, a 1573 * default size is computed that is a good trade-off between space 1574 * consumption and efficiency of new elements insertions 1575 * @param resize_pol the resizing policy (automatic or manual resizing) 1576 * @param key_uniqueness_pol uniqueness policy 1577 * 1578 * @return Returns the gum::HashTable of mountains. 1579 */ 1580 template < typename Mount, 1581 typename OtherAlloc 1582 = typename Alloc::template rebind< std::pair< Key, Mount > >::other > 1583 HashTable< Key, Mount, OtherAlloc > map(Mount (*f)(Val), 1584 Size size = Size(0), 1585 bool resize_pol = HashTableConst::default_resize_policy, 1586 bool key_uniqueness_pol 1587 = HashTableConst::default_uniqueness_policy) const; 1588 1589 /** 1590 * @brief Transforms a hashtable of vals into a hashtable of mountains. 1591 * 1592 * @warning Although the resulting hashtable has the same number of 1593 * elements as the original hashtable, by default, the size of the former 1594 * may not be equal to that of the latter. Hence iterators on the original 1595 * hashtable may not parse it in the same order as iterators on the 1596 * resulting hashtable. To guarrantee that both hashtables have the same 1597 * size (and thus have the elements in the same order), set the @e size 1598 * argument to the size of the original hashtable. 1599 * 1600 * @param f A function that maps any Val element into a Mount. 1601 * @param size The size of the resulting hashtable. When equal to 0, a 1602 * default size is computed that is a good trade-off between space 1603 * consumption and efficiency of new elements insertions 1604 * @param resize_pol the resizing policy (automatic or manual resizing) 1605 * @param key_uniqueness_pol uniqueness policy 1606 * 1607 * @return Returns the gum::HashTable of mountains. 1608 */ 1609 template < typename Mount, 1610 typename OtherAlloc 1611 = typename Alloc::template rebind< std::pair< Key, Mount > >::other > 1612 HashTable< Key, Mount, OtherAlloc > map(Mount (*f)(Val&), 1613 Size size = Size(0), 1614 bool resize_pol = HashTableConst::default_resize_policy, 1615 bool key_uniqueness_pol 1616 = HashTableConst::default_uniqueness_policy) const; 1617 1618 /** 1619 * @brief Transforms a hashtable of vals into a hashtable of mountains. 1620 * 1621 * @warning Although the resulting hashtable has the same number of 1622 * elements as the original hashtable, by default, the size of the former 1623 * may not be equal to that of the latter. Hence iterators on the original 1624 * hashtable may not parse it in the same order as iterators on the 1625 * resulting hashtable. To guarrantee that both hashtables have the same 1626 * size (and thus have the elements in the same order), set the @e size 1627 * argument to the size of the original hashtable. 1628 * 1629 * @param f A function that maps any Val element into a Mount. 1630 * @param size The size of the resulting hashtable. When equal to 0, a 1631 * default size is computed that is a good trade-off between space 1632 * consumption and efficiency of new elements insertions 1633 * @param resize_pol the resizing policy (automatic or manual resizing) 1634 * @param key_uniqueness_pol uniqueness policy 1635 * 1636 * @return Returns the gum::HashTable of mountains. 1637 */ 1638 template < typename Mount, 1639 typename OtherAlloc 1640 = typename Alloc::template rebind< std::pair< Key, Mount > >::other > 1641 HashTable< Key, Mount, OtherAlloc > map(Mount (*f)(const Val&), 1642 Size size = Size(0), 1643 bool resize_pol = HashTableConst::default_resize_policy, 1644 bool key_uniqueness_pol 1645 = HashTableConst::default_uniqueness_policy) const; 1646 1647 /** 1648 * @brief Creates a hashtable of mounts with a given value from a hashtable 1649 * of vals. 1650 * 1651 * @warning Although the resulting hashtable has the same number of 1652 * elements as the original hashtable, by default, the size of the former 1653 * may not be equal to that of the latter. Hence iterators on the original 1654 * hashtable may not parse it in the same order as iterators on the 1655 * resulting hashtable. To guarrantee that both hashtables have the same 1656 * size (and thus have the elements in the same order), set the @e size 1657 * argument to the size of the original hashtable. 1658 * 1659 * @param val The value taken by all the elements of the resulting 1660 * hashtable. 1661 * @param size The size of the resulting hashtable. When equal to 0, a 1662 * default size is computed that is a good trade-off between space 1663 * consumption and efficiency of new elements insertions 1664 * @param resize_pol the resizing policy (automatic or manual resizing) 1665 * @param key_uniqueness_pol uniqueness policy 1666 * 1667 * @return Returns the gum::HashTable of mountains. 1668 */ 1669 template < typename Mount, 1670 typename OtherAlloc 1671 = typename Alloc::template rebind< std::pair< Key, Mount > >::other > 1672 HashTable< Key, Mount, OtherAlloc > map(const Mount& val, 1673 Size size = Size(0), 1674 bool resize_pol = HashTableConst::default_resize_policy, 1675 bool key_uniqueness_pol 1676 = HashTableConst::default_uniqueness_policy) const; 1677 1678 /// @} 1679 1680 private: 1681 /// Friends to optimize the access to data, iterators must be friends 1682 /// @{ 1683 template < typename K, typename V, typename A > 1684 friend class HashTable; 1685 friend class HashTableIterator< Key, Val >; 1686 friend class HashTableConstIterator< Key, Val >; 1687 friend class HashTableIteratorSafe< Key, Val >; 1688 friend class HashTableConstIteratorSafe< Key, Val >; 1689 1690 friend std::ostream& operator<<<>(std::ostream&, const HashTable< Key, Val, Alloc >&); 1691 friend std::ostream& operator<<<>(std::ostream& s, const HashTable< Key*, Val, Alloc >& table); 1692 1693 /// For bijections to quickly access data. 1694 template < typename T1, typename T2, typename A > 1695 friend class Bijection; 1696 /// @} 1697 1698 /** 1699 * The hash table is represented as a vector of chained lists. ' __nodes' 1700 * is this very vector. 1701 */ 1702 std::vector< HashTableList< Key, Val, Alloc > > _nodes_; 1703 1704 /// The number of nodes in vector ' __nodes'. 1705 Size _size_; 1706 1707 /// Number of elements of type Val stored in the hash table. 1708 Size _nb_elements_{Size(0)}; 1709 1710 /// The function used to hash keys (may change when the table is resized). 1711 HashFunc< Key > _hash_func_; 1712 1713 /// Is resizing performed automatically? 1714 bool _resize_policy_{true}; 1715 1716 /// Shall we check for key uniqueness in the table? 1717 bool _key_uniqueness_policy_{true}; 1718 1719 /** 1720 * @brief Returns where the begin index should be. 1721 * 1722 * Beware: the beginning of a HashTable is the end of its _nodes_ vector, 1723 * i.e., the Bucket at the highest index in _nodes_. This enables a 1724 * slightly faster parsing than if it were the lowest index. @warning 1725 * std::numeric_limits<Size>::max() means that we do not know where the 1726 * beginning of the table really is (this can mean either that there is not 1727 * yet any element in the hash table or that an erase operation has been 1728 * performed and that we lost track of the element that should correspond 1729 * to the begin(). 1730 * 1731 * @return Returns where the begin index should be. 1732 */ 1733 mutable Size _begin_index_{std::numeric_limits< Size >::max()}; 1734 1735 /// The list of safe iterators pointing to the hash table. 1736 mutable std::vector< HashTableConstIteratorSafe< Key, Val >* > _safe_iterators_; 1737 1738 /** 1739 * @brief The allocator for the buckets. 1740 * 1741 * @warning the allocator field should compulsorily be the last of field of 1742 * the class. As such, for K and V fixed, all hashTable<K,V,A> are the same 1743 * (up to the allocator) for all allocators A. This feature proves useful 1744 * to avoid passing the allocator as a template parameter to iterators. 1745 */ 1746 BucketAllocator _alloc_; 1747 1748 /// Erases a given bucket. 1749 void _erase_(HashTableBucket< Key, Val >* bucket, Size index); 1750 1751 /** 1752 * @brief A function used to perform copies of HashTables. 1753 * 1754 * This code is shared by the copy constructor and the copy operator. The 1755 * function ensures that when a memory allocation problem occurs: 1756 * - no memory leak occurs 1757 * - the hashtable returned is empty but in a coherent state 1758 * - an exception is thrown 1759 * 1760 * The function assumes that both this and table have arrays ' __nodes' of 1761 * the same size. 1762 * 1763 * @param table The gum::HashTable to copy. 1764 * @tparam OtherAlloc The other gum::HashTable allocator. 1765 */ 1766 template < typename OtherAlloc > 1767 void _copy_(const HashTable< Key, Val, OtherAlloc >& table); 1768 1769 /** 1770 * @brief Used by all default constructors (general and specialized). 1771 * @param size The size of the gum::HashTable to create. 1772 */ 1773 void _create_(Size size); 1774 1775 /** 1776 * @brief Clear all the safe iterators. 1777 */ 1778 void _clearIterators_(); 1779 1780 /** 1781 * @brief Adds a new element (actually a copy of this element) in the hash 1782 * table. 1783 * 1784 * If there already exists an element with the same key in the list and the 1785 * uniqueness policy prevents multiple identical keys to belong to the same 1786 * hashtable, an exception DuplicateElement is thrown. If the uniqueness 1787 * policy is not set, the method runs in the worst case in constant time, 1788 * else if the automatic resizing policy is set, it runs in constant time 1789 * in average linear in the number of elements by slot. 1790 * 1791 * @param bucket The bucket inserted in the hash table. 1792 * @throw DuplicateElement is thrown when attempting to insert a pair 1793 * (key,val) in a hash table containing already a pair with the same key 1794 * and when the hash table's uniqueness policy is set. 1795 */ 1796 void _insert_(Bucket* bucket); 1797 }; 1798 1799 1800 // =========================================================================== 1801 // === SAFE HASH TABLES CONST ITERATORS === 1802 // =========================================================================== 1803 1804 /** 1805 * @class HashTableIteratorStaticEnd 1806 * @headerfile hashTable.h <agrum/tools/core/hashTable.h> 1807 * @brief A class used to create the static iterator used by HashTables. 1808 * @ingroup hashtable_group 1809 * 1810 * The aim of using this class rather than just creating _HashTableIterEnd_ 1811 * as a global variable is to prevent other classes to access and modify 1812 * _HashTableIterEnd_. 1813 */ 1814 class HashTableIteratorStaticEnd { 1815 private: 1816 /// The unsafe iterator used by everyone. 1817 static const HashTableIterator< int, int >* _HashTableIterEnd_; 1818 1819 /// The safe iterator used by everyone. 1820 static const HashTableIteratorSafe< int, int >* _HashTableIterEndSafe_; 1821 1822 /** 1823 * @brief Creates (if needed) and returns the iterator _HashTableIterEnd_. 1824 * @return Returns the iterator _HashTableIterEnd_. 1825 */ 1826 static const HashTableIterator< int, int >* end4Statics(); 1827 1828 /** 1829 * @brief Creates (if needed) and returns the iterator _HashTableIterEnd_. 1830 * @return Returns the iterator _HashTableIterEnd_. 1831 */ 1832 static const HashTableConstIterator< int, int >* constEnd4Statics(); 1833 1834 /** 1835 * @brief Creates (if needed) and returns the iterator 1836 * _HashTableIterEndSafe_. 1837 * @return Returns the iterator _HashTableIterEndSafe_. 1838 */ 1839 static const HashTableIteratorSafe< int, int >* endSafe4Statics(); 1840 1841 /** 1842 * @brief Creates (if needed) and returns the iterator 1843 * _HashTableIterEndSafe_. 1844 * @return Returns the iterator _HashTableIterEndSafe_. 1845 */ 1846 static const HashTableConstIteratorSafe< int, int >* constEndSafe4Statics(); 1847 1848 /// Friends that have access to the iterator. 1849 template < typename Key, typename Val, typename Alloc > 1850 friend class HashTable; 1851 }; 1852 1853 1854 // =========================================================================== 1855 // === SAFE HASH TABLES CONST ITERATORS === 1856 // =========================================================================== 1857 /** 1858 * @class HashTableConstIteratorSafe 1859 * @headerfile hashTable.h <agrum/tools/core/hashTable.h> 1860 * @brief Safe Const Iterators for hashtables. 1861 * @ingroup hashtable_group 1862 * 1863 * HashTableConstIteratorSafe provides a safe way to parse HashTables. They 1864 * are safe because they are kept informed by the hashtable they belong to of 1865 * the elements deleted by the user. Hence, even if the user removes an 1866 * element pointed to by a HashTableConstIteratorSafe, using the latter to 1867 * access this element will never crash the application. Instead it will 1868 * properly throw a UndefinedIteratorValue exception. 1869 * 1870 * Developers may consider using HashTable<x,y>::const_iterator_safe instead 1871 * of HashTableConstIteratorSafe<x,y>. 1872 * 1873 * @par Usage example: 1874 * @code 1875 * // creation of a hash table with 10 elements 1876 * HashTable<int,string> table; 1877 * for (int i = 0; i< 10; ++i) 1878 * table.insert (i,"xxx" + string (i,'x')); 1879 * 1880 * // parse the hash table 1881 * for (HashTable<int,string>::const_iterator_safe iter = table.cbeginSafe (); 1882 * iter != table.cendSafe (); ++iter) { 1883 * // display the values 1884 * cerr << "at " << iter.key () << " value = " << iter.val () << endl; 1885 * const HashTable<int,string>::value_type& elt = *iter; 1886 * const std::pair<const int, string>& xelt = *iter; 1887 * } 1888 * 1889 * // check whether two iterators point toward the same element 1890 * HashTable<int,string>::const_iterator_safe iter1 = table1.cbeginSafe (); 1891 * HashTable<int,string>::const_iterator_safe iter2 = table1.cendSafe (); 1892 * if (iter1 != iter) { 1893 * cerr << "iter1 and iter2 point toward different elements"; 1894 * } 1895 * 1896 * // make iter1 point toward nothing 1897 * iter1.clear (); 1898 * @endcode 1899 */ 1900 template < typename Key, typename Val > 1901 class HashTableConstIteratorSafe { 1902 public: 1903 /// Types for STL compliance. 1904 /// @{ 1905 using iterator_category = std::forward_iterator_tag; 1906 using key_type = Key; 1907 using mapped_type = Val; 1908 using value_type = std::pair< const Key, Val >; 1909 using reference = value_type&; 1910 using const_reference = const value_type&; 1911 using pointer = value_type*; 1912 using const_pointer = const value_type*; 1913 using difference_type = std::ptrdiff_t; 1914 /// @} 1915 1916 // ============================================================================ 1917 /// @name Constructors / Destructors 1918 // ============================================================================ 1919 /// @{ 1920 1921 /** 1922 * @brief Basic constructor: creates an iterator pointing to nothing. 1923 */ 1924 HashTableConstIteratorSafe(); 1925 1926 /** 1927 * @brief Constructor for an iterator pointing to the first element of a 1928 * hashtable. 1929 * @tparam Alloc The gum::HashTable allocator. 1930 * @param tab A gum::HashTable to iterate over. 1931 */ 1932 template < typename Alloc > 1933 HashTableConstIteratorSafe(const HashTable< Key, Val, Alloc >& tab); 1934 1935 /// 1936 /** 1937 * @brief Constructor for an iterator pointing to the nth element of a 1938 * hashtable. 1939 * 1940 * The method runs in time linear to ind_elt. 1941 * 1942 * @tparam Alloc The gum::HashTable allocator. 1943 * @param tab the hash table to which the so-called element belongs 1944 * @param ind_elt the position of the element in the hash table (0 means 1945 * the first element). 1946 * @throw UndefinedIteratorValue Raised if the element cannot be found. 1947 */ 1948 template < typename Alloc > 1949 HashTableConstIteratorSafe(const HashTable< Key, Val, Alloc >& tab, Size ind_elt); 1950 1951 /** 1952 * @brief Copy constructor. 1953 * @param from The gum::HashTableConstIteratorSafe to copy. 1954 */ 1955 HashTableConstIteratorSafe(const HashTableConstIteratorSafe< Key, Val >& from); 1956 1957 /** 1958 * @brief Copy constructor. 1959 * @param from The gum::HashTableConstIterator to copy. 1960 */ 1961 explicit HashTableConstIteratorSafe(const HashTableConstIterator< Key, Val >& from); 1962 1963 /** 1964 * @brief Move constructor. 1965 * @param from The gum::HashTableConstIteratorSafe to move. 1966 */ 1967 HashTableConstIteratorSafe(HashTableConstIteratorSafe< Key, Val >&& from); 1968 1969 /** 1970 * @brief Destructor. 1971 */ 1972 ~HashTableConstIteratorSafe() noexcept; 1973 1974 /// @} 1975 // ============================================================================ 1976 /// @name Accessors / Modifiers 1977 // ============================================================================ 1978 /// @{ 1979 1980 /** 1981 * @brief Returns the key pointed to by the iterator. 1982 * @return Returns the key pointed to by the iterator. 1983 * @throws UndefinedIteratorValue Raised when the iterator does not point 1984 * to a valid hash table element 1985 */ 1986 const key_type& key() const; 1987 1988 /// 1989 /** 1990 * @brief Returns the mapped value pointed to by the iterator. 1991 * @return Returns the mapped value pointed to by the iterator. 1992 * @throws UndefinedIteratorValue Raised when the iterator does not point 1993 * to a valid hash table element. 1994 */ 1995 const mapped_type& val() const; 1996 1997 /** 1998 * @brief Makes the iterator point toward nothing (in particular, it is not 1999 * related anymore to its current hash table). 2000 * 2001 * It is mainly used by the hashtable when the latter is deleted while the 2002 * iterator is still alive. 2003 */ 2004 void clear() noexcept; 2005 2006 /// @} 2007 // ============================================================================ 2008 /// @name Operators 2009 // ============================================================================ 2010 /// @{ 2011 2012 /** 2013 * @brief Copy operator. 2014 * @param from The gum::HashTableConstIteratorSafe to copy. 2015 * @return Returns this gum::HashTableConstIteratorSafe. 2016 */ 2017 HashTableConstIteratorSafe< Key, Val >& 2018 operator=(const HashTableConstIteratorSafe< Key, Val >& from); 2019 2020 /** 2021 * @brief Copy operator. 2022 * @param from The gum::HashTableConstIterator to copy. 2023 * @return Returns this gum::HashTableConstIteratorSafe. 2024 */ 2025 HashTableConstIteratorSafe< Key, Val >& 2026 operator=(const HashTableConstIterator< Key, Val >& from); 2027 2028 /** 2029 * @brief Move operator. 2030 * @param from The gum::HashTableConstIteratorSafe to move. 2031 * @return Returns this gum::HashTableConstIteratorSafe. 2032 */ 2033 HashTableConstIteratorSafe< Key, Val >& 2034 operator=(HashTableConstIteratorSafe< Key, Val >&& from) noexcept; 2035 2036 /** 2037 * @brief Makes the iterator point to the next element in the hash table. 2038 * 2039 * @code 2040 * for (iter = hash.beginSafe(); iter != hash.endSafe (); ++iter) { } 2041 * @endcode 2042 * 2043 * The above loop is guaranteed to parse the whole hash table as long as no 2044 * element is added to or deleted from the hash table while being in the 2045 * loop. Deleting elements during the loop is guaranteed to never produce a 2046 * segmentation fault. 2047 * 2048 * @return Returns this gum::HashTableConstIteratorSafe pointing to the 2049 * next element in the gum::HashTable it's iterating over. 2050 */ 2051 HashTableConstIteratorSafe< Key, Val >& operator++() noexcept; 2052 2053 /** 2054 * @brief Makes the iterator point to i elements further in the hashtable. 2055 * @param i The number of steps to increment the 2056 * gum::HashTableConstIteratorSafe. 2057 * @return Returns this gum::HashTableConstIteratorSafe. 2058 */ 2059 HashTableConstIteratorSafe< Key, Val >& operator+=(Size i) noexcept; 2060 2061 /** 2062 * @brief Returns a new iterator poiting to i elements further in the 2063 * hashtable. 2064 * @param i The number of steps to increment the 2065 * gum::HashTableConstIteratorSafe. 2066 * @return Returns a new gum::HashTableConstIteratorSafe. 2067 */ 2068 HashTableConstIteratorSafe< Key, Val > operator+(Size i) const; 2069 2070 /** 2071 * @brief Checks whether two iterators are not equal. 2072 * @param from from The iterator to test for inequality. 2073 * @return Returns true if from and this iterator are inequal. 2074 */ 2075 bool operator!=(const HashTableConstIteratorSafe< Key, Val >& from) const noexcept; 2076 2077 /** 2078 * @brief Checks whether two iterators are equal. 2079 * @param from from The iterator to test for equality. 2080 * @return Returns true if from and this iterator are equal. 2081 */ 2082 bool operator==(const HashTableConstIteratorSafe< Key, Val >& from) const noexcept; 2083 2084 /** 2085 * @brief Returns the element pointed to by the iterator. 2086 * @return Returns the element pointed to by the iterator. 2087 * @throws UndefinedIteratorValue Raised when the iterator does not point 2088 * to a valid hash table element. 2089 */ 2090 const value_type& operator*() const; 2091 2092 /// @} 2093 2094 protected: 2095 /** 2096 * Class HashTable must be a friend because it stores iterator end and this 2097 * can be properly initialized only when the hashtable has been fully 2098 * allocated. Thus, proper initialization can only take place within the 2099 * constructor's code of the hashtable. 2100 */ 2101 template < typename K, typename V, typename A > 2102 friend class HashTable; 2103 2104 /// The hash table the iterator is pointing to. 2105 const HashTable< Key, Val >* _table_{nullptr}; 2106 2107 /** 2108 * @brief the index of the chained list pointed to by the iterator in the 2109 * array _nodes_ of the hash table. 2110 */ 2111 Size _index_{Size(0)}; 2112 2113 /// The bucket in the chained list pointed to by the iterator. 2114 HashTableBucket< Key, Val >* _bucket_{nullptr}; 2115 2116 /** 2117 * @brief the bucket we should start from when we decide to do a ++. 2118 * 2119 * Usually it should be equal to nullptr. However, if the user has deleted 2120 * the object pointed to by bucket, this will point to another bucket. When 2121 * it is equal to nullptr, it means that the bucket reached after a ++ 2122 * belongs to another slot of the hash table's ' __node' vector. 2123 */ 2124 HashTableBucket< Key, Val >* _next_bucket_{nullptr}; 2125 2126 /// Returns the current iterator's bucket. 2127 HashTableBucket< Key, Val >* _getBucket_() const noexcept; 2128 2129 /** 2130 * @brief Returns the index in the hashtable's node vector pointed to by 2131 * the iterator. 2132 * @return Returns the index in the hashtable's node vector pointed to by 2133 * the iterator. 2134 */ 2135 Size _getIndex_() const noexcept; 2136 2137 /** 2138 * @brief Removes the iterator from its hashtable' safe iterators list. 2139 */ 2140 void _removeFromSafeList_() const; 2141 2142 /** 2143 * @brief Insert the iterator into the hashtable's list of safe iterators. 2144 */ 2145 void _insertIntoSafeList_() const; 2146 }; 2147 2148 // =========================================================================== 2149 // === HASH TABLES ITERATORS === 2150 // =========================================================================== 2151 2152 /** 2153 * @class HashTableIteratorSafe 2154 * @headerfile hashTable.h <agrum/tools/core/hashTable.h> 2155 * @brief Safe Iterators for hashtables. 2156 * @ingroup hashtable_group 2157 * 2158 * HashTableIteratorSafe provides a safe way to parse HashTables. They are 2159 * safe because they are kept informed by the hashtable they belong to of the 2160 * elements deleted by the user. Hence, even if the user removes an element 2161 * pointed to by a HashTableIteratorSafe, using the latter to access this 2162 * element will never crash the application. Instead it will properly throw 2163 * an UndefinedIteratorValue exception. 2164 * 2165 * Developers may consider using HashTable<x,y>::iterator_safe instead of 2166 * HashTableIteratorSafe<x,y>. 2167 * 2168 * @par Usage example: 2169 * @code 2170 * // creation of a hash table with 10 elements 2171 * HashTable<int,string> table; 2172 * for (int i = 0; i< 10; ++i) 2173 * table.insert (i,"xxx" + string (i,'x')); 2174 * 2175 * // parse the hash table 2176 * for (HashTable<int,string>::iterator_safe iter = table.beginSafe (); 2177 * iter != table.endSafe (); ++iter) { 2178 * // display the values 2179 * cerr << "at " << iter.key() << " value = " << iter.val () << endl; 2180 * HashTable<int,string>::value_type& elt = *iter; 2181 * std::pair<const int, string>& xelt = *iter; 2182 * } 2183 * 2184 * // check whether two iterators point toward the same element 2185 * HashTable<int,string>::iterator_safe iter1 = table1.beginSafe (); 2186 * HashTable<int,string>::iterator_safe iter2 = table1.endSafe (); 2187 * if (iter1 != iter) { 2188 * cerr << "iter1 and iter2 point toward different elements"; 2189 * } 2190 * 2191 * // make iter1 point toward nothing 2192 * iter1.clear (); 2193 * @endcode 2194 * 2195 * @tparam Key The gum::HashTable key. 2196 * @tparam Val The gum::HashTable Value. 2197 */ 2198 template < typename Key, typename Val > 2199 class HashTableIteratorSafe: public HashTableConstIteratorSafe< Key, Val > { 2200 public: 2201 /// Types for STL compliance. 2202 /// @{ 2203 using iterator_category = std::forward_iterator_tag; 2204 using key_type = Key; 2205 using mapped_type = Val; 2206 using value_type = std::pair< const Key, Val >; 2207 using reference = value_type&; 2208 using const_reference = const value_type&; 2209 using pointer = value_type*; 2210 using const_pointer = const value_type*; 2211 using difference_type = std::ptrdiff_t; 2212 /// @} 2213 2214 // ============================================================================ 2215 /// @name Constructors / Destructors 2216 // ============================================================================ 2217 /// @{ 2218 2219 /** 2220 * @brief Basic constructor: creates an iterator pointing to nothing. 2221 */ 2222 HashTableIteratorSafe(); 2223 2224 /** 2225 * @brief Constructor for an iterator pointing to the first element of a 2226 * hashtable. 2227 * @tparam Alloc The gum::HashTable allocator. 2228 */ 2229 template < typename Alloc > 2230 HashTableIteratorSafe(const HashTable< Key, Val, Alloc >& tab); 2231 2232 /** 2233 * @brief Constructor for an iterator pointing to the nth element of a 2234 * hashtable. 2235 * 2236 * The method runs in time linear to ind_elt. 2237 * 2238 * @param tab the hash table to which the so-called element belongs 2239 * @param ind_elt the position of the element in the hash table (0 means 2240 * the first element). 2241 * @tparam Alloc The gum::HashTable allocator. 2242 * @throw UndefinedIteratorValue Raised if the element cannot be found 2243 */ 2244 template < typename Alloc > 2245 HashTableIteratorSafe(const HashTable< Key, Val, Alloc >& tab, Size ind_elt); 2246 2247 /** 2248 * @brief Copy constructor. 2249 * @param from the gum::HashTableIteratorSafe to copy. 2250 * @return This gum::HashTableIteratorSafe. 2251 */ 2252 HashTableIteratorSafe(const HashTableIteratorSafe< Key, Val >& from); 2253 2254 /** 2255 * @brief Copy constructor. 2256 * @param from the gum::HashTableIterator to copy. 2257 * @return This gum::HashTableIteratorSafe. 2258 */ 2259 explicit HashTableIteratorSafe(const HashTableIterator< Key, Val >& from); 2260 2261 /** 2262 * @brief Move constructor. 2263 * @param from The gum::HashTableIteratorSafe to move. 2264 * @return Returns this gum::HashTableIteratorSafe. 2265 */ 2266 HashTableIteratorSafe(HashTableIteratorSafe< Key, Val >&& from) noexcept; 2267 2268 /** 2269 * @brief Class destructor. 2270 */ 2271 ~HashTableIteratorSafe() noexcept; 2272 2273 /// @} 2274 // ============================================================================ 2275 /// @name Accessors / Modifiers 2276 // ============================================================================ 2277 /// @{ 2278 2279 /// Usefull Alias 2280 /// @{ 2281 using HashTableConstIteratorSafe< Key, Val >::key; 2282 using HashTableConstIteratorSafe< Key, Val >::val; 2283 using HashTableConstIteratorSafe< Key, Val >::clear; 2284 /// @} 2285 2286 /** 2287 * @brief Returns the mapped value pointed to by the iterator. 2288 * @return Returns the mapped value pointed to by the iterator. 2289 * @throws UndefinedIteratorValue Raised when the iterator does not point 2290 * to a valid hash table element. 2291 */ 2292 mapped_type& val(); 2293 2294 /// @} 2295 // ============================================================================ 2296 /// @name Operators 2297 // ============================================================================ 2298 /// @{ 2299 2300 /** 2301 * @brief Copy operator. 2302 * @param from The gum::HashTableIteratorSafe to copy. 2303 * @return Returns this gum::HashTableIterator. 2304 */ 2305 HashTableIteratorSafe< Key, Val >& operator=(const HashTableIteratorSafe< Key, Val >& from); 2306 2307 /** 2308 * @brief Copy operator. 2309 * @param from The gum::HashTableIterator to copy. 2310 * @return Returns this gum::HashTableIterator. 2311 */ 2312 HashTableIteratorSafe< Key, Val >& operator=(const HashTableIterator< Key, Val >& from); 2313 2314 /** 2315 * @brief Move operator. 2316 * @param from The gum::HashTableIteratorSafe to move. 2317 * @return Returns this gum::HashTableIterator. 2318 */ 2319 HashTableIteratorSafe< Key, Val >& operator=(HashTableIteratorSafe< Key, Val >&& from) noexcept; 2320 2321 /** 2322 * @brief Makes the iterator point to the next element in the hash table. 2323 * 2324 * @code 2325 * for (iter = hash.beginSafe (); iter != hash.endSafe (); ++iter) { } 2326 * @endcode 2327 * 2328 * The above loop is guaranteed to parse the whole hash table as long as no 2329 * element is added to or deleted from the hash table while being in the 2330 * loop. Deleting elements during the loop is guaranteed to never produce a 2331 * segmentation fault. 2332 * 2333 * @return This gum::HashTableIteratorSafe. 2334 */ 2335 HashTableIteratorSafe< Key, Val >& operator++() noexcept; 2336 2337 /** 2338 * @brief Makes the iterator point to i elements further in the hashtable. 2339 * @param i The number of increments. 2340 * @return Return this gum::HashTableIteratorSafe. 2341 */ 2342 HashTableIteratorSafe< Key, Val >& operator+=(Size i) noexcept; 2343 2344 /** 2345 * @brief Returns a new iterator pointing to i elements further in the 2346 * hashtable. 2347 * @param i The number of increments. 2348 * @return Returns this gum::HashTableIteratorSafe. 2349 */ 2350 HashTableIteratorSafe< Key, Val > operator+(Size i) const; 2351 2352 /** 2353 * @brief Checks whether two iterators are pointing toward different 2354 * elements. 2355 * @param from The gum::HashTableIteratorSafe to test for inequality. 2356 * @return Returns true if this and from are not equal. 2357 */ 2358 bool operator!=(const HashTableIteratorSafe< Key, Val >& from) const noexcept; 2359 2360 /** 2361 * @brief Checks whether two iterators are pointing toward equal 2362 * elements. 2363 * @param from The gum::HashTableIteratorSafe to test for equality. 2364 * @return Returns true if this and from are equal. 2365 */ 2366 bool operator==(const HashTableIteratorSafe< Key, Val >& from) const noexcept; 2367 2368 /** 2369 * @brief Returns the value pointed to by the iterator. 2370 * @return Returns the value pointed to by the iterator. 2371 * @throws UndefinedIteratorValue Raised when the iterator does not point 2372 * to a valid hash table element 2373 */ 2374 value_type& operator*(); 2375 2376 /** 2377 * @brief Returns the value pointed to by the iterator. 2378 * @return Returns the value pointed to by the iterator. 2379 * 2380 * @throws UndefinedIteratorValue Raised when the iterator 2381 * does not point to a valid hash table element. 2382 */ 2383 const value_type& operator*() const; 2384 2385 /// @} 2386 }; 2387 2388 // =========================================================================== 2389 // === UNSAFE HASH TABLES CONST ITERATORS === 2390 // =========================================================================== 2391 2392 /** 2393 * @class HashTableConstIterator 2394 * @headerfile hashTable.h <agrum/tools/core/hashTable.h> 2395 * @brief Unsafe Const Iterators for hashtables 2396 * @ingroup hashtable_group 2397 * 2398 * HashTableConstIterator provides a fast but unsafe way to parse HashTables. 2399 * They should @b only be used when parsing hashtables in which no element is 2400 * removed from the hashtable. Removing an element where the iterator points 2401 * to will mess the iterator as it will most certainly point to an 2402 * unallocated memory. So, this kind of iterator should only be used when 2403 * parsing "(key) constant" hash tables, e.g., when we wish to display the 2404 * content of a hash table or when we wish to update the mapped values of 2405 * some elements of the hash table without ever modifying their keys. 2406 * 2407 * Developers may consider using HashTable<x,y>::const_iterator instead of 2408 * HashTableConstIterator<x,y>. 2409 * 2410 * @par Usage example: 2411 * @code 2412 * // creation of a hash table with 10 elements 2413 * HashTable<int,string> table; 2414 * for (int i = 0; i< 10; ++i) 2415 * table.insert (i,"xxx" + string (i,'x')); 2416 * 2417 * // parse the hash table 2418 * for (HashTable<int,string>::const_iterator iter = table.cbegin (); 2419 * iter != table.cend (); ++iter) { 2420 * // display the values 2421 * cerr << "at " << iter.key() << " value = " << iter.val () << endl; 2422 * const HashTable<int,string>::value_type& elt = *iter; 2423 * const std::pair<const int, string>& xelt = *iter; 2424 * } 2425 * 2426 * // check whether two iterators point toward the same element 2427 * HashTable<int,string>::const_iterator iter1 = table1.cbegin(); 2428 * HashTable<int,string>::const_iterator iter2 = table1.cend(); 2429 * if (iter1 != iter) { 2430 * cerr << "iter1 and iter2 point toward different elements"; 2431 * } 2432 * 2433 * // make iter1 point toward nothing 2434 * iter1.clear (); 2435 * @endcode 2436 * 2437 * @tparam Key The gum::HashTable key. 2438 * @tparam Val The gum::HashTable Value. 2439 */ 2440 template < typename Key, typename Val > 2441 class HashTableConstIterator { 2442 public: 2443 /// Types for STL compliance. 2444 /// @{ 2445 using iterator_category = std::forward_iterator_tag; 2446 using key_type = Key; 2447 using mapped_type = Val; 2448 using value_type = std::pair< const Key, Val >; 2449 using reference = value_type&; 2450 using const_reference = const value_type&; 2451 using pointer = value_type*; 2452 using const_pointer = const value_type*; 2453 using difference_type = std::ptrdiff_t; 2454 /// @} 2455 2456 // ============================================================================ 2457 /// @name Constructors / Destructors 2458 // ============================================================================ 2459 /// @{ 2460 2461 /** 2462 * @brief Basic constructor: creates an iterator pointing to nothing. 2463 */ 2464 HashTableConstIterator() noexcept; 2465 2466 /** 2467 * @brief Constructor for an iterator pointing to the first element of a 2468 * hashtable. 2469 * @param tab The gum::HashTable to iterate over. 2470 * @tparam Alloc The gum::HashTable allocator. 2471 */ 2472 template < typename Alloc > 2473 HashTableConstIterator(const HashTable< Key, Val, Alloc >& tab) noexcept; 2474 2475 /** 2476 * @brief Constructor for an iterator pointing to the nth element of a 2477 * hashtable. 2478 * 2479 * The method runs in time linear to ind_elt. 2480 * 2481 * @param tab The hash table to which the so-called element belongs. 2482 * @param ind_elt The position of the element in the hash table (0 means 2483 * the first element). 2484 * @throw UndefinedIteratorValue Raised if the element cannot be found. 2485 */ 2486 template < typename Alloc > 2487 HashTableConstIterator(const HashTable< Key, Val, Alloc >& tab, Size ind_elt); 2488 2489 /** 2490 * @brief Copy constructor. 2491 * @param from The gum::HashTableConstIterator to copy. 2492 */ 2493 HashTableConstIterator(const HashTableConstIterator< Key, Val >& from) noexcept; 2494 2495 /** 2496 * @brief Move constructor. 2497 * @param from The gum::HashTableConstIterator to move. 2498 */ 2499 HashTableConstIterator(HashTableConstIterator< Key, Val >&& from) noexcept; 2500 2501 /** 2502 * @brief Class destructor. 2503 */ 2504 ~HashTableConstIterator() noexcept; 2505 2506 /// @} 2507 // ============================================================================ 2508 /// @name Accessors / Modifiers 2509 // ============================================================================ 2510 /// @{ 2511 2512 /** 2513 * @brief Returns the key corresponding to the element pointed to by the 2514 * iterator. 2515 * 2516 * @warning Using this method on an iterator that points to an element that 2517 * has been deleted will most certainly result in a segfault. If unsure, 2518 * use a safe iterator instead of an unsafe one. 2519 * 2520 * @return Returns the key corresponding to the element pointed to by the 2521 * iterator. 2522 */ 2523 const key_type& key() const; 2524 2525 /** 2526 * @brief Returns the mapped value pointed to by the iterator. 2527 * 2528 * @warning Using this method on an iterator that points to an element that 2529 * has been deleted will most certainly result in a segfault. If unsure, use 2530 * a safe iterator instead of an unsafe one. 2531 * 2532 * @return Returns the mapped value pointed to by the iterator. 2533 */ 2534 const mapped_type& val() const; 2535 2536 /** 2537 * @brief Makes the iterator point toward nothing (in particular, it is not 2538 * related anymore to its current hash table). 2539 */ 2540 void clear() noexcept; 2541 2542 /// @} 2543 // ============================================================================ 2544 /// @name Operators 2545 // ============================================================================ 2546 /// @{ 2547 2548 /** 2549 * @brief Copy operator. 2550 * @param from The gum::HashTableConstIterator to copy. 2551 * @return Returns this gum::HashTableConstIterator. 2552 */ 2553 HashTableConstIterator< Key, Val >& 2554 operator=(const HashTableConstIterator< Key, Val >& from) noexcept; 2555 2556 /** 2557 * @brief Move operator. 2558 * @param from The gum::HashTableConstIterator to move. 2559 * @return Returns this gum::HashTableConstIterator. 2560 */ 2561 HashTableConstIterator< Key, Val >& 2562 operator=(HashTableConstIterator< Key, Val >&& from) noexcept; 2563 2564 /// 2565 /** 2566 * @brief Makes the iterator point to the next element in the hash table. 2567 * 2568 * @code 2569 * for (iter = cbegin (); iter != cend(); ++iter ) { } 2570 * @endcode 2571 * 2572 * The above loop is guaranteed to parse the whole hash table as long as no 2573 * element is added to or deleted from the hash table while being in the 2574 * loop. 2575 * 2576 * @warning performing a ++ on an iterator that points to an element that 2577 * has been deleted will most certainly result in a segfault. 2578 * 2579 * @return Returns this gum::HashTableConstIterator. 2580 */ 2581 HashTableConstIterator< Key, Val >& operator++() noexcept; 2582 2583 /** 2584 * @brief Makes the iterator point to i elements further in the hashtable. 2585 * @param i The number of increments. 2586 * @return Returns this gum::HashTableConstIterator. 2587 */ 2588 HashTableConstIterator< Key, Val >& operator+=(Size i) noexcept; 2589 2590 /** 2591 * @brief Returns a new iterator pointing to i elements further in the 2592 * hashtable. 2593 * @param i The number of increments. 2594 * @return Returns a new iterator pointing to i elements further in the 2595 * hashtable. 2596 */ 2597 HashTableConstIterator< Key, Val > operator+(Size i) const noexcept; 2598 2599 /** 2600 * @brief Checks whether two iterators are pointing toward different 2601 * elements. 2602 * @param from The gum::HashTableConstIterator to test for inequality. 2603 * @return Returns true if this and from are not equal. 2604 */ 2605 bool operator!=(const HashTableConstIterator< Key, Val >& from) const noexcept; 2606 2607 /** 2608 * @brief Checks whether two iterators are pointing toward equal 2609 * elements. 2610 * @param from The gum::HashTableConstIterator to test for equality. 2611 * @return Returns true if this and from are equal. 2612 */ 2613 bool operator==(const HashTableConstIterator< Key, Val >& from) const noexcept; 2614 2615 2616 /** 2617 * @brief Returns the value pointed to by the iterator. 2618 * 2619 * @warning using this method on an iterator that points to an element that 2620 * has been deleted will most certainly result in a segfault. If unsure, 2621 * use a safe iterator instead of an unsafe one. 2622 * 2623 * @return Returns the value pointed to by the iterator. 2624 */ 2625 const value_type& operator*() const; 2626 2627 /// @} 2628 2629 protected: 2630 /** 2631 * Class HashTable must be a friend because it stores iterator end and this 2632 * one can be properly initialized only when the hashtable has been fully 2633 * allocated. Thus, proper initialization can only take place within the 2634 * constructor's code of the hashtable. 2635 * 2636 * @tparam K The gum::HashTable keys type. 2637 * @tparam V The gum::HashTable values type. 2638 * @tparam A The gum::HashTable allocator. 2639 */ 2640 template < typename K, typename V, typename A > 2641 friend class HashTable; 2642 2643 /// For the safe copy constructor and operator. 2644 friend class HashTableConstIteratorSafe< Key, Val >; 2645 2646 /// The hash table the iterator is pointing to. 2647 const HashTable< Key, Val >* _table_{nullptr}; 2648 2649 /** 2650 * @brief The index of the chained list pointed by the iterator in the 2651 * array of nodes of the hash table. 2652 */ 2653 Size _index_{Size(0)}; 2654 2655 /// The bucket in the chained list pointed to by the iterator. 2656 typename HashTable< Key, Val >::Bucket* _bucket_{nullptr}; 2657 2658 /** 2659 * @brief Returns the current iterator's bucket. 2660 * @return Returns the current iterator's bucket. 2661 */ 2662 typename HashTable< Key, Val >::Bucket* _getBucket_() const noexcept; 2663 2664 /** 2665 * @brief Returns the index in the hashtable's node vector pointed to by 2666 * the iterator. 2667 * @return Returns the index in the hashtable's node vector pointed to by 2668 * the iterator. 2669 */ 2670 Size _getIndex_() const noexcept; 2671 }; 2672 2673 // =========================================================================== 2674 // === UNSAFE HASH TABLES ITERATORS === 2675 // =========================================================================== 2676 2677 /** 2678 * @class HashTableIterator 2679 * @headerfile hashTable.h <agrum/tools/core/hashTable.h> 2680 * @brief Unsafe Iterators for hashtables 2681 * @ingroup hashtable_group 2682 * 2683 * HashTableIterator provides a fast but unsafe way to parse HashTables. 2684 * They should @b only be used when parsing hashtables in which no element is 2685 * removed from the hashtable. Removing an element where the iterator points 2686 * to will mess the iterator as it will most certainly point to an 2687 * unallocated memory. So, this kind of iterator should only be used when 2688 * parsing "(key) constant" hash tables, e.g., when we wish to display the 2689 * content of a hash table or when we wish to update the mapped values of 2690 * some elements of the hash table without ever modifying their keys. 2691 * 2692 * Developers may consider using HashTable<x,y>::iterator instead of 2693 * HashTableIterator<x,y>. 2694 * @par Usage example: 2695 * @code 2696 * // creation of a hash table with 10 elements 2697 * HashTable<int,string> table; 2698 * for (int i = 0; i< 10; ++i) 2699 * table.insert (i,"xxx" + string (i,'x')); 2700 * 2701 * // parse the hash table 2702 * for (HashTable<int,string>::iterator iter = table.begin (); 2703 * iter != table.end (); ++iter) { 2704 * // display the values 2705 * cerr << "at " << iter.key() << " value = " << iter.val () << endl; 2706 * HashTable<int,string>::value_type& elt = *iter; 2707 * std::pair<const int, string>& xelt = *iter; 2708 * } 2709 * 2710 * // check whether two iterators point toward the same element 2711 * HashTable<int,string>::iterator iter1 = table1.begin(); 2712 * HashTable<int,string>::iterator iter2 = table1.end(); 2713 * if (iter1 != iter) { 2714 * cerr << "iter1 and iter2 point toward different elements"; 2715 * } 2716 * 2717 * // make iter1 point toward nothing 2718 * iter1.clear (); 2719 * @endcode 2720 * 2721 * @tparam Key The gum::HashTable key. 2722 * @tparam Val The gum::HashTable Value. 2723 */ 2724 template < typename Key, typename Val > 2725 class HashTableIterator: public HashTableConstIterator< Key, Val > { 2726 public: 2727 /// types for STL compliance 2728 /// @{ 2729 using iterator_category = std::forward_iterator_tag; 2730 using key_type = Key; 2731 using mapped_type = Val; 2732 using value_type = std::pair< const Key, Val >; 2733 using reference = value_type&; 2734 using const_reference = const value_type&; 2735 using pointer = value_type*; 2736 using const_pointer = const value_type*; 2737 using difference_type = std::ptrdiff_t; 2738 /// @} 2739 2740 // ############################################################################ 2741 /// @name Constructors / Destructors 2742 // ############################################################################ 2743 /// @{ 2744 2745 /** 2746 * @brief Basic constructor: creates an iterator pointing to nothing. 2747 */ 2748 HashTableIterator() noexcept; 2749 2750 /** 2751 * @brief Constructor for an iterator pointing to the first element of a 2752 * hashtable. 2753 * @tparam Alloc The gum::HashTable allocator. 2754 * @param tab The gum::HashTable to iterate over. 2755 */ 2756 template < typename Alloc > 2757 HashTableIterator(const HashTable< Key, Val, Alloc >& tab) noexcept; 2758 2759 /// 2760 /** 2761 * @brief Constructor for an iterator pointing to the nth element of a 2762 * hashtable. 2763 * 2764 * The method runs in time linear to ind_elt. 2765 * 2766 * @tparam Alloc The gum::HashTable allocator. 2767 * @param tab The hash table to which the so-called element belongs. 2768 * @param ind_elt The position of the element in the hash table (0 means 2769 * the first element). 2770 * @throw UndefinedIteratorValue Raised if the element cannot be found. 2771 */ 2772 template < typename Alloc > 2773 HashTableIterator(const HashTable< Key, Val, Alloc >& tab, Size ind_elt); 2774 2775 /** 2776 * @brief Copy constructor. 2777 * @param from The gum::HashTableIterator to copy. 2778 */ 2779 HashTableIterator(const HashTableIterator< Key, Val >& from) noexcept; 2780 2781 /** 2782 * @brief Move constructor. 2783 * @param from The gum::HashTableIterator to move. 2784 */ 2785 HashTableIterator(HashTableIterator< Key, Val >&& from) noexcept; 2786 2787 /** 2788 * @brief Class destructor. 2789 */ 2790 ~HashTableIterator() noexcept; 2791 2792 /// @} 2793 // ============================================================================ 2794 /// @name Accessors / Modifiers 2795 // ============================================================================ 2796 /// @{ 2797 2798 /// Usefull alias. 2799 /// @{ 2800 using HashTableConstIterator< Key, Val >::key; 2801 using HashTableConstIterator< Key, Val >::val; 2802 using HashTableConstIterator< Key, Val >::clear; 2803 /// @} 2804 2805 /** 2806 * @brief Returns the mapped value pointed to by the iterator. 2807 * 2808 * @warning using this method on an iterator that points to an element that 2809 * has been deleted will most certainly result in a segfault. If unsure, 2810 * use a safe iterator instead of an unsafe one. 2811 * 2812 * @return Returns the mapped value pointed to by the iterator. 2813 */ 2814 mapped_type& val(); 2815 2816 /// @} 2817 // ============================================================================ 2818 /// @name Operators 2819 // ============================================================================ 2820 /// @{ 2821 2822 /** 2823 * @brief Copy operator. 2824 * @param from The gum::HashTableIterator to copy. 2825 * @return Returns this gum::HashTableIterator. 2826 */ 2827 HashTableIterator< Key, Val >& operator=(const HashTableIterator< Key, Val >& from) noexcept; 2828 2829 /** 2830 * @brief Move operator. 2831 * @param from The gum::HashTableIterator to move. 2832 * @return Returns this gum::HashTableIterator. 2833 */ 2834 HashTableIterator< Key, Val >& operator=(HashTableIterator< Key, Val >&& from) noexcept; 2835 2836 /** 2837 * @brief Makes the iterator point to the next element in the hash table. 2838 * 2839 * @code 2840 * for (iter = begin(); iter != end(); ++iter) { } 2841 * @endcode 2842 * 2843 * The above loop is guaranteed to parse the whole hash table as long as no 2844 * element is added to or deleted from the hash table while being in the 2845 * loop. 2846 * 2847 * @warning performing a ++ on an iterator that points to an element that 2848 * has been deleted will most certainly result in a segfault. 2849 * 2850 * @return Returns this gum::HashTableIterator. 2851 */ 2852 HashTableIterator< Key, Val >& operator++() noexcept; 2853 2854 /** 2855 * @brief Makes the iterator point to i elements further in the hashtable. 2856 * @param i The number of increments. 2857 * @return Returns this gum::HashTableIterator. 2858 */ 2859 HashTableIterator< Key, Val >& operator+=(Size i) noexcept; 2860 2861 /** 2862 * @brief Returns a new iterator. 2863 * @param i The number of increments. 2864 * @return Returns this gum::HashTableIterator. 2865 */ 2866 HashTableIterator< Key, Val > operator+(Size i) const noexcept; 2867 2868 /** 2869 * @brief Checks whether two iterators are pointing toward different 2870 * elements. 2871 * @param from The gum::HashTableIterator to test for inequality. 2872 * @return Returns true if this and from are not equal. 2873 */ 2874 bool operator!=(const HashTableIterator< Key, Val >& from) const noexcept; 2875 2876 /** 2877 * @brief Checks whether two iterators are pointing toward equal 2878 * elements. 2879 * @param from The gum::HashTableIterator to test for equality. 2880 * @return Returns true if this and from are equal. 2881 */ 2882 bool operator==(const HashTableIterator< Key, Val >& from) const noexcept; 2883 2884 /** 2885 * @brief Returns the value pointed to by the iterator. 2886 * 2887 * @warning using this method on an iterator that points to an element that 2888 * has been deleted will most certainly result in a segfault. If unsure, 2889 * use a safe iterator instead of an unsafe one. 2890 * 2891 * @return Returns the value pointed to by the iterator. 2892 */ 2893 value_type& operator*(); 2894 2895 /** 2896 * @brief Returns the value pointed to by the iterator. 2897 * 2898 * @warning using this method on an iterator that points to an element that 2899 * has been deleted will most certainly result in a segfault. If unsure, 2900 * use a safe iterator instead of an unsafe one. 2901 * 2902 * @return Returns the value pointed to by the iterator. 2903 */ 2904 const value_type& operator*() const; 2905 2906 /// @} 2907 }; 2908 2909 } // namespace gum 2910 2911 2912 #ifndef GUM_NO_EXTERN_TEMPLATE_CLASS 2913 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS 2914 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS 2915 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS 2916 extern template class gum::HashTable< int, int >; 2917 # endif 2918 # endif 2919 # endif 2920 #endif 2921 #ifndef GUM_NO_EXTERN_TEMPLATE_CLASS 2922 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS 2923 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS 2924 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS 2925 extern template class gum::HashTable< int, std::string >; 2926 # endif 2927 # endif 2928 # endif 2929 #endif 2930 #ifndef GUM_NO_EXTERN_TEMPLATE_CLASS 2931 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS 2932 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS 2933 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS 2934 extern template class gum::HashTable< std::string, std::string >; 2935 # endif 2936 # endif 2937 # endif 2938 #endif 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< std::string, int >; 2944 # endif 2945 # endif 2946 # endif 2947 #endif 2948 2949 2950 // always include the implementation of the templates 2951 #include <agrum/tools/core/hashTable_tpl.h> 2952 2953 #endif // GUM_HASHTABLE_H 2954