Làm thế nào để đặt các cặp số nguyên không theo thứ tự trong C++?

Question

Chương trình không biên dịch một tập hợp các cặp số nguyên không theo thứ tự, nhưng nó cho các số nguyên. Có thể unordered_set và các hàm thành viên của nó được sử dụng trên các kiểu do người dùng định nghĩa và làm cách nào để xác định nó?

#include <unordered_set> 
... 

class A{ 
... 
private: 
std::unordered_set< std::pair<int, int> > u_edge_; 
}; 

error: no matching function for call to 'std::unordered_set<std::pair<unsigned int, unsigned int> >::unordered_set()' 

Answer 1

Mã của bạn biên dịch trên VS2010 SP1 (VC10), nhưng không thể biên dịch bằng GCC g ++ 4.7.2.

Tuy nhiên, bạn có thể muốn xem xét boost::hash từ Boost.Functional để băm std::pair (với bổ sung này, mã của bạn cũng biên dịch bằng g ++).

#include <unordered_set> 
#include <boost/functional/hash.hpp> 

class A 
{ 
private: 
    std::unordered_set< 
     std::pair<int, int>, 
     boost::hash< std::pair<int, int> > 
    > u_edge_; 
}; 

Answer 2

Bạn đang thiếu hàm băm cho std::pair<int, int>>. Ví dụ,

struct bad_hash 
{ 
    std::size_t operator()(const std::pair<int,int>& p) const 
    { 
    return 42; 
    } 
}; 

.... 

std::unordered_set< std::pair<int, int>, bad_hash> u_edge_; 

Bạn cũng có thể chuyên std::hash<T> cho std::hash<std::pair<int,int>>, trong trường hợp này bạn có thể bỏ qua các tham số mẫu thứ hai.

Answer 3

Vấn đề là std::unordered_set đang sử dụng mẫu std::hash để tính toán băm cho các mục nhập của nó và không có chuyên môn nào cho các cặp. Vì vậy, bạn sẽ phải làm hai việc:

1. Quyết định hàm băm nào bạn muốn sử dụng.
2. Chuyên biệt std::hash cho loại khóa của bạn (std::pair<int, int>) bằng cách sử dụng chức năng đó.

Dưới đây là một ví dụ đơn giản:

#include <unordered_set> 

namespace std { 
template <> struct hash<std::pair<int, int>> { 
    inline size_t operator()(const std::pair<int, int> &v) const { 
     std::hash<int> int_hasher; 
     return int_hasher(v.first)^int_hasher(v.second); 
    } 
}; 

} 

int main() 
{ 
    std::unordered_set< std::pair<int, int> > edge; 
} 

Answer 4

Bạn cần cung cấp một chuyên môn hóa cho std::hash<> làm việc với std::pair<int, int>. Dưới đây là một ví dụ rất đơn giản về cách bạn có thể xác định chuyên môn:

#include <utility> 
#include <unordered_set> 

namespace std 
{ 
    template<> 
    struct hash<std::pair<int, int>> 
    { 
     size_t operator() (std::pair<int, int> const& p) 
     { 
      // A bad example of computing the hash, 
      // rather replace with something more clever 
      return (std::hash<int>()(p.first) + std::hash<int>()(p.second)); 
     } 
    }; 
} 

class A 
{ 
private: 
    // This won't give you problems anymore 
    std::unordered_set< std::pair<int, int> > u_edge_; 
}; 

Answer 5

Không có cách tính chuẩn nào để tính toán băm trên một cặp. Thêm định nghĩa này để tập tin của bạn:

struct pair_hash { 
    inline std::size_t operator()(const std::pair<int,int> & v) const { 
     return v.first*31+v.second; 
    } 
}; 

Bây giờ bạn có thể sử dụng nó như thế này:

std::unordered_set< std::pair<int, int>, pair_hash> u_edge_; 

này hoạt động, bởi vì pair<T1,T2> định nghĩa bình đẳng. Đối với các lớp tùy chỉnh không cung cấp một cách để kiểm tra sự bình đẳng, bạn có thể cần phải cung cấp một hàm riêng biệt để kiểm tra xem hai cá thể có bằng nhau hay không.

Tất nhiên, giải pháp này được giới hạn ở một cặp hai số nguyên. Đây là a link to an answer giúp bạn xác định cách tổng quát hơn để tạo băm cho nhiều đối tượng.