Como a steeldriver sugeriu em seu comentário «Provavelmente o pacote está instalado, mas você removeu ou quebrou manualmente o link simbólico entre /usr/bin/g++ e /usr/bin/g++-5 - try sudo apt install --reinstall g++ »
O sudo apt install --reinstall g++ fez o truque.
Resposta fornecida porque não havia um