You could probably do a std::vector<std::pair<Key1, Key2>>, and use std::find_if(), with the predicate checking only first or only second of the pair element, returning a match for either one. It wouldn't be sorted for rapid searches, though.

But now that I think about it, you could just do std::find_if() on a std::map when you need by-value lookups, if you don't need it frequently.

You could either use a lambda to do your search, if you use C++11, or you could use a functor like this:

template<typename KeyType, typename ValueType>
class SearchByValue
{
public:
	SearchByValue(ValueType value) : value(value)
	{	}
	
	bool operator()(const std::pair<KeyType, ValueType> &pair)
	{
		//Return true if the pair's value matches our value.
		return (pair.second == this->value);
	}
	
private:
	ValueType value;
};
 
int main(int argc, char *argv[])
{
	typedef std::map<std::string, int>::iterator MyMapIterator;
	
	std::map<std::string, int> myMap;
	
	myMap["One"] = 1;
	myMap["Two"] = 2;
	myMap["Three"] = 3;
	
	MyMapIterator it = std::find_if(myMap.begin(), myMap.end(), SearchByValue<std::string, int>(2));
	
	if(it == myMap.end())
	{
		std::cout << "Couldn't find it!" << std::endl;
	}
	else
	{
		std::cout << "The returned key-value pair is: (\"" << it->first << "\", " << it->second << ")" << std::endl;
	}
					 
	return 0;
}

Result: The returned key-value pair is: ("Two", 2)

The templated functor I gave should work for most maps.

Here's a function wrapping it up every nicer (still avoiding C++11 lambda and auto, just incase you can't use them):

/*
	A functor for doing a reverse value-to-key lookup on a map.
	
	Example:
	typedef std::map<std::string, int>::iterator MyMapIterator;
	
	std::map<std::string, int> myMap;
	
	myMap["One"] = 1;
	myMap["Two"] = 2;
	myMap["Three"] = 3;
	
	MyMapIterator it = std::find_if(myMap.begin(), myMap.end(), SearchByValue<std::string, int>(2));
*/
template<typename KeyType, typename ValueType>
class SearchByValue
{
public:
	SearchByValue(const ValueType &value) : value(value)
	{	}
	
	bool operator()(const std::pair<KeyType, ValueType> &pair)
	{
		//Return true if the pair's value matches our value.
		return (pair.second == this->value);
	}
	
private:
	ValueType value;
};

//Searches a map by value to find the key.
//Example usage:
//		std::string key = SearchMapByValue(map, 357 /* value */, "fallback");
template<typename MapType>
const typename MapType::key_type &SearchMapByValue(const MapType &map, const typename MapType::mapped_type &valueToFind,
										const typename MapType::key_type &fallback = typename MapType::key_type())
{
	typename MapType::const_iterator it = std::find_if(map.begin(), map.end(), SearchByValue<typename MapType::key_type, typename MapType::mapped_type>(valueToFind));
	
	if(it == map.end())
		return fallback;
	
	return it->first;
}

And you can use it as a simple function call, and all the templated types are automaticly detected by the map passed in:

std::map<std::string, int> myMap;
	
myMap["One"] = 1;
myMap["Two"] = 2;
myMap["Three"] = 3;
	
std::cout << "The key is: \"" << SearchMapByValue(myMap, 2) << "\"" << std::endl;

Result: The key is: "Two"

Put in a stand-alone header file, all you have to do is call SearchMapByValue(myMap, 2) or SearchMapByValue(myMap, 2, "fallback") and it'll "just work" with any variable type in a map that handles equality. (Searching for floats wouldn't be a good idea, but even some complex classes that have operator == would be fine)