Are items placed in an unordered_map stored in the stack or the heap?

Question

Suppose I have the following class:

class MyOtherClass{
     std::unordered_map<int, std::multimap<int, MyClass*>> _xy;

     void putObject(int x,int y,MyClass* obj);
     void containsXkey(int x){
         bool found = false;
         std::unordered_map<int,std::multi map<int,MyClass*>>::const_iterator index = _xy.find(x);

         if(index = _xy.end(){
               found = false;
         }else{
               found = true;
         }

          return found;
     }
}

Say I want to write a function to place a MyClass at coordinates (2,3), then I would do something like this:

void putObject(int x, int y, MyClass* obj){
    if(!containsXKey(x){
          //Since it doesn't contain an empty multimap, I'm creating one.
          std::multimap<int, MyClass*> foo; //This is created on the stack
          _xy[x] = foo; //What happens here ?
    }

    std::multimap<int,MyClass*>& foo = _xy[x];
    foo.insert(y,obj);
}

So my question is: Initially there are no entries in the unordered_map, so the first time I want to add an item at a particular key, I need to create a multimap. The multimap is created on the stack. So what happens when I assign it to the key ? Is it making a copy ? Where is it being stored ?

Answer 1

Like all the dynamic sized containers, the map containers keep their elements on the dynamic memory storage* (the "heap"**).
the object itself may sit on the stack, heap or so, but inside the object there may be sub-objects or pointers that points to dynamic memory.

So what happens when I assign it to the key?

the map will make sure the internal buffer can hold another key-value pair, if not, it will expand to support a storage for one more element.

Is it making a copy?

it depends on how the key/value was passed to the map. if the key/value supports move semantics and the key was passed as r-value-reference, it will not get copied but moved instead. but if the class does not support move semantics or the key was passed as const reference, it will get copied.

Where is it being stored ?

The standard does not mandate how the map should be implemented internally, so every library may implement it how-ever it likes. Microsoft std::unordered_map keeps the key-values pair in a linked list, other libraries may choose to keep the map elements in a vector or so.

      std::multimap<int, MyClass*> foo; //This is created on the stack
      _xy[x] = foo; //What happens here ?

in this case, foo is created on the stack. the operator [] itself creates a default created std::multimap on the heap, then the operator = copies the content of foo (which are non) into _xy[y].

*assuming the map uses the standard allocator, one can set specific allocator which allocates memory from other storage.

** The standard does not state words like "stack" and "heap" directly, but states the following terms : automatic storage ("the stack"), dynamic storage ("the heap"), static storage ("the data segment"), and thread storage ("TLS").