One way of implementing explicit concurrent deletion for your elements is to have a concurrent vector/map of shared pointers pointing to the actual element. This adds some comlpexity to the find but memory management becomes easier. If memory is abundant or if deletion is scarce, perhaps modifying the deletion-canidate to a sentinal/dummy value might do the trick.
