Unique index in C++ map but custom sorting

Unique index in C++ map but custom sorting

I have a custom key for a std::map like that:
struct Foo
{
Foo(int _uid, int _priority) : unique_id(_uid), priority(_priority) {}
bool operator<(const Foo& other) const {
return priority < other.priority;
}
int unique_id;
int priority;
};
I'm creating the map with this code:
std::map <Foo, int> bla;
And this is how I am inserting items:
bla.insert(std::pair<Foo, int> (Foo(1,2), 3) )
This works fine, and the sorting works too. But my problem is, how can I
find an item only by the unique_id? The find function requires a Foo, and
this requires a priority, which I don't have when I query it.
I would more like to store the priority in the value (not as the key), but
I don't know how I can sort by value then. Is a std::map the right
class/template for that?