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

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 ha开发者_StackOverflow中文版s 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.

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.

The standard container have a requirement that the class stored in them have value semantic and thus they are copied. But

• if you store pointers of any kind, obviously what is pointed isn't copied;
• if you try to modify the stored key (you can get a reference to it), especially playing tricks with mutable members or const_cast in order to be able to do this, in such a way than the sorting order isn't conserved, you are in UB realm.

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.)

Yes -- when you insert an item into an std::map, you pass it by value, so what it contains is a copy of what you passed. Yes, the compiler will synthesize a copy constructor for you unless you declare one yourself.

It is possible to create (for example) map that uses a pointer as its key (along with a comparison function/functor that compares what the pointers refer to). If, however, you attempt to modify the keys pointed to by those pointers, you get UB. If you want to modify a key in a set/map/multiset/multimap, you need to delete the existing item from the collection, modify your copy, then insert the modified version back into the collection.