  We give a general method for constructing explicit and natural operations on
the Hochschild complex of algebras over any PROP with
$A_\infty$--multiplication---we think of such algebras as $A_\infty$--algebras
"with extra structure". As applications, we obtain an integral version of the
Costello-Kontsevich-Soibelman moduli space action on the Hochschild complex of
open TCFTs, the Tradler-Zeinalian action of Sullivan diagrams on the Hochschild
complex of strict Frobenius algebras, and give applications to string topology
in characteristic zero. Our main tool is a generalization of the Hochschild
complex.
