Inserimento (stringa, oggetto *) nella tabella hash (C ++)

Question

Questa domanda è una conseguenza della mia domanda precedente sulla creazione di un hash tabella per memorizzare chiavi stringa e puntatori come dati. Ricevo un post-costruzione di errore seg quando provo ad aggiungere voci alla mia tabella hash. Sono ancora molto confuso su quale sintassi sia appropriata.

Attualmente ho (grazie ai precedenti poster):

// 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;

Nel mio costruttore di simulazione, ho:

// 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
  ....
}

Questo sembra funzionare bene. Ottengo un errore seg quando si tenta il seguente inserimento:

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();
  ....  
}

Lettura della terza nota sull'operatore [] nella documentazione SGI , sembra che dovrebbe andare bene. Cosa c'è che non va? Sto pensando di passare a un contenitore di mappe solo per risparmiare tempo di debug ...

Aggiorna

Qualcosa sull'inizializzazione sembra sbagliato. Quando arrivo a

strainTable[ mutantSeq ] = *mItr;

il debugger riporta " EXC_BAD_ACCESS " e passa a

_Node* __first = _M_buckets[__n];

di hashtable.h.

Answer 1

Come approccio diagnostico, in realtà hai 2 istruzioni eseguite sulla linea:

1. Cerca in strainTable , che restituisce un riferimento
2. Dereferenziazione dell'iteratore
3. Assegnazione di un valore al riferimento

Qui potresti voler adottare un approccio Divide and Conquer :

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

diventa

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

(che è un consiglio generale)

Su quale linea si verifica l'errore seg? Sarebbe possibile avere i primi 10 frame dello stack?

Mentre cercavo Google, ho trovato questa segnalazione di bug , il che suggerisce che potrebbero esserci problemi con hash_map ...

Potresti stare meglio usando unordered_map se possibile, poiché è chiaramente indicato che non verrà impiegato tempo per correggere il hsah_map visto come un contenitore legacy (e questo era il 2005 ...). Nota che dovrebbe essere disponibile se usi GCC 4.x (non sono sicuro per 3.x)

Il vantaggio principale è che la struttura hash e il predicato di confronto funzionano già per std :: string , quindi non è nemmeno necessario implementali tu stesso :)

Tutto ciò che devi fare, quindi, se hai questo nel tuo compilatore, è scrivere questo:

#include <tr1/unordered_map>

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

Answer 2

Non riesco a vedere nulla di male con questo codice. L'errore deve trovarsi in un altro posto. Forse il valore di (* mItr) - > getSequence (), che sta dando una stringa non valida, o qualcosa del genere.

Come ottimizzazione, l'operatore () potrebbe prendere const & amp; invece di solo stringhe.

Answer 3

L'imbarazzante "soluzione" è che ho scoperto di non aver dichiarato la dimensione completa di un array bidimensionale nel file di intestazione della classe. Quando ho inizializzato l'array nel costruttore, mi è capitato di sovrascrivere parte dello spazio per la tabella hash.

Grazie ai suggerimenti qui, ora sono passato a uno std :: tr1 :: unordered_map!