I thought of Long Black Rifle too, but it doesn't regret the infidelity, the singer instead dies to protect the marriage of the one being unfaithful with him. And the other one I thought of, slightly off-kilter, is I Will Survive, where the singer is NOT regretting having thrown the unfaithful bum out. Maybe someone could write the song about how the thrown-out guy is watching her survive and wishing he were still along for the ride...