Wann ist ein const_cast angebracht?

[unknown]

es sollte so passieren, dass die Schlüssel (vom Typ Key, die meist "größere Objekte", z.B. längere Strings darstellen) nur einmal in der Liste gespeichert werden und in der Hashtabelle nur die Zeiger darauf gespeichert werden müssen.

Ja, ich hatte auch nochmal nachgesehen, ich war davon ausgegangen, dass in der multimap der Hash als eigentlicher Key dient und der ursprüngliche Schlüssel also überhaupt nicht jedesmal gespeichert wird. Ist leider nicht so!
Damit würdest du tatsächlich Speicherplatz sparen. Aber wie kommst du vom eigentlichen Schlüssel auf den Zeiger in deiner Liste? Durch lineare Suche?

Auch wenn das bedeutet, dass ich jetzt wieder direkt mit der multimap arbeite.

Naja, das ist ja nicht schlimm, bis auf den mehrfachen Speicherverbrauch des Schlüssels.