>>816,818
struct pair { int_least32_t key; int_least64_t value; };
std::vector<pair> v;
で、 v を常にソート済みに保つ。

sizeof(pair) は典型的には 16 バイトか 12 バイトになると思う。
その場合の容量はこう。

16バイト　*　1000万個　/　2^20　＝　153メガバイト。

ただしキーで参照するのは O(logN) で、追加削除は O(N) になってしまう。
（配列の場合はいずれも O(1) ）

std::map にすれば追加削除も O(logN) に抑えられるけど、メモリ使用量は
たぶん数倍に増えてしまう。