Using STL containers for multiple keys
===

I came across one requirement where the record is stored as

    Name :  Employee_Id  :  Address

where Name and Employee_Id are supposed to be keys that is, search function is to be provided on   
both Name and Employee Id.   
I can think of using a map to store this structure 

    std::map< std:pair<std::string,std::string> , std::string >  
    //      <         < Name   ,   Employee-Id> , Address     > 

but not exactly sure how the search function will look like (each record should be search-able on name and employee_id).

Please suggest some alternative design.