Есть ли в c++ map на основе сортированного массива?

В C++ нет. Но есть в boost: boost::container::flat_map

В бусте есть flatmap.

В стандартной библиотеке такого нет. Но написать свою обертку обычно не сложное дело.

std::lower_bound позволит написать как оператор [], так и вставку.