smatskevich

HashTableOnForwardList

Apr 1st, 2018
235
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <algorithm>
  2. #include <assert.h>
  3. #include <iostream>
  4. #include <forward_list>
  5. #include <string>
  6. #include <vector>
  7.  
  8. using std::string;
  9.  
  10. class CStringHashTable {
  11. public:
  12.     explicit CStringHashTable( int initialSize );
  13.  
  14.     // Проверка наличия элемента.
  15.     bool Has( const string& key ) const;
  16.     // Добавление. Дубли не добавляет. Если элемента нет, то возвращает false.
  17.     bool Add( const string& key );
  18.     // Удаление. Если элемента не было, возвращает false.
  19.     bool Remove( const string& key );
  20.  
  21. private:
  22.     std::vector<std::forward_list<string>> table;
  23. };
  24.  
  25. CStringHashTable::CStringHashTable( int initialSize ) :
  26.     table( initialSize )
  27. {
  28. }
  29.  
  30. bool CStringHashTable::Has( const string& key ) const
  31. {
  32.     // Получим хеш в диапазоне [0, m).
  33.     const int hash = std::hash<string>()( key ) % table.size();
  34.     // Ищем в нужном списке.
  35.     const std::forward_list<string>& list = table[hash];
  36.     return std::find( list.begin(), list.end(), key ) != list.end();
  37. }
  38.  
  39. bool CStringHashTable::Add( const string& key )
  40. {
  41.     // Получим хеш в диапазоне [0, m).
  42.     const int hash = std::hash<string>()( key ) % table.size();
  43.     // Ищем в нужном списке.
  44.     std::forward_list<string>& list = table[hash];
  45.     if( std::find( list.begin(), list.end(), key ) != list.end() ) {
  46.         return false;
  47.     }
  48.     list.push_front( key );
  49.     return true;
  50. }
  51.  
  52. bool CStringHashTable::Remove( const string& key )
  53. {
  54.     // Получим хеш в диапазоне [0, m).
  55.     const int hash = std::hash<string>()( key ) % table.size();
  56.     // Ищем в нужном списке.
  57.     std::forward_list<string>& list = table[hash];
  58.     if( std::find( list.begin(), list.end(), key ) == list.end() ) {
  59.         return false;
  60.     }
  61.     // Удаление. Здесь не эффективно - поиск элемента выполняется второй раз.
  62.     list.remove( key );
  63.     return true;
  64. }
  65.  
  66. int main()
  67. {
  68.     CStringHashTable hashTable( 8 );
  69.  
  70.     char command = 0;
  71.     string key;
  72.     while( std::cin >> command >> key ) {
  73.         switch( command ) {
  74.         case '?':
  75.             std::cout << ( hashTable.Has( key ) ? "OK" : "FAIL" ) << std::endl;
  76.             break;
  77.         case '+':
  78.             std::cout << ( hashTable.Add( key ) ? "OK" : "FAIL" ) << std::endl;
  79.             break;
  80.         case '-':
  81.             std::cout << ( hashTable.Remove( key ) ? "OK" : "FAIL" ) << std::endl;
  82.             break;
  83.         default:
  84.             assert( false );
  85.         }
  86.     }
  87.     return 0;
  88. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×