When a `key/value` is inserted into a `std::map`, does it make its own copy of the objects?

Question

This is inspired by an Item in Effective C# first edition, warning about overriding GetHashCode() naively.

Sorry, I do not have supporting code. By the way, this is not a homework, I am just not that familiar with C++/STL, and could not find information regarding implementation.

Suppose I create my own class named person which has 3 public mutable string fields:

• First Name,
• Middle Initial
• Last Name

It also provides a less than operator to compare one person to another based on first name first, then middle name, and then the last name - that is all.

I create a map from person to int (say age), and fill it up with some 20 key/value pairs. I also store pointers to my keys in an array. I then change the first name of an object that say the fifth pointer points to, and try to look up a corresponding age using this modified key (remember the object is mutable and wide open).

Why did this happen?

A) Because the key used by std::map has not changed (was copied), and I changed my own copy and now my key is not found. But how can this be? I have not provided my own copy constructor. Perhaps a default one was created by the compiler?

B) The std::map collection is actually a Red-Black tree, and I happened to have a direct pointer to a key. When I have changed the key, I changed it directly in the node of a tree. Now it is likely that my node is not positioned correctly, and will not be found using a proper tree search algorithm. I should have deleted the node, then modified they key, and then re-inserted it again. If this is the case, then I suspect that STL collections in general are rather dangerous and cause noobs to make many mistakes.

C) Something else?

I would appreciate your insights.

Answer 1

When you use std containers all data is copied into the container. For maps this is no different.

One restriction that map places on the data is that the key is non mutable. Once it is inserted it is fixed to change the key you must find/erase and re-insert to change the value of the key.

struct Person
{
   std::string   first;
   std::string   middle;
   std::string   last;
   Person(std::string const& f, std::string const& s, std::string const& l) { BLABLA }
   bool operator<(Person const& rhs)                                        { return BLABLABLA;}
};
std::map<Person,int>   ageMap;

ageMap[Person("Tom", "Jones", "Smith")] = 68;
ageMap[Person("Tom", "I",     "Smith")] = 46;
ageMap[Person("Tom", "II",    "Smith")] = 24;

When you create your array of Person it will fail unless the array contains const pointers.

Person* pMap[3];
pMap[0] = &ageMap.begin().first;       // Fail need a const pointer.

Person const* pMapConst[3];
pMapConst[0] = &ageMap.begin().first;  // OK. Note a const pointer.

Answer 2

The entries always make a copy. If the key type is std::string, then, yes, that's a copy. (Behind the scenes, std::string does some optimizations so the characters aren't necessarily always copied, but that's besides the point.)

(I think there's no way to get a pointer into the map's objects, so you can't change that key, ever again, just get copies upon iteration or other retrieval.)

Now, if your key type is *std::string (a pointer!) then the bits in the pointer are copied, but if the value of the particular string instance is later changed, then the key will effectively be changed.

(And the comparator needs to be appropriate for your key type.)