Ví dụ đơn giản C++ hash_set

Question

Tôi mới dùng C++ và STL. Tôi đang mắc kẹt với các ví dụ đơn giản sau đây của một hash thiết lập lưu trữ cấu trúc dữ liệu tùy chỉnh:

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

} 

khi tôi cố gắng để biên dịch nó, tôi nhận được thông báo lỗi sau:

/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 

Tôi đang làm gì sai ?

Answer 1

Rất gần! Các lỗi cuối cùng trong đầu ra của bạn tiết lộ thói quen hash_trip của bạn cần được khai báo const:

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

Có thể bạn sẽ cần phải làm điều tương tự cho eq_trip. Ngoài ra, tôi muốn giới thiệu thông qua các đối số cho các chức năng này bằng cách tham chiếu liên tục để tránh một bản sao không cần thiết của các dữ liệu bạn đang đi qua:

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

Answer 2

Bạn nên điều tra sử dụng phần mở rộng TR1 của STL cụ thể là

• unordered_map
• unordered_set
• unordered_multimap
• unordered_mutliset

Hầu hết C hiện đại trình biên dịch ++ tàu với các phần mở rộng, do đó không có nhu cầu sử dụng một lớp phi tiêu chuẩn như hash_set, vv

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