Avoid duplicating card key memory

Question

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

Is there a way to do this without having two copies of the std::string key (one belongs to the map, inside the content object)? Could there be a link to another?

Answer 1

Is it possible to use boost :: bimap? The following 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 did this is because it is dangerous. You must GUARANTEE that none of the std::string members will change, or the whole map becomes invalid. Interestingly, the first solution that comes to mind seems insanely hacked, and looks like UB, but I think that the UB skirt is very careful.

 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, it is clear that this craziness is close to UB, and is highly discouraged. Basically, during input / search, key points on your temporary object or input line, and then, as soon as the object is inserted / found, the key is changed to indicate the value contained in the string member, and until you never do nothing to invalidate the .c_str() return value on any contained person object, everything just works. I think.

Answer 3

Why don't you create two objects:

 std::set<std::string> wordSet; std::map<std::string*, T> yourMap; 

T should contain a pointer to std :: string, and yourMap should be a custom comparator. In addition, you can wrap it all in some class.

Answer 4

Both can be a reference to the same value. For instance:

 #include <stdio.h> #include <string> #include <map> struct xx { std::string mykey; int value; }; int main (int argc, char **argv) { std::string key1("the-key"); std::map<std::string, xx> map; map[key1].mykey = key1; map[key1].value = 13; std::string &lookup_key = map[key1].mykey; printf("%d\n", map[lookup_key].value); }