CODEWITHSUNDEEP
c++referencestdmap
Ben Voigt
Ben Voigt

Reputation: 283614

Avoid duplicate storage of map key

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?

Upvotes: 7

Views: 1565

Answers (4)

Mooing Duck
Mooing Duck

Reputation: 66922

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.

Upvotes: 2

Peter R
Peter R

Reputation: 2985

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";

}

Upvotes: 3

piotrekg2
piotrekg2

Reputation: 1257

Why don't you create two objects:

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

T must contain pointer to std::string, and yourMap needs custom comparator. Additionally you can wrap all these in some class.

Upvotes: 1

ash
ash

Reputation: 5155

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

#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);
}

Upvotes: -1

Related Questions