Inserting (string, object * ) into hash table (C++)

Question

This question is an offgrowth of my previous question on creating a hash table to store string keys and pointers as data. I'm getting a seg fault post-construction when I try to add entries to my hash table. I'm still very confused about what syntax is appropriate.

I currently have (thanks to previous posters):

// Simulation.h
#include <ext/hash_map>
using namespace __gnu_cxx;
...
typedef struct { size_t operator()( const string& str ) const 
  { return __gnu_cxx::__stl_hash_string( str.c_str() ); } } strhash;

struct eqstr {
  bool operator()(string s1, string s2) const {
   return ( s1.compare(s2) == 0 );
  }
};
....
hash_map< string, Strain *, strhash, eqstr > strainTable;

In my Simulation constructor, I have:

// Simulation.cpp
Simulation::Simulation() : ... {
  string MRCA;
  for ( int b = 0; b < SEQ_LENGTH; b++ ) {
    int randBase = rgen.uniform(0,NUM_BASES); 
    MRCA.push_back( BASES[ randBase ] );
  }
  Strain * firstStrainPtr;
  firstStrainPtr = new Strain( idCtr, MRCA, NUM_STEPS );
  strainTable[ MRCA ]= firstStrainPtr; // <-- Hash table initialization
  ....
}

This seems to work fine. I get a seg fault when the following insertion is attempted:

void Simulation::updateSimulation( double t ) {
   ....
   // Add mutants to liveStrains() and strainTable
   vector< Strain * >::const_iterator mItr = newMutants.begin();
   for ( mItr = newMutants.begin(); mItr != newMutants.end(); ++mItr ) // for each mutant in deme
{
  string mutantSeq = ( *mItr )->getSequence();
  cout << "mutantSeq is " << mutantSeq << endl; // <-- This is fine
  liveStrains.push_back( *mItr );
  strainTable[ mutantSeq ] = *mItr; // <-- Seg fault happens here
}
  newMutants.clear();
  ....  
}

Reading the third note on the operator[] in the SGI documentation, this seems like it should be fine. What's wrong? I'm thinking of switching to a map container just to save debugging time...

Update

Something about the initialization seems wrong. When I get to

strainTable[ mutantSeq ] = *mItr;

the debugger reports "EXC_BAD_ACCESS" and jumps to

_Node* __first = _M_buckets[__n];

of hashtable.h.

Answer 1

I can't see any bad with this code. The error has to have in another place. Maybe the value of (*mItr)->getSequence(), that is giving an invalid string, or something like that.

As an optimization, the operator() could take string const& instead of just string's.

Answer 2

As a diagnosis approach, you actually have 2 instructions executed on the line:

1. Lookup in strainTable, which returns a reference
2. Dereferencing the iterator
3. Assignation of a value to the reference

Here you might want to take a Divide and Conquer approach:

  strainTable[ mutantSeq ] = *mItr; // <-- Seg fault happens here

Becomes

  Strain*& aReference = strainTable[ mutantSeq ];
  Strain* const aPtr = *mItr;
  aReference = aPtr;

(which is a general advice)

On which line does the seg fault occur ? Would it be possible to have the 10 first frames of the stack ?

While looking up Google, I came up this bug report, which suggests there might be issues with the hash_map...

You might be better off using the unordered_map if possible, as it's clearly indicated that no time will be taken fixing the hsah_map viewed as a legacy container (and this was 2005...). Note that it should be available if you use GCC 4.x (not sure for 3.x)

The main advantage is that the hash structure and comparison predicate already work for std::string so you don't even have to implement them yourself :)

All you have to do, therefore, if you have this in your compiler, is to write this:

#include <tr1/unordered_map>

typedef std::tr1::unordered_map<std::string, Strain*> strain_hash_map;

Answer 3

The embarrassing "solution" is that I discovered I had not declared the full size of a two-dimensional array in the class header file. When I initialized the array in the constructor, it happened to overwrite some of the space for the hash table.

Thanks to the suggestions here, I've now moved to a std::tr1::unordered_map!