I'd like to know if its possible to create a variable of type std::unordered_map like this:
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(); }>
I expected it to work, because the KeyEqual template just expects a type that is implementing the () operator, but visual studio won't let me compile it, saying it's missing a type where the lambda stands.
First, as Richard Hodges says in his answer, you can't use std::weak_ptras a key since it is not stable. Ignoring this, we can then look at the general question: Can we use lambdas for template parameters.
The generic solution is to do as described in the following answer. There are two things to notice
The reason for 2) is that the default constructor is removed from the type that the compiler creates for the lambda.
For std::set this is not to bad, but consider std::unordered_map which has no constructor taking a single key compare function:
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};
The first argument is the initial bucket size, and is implementation defined. I am using 0 assuming that the implementation will find an optimized value when the first item is inserted. The second is the hash function and finally the lambda.
We can improve it a bit by replacing the decltype(...) with function<bool(A,A)>. This allows us to declare the type in a header and therefore pass it to other functions without requiring the actual lambda to be shared. The declaration will become:
typedef std::unordered_map<
A,
B,
std::hash<A>,
std::function<bool(A,A)>
> custom_unordered_map;
And it can be used as follows:
custom_unordered_map map2{0, std::hash<A>{},
[](const A & lhs, const A & rhs) { return lhs==rhs; } };
This solution will allow custom lambdas to be used directly and also with free functions.
The main benefit with this solution is that it allows different compare functions to be used, but it is very verbose to use.
If only a single compare function is required, a less verbose solution (for the users of the type) is to define a functor:
struct Compare {
bool operator () (const A & lhs, const A & rhs) {
return lhs==rhs;
}
};
This can then be used in the normal way:
std::unordered_map<A, B, std::hash<A>, Compare> map4;
NOTE: With this solution the default constructor can be used.
The following is a full example:
#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;
}
This can be compiled on Ubuntu 15.10 using the command g++ map_lambda.cpp --std=c++11 -o map_lambda.
My personal opinion is to use the last solution, unless there is a need to use different functions for key comparison.
You have to define the lambda implementation in the constructor. There is example how to do this.
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;
}
);
Here's the answer, and I'm afraid you're not going to like it.
What you're trying to do is not possible to do without a logic error.
(at this point please read the text below the code. It's important!)
If it could work, it would be something like this...
#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());
}
so what's the problem ?
You see how I'm comparing equality of weak_ptr's? This is the only safe way to know if they're referring to the same object. You have to compare the address of the control blocks. This is because, once inserted into your map, the last shared_ptr could go away.
The next time you locked the weak_ptr in the map's key to get the object address, you'd get nullptr. So the key is not stable, which is a requirement for unordered_map.
and ?
Calculating a hash has the same problem, but even worse. Because you don't have access to the address of the control block, only its relative order in relation to others.
So you can't reliably compute a hash of a weak_ptr because when you call lock(), the answer might be different on two subsequent calls.
There's really no solution?
Absolutely not. The lock() solution will appear to work in testing, but when your code hits production, it will fail randomly and inexplicably.
Then what?
You must use a std::map and accept the O(logN) lookup performance.
