Containers for multi-criteria lookups

Consider a collection of objects of type PersonEntry, as defined in the following code:

 1 struct PersonEntry
 2 {
 3   std::string name;
 4   std::string phoneNumber;
 5   std::string city;
 6 };

An object of this type represents an entry in a telephone directory perhaps. How would you design a data structure that allows you to look up a person by name? We can use a std::set of PersonEntry objects for it, with an appropriate ordering relation defined for PersonEntry. Since we want to search by name, we should define the ordering relationship by name:

 1 bool operator<(const PersonEntry& left, 
 2                const PersonEntry& right) {
 3   return left.name< right.name;
 4 }

Now std::set stores only unique elements and any two PersonEntry objects with the same name would be considered duplicates. Since namesakes are common in real life, we should choose a container that allows duplicates, that is, std::multiset. We can then insert elements...