的std :: unordered_map - 專業KeyEqual和λ

Question

我想知道，如果它可以創建std::unordered_map類型的像這樣的變量：

std::unordered_map<std::weak_ptr<A>, B, std::hash<std::weak_ptr<A>, 
[](const std::weak_ptr<A>& lhs, const std::weak_ptr<B>& rhs) -> bool { return lhs.lock() == rhs.lock(); }> 

我希望它的工作，因爲KeyEqual模板只是希望一種正在實現()運算符的類型，但visual studio不會讓我編譯它，並說它缺少lambda所代表的類型。

Answer 1

首先，正如Richard Hodges在他的回答中所說的那樣，您不能使用std::weak_ptr作爲關鍵字，因爲它不穩定。忽略這一點，我們可以看一下一般問題：我們可以使用lambdas作爲模板參數嗎？

通用解決方案是按照the following answer中所述進行操作。有兩件事要注意

1. lambda必須單獨定義。
2. lambda必須作爲參數傳入。

2）的原因是從編譯器爲lambda創建的類型中刪除了默認構造函數。

對於std::set這並不壞，但考慮到其std::unordered_map沒有構造函數取一個鍵比較功能：

auto compare = [](const A & lhs, const A & rhs) { return lhs==rhs; }; 
std::unordered_map< 
    A, 
    B, 
    std::hash<A>, 
    decltype(compare) 
> map1{0, std::hash<A>{}, compare}; 

第一個參數是初始桶大小，並且是實現定義。我正在使用0，假設實現將在插入第一個項目時找到優化值。第二個是散列函數，最後是lambda。

我們可以通過用function<bool(A,A)>代替decltype(...)來改善它。這允許我們在頭中聲明類型，並將其傳遞給其他函數，而不需要共享實際的lambda。該宣言將成爲：

typedef std::unordered_map< 
      A, 
      B, 
      std::hash<A>, 
      std::function<bool(A,A)> 
    > custom_unordered_map; 

而且它可以如下使用：

custom_unordered_map map2{0, std::hash<A>{}, 
    [](const A & lhs, const A & rhs) { return lhs==rhs; } }; 

該解決方案將允許自定義的lambda表達式直接，也使用免費的功能。

該解決方案的主要優點是它允許使用不同的比較函數，但它使用起來非常冗長。

如果只需要一個單一的比較功能，一個更簡潔的解決方案（針對類型的用戶）是定義一個算符：

struct Compare { 
    bool operator() (const A & lhs, const A & rhs) { 
     return lhs==rhs; 
    } 
}; 

這然後可以在正常的方式使用：

std::unordered_map<A, B, std::hash<A>, Compare> map4; 

注：使用此解決方案可以使用默認構造函數。

下面是一個完整的例子：

#include <functional> 
#include <memory> 
#include <unordered_map> 

using A = int; 
using B = int; 



struct Compare { 
    bool operator() (const A & lhs, const A & rhs) { 
     return lhs==rhs; 
    } 
}; 

bool compare_func(const A & lhs, const A & rhs) { 
    return lhs==rhs; 
} 

int main() { 

    // Using lamda: default constructor is deleted, so the lambda 
    // must be passed as argument to the constructor. 
    auto compare = [](const A & lhs, const A & rhs) { return lhs==rhs; }; 
    std::unordered_map< 
     A, 
     B, 
     std::hash<A>, 
     decltype(compare) 
    > map1{0, std::hash<A>{}, compare}; 

    // Alternative: use std::function. More general, and allows any lambda to be used 
    typedef std::unordered_map< 
       A, 
       B, 
       std::hash<A>, 
       std::function<bool(A,A)> 
     > custom_unordered_map; 

    custom_unordered_map map2{0, std::hash<A>{}, 
     [](const A & lhs, const A & rhs) { return lhs==rhs; } }; 

    custom_unordered_map map3{0, std::hash<A>{}, compare_func}; 

    // Use of function class 
    std::unordered_map<A, B, std::hash<A>, Compare> map4; 
} 

這可以在Ubuntu 15.10使用命令g++ map_lambda.cpp --std=c++11 -o map_lambda進行編譯。

我的個人意見是使用最後的解決方案，除非需要使用不同的函數進行密鑰比較。

Answer 2

您必須在構造函數中定義lambda實現。 有例子如何做到這一點。

auto hash = std::unordered_map<std::string, int, std::hash<std::string>, std::function<bool(const std::string&, const std::string&) >>(0, std::hash<std::string>(), 
    [](const std::string& lhs, const std::string& rhs) 
    { 
     return lhs == rhs; 
    } 
); 

Answer 3

這是答案，恐怕你不會喜歡它。

你想要做的是不可能沒有邏輯錯誤。

（在這一點上，請閱讀下面的代碼的文本。這一點很重要！）

如果它可以工作，這將是這樣的......

#include <unordered_map> 
#include <string> 
#include <cstdint> 
#include <utility> 
#include <cassert> 

struct A {}; 
struct B{}; 

int main() 
{ 
    auto owner_equal = [](const auto& l, const auto& r) 
    { 
     return not l.owner_before(r) 
     and not r.owner_before(l); 
    }; 



    using equal_type = decltype(owner_equal); 

    std::unordered_map< 
    std::weak_ptr<A>, 
    B, 
    std::hash<std::weak_ptr<A>>, 
    equal_type> my_map; 

    auto pa = std::make_shared<A>; 
    my_map.emplace(pa, B{}); 
    auto wa = std::weak_ptr<A>(pa); 
    pa.reset(); 

    assert(my_map.find(wa) != my_map.end()); 
} 

所以有什麼問題 ？

你看我如何比較weak_ptr的平等嗎？這是知道他們是否指向同一個對象的唯一安全方法。你必須比較控制塊的地址。這是因爲，一旦插入到您的地圖中，最後的shared_ptr可能會消失。

下次您將weak_ptr鎖定在地圖的關鍵點以獲取對象地址時，您會得到nullptr。所以關鍵是不穩定，這是unordered_map的要求。

和？

計算散列具有相同的問題，但更糟。因爲您無法訪問控制塊的地址，只能訪問與其他控件相關的順序。

所以你不能可靠地計算一個weak_ptr的散列，因爲當你調用lock（）時，回答可能會在後續的兩次調用中有所不同。

真的沒有解決方案嗎？

絕對不是。 lock()解決方案似乎可以在測試中使用，但是當您的代碼達到生產時，它將隨機且無法解釋地失敗。

然後呢？

您必須使用std::map並接受O（logN）查找性能。