C++でのメモリ確保について教えて下さい。

要素数が変動する配列の塊の為の領域を膨大な数確保するとします。
データ1[70]
データ2[1]
データ3[36]
データ4[12]
・
・
・
そしてそれらを管理するアドレスの配列を作ります。
データ1の開始アドレス
データ2の開始アドレス
データ3の開始アドレス
データ4の開始アドレス
・
・
・
このとき、領域確保はひとつずつnewとかで確保したほうがいいのでしょうか？
それとも巨大な領域を自分で確保し、その中に隙間を詰めるようにデータを詰め込んでいく
管理クラスを自作するほうがいいのでしょうか？
前者のほうが簡単そうではあるんですが、C++の動作の知識があまりなくて以下の不安があります。
・膨大な数こまごまと領域確保することで何らかの処理負荷が発生しないか？
・もしも適当に確保出来る空き領域見つけて確保する場合、隙間がまばらになって
　メモリが断片化され、本来可能な確保量よりも確保出来る容量が少なくなってしまわないか？

データ領域は数万から最悪数百万個単位で確保し、頻繁に消したり、追加するとします。
宜しくお願いします。