Geek Answers Handbook

Simple C ++ example hash_set

I am new to C ++ and STL. I adhere to the following simple example hash set storing user data structures:

#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); }

when I try to compile it, the following error message appears:

 /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

What am I doing wrong?

+6
c ++ stl hashset
source share
2 answers

So close! The last error in your output shows that your hash_trip program must be declared const:

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

You probably need to do the same for eq_trip . In addition, I would recommend passing arguments to these functions using a permalink to avoid an unnecessary copy of the data you pass in:

 size_t operator()(const trip& t) const // note the '&' { //... }
+8
source share

You should explore the use of the STL TR1 extension, namely

  • unordered_map
  • unordered_set
  • unordered_multimap
  • unordered_mutliset

Most modern C ++ compilers come with these extensions, so there is no need to use a non-standard class such as hash_set, etc.

+11
source share

More articles:


All Articles