C++ - Map of pairs - check if a pair with given first coordinate exists [duplicate]

This question already has an answer here:

• Finding any element with specific first coordinate in set<pair> > 2 answers

I'm holding a map sorted on std::pair<K, V>. (It's type is std::map<std::pair<K, V>, size_t>). I want to find ANY pair with given first coordinate (i.e. with K fixed, find if there is any object in map, with key of form std::pair<K, _>, I don't care about the second coordinate). Obviously it can be done in O(log n), as searching specific pair is also done in O(log n) [that's standard find() operation]. Is there some way to do that without having to write my own map from scratch?

One more thing - I can't change comparing function, as I want pairs like (1,2), (1,3) to be different, and if comparator compares keys only, it will treat them as equals. I want to preserve standard find() operation, as I need to use it as well.

Solution from duplicate link assumes that I know how minimum value of second coordinate looks like. I don't.