If you are referring to an app that deletes multiple contacts, those contacts would be deleted from your iCloud contacts with your next iCloud back up. iCloud backs up what is currently on your phone. I don't think it stores old contacts that have been deleted. Those that are Gmail or other contacts will still be available from Gmail. Before you delete a contact, you can go online to your Gmail account (if you have Gmail) and add all your iCloud contacts to your Gmail contacts list. Then when you delete them, they will still be there in that list. I think.
Sent from my ancient but trustworthy iPhone 5.