> Is there some way that this can interface with boost::shared_ptr/weak_ptr better?
> weak_key_map<int, int> m;
> boost::shared_ptr<int> k(new int(1));
> m.insert(std::make_pair(k,5));
>
> assert(*m.find(k) == 5);
>
> k.reset();
>
> assert(m.empty());

I'd also like that, but in this approach, I can't figure how to hook into the key shared_ptr deleter to have access to a notification of the smart_ptr deletion. I think we can currently get the current deleter of a shared_ptr, but we can't change it to combine it with another deleter.

I rather suspect that the data structure would need to be implemented from
scratch.  One of the nastier problems is how to deal with the case of:
iterator invalidation.  The safest solution is to make the presence of an
iterator to a particular element guarantee that the key continues to exist.

That's a good point ! To make a parallel with Python, the iteration seems to be an issue :

quote from Python doc
Note: Caution: Because a WeakValueDictionary is built on top of a Python dictionary, it must not change size when iterating over it. This can be difficult to ensure for a WeakValueDictionary because actions performed by the program during iteration may cause items in the dictionary to vanish "by magic" (as a side effect of garbage collection).

Reimplementing the whole map structure brings the task to another level of complexity...