Thread: hash function insert problems

  1. #1
    Registered User
    Join Date
    Apr 2008
    Location
    New York
    Posts
    9

    hash function insert problems

    I am trying to implement the insert function, which inserts a new value into a hash table.
    I am getting a compile error though which doesn't make sense to me.

    To outline my data structure, I have a hash_set which includes a vector<HashNode*> m_table. Each HashNode is constructed like a node in a doubly linked list, so each HashNode has a 'next' and 'prev' where the end node points to 0.

    My compilation error is this.

    Code:
    hash_set.h: In member function ‘std::pair<hash_set<KeyType, HashFunc>::iterator, bool> hash_set<KeyType, HashFunc>::insert(const KeyType&)’:
    hash_set.h:185: error: name lookup of ‘pt’ changed for new ISO ‘for’ scoping
    hash_set.h:181: error:   using obsolete binding at ‘pt’

    And here is my code.

    Code:
    //  Insert the key if it is not already there.
      std::pair< iterator, bool > insert( KeyType const& key )
      {
        const float LOAD_FRACTION_FOR_RESIZE = 1.25;
    
        //  Resize if necessary.
        if ( m_size >= LOAD_FRACTION_FOR_RESIZE * m_table.size() )
          this->resize_table( 2*m_table.size()+1 );  // making the new and old sizes relatively prime breaks up clusters
    
    
        if (find(key)==end()) 
          return std::make_pair(end(),false);
        else {
    
          unsigned int hash_value = m_hash(key);
          unsigned int index = hash_value%m_table.size();
          
          for (HashNode* pt = m_table[index];pt->next;pt=pt->next) {
    	if (pt->key == key)
    	  return std::make_pair(iterator(this,index,pt),false);
          }
          pt->key=key;
          return std::make_pair(iterator(this,index,pt),true);
        }
      }

  2. #2
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    > pt->key=key;
    > return std::make_pair(iterator(this,index,pt),true);
    pt is no longer in scope at this point, as it was declared within the above for-loop.

  3. #3
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    If you declare a variable in the for-loop intializer like the red bit, then you should not be using it after the end of the for-loop like the green bits:
    Code:
          for (HashNode* pt = m_table[index];pt->next;pt=pt->next) {
    	if (pt->key == key)
    	  return std::make_pair(iterator(this,index,pt),false);
          }
          pt->key=key;
          return std::make_pair(iterator(this,index,pt),true);
    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  4. #4
    Registered User
    Join Date
    Apr 2008
    Location
    New York
    Posts
    9
    how should I move to the end of the list to add a value then? I need to add the value at the end of the list if it doesn't find it. So basically it needs to add a value to pt after the for loop because pt moves to the end of the list.

    I changed my code to this below which compiles and I believe it should work. When I ran some test code, I could not access .second for the pair returned. Do my return statements look correct? For some reason the bool at the end is not accessible.

    The function returns a pair<iterator,bool>


    Code:
    for (HashNode* pt = m_table[index];pt->next;pt=pt->next) {
    	if (pt->key == key)
    	  return std::make_pair(iterator(this,index,pt),false);
            else if (!pt->next) {
              pt->next->key=key;
              return std::make_pair(iterator(this,index,pt),true);
             }
          }
          pt->key=key;
          return std::make_pair(iterator(this,index,pt),true);

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    No, move the HashNode *pt out of the for() statement - just before it is fine.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  6. #6
    Registered User
    Join Date
    Apr 2008
    Location
    New York
    Posts
    9
    Thanks! I got it!
    All good now with slight modifications.

    Thanks again

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Compiling sample DarkGDK Program
    By Phyxashun in forum Game Programming
    Replies: 6
    Last Post: 01-27-2009, 03:07 AM
  2. Hash function for two numbers
    By Sfel in forum C Programming
    Replies: 10
    Last Post: 03-29-2008, 04:55 PM
  3. Group Project Help/Volunteer
    By DarkDot in forum C++ Programming
    Replies: 3
    Last Post: 04-24-2007, 11:36 PM
  4. <Gulp>
    By kryptkat in forum Windows Programming
    Replies: 7
    Last Post: 01-14-2006, 01:03 PM
  5. Big problems with the Text function
    By GaPe in forum C Programming
    Replies: 26
    Last Post: 05-22-2002, 10:42 AM