Reference as key in std::map

Question

Suppose some data structure:

typedef struct {
    std::string s;
    int i;
} data;

If I use the field data.s as key when adding instances of data in a map of type std::map<std::string&, data>, do the string gets copied? Is it safe to erase an element of the map because the reference will become invalid?

Also do the answers to these questions also apply to an unordered_map?

EDIT:

This is my current solution... but adding iterator to the map is UGLY:

typedef struct {
    const std::string* s;
    int i;
} data;

std::map<std::string, data> map;
typedef std::map<std::string, data>::iterator iterator;

// add an element to the map
iterator add_element(const std::string& s) {
    std::pair<iterator, bool> p = states.insert(std::make_pair(s, data()));
    iterator i = p.first;
    if(p.second) {
        data& d = (*i).second;
        d.s = &(*i).first;
    }
    return i;
}

Answer 1

You can't store references in Standard Library containers - your map should look like:

map <string,data> mymap;

The map will manage both the key string and the struct instances, which will be copies, for you. Both map an unordered_map work in the same way in this regard, as do all other Standard Library containers.

Note that in C++, you don't need typedefs to declare structs:

struct data {
    std::string s;
    int i;
};

Answer 2

You should use pointer in this case. With reference i'm not sure it'll be able to compile at all.

std::map<std::string * , data>

Deleting should not be a problem. String should not be copied. It'll probably work with reference too, but i never considered/tried such a usage.

Answer 3

You may want to take a look at boost.ref. It provides a wrapper that enables references to be used in STL-containers like this:

std::map<boost::reference_wrapper<std::string>, data>

Answer 4

You cannot use the reference. The map can copy the content. This is I guess implementation dependent.

But tested with the microsoft STL.

struct data
{
            data(data const& rhs)
            {
               a new object will be created here
            }
            std::string s;
            int i; 
};

Add some objects to the map and you will run into the copy constructor. This should invalidate your reference.

Answer 5

Hi, I don't think there's a big performance gain if you choose pointer instead of object. Only do this if you're managing data with lot of existing string objects which need to hold inside the container. Also the destruction of the objects has to be managed manually before destructing the container.