Здравствуйте, пффф, Вы писали:

П>Ищу по ключу в мапе, обычно всё должно находится, если не найдено — это беда-беда. Хочу кинуть какое-то из стандартных исключений, но что-то не очень понятно, какое лучше всего подходит к данной ситуации

Отсутствие ключа в мэпе само по себе не есть исключительная ситуация для кода библиотеки. Это не индекс за пределами длины массива. Поэтому найти подходящее исключение и не удается.

Наиболее логичное ИМХО — свой наследник от runtime_error или logic_error