Avoid duplicate storage of map key

Question

Let's say I have a std::map<std::string, T> (or unordered_map) and I want to access the key from an iterator/reference/pointer to the content.

Is there a way to do that without having two copies of the std::string key (one owned by the map, one inside the content object)? Can one be a reference to the other?

Answer 1

Would you consider using boost::bimap? Below is a simple example:

#include <boost/bimap.hpp>
#include <string>
struct Person
{
    Person()
    {}
    Person(const std::string& f, const std::string& l, int a) : first(f), last(l), age(a)
    {}
    std::string first;
    std::string last;
    int age;
};

bool operator <(const Person& lhs, const Person& rhs)
{
    if(lhs.last < rhs.last)
        return true;
    return false;
}

std::ostream& operator << (std::ostream& os, const Person& p)
{
    os << "First Name: " << p.first << " Last Name: " << p.last << " Age: " << p.age;
    return os;
}

int main() 
{
    typedef boost::bimap<std::string, Person> people;
    typedef people::value_type value;

    people m;
    m.insert(value("12345",Person("fred", "rabbit", 10)));
    m.insert(value("67890",Person("benjamin", "bunny", 12)));

    Person p = m.left.at("12345");
    std::cout << "Person with serial no. 12345 is: " << p << "\n";
    std::cout << "Serial number of " << p << " is: " << m.right.at(p) << "\n";

}

Answer 2

The reason they made this hard is because it's dangerous. You have to GUARANTEE that none of the std::string members being key'd off of will never change value, or the whole map becomes invalidated. Interesting, the first solution that comes to mind appears insanely hackish, and looks like UB, but I believe I very carefully skirt the UB.

struct key_type {
    mutable const char* ptr;    
};
bool operator<(const key_type& lhs, const key_type& rhs)
{return strcmp(lhs.ptr, rhs.ptr)<0;}

struct person {
    std::string name;
    int age;
};
person& people_map_get(std::map<key_type, person>& map, const char* name) {
    auto it = map.insert(name, person{name}).first; //grab, possibly insert
    if->first.ptr = it->second.name.c_str(); //in case of insert, fix ptr
    return it->second;
}
person& people_map_assign(std::map<key_type, person>& map, person p) {
    auto pair = map.insert(name, p); //grab, possibly insert
    auto it = pair.first;       
    if (pair.second == false) 
        it->second = std::move(p);
    if->first.ptr = it->second.name.c_str(); //ptr probably invalidated, so update it
    return it->second;
}

int main() {
    std::map<key_type, person> people;
    people_map_assign(people, person{"ted"});
    person frank = people_map_get(people, "frank");
}

As I hope is clear, this is crazy close to UB, and very much not recommended. Basically, during an insert/find, the key points at your temporary object or input string, and then as soon as the object is inserted/found, the key is changed to point at the value contained in the string member, and as long as you never do anything that would invalidate the return value of .c_str() on any contained person object, everything just barely works. I think.