C++ lưu trữ một giá trị trong một cặp không có thứ tự

Question

Tôi muốn lưu trữ một giá trị dấu chấm động cho một cặp số nguyên không theo thứ tự. Tôi không thể tìm thấy bất kỳ loại hướng dẫn dễ hiểu nào cho việc này. Ví dụ: đối với cặp không có thứ tự {i,j} Tôi muốn lưu trữ một giá trị dấu phẩy động f. Làm cách nào để chèn, lưu trữ và truy xuất các giá trị như thế này?

Answer 1

Dưới đây là một số mã chỉ thị:

#include <iostream> 
#include <unordered_map> 
#include <utility> 

struct Hasher 
{ 
    int operator()(const std::pair<int, int>& p) const 
    { 
     return p.first^(p.second << 7)^(p.second >> 3); 
    } 
}; 

int main() 
{ 
    std::unordered_map<std::pair<int,int>, float, Hasher> m = 
    { { {1,3}, 2.3 }, 
     { {2,3}, 4.234 }, 
     { {3,5}, -2 }, 
    }; 

    // do a lookup 
    std::cout << m[std::make_pair(2,3)] << '\n'; 
    // add more data 
    m[std::make_pair(65,73)] = 1.23; 
    // output everything (unordered) 
    for (auto& x : m) 
     std::cout << x.first.first << ',' << x.first.second 
      << ' ' << x.second << '\n'; 
} 

Lưu ý rằng nó dựa trên quy ước mà bạn lưu trữ các cặp có thứ tự với số lượng thấp đầu tiên (nếu họ không bình đẳng). Bạn có thể thấy thuận tiện khi viết một hàm hỗ trợ nhận một cặp và trả về theo thứ tự đó, vì vậy bạn có thể sử dụng hàm đó khi chèn các giá trị mới trong bản đồ và khi sử dụng cặp làm khóa để tìm giá trị trong bản đồ.

Output:

4.234 
3,5 -2 
1,3 2.3 
65,73 1.23 
2,3 4.234 

Xem nó trên ideone.com. Nếu bạn muốn thực hiện hàm băm tốt hơn, chỉ cần tìm hiểu cách thực hiện hash_combine (hoặc sử dụng tăng) - nhiều câu hỏi ở đây về SO giải thích cách thực hiện điều đó cho std::pair<> s.

Answer 2

Bạn triển khai loại UPair với các yêu cầu và tình trạng quá tải ::std::hash (đây là dịp hiếm hoi mà bạn được phép thực hiện điều gì đó trong std).

#include <utility> 
#include <unordered_map> 

template <typename T> 
class UPair { 
    private: 
    ::std::pair<T,T> p; 
    public: 
    UPair(T a, T b) : p(::std::min(a,b),::std::max(a,b)) { 
    } 
    UPair(::std::pair<T,T> pair) : p(::std::min(pair.first,pair.second),::std::max(pair.first,pair.second)) { 
    } 
    friend bool operator==(UPair const& a, UPair const& b) { 
     return a.p == b.p; 
    } 
    operator ::std::pair<T,T>() const { 
     return p; 
    } 
}; 
namespace std { 
    template <typename T> 
    struct hash<UPair<T>> { 
    ::std::size_t operator()(UPair<T> const& up) const { 
     return ::std::hash<::std::size_t>()(
       ::std::hash<T>()(::std::pair<T,T>(up).first) 
      )^
      ::std::hash<T>()(::std::pair<T,T>(up).second); 
     // the double hash is there to avoid the likely scenario of having the same value in .first and .second, resulinting in always 0 
     // that would be a problem for the unordered_map's performance 
    } 
    }; 
} 

int main() { 
    ::std::unordered_map<UPair<int>,float> um; 
    um[UPair<int>(3,7)] = 3.14; 
    um[UPair<int>(8,7)] = 2.71; 
    return 10*um[::std::make_pair(7,3)]; // correctly returns 31 
} 

Answer 3

Cách đơn giản để xử lý có thứ tự cặp int được sử dụng để tạo ra std::minmax(i,j)std::pair<int,int>. Bằng cách này bạn có thể thực hiện lưu trữ của bạn như thế này:

std::map<std::pair<int,int>,float> storage; 
    storage[std::minmax(i,j)] = 0.f; 
    storage[std::minmax(j,i)] = 1.f; //rewrites storage[(i,j)] 

băm Phải thừa nhận rằng thích hợp sẽ cung cấp cho bạn một số hiệu năng cao hơn, nhưng có rất ít tác hại trong hoãn loại tối ưu hóa.