simple C++ hash_set example

Question

Sono nuovo di C++ e STL. Sono bloccato con il seguente semplice esempio di un hash set memorizzare strutture di dati personalizzati:

#include <iostream> 
#include <ext/hash_set> 

using namespace std; 
using namespace __gnu_cxx; 

struct trip { 
    int trip_id; 
    int delta_n; 
    int delta_secs; 

    trip(int trip_id, int delta_n, int delta_secs){ 
     this->trip_id = trip_id; 
     this->delta_n = delta_n; 
     this->delta_secs = delta_secs; 
    } 
}; 


struct hash_trip 
{ 
    size_t operator()(const trip t) 
    { 
     hash<int> H; 
     return H(t.trip_id); 
    } 
}; 

struct eq_trip 
{ 
    bool operator()(const trip t1, const trip t2) { 
     return (t1.trip_id==t2.trip_id) && 
     (t1.delta_n==t2.delta_n) && 
     (t1.delta_secs==t2.delta_secs); 
    } 
}; 

int main() 
{ 
    hash_set<trip, hash_trip, eq_trip> trips; 

    trip t = trip(3,2,-1); 
    trip t1 = trip(3,2,0); 

    trips.insert(t); 

} 

quando provo a compilare, ottengo il seguente messaggio di errore:

/usr/include/c++/4.2.1/ext/hashtable.h: In member function ‘size_t __gnu_cxx::hashtable<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>::_M_bkt_num_key(const _Key&, size_t) const [with _Val = trip, _Key = trip, _HashFcn = hash_trip, _ExtractKey = std::_Identity<trip>, _EqualKey = eq_trip, _Alloc = std::allocator<trip>]’: 
/usr/include/c++/4.2.1/ext/hashtable.h:599: instantiated from ‘size_t __gnu_cxx::hashtable<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>::_M_bkt_num(const _Val&, size_t) const [with _Val = trip, _Key = trip, _HashFcn = hash_trip, _ExtractKey = std::_Identity<trip>, _EqualKey = eq_trip, _Alloc = std::allocator<trip>]’ 
/usr/include/c++/4.2.1/ext/hashtable.h:1006: instantiated from ‘void __gnu_cxx::hashtable<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>::resize(size_t) [with _Val = trip, _Key = trip, _HashFcn = hash_trip, _ExtractKey = std::_Identity<trip>, _EqualKey = eq_trip, _Alloc = std::allocator<trip>]’ 
/usr/include/c++/4.2.1/ext/hashtable.h:437: instantiated from ‘std::pair<__gnu_cxx::_Hashtable_iterator<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>, bool> __gnu_cxx::hashtable<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>::insert_unique(const _Val&) [with _Val = trip, _Key = trip, _HashFcn = hash_trip, _ExtractKey = std::_Identity<trip>, _EqualKey = eq_trip, _Alloc = std::allocator<trip>]’ 
/usr/include/c++/4.2.1/ext/hash_set:197: instantiated from ‘std::pair<typename __gnu_cxx::hashtable<_Value, _Value, _HashFcn, std::_Identity<_Value>, _EqualKey, _Alloc>::const_iterator, bool> __gnu_cxx::hash_set<_Value, _HashFcn, _EqualKey, _Alloc>::insert(const typename __gnu_cxx::hashtable<_Value, _Value, _HashFcn, std::_Identity<_Value>, _EqualKey, _Alloc>::value_type&) [with _Value = trip, _HashFcn = hash_trip, _EqualKey = eq_trip, _Alloc = std::allocator<trip>]’ 
try.cpp:45: instantiated from here 
/usr/include/c++/4.2.1/ext/hashtable.h:595: error: passing ‘const hash_trip’ as ‘this’ argument of ‘size_t hash_trip::operator()(trip)’ discards qualifiers 

Che cosa sto facendo di sbagliato ?

Answer 1

Così vicino! L'ultimo errore in uscita rivela la tua hash_trip routine deve essere dichiarato const:

size_t operator()(const trip t) const // note the ending 'const' 
{ 
    //... 
} 

Avrete probabilmente bisogno di fare la stessa cosa per eq_trip. Inoltre, mi sento di raccomandare il passaggio degli argomenti a queste funzioni con riferimento costante al fine di evitare una copia inutile dei dati si sta passando:

size_t operator()(const trip& t) const // note the '&' 
{ 
    //... 
} 

Answer 2

si dovrebbe indagare utilizzando l'estensione TR1 del STL cioè

• unordered_map
• unordered_set
• unordered_multimap
• unordered_mutliset

maggior parte della nave compilatori C++ moderno con queste estensioni, quindi non v'è alcuna necessità di utilizzare una classe non standard come hash_set ecc

• http://en.wikipedia.org/wiki/Unordered_map_%28C%2B%2B_class%29
• http://publib.boulder.ibm.com/infocenter/comphelp/v9v111/index.jsp?topic=/com.ibm.xlcpp9.aix.doc/standlib/stl_unordered_map.htm
• http://www.cplusplus.com/reference/unordered_set/unordered_set/