Làm cách nào để tìm kiếm một bản đồ :: bằng cách sử dụng một loại khóa khác

Question

Nếu tôi có std::map<X, Blah>, cách tốt nhất để tìm kiếm một mục phù hợp trong bản đồ bằng cách sử dụng phiên bản Y là gì?

Giả sử thông tin trong Y đủ để tìm duy nhất một số X, nhưng vì lý do hiệu suất tôi không muốn tạo phiên bản X bằng cách sao chép Y giá trị.

Tôi nhận ra mình có thể làm điều này bằng cách tạo một lớp cơ sở chung hoặc giao diện cho X và Y và làm cho khóa bản đồ, nhưng có cách nào khác không? ví dụ. tạo một số loại đối tượng so sánh?

Đây là đoạn mã mẫu cho rõ ràng:

class X 
{ 
public: 
    int id; 
    int subId; 
}; 

std::map<X, Details> detailsMap; 

class Y 
{ 
public: 
    int getId(); 
    int getSubId(); 
    int someOtherUnrelatedThings1; 
    int someOtherUnrelatedThings2; 
}; 

Bây giờ, nếu tôi có một thể hiện của Y, về nguyên tắc tôi sẽ có thể tìm thấy phù hợp với các mục trong bản đồ của tôi, vì tôi có thể nhận được một id và subId. Nhưng tôi có thể làm điều đó mà không cần tạo một thể hiện của X và sao chép trên id và subId?

Answer 1

Với C++ 14, bạn có thể sử dụng tra cứu không đồng nhất.

Nếu bạn muốn tìm yếu tố có quan trọng mà so sánh tương đương cho lập luận của std::map::find, bạn nên cung cấp một sánh như một tham số mẫu thứ ba mà cần phải có Comparator::is_transparent ký hiệu là một loại. Nó cũng phải chứa bool operator() so sánh khóa bản đồ của bạn với bất kỳ loại nào khác mà bạn muốn.

mô tả vui sang một bên, đây là một ví dụ:

struct X 
{ 
    int id; 
    int subid; 
}; 

struct Details {}; 

struct Comparator 
{ 
    using is_transparent = std::true_type; 

    // standard comparison (between two instances of X) 
    bool operator()(const X& lhs, const X& rhs) const { return lhs.id < rhs.id; } 

    // comparison via id (compares X with integer) 
    bool operator()(const X& lhs, int rhs) const { return lhs.id < rhs; } 
    bool operator()(int lhs, const X& rhs) const { return lhs < rhs.id; } 

    // Same thing with Y 
    bool operator()(const X& lhs, const Y& rhs) const { return lhs.id < rhs.getId(); } 
    bool operator()(const Y& lhs, const X& rhs) const { return lhs.getId() < rhs.id; } 
}; 

int main() 
{ 
    std::map<X, Details, Comparator> detailsMap = { 
     { X{1, 2}, Details{} }, 
     { X{3, 4}, Details{} }, 
     { X{5, 6}, Details{} } 
    }; 

    // it1 and it2 point to the same element. 
    auto it1 = detailsMap.find(X{1, 2}); 
    auto it2 = detailsMap.find(1); 

    std::cout << detailsMap.size() << std::endl; 
    std::cout << std::boolalpha << (it1 == detailsMap.end()) << std::endl; // false 
    std::cout << std::boolalpha << (it1 == it2) << std::endl; // true 
} 

Lưu ý tuy nhiên đó GCC didin't thực hiện nó cho đến khi sửa đổi 219888.

Answer 2

C++ 14 đã thêm is_transparent hỗ trợ cho map đặt hàng.

struct compare_helper { 
    X const* px = nullptr; 
    Y const* py = nullptr; 
    compare_helper(compare_helper&&)=default; 
    compare_helper(X const& x):px(&x) {} 
    compare_helper(Y const& y):py(&y) {} 
    explicit operator bool()const{return px&&py;} 
    friend bool operator<(compare_helper&& lhs, compare_helper&& rhs) { 
    if (!lhs || !rhs) { 
     return !rhs < !lhs; 
    } 
    // TODO: compare lhs and rhs based off px and py 
    } 
}; 
struct ordering_helper { 
    using is_transparent=std::true_type; 
    bool operator()(compare_helper lhs, compare_helper rhs)const{ 
    return std::move(lhs)<std::move(rhs); 
    } 
}; 

nay xác định lại bạn std::map:

std::map<X, Details, ordering_helper> detailsMap; 

và bạn đã làm xong. Bây giờ, bạn có thể chuyển số Y const& đến detailsMap.find hoặc bất kỳ thứ gì.

Hiện tại // TODO: compare lhs and rhs based off px and py hơi khó chịu.

Nhưng nó phải ghi được.

Nếu bạn cần nhiều lớp khác nhau để có thể so sánh với X và bạn cần một lớp học lớn compare_helper với mỗi lần lưu hoặc bạn cần phải xóa thao tác bằng cách nào đó.

Về cơ bản, compare_helper cần lưu trữ con trỏ đến X hoặc std::function< int(X const&) > cho bạn biết nếu X nhỏ hơn, bằng hoặc lớn hơn thông số khác. (bạn sẽ thấy điều này không thành công khi so sánh số Y với số Y hoặc Z đối với số Y - trong trường hợp đó, trả về false phải an toàn, vì bạn sẽ chỉ thấy một số không X trong tìm kiếm bản đồ nhất định).

Chúng ta có thể tách này từ định nghĩa của compare_helper với một số ADL:

struct compare_helper { 
    X const* px = nullptr; 
    using f_helper = std::function< int(X const&) >; 
    f_helper not_X; 
    compare_helper(compare_helper&&)=default; 
    compare_helper(X const& x):px(std::addressof(x)) {} 
    template<class NotX, 
    class=std::enable_if_t< std::is_convertible< 
     decltype(compare_with_X(std::forward<NotX>(notx))) 
     , f_helper 
    >{} 
    > 
    compare_helper(NotX&& notx): 
    not_X(compare_with_X(std::forward<NotX>(notx))) 
    {} 
    explicit operator bool()const{return px&&not_X;} 
    friend bool operator<(compare_helper&& lhs, compare_helper&& rhs) { 
    if (!lhs || !rhs) { 
     return !rhs < !lhs; 
    } 
    if (lhs.px && rhs.px) { return *lhs.px < *rhs.px; } 
    if (lhs.px && rhs.not_X) { return rhs.not_X(*lhs.px) < 0; } 
    if (lhs.not_X && rhs.px) { return lhs.not_X(*rhs.px) > 0; } 
    else return false; 
    } 
}; 

nay là người dùng cuối chỉ đơn giản là phải ghi đè lên các chức năng miễn phí compare_with_X trong không gian tên của các loại bạn muốn so sánh với X để trả về số std::function<int(X const&)> và bản đồ ở trên cho phép tra cứu từ loại không thuộc loại X của bạn.

Answer 3

Không có cách nào để sử dụng find của map với loại dữ liệu khác. Nhưng dừng lại ngay bây giờ. Bạn có thực sự đo rằng việc tạo một X có phải là sự cố không? Do đó, getId và getSubId là không có khả năng trình biên dịch sẽ không thể cho biết liệu chúng có tác dụng phụ hay phải tiếp tục gọi chúng, làm cho việc tạo tạm thời X thực sự nhanh hơn.

Câu trả lời rõ ràng ở đây là chỉ cần tạo X và thực hiện theo cách hiển nhiên cho đến khi đo chỉ ra cách khác.