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