Respecto a tu primer recorrido, si utilizas C++11, lo más fácil es hacerlo de la siguiente forma:

void mostrarAsignaturas()
{
    for (const auto & i : asignaturas) { // Son dos sentencias. Necesitas las llaves!!!
       i.first->mostrar(); 
       cout << i.second << endl;
   }
}

Respecto al recorrido del map interno:

void mostrarAsignaturas(Empresa* e)
{
    for (const auto& i : empresa_empleado[e]) {
        i.first->mostrar();
        i.second->mostrar();
   }
}

A la vieja usanza (sin los `based-range for` ni `auto`s), sería:

void mostrarAsignaturas(Empresa* e)
{
    const AD& empleados_e = empresa_empleado[e];
 
    for (AD::const_iterator i = empleados_e.begin(); i != empleados_e.end(); ++i) {
        i->first->mostrar();
        i->second->mostrar();
   }
}

Otra variante (con `auto`s pero sin `based-range for`):

void mostrarAsignaturas(Empresa* e)
{
    const auto& empleados_e = empresa_empleado[e];
 
    for (auto i = empleados_e.begin(); i != empleados_e.end(); ++i) {
        i->first->mostrar();
        i->second->mostrar();
   }
}

Los `auto`s lo que hacen es deducir el tipo (aunque siempre deducen el valor por copia; si lo que quieres es una referencia, tienes que forzarla escribiendo `&` junto a `auto`; y si la referencia la quieres constante, pues pones también `const`).

Un `range-based for` como el siguiente (supongamos que `v` es un `vector<int>` no constante):

for (auto i : v) {
   /* codigo */
}

Sería equivalente a lo siguiente:

// `it` tiene tipo `vector<int>::iterator`
for (auto it = v.begin(); it != v.end(); ++it) {
   auto i = *it; // `i` tiene tipo `int`.
   /* codigo */
}

Y si fuera por referencia:

// `it` tiene tipo `vector<int>::iterator`
for (auto it = v.begin(); it != v.end(); ++it) {
   auto& i = *it; // `i` tiene tipo `int&`.
   /* codigo */
}

Espero que con todo ésto, te haya quedado claro como se recorren rangos