What you really want is a single copy of the data and multiple (optimized) search paths to that data, much like typical database systems. The common solution is to create a primary container that holds the data and then secondary containers providing iterators into the primary container:
Code:
// For example, a map
typedef map<string, long> DataMap;
typedef map<string, DataMap::iterator> StringKeyMap;
typedef map<long, DataMap::iterator> CostKeyMap;
DataMap Primary;
StringKeyMap StringSecondary;
CostKeyMap CostSecondary;
Or without STL assistance, a single balanced tree holding the data and N trees with pointers to the data instead of copies of the data (as you seemed to want before).