dlmalloc
GNU Cライブラリ (glibc) の malloc は、dlmalloc を元に作られている
chunk および利用中フラグがあるため、8バイトまたは16バイトのオーバヘッドを含めたメモリ確保が必要である。
アロケートされていないchunkも他のフリーなchunkへのポインタを持つため、chunkの最小サイズは24バイトとなっている

つーわけで、std::mapの、1エントリは、上記のnewのオーバーヘッド　+　ID、ポインタ、left、right、などが必要なので、
相当なサイズになることが分かってもらえるだろうか
一方で、配列でする場合は、1エントリ4バイトで済む
余程の無駄遣いをしない限りは、配列の方がメモリ効率が良いし、オマケに速度も速いのだ